SEED: A statically greedy and dynamically adaptive approach for speculative loop execution

Lin Gao, Lian Li, Jingling Xue, Pen Chung Yew

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

Research on compiler techniques for thread-level loop speculation has so far remained on studying its performance limits: loop candidates that are worthy of parallelization are manually selected by the researchers or based on extensive profiling and preexecution. It is therefore difficult to include them in a production compiler for speculative multithreaded multicore processors. In a way, existing techniques are statically adaptive ('realized'; by the researchers for different inputs) yet dynamically greedy (since all iterations of all selected loop candidates are always parallelized at run time). This paper introduces a Statically GrEEdy and Dynamically Adaptive (SEED) approach for thread-level speculation on loops that is quite different from most other existing techniques. SEED relies on the compiler to select and optimize loop candidates greedily (possibly in an input-independent way) and provides a runtime scheduler to schedule loop iterations adaptively. To select loops for parallelization at runtime (subject to program inputs), loop iterations are prioritized in terms of their potential benefits rather than their degree of speculation as in many prior studies. In our current implementation, the benefits of speculative threads are estimated by a simple yet effective cost model. It comprises a mechanism for efficiently tracing the loop nesting structures of the program and a mechanism for predicting the outcome of speculative threads. We have evaluated SEED using a set of SPECint2000 and Olden benchmarks. Compared to existing techniques with a program's loop candidates being ideally selected a priori, SEED can achieve comparable or better performance while aututomating the entire loop candidate selection process.

Original languageEnglish (US)
Article number6148216
Pages (from-to)1004-1016
Number of pages13
JournalIEEE Transactions on Computers
Volume62
Issue number5
DOIs
StatePublished - 2013

Keywords

  • Loop-level speculation
  • speculative compilation
  • thread-level speculation

Fingerprint

Dive into the research topics of 'SEED: A statically greedy and dynamically adaptive approach for speculative loop execution'. Together they form a unique fingerprint.

Cite this