Register tiling in nonrectangular iteration spaces
ACM Transactions on Programming Languages and Systems · 2002-07 · 24 (4) · 409-453
DOI: 10.1145/567097.567101 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Programming Languages and Systems, 2002-07. Verfasst von Marta Jiménez und 2 weiteren Autor:innen. Die Arbeit wurde bisher 29-mal zitiert (Crossref) und nennt 50 Literaturangaben.
Abstract (Originalsprache)
Loop tiling is a well-known loop transformation generally used to expose coarse-grain parallelism and to exploit data reuse at the cache level. Tiling can also be used to exploit data reuse at the register level and to improve a program's ILP. However, previous proposals in the literature (as well as commercial compilers) are only able to perform multidimensional tiling for the register level when the iteration space is rectangular. In this article we present a new general algorithm to perform multidimensional tiling for the register level in both rectangular and nonrectangular iteration spaces. We also propose a simple heuristic to determine the tiling parameters at this level. Finally, we evaluate our method using as benchmarks typical linear algebra algorithms having nonrectangular iteration spaces and compare our proposal against hand-optimized vendor-supplied numerical libraries and against commercial compilers able to perform optimizing code transformations such as inner unrolling, unroll-and-jam, and software pipelining. Measurements were taken on three different superscalar microprocessors. Results will show that our method outperforms the native compilers (showing speedups of 2.5 in average) and matches the performance of vendor-supplied numerical libraries. The general conclusion is that compiler technology can make it possible for nonrectangular loop nests to achieve as high performance as hand-optimized codes.
Zitieren
APA
Jiménez, M., Llabería, J. M., & Fernández, A. (2002). Register tiling in nonrectangular iteration spaces. ACM Transactions on Programming Languages and Systems, 24(4), 409-453. https://doi.org/10.1145/567097.567101
Vancouver
Jiménez M, Llabería JM, Fernández A. Register tiling in nonrectangular iteration spaces. ACM Transactions on Programming Languages and Systems. 2002;24(4):409-453. doi:10.1145/567097.567101
BibTeX
@article{Jimnez2002,
author = {Jiménez, Marta and Llabería, José M. and Fernández, Agustín},
title = {Register tiling in nonrectangular iteration spaces},
journal = {ACM Transactions on Programming Languages and Systems},
year = {2002},
volume = {24},
number = {4},
pages = {409--453},
doi = {10.1145/567097.567101}
}
EUVIMED