Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Journal of Information Science and Engineering, Vol.18 No.5, pp.667-691 (September 2002)


Code Generation Methods for Tiling Transformations


Georgios Goumas, Maria Athanasaki and nectarios koziris

Computing Systems Laboratory
Department of Electrical and Computer Engineering
National Technical University of Athens
Zografou Campus, Zografou 15773, Athens, Greece
E-mail: {goumas, mathan, nkoziris}@cslab.ece.ntua.gr

Tiling or supernode transformation has been widely used to improve locality in multi-level memory hierarchies, as well as to efficiently execute loops on parallel architectures. However, automatic code generation for tiled loops can be a very complex compiler work due to non-rectangular tile shapes and arbitrary iteration space bounds. In this paper, we first survey code generation methods for nested loops which are transformed using non-unimodular transformations. All methods are based on Fourier-Motzkin (FM) elimination. Next, we consider and enhance previous work on rewriting tiled loops by considering parallelepiped tiles and arbitrary iteration space shapes. In order to generate tiled code, all methods first enumerate the tiles containing points within the iteration space, and second, sweep the points within each tile. For the first, we extend previous work in order to access all tile origins correctly, while for the latter, we propose the transformation of the initial parallelepiped tile iteration space into a rectangular one, so as to generate code efficiently with the aid of a non-unimodular transformation matrix and its Hermite Normal Form (HNF). The resulting systems of inequalities are much simpler than those in bibliography; thus their solutions are determined more efficiently using the FM elimination. Experimental results which compare all presented approaches, show that the proposed method for generating tiled code is significantly faster, and thus rewriting any n-D tiled loop in a much more efficient and direct way.

Keywords: loop tiling, supernodes, non-unimodular transformations, Fourier-Motzkin elimination, code generation

Full Text () Retrieve PDF document (200209_02.pdf)

Received September 3, 2001; accepted April 15, 2002.
Communicated by Jang-Ping Sheu, Makoto Takizawa and Myongsoon Park.