A singular loop transformation framework based on non-singular matrices |
| |
Authors: | Wei Li Keshav Pingali |
| |
Affiliation: | (1) Department of Computer Science, Cornell University, 14853 Ithaca, New York |
| |
Abstract: | In this paper, we discuss a loop transformation framework that is based on integer non-singular matrices. The transformations
included in this framework are called Λ-transformations and include permutation, skewing and reversal, as well as a transformation
calledloop scaling. This framework is more general than existing ones; however, it is also more difficult to generate code in our framework.
This paper shows how integer lattice theory can be used to generate efficient code. An added advantage of our framework over
existing ones is that there is a simple completion algorithm which, given a partial transformation matrix, produces a full
transformation matrix that satisfies all dependences. This completion procedure has applications in parallelization and in
the generation of code for NUMA machines.
This work was supported by the Cornell Theory Center, NSF Presidential Young Investigator award #CCR-8958543. by NSF Grant
#CCR-9008526, and by a grant from the Hewlett-Packard Company. |
| |
Keywords: | Loop transformation compound transformations nonsingular matrices Hermite normal form code generation |
本文献已被 SpringerLink 等数据库收录! |
|