Spice: Speculative Parallel Iteration Chunk Execution

Easwaran Raman, Neil Vachharajani, Ram Rangan, David I. August

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

27 Scopus citations

Abstract

The recent trend in the processor industry of packing multiple processor cores in a chip has increased the importance of automatic techniques for extracting thread level parallelism. A promising approach for extracting thread level parallelism in general purpose applications is to apply memory alias or value speculation to break dependences amongst threads and executes them concurrently. In this work, we present a speculative parallelization technique called Speculative Parallel Iteration Chunk execution (Spice) which relies on a novel software-only value prediction mechanism. Our value prediction technique predicts the loop live-ins of only a few iterations of a given loop, enabling speculative threads to start from those iterations. It also increases the probability of successful speculation by only predicting that the values will be used as live-ins in some future iterations of the loop. These twin properties enable our value prediction scheme to have high prediction accuracies while exposing significant coarse-grained thread-level parallelism. Spice has been implemented as an automatic transformation in a research compiler. The technique results in up to 157% speedup (101% on average) with 4 threads.

Original languageEnglish (US)
Title of host publicationProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization
Pages175-184
Number of pages10
DOIs
StatePublished - May 19 2008

Publication series

NameProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Automatic paralleization
  • Multicore architectures
  • Speculative parallelization
  • Thread level parallelism
  • Value speculation

Fingerprint Dive into the research topics of 'Spice: Speculative Parallel Iteration Chunk Execution'. Together they form a unique fingerprint.

  • Cite this

    Raman, E., Vachharajani, N., Rangan, R., & August, D. I. (2008). Spice: Speculative Parallel Iteration Chunk Execution. In Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization (pp. 175-184). (Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization). https://doi.org/10.1145/1356058.1356082