Multi-level tiling: M for the price of one

Dae Gon Kim, Lakshminarayanan Renganarayanan, Dave Rostron, Sanjay Rajopadhye, Michelle Mills Strout

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations

Abstract

Tiling is a widely used loop transformation for exposing/-exploiting parallelism and data locality. High-performance implementations use multiple levels of tiling to exploit the hierarchy of parallelism and cache/register locality. Efficient generation of multi-level tiled code is essential for effective use of multi-level tiling. Parameterized tiled code, where tile sizes are not fixed but left as symbolic parameters can enable several dynamic and run-time optimizations. Previous solutions to multi-level tiled loop generation are limited to the case where tile sizes are fixed at compile time. We present an algorithm that can generate multi-level parameterized tiled loops at the same cost as generating single-level tiled loops. The efficiency of our method is demonstrated on several benchmarks. We also present a method-useful in register tiling-for separating partial and full tiles at any-arbitrary level of tiling. The code generator we have implemented is available as an open source tool. (c) 2007 ACM.

Original languageEnglish (US)
Title of host publicationProceedings of the 2007 ACM/IEEE Conference on Supercomputing, SC'07
DOIs
StatePublished - 2007
Externally publishedYes
Event2007 ACM/IEEE Conference on Supercomputing, SC'07 - Reno, NV, United States
Duration: Nov 10 2007Nov 16 2007

Publication series

NameProceedings of the 2007 ACM/IEEE Conference on Supercomputing, SC'07

Other

Other2007 ACM/IEEE Conference on Supercomputing, SC'07
Country/TerritoryUnited States
CityReno, NV
Period11/10/0711/16/07

Keywords

  • Data locality
  • Multi-level tiling
  • Parallelism
  • Parameterized code generation

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Multi-level tiling: M for the price of one'. Together they form a unique fingerprint.

Cite this