Implementation of sensitivity analysis for automatic parallelization

Silvius Rus, Maikel Pennings, Lawrence Rauchwerger

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

Abstract

Sensitivity Analysis (SA) is a novel compiler technique that complements, and integrates with, static automatic parallelization analysis for the cases when program behavior is input sensitive. 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. While SA's principles are fairly simple, implementing it in a real compiler and obtaining good experimental results on benchmark codes is a difficult task. In this paper we present some of the most important implementation issues that we had to overcome in order to achieve a fairly successful automatic parallelizer. We present techniques related to validating dependence removing transformations, e.g., privatization or pushback parallelization, and static and dynamic evaluation of complex conditions for loop parallelization. We concern ourselves with multi-version and parallel code generation as well as the use of speculative parallelization when other, less costly options fail. We present a summary table of the contributions of our techniques to the successful parallelization of 22 industry benchmark codes. We also report speedups and parallel coverage of these codes on two multicore based systems and compare them to results obtained by the Ifort compiler.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 21st International Workshop, LCPC 2008, Revised Selected Papers
Pages316-330
Number of pages15
DOIs
StatePublished - Dec 1 2008
Externally publishedYes
Event21st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2008 - Edmonton, AB, Canada
Duration: Jul 31 2008Aug 2 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5335 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other21st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2008
CountryCanada
CityEdmonton, AB
Period7/31/088/2/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Implementation of sensitivity analysis for automatic parallelization'. Together they form a unique fingerprint.

  • Cite this

    Rus, S., Pennings, M., & Rauchwerger, L. (2008). Implementation of sensitivity analysis for automatic parallelization. In Languages and Compilers for Parallel Computing - 21st International Workshop, LCPC 2008, Revised Selected Papers (pp. 316-330). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5335 LNCS). https://doi.org/10.1007/978-3-540-89740-8_22