CDA, computation decomposition and alignment

grantor: University of TorontoRestructuring compilers have been effective in tailoring nested loops and arrays as as to improve performance on both uniprocessor and multiprocessor systems. The regular structure of nested loops and arrays has enabled their systematic analysis and transformation. The focus of this dissertation is a new and generalized loop transformation framework, called Computation Decomposition and Alignment (CDA). The linear loop transformation framework introduced in 1990 was a major breakthrough, partly because it provided a unified view of many of the earlier loop transformations, and partly because it was a formal method based on linear algebra. Since then, the compiler community has designed algorithms which automatically derive linear transformations that achieve specific optimization objectives in given nested loops. The framework also sparked the development of generic techniques to derive efficient code for the linearly transformed loop structures. The main contribution of this dissertation is the CDA transformation framework, which is capable of restructuring nested loops at the granularity of statements and subexpressions. The granularity of transformation is thus finer than in the linear loop transformation framework, which transforms nested loops at the granularity of entire iterations. A CDA transformation is applied to a nested loop in two steps. First, the loop iteration space is decomposed into multiple computation spaces, each representing computations of a statement or a subexpression. Second, each of the computation spaces is linearly transformed with a (possibly) different transformation matrix. CDA unifies into a single framework many existing transformations including all linear loop transformations. A linear loop transformation only modifies the execution order of the iterations, while a CDA transformation modifies both the composition of the iterations and the execution order of the re-composed iterations. This feature enables new optimizations which cannot be obtained by linear loop transformations alone. In this thesis, we show how CDA transformations can achieve the effect of certain global data transformations. We present heuristic algorithms to automatically derive CDA transformations to reduce (i) the number of cache conflicts and (ii) the number of ownership tests, and we show how CDA can achieve several other optimizations. We also compare the performance of some benchmark loops to the corresponding CDA transformed loops using a simulator and three different types of real computer systems.Ph.D