Speculative parallelization of partial reduction variables

Reduction variables are an important class of cross-thread depen-dence that can be parallelized by exploiting the associativity and commutativity of their operation. In this paper, we define a class of shared variables called partial reduction variables (PRV). These variables either cannot be proven to be reductions or they violate the requirements of a reduction variable in some way. We describe an algorithm that allows the compiler to detect PRVs, and we also discuss the necessary requirements to paral-lelize detected PRVs. Based on these requirements, we propose an implementation in a TLS system to parallelize PRVs that works by a combination of techniques at compile time and in the hard-ware. The compiler transforms the variable under the assumption that the reduction-like behavior proven statically will hold true at runtime. However, if a thread reads or updates the shared variable as a result of an alias or unlikely control path, a lightweight hard-ware mechanism will detect the access and synchronize it to ensure correct execution. We implement our compiler analysis and trans-formation in GCC, and analyze its potential on the SPEC CPU 2000 benchmarks. We find that supporting PRVs provides up to 46 % per-formance gain over a highly optimized TLS system and on average 10.7 % performance improvement