Dynamic Enforcement of Determinism in a Parallel Scripting Language
L. Lu, W. Ji, and M. Scott. Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, page 519--529. New York, NY, USA, ACM, (2014)
DOI: 10.1145/2594291.2594300
Abstract
Determinism is an appealing property for parallel programs, as it simplifies understanding, reasoning and debugging. It is particularly appealing in dynamic (scripting) languages, where ease of programming is a dominant design goal. Some existing parallel languages use the type system to enforce determinism statically, but this is not generally practical for dynamic languages. In this paper, we describe how determinism can be obtained---and dynamically enforced/verified---for appropriate extensions to a parallel scripting language. Specifically, we introduce the constructs of Deterministic Parallel Ruby (DPR), together with a run-time system (Tardis) that verifies properties required for determinism, including correct usage of reductions and commutative operators, and the mutual independence (data-race freedom) of concurrent tasks. Experimental results confirm that DPR can provide scalable performance on multicore machines and that the overhead of Tardis is low enough for practical testing. In particular, Tardis significantly outperforms alternative data-race detectors with comparable functionality. We conclude with a discussion of future directions in the dynamic enforcement of determinism.
Description
Dynamic enforcement of determinism in a parallel scripting language
%0 Conference Paper
%1 Lu:2014:DED
%A Lu, Li
%A Ji, Weixing
%A Scott, Michael L.
%B Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation
%C New York, NY, USA
%D 2014
%I ACM
%K DataRace Debugging Determinism Parallel Performance Ruby
%P 519--529
%R 10.1145/2594291.2594300
%T Dynamic Enforcement of Determinism in a Parallel Scripting Language
%U https://www.cs.rochester.edu/u/scott/papers/2014_PLDI_DPR.pdf
%X Determinism is an appealing property for parallel programs, as it simplifies understanding, reasoning and debugging. It is particularly appealing in dynamic (scripting) languages, where ease of programming is a dominant design goal. Some existing parallel languages use the type system to enforce determinism statically, but this is not generally practical for dynamic languages. In this paper, we describe how determinism can be obtained---and dynamically enforced/verified---for appropriate extensions to a parallel scripting language. Specifically, we introduce the constructs of Deterministic Parallel Ruby (DPR), together with a run-time system (Tardis) that verifies properties required for determinism, including correct usage of reductions and commutative operators, and the mutual independence (data-race freedom) of concurrent tasks. Experimental results confirm that DPR can provide scalable performance on multicore machines and that the overhead of Tardis is low enough for practical testing. In particular, Tardis significantly outperforms alternative data-race detectors with comparable functionality. We conclude with a discussion of future directions in the dynamic enforcement of determinism.
%@ 978-1-4503-2784-8
@inproceedings{Lu:2014:DED,
abstract = {Determinism is an appealing property for parallel programs, as it simplifies understanding, reasoning and debugging. It is particularly appealing in dynamic (scripting) languages, where ease of programming is a dominant design goal. Some existing parallel languages use the type system to enforce determinism statically, but this is not generally practical for dynamic languages. In this paper, we describe how determinism can be obtained---and dynamically enforced/verified---for appropriate extensions to a parallel scripting language. Specifically, we introduce the constructs of Deterministic Parallel Ruby (DPR), together with a run-time system (Tardis) that verifies properties required for determinism, including correct usage of reductions and commutative operators, and the mutual independence (data-race freedom) of concurrent tasks. Experimental results confirm that DPR can provide scalable performance on multicore machines and that the overhead of Tardis is low enough for practical testing. In particular, Tardis significantly outperforms alternative data-race detectors with comparable functionality. We conclude with a discussion of future directions in the dynamic enforcement of determinism.},
acmid = {2594300},
added-at = {2015-02-23T14:51:32.000+0100},
address = {New York, NY, USA},
author = {Lu, Li and Ji, Weixing and Scott, Michael L.},
biburl = {https://www.bibsonomy.org/bibtex/2783e6dd07b35a5dec2ab2eb72aa6d8f3/gron},
booktitle = {Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation},
description = {Dynamic enforcement of determinism in a parallel scripting language},
doi = {10.1145/2594291.2594300},
interhash = {5a0c42384a2dec3ac14b174ee288066b},
intrahash = {783e6dd07b35a5dec2ab2eb72aa6d8f3},
isbn = {978-1-4503-2784-8},
keywords = {DataRace Debugging Determinism Parallel Performance Ruby},
location = {Edinburgh, United Kingdom},
numpages = {11},
pages = {519--529},
publisher = {ACM},
series = {PLDI '14},
timestamp = {2015-02-23T14:51:57.000+0100},
title = {Dynamic Enforcement of Determinism in a Parallel Scripting Language},
url = {https://www.cs.rochester.edu/u/scott/papers/2014_PLDI_DPR.pdf},
year = 2014
}