 |
Hybrid Data Dependence Analysis
Hybrid Data Dependence Analysis (HDA) takes as input a dependence equation Dependence Set = Φ, where Dependence Set is expressed as a Uniform Set of References. It extracts equivalent predicates that can be easily evaluated at run-time based on:
- A divide-and-conquer approach that breaks the dependence problem into subproblems following the syntactic structure of the USR, based on set algebra identities
- Extraction of conditional approximations of USRs
- Extraction of conditions from LMAD (linear intervals) relations
- Pattern matching against an established library
The evaluation of these predicates takes place at run-time as soon as their input values become available. They are organized in a cascade of simple (e.g. comparisons) to complex (e.g. interprocedural inspectors or speculation validation) tests. Library routines such as interval overlap tests handle known patterns efficiently, while reference-based tests provide a fallback when a predicate could not be extracted.
| Data Structures | Algorithms |
Publications and Presentations
|
Silvius Rus, Lawrence Rauchwerger, "Hybrid Dependence Analysis for Automatic Parallelization," Technical Report, TR05-013, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2005. |