Loop Parallelization using Dynamic Commutativity Analysis

Chris Vasiladiotis, Roberto Castaneda Lozano, Murray Cole, Bjoern Franke

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

Abstract / Description of output

Automatic parallelization has largely failed to keep its promise of extracting parallelism from sequential legacy code to maximize performance on multi-core systems outside the numerical domain. In this paper, we develop a novel dynamic commutativity analysis (DCA) for identifying parallelizable loops. Using commutativity instead of dependence tests, DCA avoids many of the overly strict data dependence constraints limiting existing parallelizing compilers. DCA extends the scope of automatic parallelization to uniformly include both regular array-based and irregular pointer-based codes. We have prototyped our novel parallelism detection analysis and evaluated it extensively against five state-of-the-art dependence-based techniques in two experimental settings. First, when applied to the NAS benchmarks which contain almost 1400 loops, DCA is able to identify as many parallel loops (over 1200) as the profile-guided dependence techniques and almost twice as many as all the static techniques combined. We then apply DCA to complex pointer-based loops, where it can successfully detect parallelism, while existing techniques fail to identify any. When combined with existing parallel code generation techniques, this results in an average speedup of 3.6× (and up to 55×) across the NAS benchmarks on a 72-core host, and up to 36.9× for the pointer-based loops, demonstrating the effectiveness of DCA in identifying profitable parallelism across a wide range of loops.
Original languageEnglish
Title of host publication2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)
Pages150 - 161
Number of pages12
ISBN (Electronic)978-1-7281-8613-9
ISBN (Print)978-1-7281-8614-6
Publication statusPublished - 11 Mar 2021
Event2021 International Symposium on Code Generation and Optimization - Virtual Conference
Duration: 27 Feb 20213 Mar 2021


Symposium2021 International Symposium on Code Generation and Optimization
Abbreviated titleCGO 2021
CityVirtual Conference
Internet address

Keywords / Materials (for Non-textual outputs)

  • commutativity analysis
  • parallelization


Dive into the research topics of 'Loop Parallelization using Dynamic Commutativity Analysis'. Together they form a unique fingerprint.

Cite this