DATE: Thursday, October 31, 2013
TIME: 1:30 - 2 pm
PLACE: Gates 8102

SPEAKERS: Heming Cui, PhD student, Computer Science, Columbia University

TITLE: PARROT: A Practical Runtime for Deterministic, Stable, and Reliable Threads

ABSTRACT:
Multithreaded programs are hard to get right. A key reason is that the contract between developers and runtimes grants exponentially many schedules to the runtimes.

I will present PARROT, a simple, practical runtime with a new contract to developers. By default, it orders thread synchronizations in the well-defined round-robin order, vastly reducing schedules to provide determinism (more precisely, deterministic synchronizations) and stability (i.e., robustness against input or code perturbations, a more useful property than determinism). When default schedules are slow, it allows developers to write intuitive performance hints in their code to switch or add schedules for speed. We believe this "meet in the middle" contract eases writing correct, efficient programs.

I will further present an ecosystem formed by integrating PARROT with a model checker called DBUG. This ecosystem is more effective than either system alone: DBUG checks the schedules that matter to PARROT, and PARROT greatly increases the coverage of DBUG.

Results on a diverse set of 108 programs, roughly 10x more than any prior evaluation, show that PARROT is easy to use (averaging 1.2 lines of hints per program); achieves low overhead (6.9% for 55 real-world programs and 12.7% for all 108 programs), 10x better than two prior systems; scales well to the maximum allowed cores on a 24-core server and to different scales/types of workloads; and increases DBUG's coverage by 10^6 - 10^19734 for 56 programs. PARROT's source code, entire benchmark suite, and raw results are available at: http://github.com/columbia/smt-mc.

BIO:
Heming Cui (http://www.cs.columbia.edu/~heming) is a fourth-year PhD student at Computer Science of Columbia University. He has been working on improving software reliability and security with runtime and program analysis techniques. His interests are in: operating systems,distributed systems, software reliability, security, and program analysis. Before joining Columbia, he obtained his master and bachelor degrees from Tsinghua University, Beijing, China.

 

SDI / ISTC SEMINAR QUESTIONS?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/