TY - JOUR
T1 - Speculatively Exploiting Cross-Invocation Parallelism
AU - Huang, Jialu
AU - Prabhu, Prakash
AU - Jablin, Thomas B.
AU - Ghosh, Soumyadeep
AU - Apostolakis, Sotiris
AU - Lee, Jae W.
AU - August, David I.
N1 - Funding Information:
Acknowledgments We thank the Liberty Research Group for their support and feedback during this work. We also thank Xipeng Shen and the anonymous reviewers for their insightful comments and suggestions. This work is supported by the National Science Foundation (NSF) through Grants OCI-1047879, CCF-1439085, and CNS-0964328. All opinions ndings, conclusions, and recommendations expressed in this paper are those of the Liberty Research Group and do not necessarily reect the views of the NSF. This work was carried out when the authors were working at Princeton University.
PY - 2016
Y1 - 2016
N2 - Automatic parallelization has shown promise in producing scalable multi-threaded programs for multi-core architectures. Most existing automatic techniques parallelize independent loops and insert global synchronization between loop invocations. For programs with many loop invocations, frequent synchronization often becomes the performance bottleneck. Some techniques exploit cross-invocation parallelism to overcome this problem. Using static analysis, they partition iterations among threads to avoid cross-thread dependences. However, this approach may fail if dependence pattern information is not available at compile time. To address this limitation, this work proposes SpecCross-the first automatic parallelization technique to exploit cross-invocation parallelism using speculation. With speculation, iterations from different loop invocations can execute concurrently, and the program synchronizes only on misspeculation. This allows SpecCross to adapt to dependence patterns that only manifest on particular inputs at runtime. Evaluation on eight programs shows that SpecCross achieves a geomean speedup of 3.43x over parallel execution without cross-invocation parallelization.
AB - Automatic parallelization has shown promise in producing scalable multi-threaded programs for multi-core architectures. Most existing automatic techniques parallelize independent loops and insert global synchronization between loop invocations. For programs with many loop invocations, frequent synchronization often becomes the performance bottleneck. Some techniques exploit cross-invocation parallelism to overcome this problem. Using static analysis, they partition iterations among threads to avoid cross-thread dependences. However, this approach may fail if dependence pattern information is not available at compile time. To address this limitation, this work proposes SpecCross-the first automatic parallelization technique to exploit cross-invocation parallelism using speculation. With speculation, iterations from different loop invocations can execute concurrently, and the program synchronizes only on misspeculation. This allows SpecCross to adapt to dependence patterns that only manifest on particular inputs at runtime. Evaluation on eight programs shows that SpecCross achieves a geomean speedup of 3.43x over parallel execution without cross-invocation parallelization.
KW - Automatic parallelization
KW - barrier speculation
KW - code generation
UR - http://www.scopus.com/inward/record.url?scp=84989285796&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84989285796&partnerID=8YFLogxK
U2 - 10.1145/2967938.2967959
DO - 10.1145/2967938.2967959
M3 - Conference article
AN - SCOPUS:84989285796
SN - 1089-795X
SP - 207
EP - 219
JO - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT
JF - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT
T2 - 25th International Conference on Parallel Architectures and Compilation Techniques, PACT 2016
Y2 - 11 September 2016 through 15 September 2016
ER -