Repository logo
 

Scalable and efficient tools for multi-level tiling

Simple item page
dc.contributor.authorRenganarayana, Lakshminarayanan, author
dc.contributor.authorRajopadhye, Sanjay, advisor
dc.date.accessioned2024-03-13T20:12:31Z
dc.date.available2024-03-13T20:12:31Z
dc.date.issued2008
dc.description.abstractIn the era of many-core systems, application performance will come from parallelism and data locality. Effective exploitation of these require explicit (re)structuring of the applications. Multilevel (or hierarchical) tiling is one such structuring technique used in almost all high-performance implementations. Lack of tool support has limited the use of multi-level tiling to program optimization experts. We present solutions to two fundamental problems in multi-level tiling, viz., optimal tile size selection and parameterized tiled loop generation. Our solutions provide scalable and efficient tools for multi-level tiling. Parameterized tiled code refers to tiled loops where the tile sizes are not (fixed) compile-time constants but are left as symbolic parameters. It can enable selection and adaptation of tile sizes across a spectrum of stages through compilation to run-time. We introduce two polyhedral sets, viz., inset and outset, and use them to develop a variety of scalable and efficient multi-level tiled loop generation algorithms. The generation efficiency and code quality are demonstrated on a variety of benchmarks such as stencil computations and matrix subroutines from BLAS. Our technique can generate tiled loop nests with parameterized, fixed or mixed tile sizes, thereby providing a one-size-fits all solution ideal for inclusion in production compilers. Optimal tile size selection (TSS) refers to the selection of tile sizes that optimize some cost (e.g., execution time) model. We show that these cost models share a fundamental mathematical property, viz., positivity, that allows us to reduce optimal TSS to convex optimization problems. Almost all TSS models proposed in the literature for parallelism, caches, and registers, lend themselves to this reduction. We present the reduction of five different TSS models proposed in the literature by different authors in a variety of tiling contexts. Our convex optimization based TSS framework is the first one to provide a solution that is both efficient and scalable to multiple levels of tiling.
dc.format.mediumborn digital
dc.format.mediumdoctoral dissertations
dc.identifierETDF_Renganarayana_2008_3321306.pdf
dc.identifier.urihttps://hdl.handle.net/10217/237921
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
dc.rights.licensePer the terms of a contractual agreement, all use of this item is limited to the non-commercial use of Colorado State University and its authorized users.
dc.subjectcode generation
dc.subjectcompiler optimization
dc.subjectconvex optimization
dc.subjectloop tiling
dc.subjectparallelization
dc.subjectcomputer science
dc.titleScalable and efficient tools for multi-level tiling
dc.typeText
dcterms.rights.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineComputer Science
thesis.degree.grantorColorado State University
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy (Ph.D.)

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ETDF_Renganarayana_2008_3321306.pdf
Size:
2.61 MB
Format:
Adobe Portable Document Format
Download

Collections

2000-2019
Theses and Dissertations