research-article

Deterministic galois: on-demand, portable and parameterless

Authors:

Andrew Lenharth,

Keshav PingaliAuthors Info & Claims

ACM SIGPLAN Notices, Volume 49, Issue 4

Pages 499 - 512

https://doi.org/10.1145/2644865.2541964

Published: 24 February 2014 Publication History

Abstract

Non-determinism in program execution can make program development and debugging difficult. In this paper, we argue that solutions to this problem should be on-demand, portable and parameterless. On-demand means that the programming model should permit the writing of non-deterministic programs since these programs often perform better than deterministic ones for the same problem. Portable means that the program should produce the same answer even if it is run on different machines. Parameterless means that if there are machine-dependent scheduling parameters that must be tuned for good performance, they must not affect the output.

Although many solutions for deterministic program execution have been proposed in the literature, they fall short along one or more of these dimensions. To remedy this, we propose a new approach, based on the Galois programming model, in which (i) the programming model permits the writing of non-deterministic programs and (ii) the runtime system executes these programs deterministically if needed. Evaluation of this approach on a collection of benchmarks from the PARSEC, PBBS, and Lonestar suites shows that it delivers deterministic execution with substantially less overhead than other systems in the literature.

References

[1]

N. Amenta, S. Choi, and G. Rote. Incremental constructions con brio. In Proc. Symp. on Computational Geometry (SCG), 2003.

Digital Library

[2]

A. Aviram, S.-C. Weng, S. Hu, and B. Ford. Efficient system-enforced deterministic parallelism. In Proc. USENIX Conf. Operating Systems Design and Implementation, OSDI, pages 1--16, 2010.

Digital Library

[3]

Bergan, Anderson, Devietti, Ceze, and Grossman}bergan10T. Bergan, O. Anderson, J. Devietti, L. Ceze, and D. Grossman. CoreDet: a compiler and runtime system for deterministic multithreaded execution. In Proc. Intl Conf. Architectural Support for Programming Languages and Operating Systems, ASPLOS, pages 53--64, 2010.

Digital Library

[4]

Bergan, Hunt, Ceze, and Gribble}bergan10-dOST. Bergan, N. Hunt, L. Ceze, and S. D. Gribble. Deterministic process groups in dOS. In Proc. USENIX Conf. Operating Systems Design and Implementation, OSDI, pages 1--16, 2010.

Digital Library

[5]

E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: safe multithreaded programming for C/C++. In Proc. ACM SIGPLAN Conf. Object Oriented Programming Systems Languages and Applications, OOPSLA, pages 81--96, 2009.

Digital Library

[6]

C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: characterization and architectural implications. In Proc. Intl Conf. Parallel Architectures and Compilation Techniques, PACT, pages 72--81, 2008.

Digital Library

[7]

G. E. Blelloch, J. T. Fineman, P. B. Gibbons, and J. Shun. Internally deterministic parallel algorithms can be fast. In Proc. ACM SIGPLAN Symp. Principles and Practice of Parallel Programming, PPoPP, pages 135--146, 2012.

Digital Library

[8]

R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: An efficient multithreaded runtime system. In Proc. ACM SIGPLAN Symp. Principles and Practice of Parallel Programming, PPoPP, 1995.

Digital Library

[9]

R. L. Bocchino, Jr., V. S. Adve, S. V. Adve, and M. Snir. Parallel programming must be deterministic by default. In Proc. USENIX Conf. Hot Topics in Parallelism, HotPar, pages 4--4, 2009.

Digital Library

[10]

R. L. Bocchino, Jr., S. Heumann, N. Honarmand, S. V. Adve, V. S. Adve, A. Welc, and T. Shpeisman. Safe nondeterminism in a deterministic-by-default parallel language. In Proc. ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, POPL, pages 535--548, 2011.

Digital Library

[11]

S. Burckhardt, A. Baldassin, and D. Leijen. Concurrent programming with revisions and isolation types. In Proc. ACM SIGPLAN Conf. Object Oriented Programming Systems Languages and Applications, OOPSLA, 2010.

Digital Library

[12]

