 |
Uniform Set of References (USR)
USR: Representation of memory locations sets that tolerates compile-time analysis failure.
The representation of memory location sets in compilers is crucial to the success of various analysis and optimization techniques: data dependence, parallelization, locality enhancement, checkpoint etc. For instance, a data independence test on a loop can be formulated as: the set of memory locations that carry dependences across different iterations is empty. We introduce a novel representation of memory locations sets closed with respect to composition operators commonly used by analyses of memory references: set intersection, set union, set difference, predication, union over an index space and translation across subprogram boundaries. This representation can tolerate static analysis failures. Previous static analyses had to approximate the results of their operations with memory location sets.
Our representation is persistent between compile-time and run-time. This feature is crucial to hybrid analyses of memory patterns, which consist of a continuum of compile-time and run-time manipulations of memory location sets.
The figure above presents the description of our representation using a grammar. Operands are either program constructs (variables, recurrence formulas, call sites, predicates), or partially aggregated LMADs (multi-dimensional intervals). A memory locations set is an expression in this grammar. The set of memory locations referenced by any well-nested program slice can be described using this language. Partial aggregation is achieved by mechanical transformations on parse trees. Persistence is implemented by embedding code to represent a memory location set as a run-time data structure. The code generation scheme is based on an attribute grammar.
Publications
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.
Technical Report(ps, pdf, ppt, abstract)
Silvius Rus, Lawrence Rauchwerger, Jay Hoeflinger, "Hybrid Analysis: Static & Dynamic Memory Reference Analysis," International Journal of Parallel Programming, 31(4):251-283, Aug 2003. Also, In Proc. ACM Int. Conf.
Supercomputing (ICS), pp. 274-284, New York City, Jun 2002. Also, Technical Report, TR02-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2002.
Journal(pdf, ppt, abstract) Proceedings(ps, pdf, ppt, abstract) Technical Report(ps, pdf, ppt, abstract)