Commutative set: A language extension for implicit parallel programming

Prakash Prabhu, Soumyadeep Ghosh, Yun Zhang, Nick P. Johnson, David I. August

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationPLDI'11 - Proceedings of the 2011 ACM Conference on Programming Language Design and Implementation
Pages1-11
Number of pages11
DOIs
StatePublished - Jul 7 2011
Event32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'11 - San Jose, CA, United States
Duration: Jun 4 2011Jun 8 2011

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Other

Other32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'11
CountryUnited States
CitySan Jose, CA
Period6/4/116/8/11

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • automatic parallelization
  • implicit parallelism
  • programming model
  • semantic commutativity
  • static analysis

Fingerprint Dive into the research topics of 'Commutative set: A language extension for implicit parallel programming'. Together they form a unique fingerprint.

  • Cite this

    Prabhu, P., Ghosh, S., Zhang, Y., Johnson, N. P., & August, D. I. (2011). Commutative set: A language extension for implicit parallel programming. In PLDI'11 - Proceedings of the 2011 ACM Conference on Programming Language Design and Implementation (pp. 1-11). (Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)). https://doi.org/10.1145/1993498.1993500