File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/2517349.2522735
- Scopus: eid_2-s2.0-84889686029
- WOS: WOS:000494967500025
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Parrot: A practical runtime for deterministic, stable, and reliable threads
Title | Parrot: A practical runtime for deterministic, stable, and reliable threads |
---|---|
Authors | |
Keywords | stable multithreading deterministic multithreading software model checking state space reduction |
Issue Date | 2013 |
Citation | SOSP 2013 - Proceedings of the 24th ACM Symposium on Operating Systems Principles, 2013, p. 388-405 How to Cite? |
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. 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 Identifier | http://hdl.handle.net/10722/207903 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cui, H | - |
dc.contributor.author | Šimša, J | - |
dc.contributor.author | Lin, Y | - |
dc.contributor.author | Li, H | - |
dc.contributor.author | Blum, B | - |
dc.contributor.author | Xu, X | - |
dc.contributor.author | Yang, J | - |
dc.contributor.author | Gibson, GA | - |
dc.contributor.author | Bryant, RE | - |
dc.date.accessioned | 2015-01-26T11:46:41Z | - |
dc.date.available | 2015-01-26T11:46:41Z | - |
dc.date.issued | 2013 | - |
dc.identifier.citation | SOSP 2013 - Proceedings of the 24th ACM Symposium on Operating Systems Principles, 2013, p. 388-405 | - |
dc.identifier.uri | http://hdl.handle.net/10722/207903 | - |
dc.description.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. 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.language | eng | - |
dc.relation.ispartof | SOSP 2013 - Proceedings of the 24th ACM Symposium on Operating Systems Principles | - |
dc.subject | stable multithreading | - |
dc.subject | deterministic multithreading | - |
dc.subject | software model checking | - |
dc.subject | state space reduction | - |
dc.title | Parrot: A practical runtime for deterministic, stable, and reliable threads | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/2517349.2522735 | - |
dc.identifier.scopus | eid_2-s2.0-84889686029 | - |
dc.identifier.spage | 388 | - |
dc.identifier.epage | 405 | - |
dc.identifier.isi | WOS:000494967500025 | - |