Symbolic Array Data Flow Analysis and Pattern Recognition in Numerical Codes
Christoph W. Keßler · Birkhäuser Basel eBooks · 1994
The PARAMAT approach to fully automatic distributed-memory parallelization consists of three basic ideas: First, we observe that we can cover large parts of many numerical codes by a small set of typical programming patterns. Second, we give a fast and powerful pattern recognition algorithm which tries to locally recover the semantics of the program while being robust against many common code modifications like loop distribution, loop interchange, loop blocking or loop unrolling. Third, we use the restored program semantics information to guide data partitioning, run time prediction and sophisticated optimizing code transformations including algorithm replacement. In this paper we focus on the symbolic array dataflow analysis techniques of PARAMAT’s pattern recognition tool. We introduce a compact symbolic access descriptor and use it to compute array data flow that guides the recognition process. As an example, we show the application of this method to recognize and reroll unrolled loops. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.