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 Loop Nests (REVISED)
Authors: Ahmed, Nawaaz
Mateev, Nikolay
Pingali, Keshav
Keywords: computer science
technical report
Issue Date: 31-Jan-2000
Publisher: Cornell University
Abstract: Tiling is one of the more important transformations for enhancing locality of reference in programs. Tiling of perfectly-nested loop nests (which are loop nests in which all assignment statements are contained in the innermost loop) is well understood. In practice, most loop nests are imperfectly-nested, so existing compilers heuristically try to find a sequence of transformations that convert such loop nests into perfectly-nested ones but not always succeed. In this paper, we propose a novel 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. The set of possible embeddings is constrained so that the resulting product space can be legally tiled. From this set we choose embeddings that enhance data reuse. 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 single approach in the literature can tile all these codes automatically.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
2000-1782.pdf300.47 kBAdobe PDFView/Open
2000-1782.ps528.33 kBPostscriptView/Open

Refworks Export

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


© 2014 Cornell University Library Contact Us