Smashing: Folding space to tile through time

Nissa Osheim, Michelle Mills Strout, Dave Rostron, Sanjay Rajopadhye

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

6 Scopus citations

Abstract

Partial differential equation solvers spend most of their computation time performing nearest neighbor (stencil) computations on grids that model spatial domains. Tiling is an effective performance optimization for improving the data locality and enabling course-grain parallelization for such computations. However, when the domains are periodic, tiling through time is not directly applicable due to wrap-around dependencies. It is possible to tile within the spatial domain, but tiling across time (i.e. time skewing) is not legal since no constant skewing can render all loops fully permutable. We introduce a technique called smashing that maps a periodic domain to computer memory without creating any wrap-around dependencies. For a periodic cylinder domain where time skewing improves performance, the performance of smashing is comparable to another method, circular skewing, which also handles the periodicity of a cylinder. Unlike circular skewing, smashing can remove wrap-around dependencies for an icosahedron model of earth's atmosphere.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 21st International Workshop, LCPC 2008, Revised Selected Papers
Pages80-93
Number of pages14
DOIs
StatePublished - 2008
Externally publishedYes
Event21st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2008 - Edmonton, AB, Canada
Duration: Jul 31 2008Aug 2 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5335 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2008
Country/TerritoryCanada
CityEdmonton, AB
Period7/31/088/2/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Smashing: Folding space to tile through time'. Together they form a unique fingerprint.

Cite this