K. M. Chandy and J. Misra. The drinking philosophers problem. ACM Trans. Program. Lang. Syst., 6 (4), Oct. 1984.

Digital Library

[13]

B. V. Cherkassy and A. V. Goldberg. On implementing push-relabel method for the maximum flow problem. In Proc. Intl Conf. Integer Programming and Combinatorial Optimization, IPCO, pages 157--171, 1995.

Digital Library

[14]

K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4 (5): 287--421, 1989.

Digital Library

[15]

H. Cui, J. Simsa, Y.-H. Lin, H. Li, B. Blum, X. Xu, J. Yang, G. A. Gibson, and R. E. Bryant. Parrot: A practical runtime for deterministic, stable, and reliable threads. In Proc. ACM Symp. Operating Systems Principles, SOSP, pages 388--405, 2013.

Digital Library

[16]

J. Devietti, B. Lucia, L. Ceze, and M. Oskin. DMP: deterministic shared memory multiprocessing. In Proc. Intl Conf. Architectural Support for Programming Languages and Operating Systems, ASPLOS, pages 85--96, 2009.

Digital Library

[17]

J. Devietti, J. Nelson, T. Bergan, L. Ceze, and D. Grossman. RCDC: a relaxed consistency deterministic computer. In Proc. Intl Conf. Architectural Support for Programming Languages and Operating Systems, ASPLOS, 2011.

Digital Library

[18]

A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. J. ACM, 35 (4): 921--940, 1988.

Digital Library

[19]

T. Harris and K. Fraser. Language support for lightweight transactions. In Proc. ACM SIGPLAN Conf. Object Oriented Programming Systems Languages and Applications, OOPSLA, pages 388--402, 2003.

Digital Library

[20]

M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In Proc. ACM SIGPLAN Symp. Principles and Practice of Parallel Programming, PPoPP, pages 207--216, 2008.

Digital Library

[21]

D. Hower, P. Dudnik, M. D. Hill, and D. A. Wood. Calvin: Deterministic or not? free will to choose. In IEEE Intl Symp. High Performance Computer Architecture, HPCA, pages 333--334, 2011.

Digital Library

[22]

al, and Pingali}kulkarni09M. Kulkarni, M. Burtscher, C. Casçaval, and K. Pingali. Lonestar: A suite of parallel irregular programs. In IEEE Intl Symp. Performance Analysis of Systems and Software, ISPASS, pages 65--76, 2009.

[23]

C. E. Leiserson and T. B. Schardl. A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers). In Proc. ACM Symp. Parallelism in Algorithms and Architectures, SPAA, pages 303--314, 2010.

Digital Library

[24]

T. Liu, C. Curtsinger, and E. D. Berger. Dthreads: Efficient deterministic multithreading. In Proc. ACM Symp. Operating Systems Principles, SOSP, pages 327--336, New York, NY, USA, 2011.

Digital Library

[25]

M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: efficient deterministic multithreading in software. In Proc. Intl Conf. Architectural Support for Programming Languages and Operating Systems, ASPLOS, 2009.

Digital Library

[26]

ez-Lojo, Prountzos, and Sui}pingali11K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M. A. Hassaan, R. Kaleem, T.-H. Lee, A. Lenharth, R. Manevich, M. Méndez-Lojo, D. Prountzos, and X. Sui. The tao of parallelism in algorithms. In Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, PLDI, pages 12--25, 2011.

Digital Library

[27]

W. Thies, M. Karczmarek, and S. P. Amarasinghe. StreamIt: A language for streaming applications. In Proc. Intl Conf. Compiler Construction, CC, pages 179--196, 2002.

Digital Library

Cited By

Gelashvili RSpiegelman AXiang ZDanezis GLi ZMalkhi DXia YZhou RDehnavi MKulkarni MKrishnamoorthy S(2023)Block-STMProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577524(232-244)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577524
Rehman AAhmad MKhan O(2021)A performance predictor for implementation selection of parallelized static and temporal graph algorithmsConcurrency and Computation: Practice and Experience10.1002/cpe.626734:2Online publication date: 26-Apr-2021
https://doi.org/10.1002/cpe.6267
Shun J(2017)Shared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787Online publication date: 9-Jun-2017
https://doi.org/10.1145/3018787
Show More Cited By

