Reconstructing affine codes from their memory traces

Complete comprehension of loop codes is desirable for a variety of program optimizations. Compilers perform static transforms and analyses, such as loop tiling or memory partitioning, by construct-ing and manipulating formal representations of the source code. Runtime systems observe and characterize application behavior to drive resource management and allocation, including dependence detection and parallelization, or scheduling. However, the source code of target applications is not always available to the compiler or runtime system in an analyzable form. It becomes necessary to find alternate ways to model application behavior. This paper presents a novel mathematical framework to rebuild loops from their memory access trace. An exploration engine tra-verses a tree-like solution space, driven by the access strides in the trace. It is guaranteed that the engine will find the minimal affine nest capable of reproducing the observed sequence of accesses by exploring this space in a brute force fashion, but most real traces will not be tractable in this way. Methods for an efficient solu-tion space traversal based on mathematical properties of the equa-tion systems which model the solution space are proposed. The experimental evaluation shows that these strategies achieve effi-cient loop reconstruction, processing hundreds of gigabytes of trace data in minutes. The proposed approach is capable of correctly and minimally reconstructing 100 % of the static control parts in Poly-Bench/C applications. As a side effect, this achieves very high com-pression rates of trace files. When used for dynamic access charac-terization, it is capable of predicting over 99 % of future memory accesses. 1