Informatics Report Series


Report   

EDI-INF-RR-0877


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:A Compiler Cost Model for Speculative Parallelization
Authors: Jialin Dou ; Marcelo Cintra
Date: 2007
Publication Type:Journal Article
DOI:10.1145/1250727.1250732
Abstract:
Speculative parallelization is a technique that allows code sections that cannot be fully analyzed by the compiler to be aggressively executed in parallel. However, while speculative parallelization can potentially deliver significant speedups, several overheads associated with this technique can limit these speedups in practice. This paper proposes a novel compiler static cost model of speculative multithreaded execution that can be used to predict the resulting performance. This model attempts to predict the expected speedups, or slowdowns, of the candidate speculative sections based on the estimation of the combined run-time effects of various overheads, and taking into account the scheduling restrictions of most speculative execution environments. The model is based on estimating the likely execution duration of threads and considers all the possible permutations of these threads. Also, this model produces a quantitative estimate of the speedup, which is different from prior heuristics that only qualitatively estimate the benefits of speculative multithreaded execution. In previous work, a limited version of the framework was evaluated on a number of loops from a collection of SPEC benchmarks that suffer mainly from load imbalance and thread dispatch and commit overheads. In this work, an extended framework is also evaluated on loops that may suffer from data dependence violations. Experimental results show that prediction accuracy is lower when loops with violations are included. Nevertheless, accuracy is still very high for a static model: the framework can identify on average 45% of the loops that cause slowdowns and on average 96% of the loops that lead to speedups; it predicts the speedups or slowdowns with an error of less than 20% for an average of 28% of the loops across the benchmarks, and with an error of less than 50% for an average of 80% of the loops. Overall, the framework often outperforms, by as much as 25%, a naive approach that atte
Links To Paper
1st Link
Bibtex format
@Article{EDI-INF-RR-0877,
author = { Jialin Dou and Marcelo Cintra },
title = {A Compiler Cost Model for Speculative Parallelization},
journal = {},
year = 2007,
doi = {10.1145/1250727.1250732},
url = {http://homepages.inf.ed.ac.uk/mc/Publications/taco07.pdf},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh