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

Gao, Lin, Li, Lian, Xue, Jingling and Yew, Pen-Chung (2013) SEED: a statically greedy and dynamically adaptive approach for speculative loop execution. IEEE Transactions on Computers, 62 5: 1004-1016. doi:10.1109/TC.2012.41

Author Gao, Lin
Li, Lian
Xue, Jingling
Yew, Pen-Chung
Title SEED: a statically greedy and dynamically adaptive approach for speculative loop execution
Journal name IEEE Transactions on Computers   Check publisher's open access policy
ISSN 0018-9340
Publication date 2013-05
Year available 2012
Sub-type Article (original research)
DOI 10.1109/TC.2012.41
Volume 62
Issue 5
Start page 1004
End page 1016
Total pages 13
Place of publication Piscataway, NJ, United States
Publisher Institute of Electrical and Electronics Engineers
Collection year 2014
Language eng
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.
Keyword Loop-level speculation
thread-level speculation
speculative compilation
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2014 Collection
Earth Systems Science Computational Centre Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 11 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 16 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 12 May 2013, 00:47:55 EST by System User on behalf of Scholarly Communication and Digitisation Service