The pochoir stencil compiler

By Yuan Tang, Rezaul Alam Chowdhury, Bradley C. Kuszmaul, Chi-Keung Luk, Charles E. Leiserson. ACM Symposium on Parallelism in Algorithms and Architectures, 2011

374 citations recorded by the source corpus.

A stencil computation repeatedly updates each point of a d-dimensional grid as a function of itself and its near neighbors. Parallel cache-efficient stencil algorithms based on "trapezoidal decompositions" are known, but most programmers find them difficult to write. The Pochoir stencil compiler allows a programmer to write a simple specification of a stencil in a domain-specific stencil language embedded in C++ which the Pochoir compiler then translates into high-performing Cilk code that employs an efficient parallel cache-oblivious algorithm. Pochoir supports general d-dimensional stencils and handles both periodic and aperiodic boundary conditions in one unified algorithm. The Pochoir system provides a C++ template library that allows the user's stencil specification to be executed directly in C++ without the Pochoir compiler (albeit more slowly), which simplifies user debugging and greatly simplified the implementation of the Pochoir compiler itself. A host of stencil benchmarks run on a modern multicore machine demonstrates that Pochoir outperforms standard parallelloop implementations, typically running 2-10 times faster. The algorithm behind Pochoir improves on prior cache-efficient algorithms on multidimensional grids by making "hyperspace" cuts, which yield asymptotically more parallelism for the same cache efficiency.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/e1ef06c2662a78dd2d885fb375b549dc4f01c9ba

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Frédo Durand
2. Saman P. Amarasinghe

In Hardware and Architecture

1. Andrew Adams
2. Jonathan Ragan-Kelley
3. Frédo Durand
4. Saman P. Amarasinghe
5. Yuandong Tian
6. Xinyun Chen

Citations in the corpus

• Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines (2013, methodology): “The Pochoir compiler automatically transforms stencil codes from serial form into a parallel cache oblivious form using similar algorithms [28].”
• A quadtree-adaptive multigrid solver for the Serre-Green-Naghdi equations (2015, background): “For example, the implementation of optimal storage and traversal strategies is highly non-trivial, even for simple Cartesian grids, and is itself a whole sub-discipline of computer science [16,49].”