Hybrid Analysis: Static & Dynamic Memory Reference Analysis

Silvius Rus, Lawrence Rauchwerger, Jay Hoeflinger

Research output: Contribution to journalReview article

Abstract

We present a novel Hybrid Analysis technology which can efficiently and seamlessly integrate all static and run-time analysis of memory references into a single framework that is capable of performing all data dependence analysis and can generate necessary information for most associated memory related optimizations. We use HA to perform automatic parallelization by extracting run-time assertions from any loop and generating appropriate run-time tests that range from a low cost scalar comparison to a full, reference by reference run-time analysis. Moreover we can order the run-time tests in increasing order of complexity (overhead) and thus risk the minimum necessary overhead. We accomplish this by both extending compile time IP analysis techniques and by incorporating speculative run-time techniques when necessary. Our solution is to bridge "free" compile time techniques with exhaustive run-time techniques through a continuum of simple to complex solutions. We have implemented our framework in the Polaris compiler by introducing an innovative intermediate representation called RT_LMAD and a run-time library that can operate on it. Based on the experimental results obtained to date we hope to automatically parallelize most and possibly all PERFECT codes, a significant accomplishment.

Original languageEnglish (US)
Pages (from-to)251-283
Number of pages33
JournalInternational Journal of Parallel Programming
Volume31
Issue number4
DOIs
StatePublished - Aug 1 2003

Keywords

  • Automatic parallelization
  • Hybrid analysis
  • Memory access representation

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

Fingerprint Dive into the research topics of 'Hybrid Analysis: Static & Dynamic Memory Reference Analysis'. Together they form a unique fingerprint.

  • Cite this