ACM Transactions on Programming Languages and Systems · 2002 · 36 citations · 40 references
ComputingComputer EngineeringComputer ScienceAlgorithmsCompilersComputer ArchitectureAlgorithm AnalysisData-flow AnalysisHardware AccelerationRegister AllocationSuperscalar ProcessingCompiler DesignComputational Linear AlgebraLoop TilingLoop UnrollingSoftware PipeliningSuperscalar MicroarchitectureTilingsTransformations
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.
40
A set of level 3 basic linear algebra subprograms
Jack Dongarra, Jeremy Du Croz, Sven Hammarling et al. · ACM Transactions on Mathematical Software · 1990 · 1.8K citations · Full text
A data locality optimizing algorithm
Michael E. Wolf, Monica S. Lam · 1991 · 1.3K citations · Full text
Monica S. Lam · ACM SIGPLAN Notices · 2004 · 890 citations
The Mips R10000 superscalar microprocessor
K.C. Yeager · IEEE Micro · 1996 · 840 citations