TY - GEN
T1 - Sensitivity analysis for automatic parallelization on multi-cores
AU - Rus, Silvius
AU - Pennings, Maikel
AU - Rauchwerger, Lawrence
PY - 2007
Y1 - 2007
N2 - Sensitivity Analysis (SA) is a novel compiler technique that complements, and integrates with, static automatic parallelization analysis for the cases when relevant program behavior is input sensitive. In this paper we show how SA can extract all the input dependent, statically unavailable, conditions for which loops can be dynamically parallelized. SA generates a sequence of sufficient conditions which, when evaluated dynamically in order of their complexity, can each validate the dynamic parallel execution of the corresponding loop. For example, SA can first attempt to validate parallelization by checking simple conditions related to loop bounds. If such simple conditions cannot be met, then validating dynamic parallelization may require evaluating conditions related to the entire memory reference trace of a loop, thus decreasing the benefits of parallel execution. We have implemented Sensitivity Analysis in the Polaris compiler and evaluated its performance using 22 industry standard benchmark codes running on two multicore systems. In most cases we have obtained speedups superior to the Intel Ifort compiler because with SA we could complement static analysis with minimum cost dynamic analysis and extract most of the available coarse grained parallelism.
AB - Sensitivity Analysis (SA) is a novel compiler technique that complements, and integrates with, static automatic parallelization analysis for the cases when relevant program behavior is input sensitive. In this paper we show how SA can extract all the input dependent, statically unavailable, conditions for which loops can be dynamically parallelized. SA generates a sequence of sufficient conditions which, when evaluated dynamically in order of their complexity, can each validate the dynamic parallel execution of the corresponding loop. For example, SA can first attempt to validate parallelization by checking simple conditions related to loop bounds. If such simple conditions cannot be met, then validating dynamic parallelization may require evaluating conditions related to the entire memory reference trace of a loop, thus decreasing the benefits of parallel execution. We have implemented Sensitivity Analysis in the Polaris compiler and evaluated its performance using 22 industry standard benchmark codes running on two multicore systems. In most cases we have obtained speedups superior to the Intel Ifort compiler because with SA we could complement static analysis with minimum cost dynamic analysis and extract most of the available coarse grained parallelism.
KW - Multicore
KW - Parallelism
KW - Sensitivity analysis
UR - http://www.scopus.com/inward/record.url?scp=34548045548&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548045548&partnerID=8YFLogxK
U2 - 10.1145/1274971.1275008
DO - 10.1145/1274971.1275008
M3 - Conference contribution
AN - SCOPUS:34548045548
SN - 1595937684
SN - 9781595937681
T3 - Proceedings of the International Conference on Supercomputing
SP - 263
EP - 273
BT - Proceedings of ICS07
T2 - 21st ACM International Conference on Supercomputing, ICS07
Y2 - 17 June 2007 through 21 June 2007
ER -