DocumentCode :
2627344
Title :
An algorithm to automate non-unimodular transformations of loop nests
Author :
Xue, Jingling
Author_Institution :
Sch. of Electr. & Electron. Eng., Nanyang Technol. Univ., Singapore
fYear :
1993
fDate :
1-4 Dec 1993
Firstpage :
512
Lastpage :
519
Abstract :
This paper provides a solution to the open problem of automatic rewriting loop nests for non-unimodular transformations. We present an algorithm that rewrites a loop nest under any non-singular (unimodular or non-unimodular) transformation. The algorithm works nicely with unimodular transformations being treated as a special case. The first step of the algorithm calculates the loop bounds using the Fourier-Motzkin elimination method. The second step relies on a method based on the theory of Hermite normal form and lattice and is only needed for non-unimodular transformations. It consists of calculating the loop strides and adjusting the loop bounds derived in the first step so that the "holes" in the image iteration space are skipped. The time complexity of the second step is polynomial, which is the time complexity of calculating the Hermite normal form of an n × n matrix, where n is the depth of the loop nest. The adjusted loop bounds are the simplest that can be expected
Keywords :
computational complexity; iterative methods; matrix algebra; open systems; parallel algorithms; polynomials; rewriting systems; Fourier-Motzkin elimination method; Hermite normal form; adjusted loop bounds; automatic rewriting loop nests; image iteration space; lattice; loop nests; n × n matrix; nonunimodular transformations; open problem; polynomial; rewriting algorithm; time complexity; Algorithm design and analysis; Lattices; Polynomials; Terminology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing, 1993. Proceedings of the Fifth IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-4222-X
Type :
conf
DOI :
10.1109/SPDP.1993.395490
Filename :
395490
Link To Document :
بازگشت