Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Tiling Imperfectly-nested Loops

Tiling Imperfectly-nested Loops

File(s)
99-1770.pdf (292.16 KB)
99-1770.ps (318.51 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7424
Collections
Computer Science Technical Reports
Author
Ahmed, Nawaaz
Mateev, Nikolay
Pingali, Keshav
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.

Date Issued
1999-09
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR99-1770
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance