research-article

Commutative set: a language extension for implicit parallel programming

Authors:

Prakash Prabhu,

Soumyadeep Ghosh,

Nick P. Johnson,

David I. AugustAuthors Info & Claims

PLDI '11: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 1 - 11

https://doi.org/10.1145/1993498.1993500

Published: 04 June 2011 Publication History

Abstract

Sequential programming models express a total program order, of which a partial order must be respected. This inhibits parallelizing tools from extracting scalable performance. Programmer written semantic commutativity assertions provide a natural way of relaxing this partial order, thereby exposing parallelism implicitly in a program. Existing implicit parallel programming models based on semantic commutativity either require additional programming extensions, or have limited expressiveness. This paper presents a generalized semantic commutativity based programming extension, called Commutative Set (COMMSET), and associated compiler technology that enables multiple forms of parallelism. COMMSET expressions are syntactically succinct and enable the programmer to specify commutativity relations between groups of arbitrary structured code blocks. Using only this construct, serializing constraints that inhibit parallelization can be relaxed, independent of any particular parallelization strategy or concurrency control mechanism. COMMSET enables well performing parallelizations in cases where they were inapplicable or non-performing before. By extending eight sequential programs with only 8 annotations per program on average, COMMSET and the associated compiler technology produced a geomean speedup of 5.7x on eight cores compared to 1.5x for the best non-COMMSET parallelization.

References

[1]

F. Aleen and N. Clark. Commutativity analysis for software parallelization: Letting program transformations see the big picture. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2009.

Digital Library

[2]

Apple Open Source. md5sum: Message Digest 5 computation. http://www.opensource.apple.com/darwinsource/.

[3]

E. Ayguadé, N. Copty, A. Duran, J. Hoeflinger, Y. Lin, F. Massaioli, X. Teruel, P. Unnikrishnan, and G. Zhang. The design of OpenMP tasks. IEEE Transactions on Parallel and Distributed Systems, 2009.

Digital Library

[4]

G. E. Blelloch and J. Greiner. A provable time and space efficient implementation of NESL. In Proceedings of the First ACM SIGPLAN International Conference on Functional Programming (ICFP), 1996.

Digital Library

[5]

R. L. Bocchino, Jr., V. S. Adve, D. Dig, S. V. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian. A type and effect system for Deterministic Parallel Java. In Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA), 2009.

Digital Library

[6]

M. Bridges, N. Vachharajani, Y. Zhang, T. Jablin, and D. August. Revisiting the sequential programming model for multi-core. In Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2007.

Digital Library

[7]

M. J. Bridges. The VELOCITY compiler: Extracting efficient multicore execution from legacy sequential codes. PhD thesis, 2008.

Digital Library

[8]

D. R. Butenhof. Programming with POSIX threads. Addison-Wesley Longman Publishing Co., Inc., 1997.

Digital Library

[9]

M. C. Carlisle. Olden: Parallelizing programs with dynamic data structures on distributed-memory machines. PhD thesis, 1996.

Digital Library

[10]

B. D. Carlstrom, A. McDonald, M. Carbin, C. Kozyrakis, and K. Olukotun. Transactional collection classes. In Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2007.

Digital Library

[11]

R. Eigenmann, J. Hoeflinger, Z. Li, and D. A. Padua. Experience in the automatic parallelization of four Perfect-benchmark programs. In Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing (LCPC), 1992.

Digital Library

[12]

J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst., 9(3), 1987.

Digital Library

[13]

T. Harris and S. Singh. Feedback directed implicit parallelism. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming (ICFP), 2007.

Digital Library

[14]

J. L. Henning. SPEC CPU2006 benchmark descriptions. SIGARCH Comput. Archit. News, 2006.

Digital Library

[15]

W.-m. Hwu, S. Ryoo, S.-Z. Ueng, J. Kelm, I. Gelado, S. Stone, R. Kidd, S. Baghsorkhi, A. Mahesri, S. Tsao, N. Navarro, S. Lumetta, M. Frank, and S. Patel. Implicitly parallel programming models for thousand-core microprocessors. In Proceedings of the 44th annual Design Automation Conference (DAC), 2007.

Digital Library

[16]

K. Kennedy and J. R. Allen. Optimizing Compilers for Modern Architectures: a Dependence-based Approach. Morgan Kaufmann Publishers Inc., 2002.

Digital Library

[17]

E. Koskinen, M. Parkinson, and M. Herlihy. Coarse-grained transactions. In Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), 2010.

Digital Library

[18]

M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic parallelism requires abstractions. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).

Digital Library

[19]

C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis and transformation. In Proceedings of 2nd International Symposium on Code Generation and Optimization (CGO), 2004.

Digital Library

[20]

R. Leino, P. Müller, and J. Smans. Deadlock-free channels and locks. In Proceedings of the 19th European Symposium on Programming (ESOP), 2010.

Digital Library

[21]

G. Memik, W. H. Mangione-Smith, and W. Hu. NetBench: a benchmarking suite for network processors. In Proceedings of the 2001 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2001.

Digital Library

[22]

C. C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In IEEE International Symposium on Workload Characterization (IISWC), 2008.

[23]

R. Narayanan, B. Ozisikyilmaz, J. Zambreno, G. Memik, and A. Choudhary. MineBench: A benchmark suite for data mining workloads. In IEEE International Symposium on Workload Characterization (IIWSC), 2006.

[24]

G. Ottoni. Global Instruction Scheduling for Multi-Threaded Architectures. PhD thesis, 2008.

Digital Library

[25]

G. Ottoni, R. Rangan, A. Stoler, and D. I. August. Automatic thread extraction with decoupled software pipelining. Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2005.

Digital Library

[26]

E. Raman, G. Ottoni, A. Raman, M. J. Bridges, and D. I. August. Parallel-stage decoupled software pipelining. In Proceedings of the 6th annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2008.

Digital Library

[27]

M. C. Rinard. The design, implementation and evaluation of Jade, a portable, implicitly parallel programming language. PhD thesis, 1994.

Digital Library

[28]

M. C. Rinard and P. Diniz. Commutativity analysis: A new analysis framework for parallelizing compilers. In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation (PLDI).

Digital Library

[29]

P. Selinger. potrace: Transforming bitmaps into vector graphics. http://potrace.sourceforge.net.

[30]

H. Vandierendonck, S. Rul, and K. De Bosschere. The Paralax infrastructure: Automatic parallelization with a helping hand. In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2010.

Digital Library

[31]

C. von Praun, L. Ceze, and C. Caşcaval. Implicit parallelism with ordered transactions. In Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2007.

Digital Library

[32]

P. Wu and D. A. Padua. Beyond arrays - a container-centric approach for parallelization of real-world symbolic applications. In Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing (LCPC), 1999.

Digital Library

[33]

R. M. Yoo, Y. Ni, A. Welc, B. Saha, A.-R. Adl-Tabatabai, and H.-H. S. Lee. Kicking the tires of software transactional memory: Why the going gets tough. In Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), 2008.

Digital Library

[34]

H. Zhong, M. Mehrara, S. Lieberman, and S. Mahlke. Uncovering hidden loop level parallelism in sequential applications. In Proceedings of 14th International Conference on High-Performance Computer Architecture (HPCA), 2008.

Cited By

Tan ZChon YKruse MDoerfert JXu ZHomerding BCampanoni SAugust DAamodt TJerger NSwift M(2023)SPLENDID: Supporting Parallel LLVM-IR Enhanced Natural Decompilation for Interactive DevelopmentProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582058(679-693)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3582016.3582058
Chen AFathololumi PNicola MPincus JBrennan TKoskinen E(2023)Better Predicates and Heuristics for Improved Commutativity SynthesisAutomated Technology for Verification and Analysis10.1007/978-3-031-45332-8_5(93-113)Online publication date: 19-Oct-2023
https://doi.org/10.1007/978-3-031-45332-8_5
Pîrlea GKumar ASergey IFreund SYahav E(2021)Practical smart contract sharding with ownership and commutativity analysisProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454112(1327-1341)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454112
Show More Cited By

Index Terms

Commutative set: a language extension for implicit parallel programming
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Commutative set: a language extension for implicit parallel programming
PLDI '11

Sequential programming models express a total program order, of which a partial order must be respected. This inhibits parallelizing tools from extracting scalable performance. Programmer written semantic commutativity assertions provide a natural way ...
Programming Multicores: Do Applications Programmers Need to Write Explicitly Parallel Programs?

In this panel discussion from the 2009 Workshop on Computer Architecture Research Directions, David August and Keshav Pingali debate whether explicitly parallel programming is a necessary evil for applications programmers, assess the current state of ...
Comparing Parallel Functional Languages: Programming and Performance

This paper presents a practical evaluation and comparison of three state-of-the-art parallel functional languages. The evaluation is based on implementations of three typical symbolic computation programs, with performance measured on a Beowulf-class ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '11: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2011

668 pages

ISBN:9781450306638

DOI:10.1145/1993498

General Chair:
Mary Hall
University of Utah
,
Program Chair:
David Padua
University of Illinois at Urbana-Champaign

ACM SIGPLAN Notices Volume 46, Issue 6
PLDI '11
June 2011
652 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1993316
Issue’s Table of Contents

Copyright © 2011 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 ACM 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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '11

Sponsor:

SIGPLAN

PLDI '11: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 4 - 8, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
714
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)4

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tan ZChon YKruse MDoerfert JXu ZHomerding BCampanoni SAugust DAamodt TJerger NSwift M(2023)SPLENDID: Supporting Parallel LLVM-IR Enhanced Natural Decompilation for Interactive DevelopmentProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582058(679-693)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3582016.3582058
Chen AFathololumi PNicola MPincus JBrennan TKoskinen E(2023)Better Predicates and Heuristics for Improved Commutativity SynthesisAutomated Technology for Verification and Analysis10.1007/978-3-031-45332-8_5(93-113)Online publication date: 19-Oct-2023
https://doi.org/10.1007/978-3-031-45332-8_5
Pîrlea GKumar ASergey IFreund SYahav E(2021)Practical smart contract sharding with ownership and commutativity analysisProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454112(1327-1341)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454112
Vasiladiotis CLozano RCole MFranke BLee J(2021)Loop parallelization using dynamic commutativity analysisProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370319(150-161)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370319
von Koch TManilov SVasiladiotis CCole MFranke BDubach CXue J(2018)Towards a compiler analysis for parallel algorithmic skeletonsProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179513(174-184)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179513
Clements AKaashoek MKohler EMorris RZeldovich N(2017)The scalable commutativity ruleCommunications of the ACM10.1145/306891460:8(83-90)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3068914
Oh TBeard SJohnson NPopovych SAugust D(2017)A Generalized Framework for Automatic Scripting Language Parallelization2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT.2017.28(356-369)Online publication date: Sep-2017
https://doi.org/10.1109/PACT.2017.28
Zhang GChiu VSanchez DHsu WYang CLipasti MLee H(2016)Exploiting semantic commutativity in hardware speculationThe 49th Annual IEEE/ACM International Symposium on Microarchitecture10.5555/3195638.3195679(1-12)Online publication date: 15-Oct-2016
https://dl.acm.org/doi/10.5555/3195638.3195679
Huang JPrabhu PJablin TGhosh SApostolakis SLee JAugust DZaks AMendelson BRauchwerger LHwu W(2016)Speculatively Exploiting Cross-Invocation ParallelismProceedings of the 2016 International Conference on Parallel Architectures and Compilation10.1145/2967938.2967959(207-221)Online publication date: 11-Sep-2016
https://dl.acm.org/doi/10.1145/2967938.2967959
Zhang GChiu VSanchez D(2016)Exploiting semantic commutativity in hardware speculation2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO.2016.7783737(1-12)Online publication date: Oct-2016
https://doi.org/10.1109/MICRO.2016.7783737
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 Table of Contents