article · 2008

Abstract Tiling Imperfectly-nested Loop Nests

Nawaaz Ahmed, Nikolay Mateev, Keshav Pingali

Cited by 0Abstract and details only

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. 1 Background and Previous Work The memory systems of computers are organized as a hierarchy in which the latency of memory accesses increases by roughly an order of magnitude from one level of the hierarchy to the next. Therefore, a program runs well only if it exhibits enough locality of reference for most of its data accesses to be satisfied by the faster levels of the memory hierarchy. Unfortunately, programs produced by straightforward coding of most algorithms do not exhibit sufficient locality of reference. The numerical linear algebra community has addressed this problem by writing libraries of carefully hand-crafted programs such as the Basic Linear Algebra Subroutines (BLAS) [22] and LAPACK [3] for algorithms of interest to their community. However, these 0This work was supported by NSF grants CCR-9720211, EIA-9726388

Cite this paper

APA 7

Ahmed, N., Mateev, N., & Pingali, K. (2008). Abstract Tiling Imperfectly-nested Loop Nests.

MLA 9

Ahmed, Nawaaz, et al. “Abstract Tiling Imperfectly-nested Loop Nests.” 2008.

Chicago

Ahmed, Nawaaz, Nikolay Mateev, and Keshav Pingali. 2008. “Abstract Tiling Imperfectly-nested Loop Nests.”

Harvard

Ahmed, N., Mateev, N. and Pingali, K. (2008) ‘Abstract Tiling Imperfectly-nested Loop Nests’.

BibTeX

@article{ahmed2008abstract,
  title = {{Abstract Tiling Imperfectly-nested Loop Nests}},
  author = {Ahmed, Nawaaz and Mateev, Nikolay and Pingali, Keshav},
  year = {2008}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.