File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Parrot: A practical runtime for deterministic, stable, and reliable threads

TitleParrot: A practical runtime for deterministic, stable, and reliable threads
Authors
Keywordsstable multithreading
deterministic multithreading
software model checking
state space reduction
Issue Date2013
Citation
SOSP 2013 - Proceedings of the 24th ACM Symposium on Operating Systems Principles, 2013, p. 388-405 How to Cite?
AbstractMultithreaded programs are hard to get right. A key reason is that the contract between developers and runtimes grants exponentially many schedules to the runtimes. We 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. We 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 - 1019734 for 56 programs. Parrot's source code, entire benchmark suite, and raw results are available at github.com/columbia/smt-mc. © 2013 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/207903

 

DC FieldValueLanguage
dc.contributor.authorCui, H-
dc.contributor.authorŠimša, J-
dc.contributor.authorLin, Y-
dc.contributor.authorLi, H-
dc.contributor.authorBlum, B-
dc.contributor.authorXu, X-
dc.contributor.authorYang, J-
dc.contributor.authorGibson, GA-
dc.contributor.authorBryant, RE-
dc.date.accessioned2015-01-26T11:46:41Z-
dc.date.available2015-01-26T11:46:41Z-
dc.date.issued2013-
dc.identifier.citationSOSP 2013 - Proceedings of the 24th ACM Symposium on Operating Systems Principles, 2013, p. 388-405-
dc.identifier.urihttp://hdl.handle.net/10722/207903-
dc.description.abstractMultithreaded programs are hard to get right. A key reason is that the contract between developers and runtimes grants exponentially many schedules to the runtimes. We 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. We 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 - 1019734 for 56 programs. Parrot's source code, entire benchmark suite, and raw results are available at github.com/columbia/smt-mc. © 2013 ACM.-
dc.languageeng-
dc.relation.ispartofSOSP 2013 - Proceedings of the 24th ACM Symposium on Operating Systems Principles-
dc.subjectstable multithreading-
dc.subjectdeterministic multithreading-
dc.subjectsoftware model checking-
dc.subjectstate space reduction-
dc.titleParrot: A practical runtime for deterministic, stable, and reliable threads-
dc.typeConference_Paper-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/2517349.2522735-
dc.identifier.scopuseid_2-s2.0-84889686029-
dc.identifier.spage388-
dc.identifier.epage405-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats