Commutative Set: A Language Extension for Implicit Parallel Programming [abstract] (ACM DL, PDF)
Prakash Prabhu, Soumyadeep Ghosh, Yun Zhang, Nick P. Johnson, and David I. August
Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2011.
Accept Rate: 23% (55/236).
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.