Speculatively Exploiting Cross-Invocation Parallelism

Jialu Huang, Prakash Prabhu, Thomas B. Jablin, Soumyadeep Ghosh, Sotiris Apostolakis, Jae W. Lee, David I. August

Research output: Contribution to journalConference article

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)207-219
Number of pages13
JournalParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
DOIs
StatePublished - Jan 1 2016
Event25th International Conference on Parallel Architectures and Compilation Techniques, PACT 2016 - Haifa, Israel
Duration: Sep 11 2016Sep 15 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • Automatic parallelization
  • barrier speculation
  • code generation

Fingerprint Dive into the research topics of 'Speculatively Exploiting Cross-Invocation Parallelism'. Together they form a unique fingerprint.

  • Cite this