Index Terms

Deterministic galois: on-demand, portable and parameterless
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures

Recommendations

Deterministic galois: on-demand, portable and parameterless
ASPLOS '14: Proceedings of the 19th international conference on Architectural support for programming languages and operating systems

Non-determinism in program execution can make program development and debugging difficult. In this paper, we argue that solutions to this problem should be on-demand, portable and parameterless. On-demand means that the programming model should permit ...
Deterministic galois: on-demand, portable and parameterless
ASPLOS '14

Non-determinism in program execution can make program development and debugging difficult. In this paper, we argue that solutions to this problem should be on-demand, portable and parameterless. On-demand means that the programming model should permit ...
A fully concurrent garbage collector for functional programs on multicore processors
ICFP 2016: Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming

This paper presents a concurrent garbage collection method for functional programs running on a multicore processor. It is a concurrent extension of our bitmap-marking non-moving collector with Yuasa's snapshot-at-the-beginning strategy. Our collector ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 49, Issue 4

ASPLOS '14

April 2014

729 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2644865

Editors:
Mark W. Bailey
Hamilton College, Clinton, NY
,
Rajeev Balasubramonian
University of Utah
,
Al Davis
University of Utah
,
Sarita Adve
University of Illinois at Urbana-Champ

Issue’s Table of Contents

ASPLOS '14: Proceedings of the 19th international conference on Architectural support for programming languages and operating systems
February 2014
780 pages
ISBN:9781450323055
DOI:10.1145/2541940
General Chairs:
Rajeev Balasubramonian
University of Utah
,
Al Davis
University of Utah
,
Program Chair:
Sarita Adve
University of Illinois at Urbana-Champ

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 February 2014

Published in SIGPLAN Volume 49, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
456
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gelashvili RSpiegelman AXiang ZDanezis GLi ZMalkhi DXia YZhou RDehnavi MKulkarni MKrishnamoorthy S(2023)Block-STMProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577524(232-244)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577524
Rehman AAhmad MKhan O(2021)A performance predictor for implementation selection of parallelized static and temporal graph algorithmsConcurrency and Computation: Practice and Experience10.1002/cpe.626734:2Online publication date: 26-Apr-2021
https://doi.org/10.1002/cpe.6267
Shun J(2017)Shared-Memory Parallelism Can Be Simple, Fast, and Scalable10.1145/3018787Online publication date: 9-Jun-2017
https://doi.org/10.1145/3018787
Zhao QQiu ZShao SHui XKhan HJin GKloeckner AMoreira J(2022)Understanding and Reaching the Performance Limit of Schedule Tuning on Stable Synchronization DeterminismProceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1145/3559009.3569669(223-238)Online publication date: 8-Oct-2022
https://dl.acm.org/doi/10.1145/3559009.3569669
Maleki SAgarwal UBurtscher MPingali KLee JPetrank E(2021)BiPartProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441611(161-174)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441611
Shen MXiao N(2021)Load Balance-Centric Distributed Parallel Routing for Large-Scale FPGAs2021 31st International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL53798.2021.00046(242-248)Online publication date: Aug-2021
https://doi.org/10.1109/FPL53798.2021.00046
Apostolakis SXu ZChan GCampanoni SAugust DLarus JCeze LStrauss K(2020)PerspectiveProceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3373376.3378458(351-367)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3373376.3378458
Utterback RAgrawal KLee IKulkarni M(2019)Processor-Oblivious Record and ReplayACM Transactions on Parallel Computing10.1145/33656596:4(1-28)Online publication date: 17-Dec-2019
https://dl.acm.org/doi/10.1145/3365659
Xia YYu XMoses WShun JDevadas S(2019)LiTMProceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3303084.3309487(1-10)Online publication date: 17-Feb-2019
https://dl.acm.org/doi/10.1145/3303084.3309487
Zhao QQiu ZJin GHollingsworth JKeidar I(2019)Semantics-aware scheduling policies for synchronization determinismProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295731(242-256)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295731
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents