Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Tiling Imperfectly-nested Loops
Authors: Ahmed, Nawaaz
Mateev, Nikolay
Pingali, Keshav
Keywords: computer science
technical report
Issue Date: Sep-1999
Publisher: Cornell University
Abstract: Tiling is one of the more important transformations for enhancing locality of reference in programs. Intuitively, tiling a set of loops achieves the effect of interleaving iterations of these loops. Tiling has been applied only to perfectly-nested loop nests which are loop nests in which all assignment statements are contained in the innermost loop. In practice, most loop nests are imperfectly-nested, so existing techniques have limited utility. In this paper, we propose an approach to tiling imperfectly-nested loop nests. The key idea is to embed the iteration space of every statement in the imperfectly-nested loop nest into a special space called the product space which is tiled to produce the final code. We evaluate the effectiveness of this approach for dense numerical linear algebra benchmarks, relaxation codes, and the tomcatv code from the SPEC benchmarks. No other approach in the literature can tile all these codes automatically.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
99-1770.pdf292.16 kBAdobe PDFView/Open
99-1770.ps318.51 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us