POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

This paper proposes a new way to exploit code commutativity to parallelize sequential programs. While prior work provided the ability to identify and exploit commutative function calls or adjacent code blocks, this paper describes the first method that dynamically exploits statically known commutativity conditions of arbitrary code regions. In this method, programmers give parameterized names to code blocks anywhere in the program, and provide commutativity expressions over those parameters and the global state. Novel algorithms exploit this commutativity and dependence information to automatically construct a program-specific parallelization scheme, yielding asynchronous tasks executed through a commutativity-aware scheduler. We furthermore show that commutativity conditions can be verified automatically, reducing reliance on manual effort and increasing confidence in correctness. We implement our approach in a new compiler and runtime system called NCBPar that takes in a sequential program and produces a parallel version that dynamically exploits the commutativity conditions. We experimentally demonstrate that NCBPar (i) strictly generalizes prior commutativity-based parallelization techniques, (ii) enables parallelization opportunities beyond the reach of existing methods, and (iii) automatically verifies commutativity conditions.