Collective Analysis and Transformation of Loop Clusters

this memo is a new loop analysis and transformation technique which brings compiler technology closer to meeting the needs of newer high-performance computer architectures. In specific terms, the technique provides a way of analyzing loop clusters in which the lead loops define array elements and successor loops use these elements to define yet other arrays. Array computations of this type could easily comprise a large portion of any scientific computation, especially if the application were written in a language such as FORTRAN 90. Consequently, being able to process arrays of this type efficiently is of fundamental importance. When array elements which are generated in one loop are able to be referenced in the same order by successor loops, the loops are compatible for pipelined processing. On a multiprocessor, pipelined processing is accomplished by running the constituent loops on different processors; whereas on a uniprocessor, the loops are fused and intermediate arrays eliminated through a process of collective transformation, a process itself which often creates opportunities for additional code improvement. By considering clusters as a collection, rather than individually, a compiler is able to identify opportunities for transformation which would not be apparent were the loops considered individually, as in traditional loop optimization. As we show in this document, the benefit from applying a global perspective to loop transformation can be substantial, especially in compiling programs, such as FORTRAN-90 programs, which allow statements in vector notation. The particular loop analysis methods we evaluate are based upon techniques developed by Sarkar and Gao [23]. Gao first raised the issue of collective loop analysis in the context of an intrablock pipelinin..