IEGen: semi-automatic generation of inspectors and executors
Date
2010
Authors
LaMielle, Alan, author
Strout, Michelle, advisor
Rajopadhye, Sanjay Vishnu, committee member
Liu, Jiangguo, committee member
Journal Title
Journal ISSN
Volume Title
Abstract
Software that simulates real-world phenomena such as heat transfer over surfaces and molecular interaction is often based on irregular computational kernels. Indirect array accesses such as A[B[i]] that are found in irregular computations often exhibit a memory access pattern that does not make efficient use of the memory hierarchy, reducing performance. Additionally, indirect array accesses hinder our ability to apply loop optimizations to improve data locality or introduce parallelism at compile time. One approach to solving this problem, an inspector/executor strategy, inspects the index arrays (B) at runtime to determine the order of accesses to the data arrays (A), reorders the data and index arrays, and executes a transformed computation that accesses the data arrays in a more efficient manner. For the most part, the application of inspector/executor strategies to irregular computations has been done manually or with limited generality. This thesis presents the Inspector/Executor Generator (IEGen). This tool accepts an irregular computation specification and sequence of run-time reordering transformations to apply to that computation as input. IEGen then generates serial inspector and executor code that implements the transformed computation. We contribute an inspector intermediate representation (IR) called an Inspector Dependence Graph (IDG), a method for code generation of inspectors based on an IDG, a method for code generation of executors, and techniques for manipulating affine constraints with uninterpreted function symbol (UFS) expressions to enable code generation. We evaluate our techniques against an existing library that supports limited UFS expressions and additionally show that generalized generation of inspectors and executors that implement composed run-time reordering transformations is possible.
Description
Department Head: L. Darrell Whitley.