Writing productive stencil codes with overlapped tiling

Jia Guo, Ganesh Bikshandi, Basilio B. Fraguela, David Padua

Research output: Contribution to journalArticlepeer-review

Abstract

Stencil computations constitute the kernel of many scientific applications. Tiling is often used to improve the performance of stencil codes for data locality and parallelism. However, tiled stencil codes typically require shadow regions, whose management becomes a burden to programmers. In fact, it is often the case that the code required to manage these regions, and in particular their updates, is much longer than the computational kernel of the stencil. As a result, shadow regions usually impact programmers' productivity negatively. In this paper, we describe overlapped tiling, a construct that supports shadow regions in a convenient, flexible and efficient manner in the context of the hierarchically tiled array (HTA) data type. The HTA is a class designed to express algorithms with a high degree of parallelism and/or locality as naturally as possible in terms of tiles. We discuss the syntax and implementation of overlapped HTAs as well as our experience in rewriting parallel and sequential codes using them. The results have been satisfactory in terms of both productivity and performance. For example, overlapped HTAs reduced the number of communication statements in non-tri vial codes by 78% on average while speeding them up. We also examine different implementation options and compare overlapped HTAs with previous approaches.

Original languageEnglish (US)
Pages (from-to)25-39
Number of pages15
JournalConcurrency and Computation: Practice and Experience
Volume21
Issue number1
DOIs
StatePublished - Jan 2009

Keywords

  • Overlapped tiling
  • Productivity
  • Shadow regions
  • Stencil computations
  • Tiles

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Writing productive stencil codes with overlapped tiling'. Together they form a unique fingerprint.

Cite this