# The Pochoir Project

(Difference between revisions)
 Revision as of 20:11, 11 February 2011 (view source)Yuantang (Talk | contribs) (→Pochoir Team)← Older edit Latest revision as of 21:36, 28 August 2012 (view source)m (Protected "The Pochoir Project" ([edit=sysop] (indefinite) [move=sysop] (indefinite))) (67 intermediate revisions not shown) Line 1: Line 1: - == Welcome to Pochoir == + ==
Welcome to Pochoir == - [[File:lbm.png|230px|left]] [[File:sim-space-cut.png]] +
[[File:lbm.png|230px|left]] [[File:sim-space-cut.png]] - == Pochoir - Parallel Stencil Computation Compiler == + ==
The Pochoir Stencil Compiler == - Pochoir (pronounced "PO-shwar") is a compiler and run-time system for implementing stencil computations on multicore processors. A stencil defines the value of a grid point in a d-dimensional spatial grid at time t as a function of neighboring grid points at recent times before t. A stencil computation computes the stencil for each grid point over many time steps. + Pochoir (pronounced "PO-shwar") is a compiler and runtime system for implementing stencil computations on multicore processors. A stencil defines the value of a grid point in a ''d''-dimensional spatial grid at time ''t'' as a function of neighboring grid points at recent times before ''t''. A stencil computation computes the stencil for each grid point over many time steps. Using Pochoir, a user specifies a computing kernel and boundary conditions using a simple stencil language embedded in C++.  The Pochoir compiler produces cache-efficient multithreaded C++ code that can be compiled with the Intel 12.0 compiler for C++ with the Cilk multithreading extensions, which is available as part of the [http://software.intel.com/en-us/articles/intel-parallel-composer/ Intel Parallel Computer] suite.  The Pochoir package contains two main components:  a C++ template library for debugging and testing Pochoir compliance and a domain-specific compiler written in Haskell that produces highly optimized code.  (Currently, the Pochoir package has only been tested on Linux systems.) - In Pochoir, user typically just need to specify his /or her stencil computing kernel and boundary conditions in an embedded domain specific language in C++. Depending on the purpose of checking functional correctness or performance, user can employ either a native C++ compiler or Pochoir compiler to compile and run his /or her code. If the user employs the Pochoir compiler, the basic parallelization and optimization strategy of Pochoir is divide-and-conquer (cache-oblivious algorithm). In higher dimensional space-time grid, Pochoir employs a novel cutting strategy of simultaneous space cut. + Here is an example of a 2D heat equation coded in Pochoir: + + #define mod(r,m) ((r)%(m) + ((r)<0)? (m):0) + Pochoir_Boundary_2D(heat_bv, a, t, x, y) + return a.get(t,mod(x,a.size(1)),mod(y,a.size(0))); + Pochoir_Boundary_End - Pochoir is an open source software project hosted by SuperTech group at CSAIL, MIT. You are invited to contribute in many forms (documentation, translation, writing code, fixing bugs, porting to other platforms...). + int main(void) { + Pochoir_Shape_2D 2D_five_pt[] = {{1,0,0}, {0,1,0}, {0,-1,0}, {0,-1,-1}, {0,0,-1}, {0,0,1}}; + Pochoir_2D heat(2D_five_pt); - The Pochoir package contains three (3) main components: an embedded domain specific language (EDSL) in native C++ for stencil, a C++ template library for baseline run, and a domain specific compiler for optimal run. + Pochoir_Array_2D(double) u(X, Y); + u.Register_Boundary(heat_bv); + heat.Register_Array(u); - The Pochoir EDSL is native C++, the library is C++ template library, and the DSL compiler is written in Haskell. Currently, the Pochoir package is only tested on Linux system. + Pochoir_Kernel_2D(heat_fn, t, x, y) + u(t+1, x, y) = CX * (u(t, x+1, y) - 2 * u(t, x, y) + u(t, x-1, y)) + CY * (u(t, x, y+1) - 2 * u(t, x, y) + u(t, x, y-1)) + u(t, x, y); + Pochoir_Kernel_End + + for (int x = 0; x < X; ++x) + for (int y = 0; y < Y; ++y) + u(0, x, y) = rand(); - == Pochoir Team == + heat.Run(T, heat_fn); - The project is jointly developed by SuperTech group at MIT and Intel Corp.. The core team includes: + for (int x = 0; x < X; ++x) + for (int y = 0; y < Y; ++y) + cout << u(T, x, y); - \begin{itemize} + return 0; - \item Yuan Tang + } - \item Charles E. Leiserson + - \item Rezaul Alam Chowdhury + - \item Chi-Keung Luk + - \item Bradley C. Kuszmaul. + - \end{itemize} + - == Current Release == + Pochoir is an open-source software project hosted by Supertech group at CSAIL, MIT. You are invited to contribute in any form (documentation, translation, writing code, fixing bugs, porting to other platforms, etc.).  We are particularly interested in developing a set of real-world example stencil computations. - Pochoir 1.0 is now released (Feb, 2011) + - [http://people.csail.mit.edu/yuantang/Pochoir.tgz Download Pochoir Source Code] + ==
Performance Graphs == + [[File:hotParSubmission1.png|700px]] - == Documentation == + Comparing the number of grid points processed per second (semilogarithmic scale) for Pochoir-generated code on 12 cores versus serial- and parallel-loop implementations. In all figures, the top curve is for the Pochoir-generated code, the middle curve is for parallel loops, and the bottom curve is for serial loops. (a) A 3D wave equation with a nonperiodic boundary condition executing for 1000 time steps. (b) A 2D heat equation on a torus executing for 3200 time steps. (c) 1D pairwise sequence alignment (no time step). (d) A Lattice Boltzmann method with a nonperiodic boundary condition for 3000 time steps. - [http://people.csail.mit.edu/yuantang/manual.pdf Manual] + - == Road Map == + ==
Pochoir Team == - 1) Performance, Performance, and Performance + - 2) Algorithm, Algorithm, and Algorithm + The Pochoir project is joint research by the [https://groups.csail.mit.edu/sct/wiki/index.php?title=Main_Page Supertech Research Group at MIT], [http://www.intel.com/?en_US_01 Intel Corporation], [http://www.cs.sunysb.edu/ Department of Computer Science, State University of New York at Stony Brook], [http://math.mit.edu/~stevenj/group.html Nanostructures and Computation Group at MIT], and [http://www.fudan.edu.cn Fudan University in China].  The core team includes the following researchers: - 3) More boundary conditions, such as irregular shaped computing domain + *[http://people.csail.mit.edu/cel/ Charles E. Leiserson], project leader - '''Pochoir''' is covered by the [http://www.gnu.org/licenses/gpl.html GNU Public License version 3.0] + *[http://people.csail.mit.edu/yuantang Yuan Tang] + *[http://www.cs.utexas.edu/~shaikat/ Rezaul Alam Chowdhury] + + *[http://people.csail.mit.edu/bradley/ Bradley C. Kuszmaul] + + *[http://www.ckluk.org/ck/ Chi-Keung Luk] + + *[http://math.mit.edu/~stevenj/ Steven G. Johnson] + + ==
Current Release == + Pochoir 0.5 [http://people.csail.mit.edu/yuantang/Pochoir_v0.5.tar.bz2] is now released (Feb, 2011) + + Please send your name and affiliation to [mailto:pochoir@csail.mit.edu Pochoir Development List] to let us know that you are interested in using Pochoir, so that we can provide better technical support to all our known customers, which includes bug fix, new release notification, new feature incorporation, etc. + + '''Pochoir''' is released under the [http://www.gnu.org/licenses/gpl.html GNU Public License version 3.0]. + + ==
Documentation == + [http://people.csail.mit.edu/yuantang/pochoir_spaa11.pdf The Pochoir Stencil Compiler], Yuan Tang, Rezaul Alam Chowdhury, Bradley C. Kuszmaul, Chi-Keung Luk, and Charles E. Leiserson, to appear in 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'2011), 2011. + + [http://people.csail.mit.edu/yuantang/pochoir_hotPar11.pdf Coding Stencil Computations Using the Pochoir Stencil-Specification Language], Yuan Tang, Rezaul Alam Chowdhury, Chi-Keung Luk, Charles E. Leiserson, to appear in 3rd USENIX Workshop on Hot Topics in Parallelism (HotPar'11), 2011. + + [http://people.csail.mit.edu/yuantang/pochoir_manual.pdf Manual] + + == Acknowledgment == + + The Pochoir project is supported in part by a grant from [http://www.intel.com/?en_US_01 Intel Corporation] and in part by [http://www.nsf.gov/ NSF] Grants CCF-0937860 and CNS-1017058. ---- ---- - Copyright  ©  2010-2011 [http://people.csail.mit.edu/yuantang/ Yuan Tang] and [http://people.csail.mit.edu/cel/ Charles E. Leiserson], All Rights Reserved. +

## The Pochoir Stencil Compiler

Pochoir (pronounced "PO-shwar") is a compiler and runtime system for implementing stencil computations on multicore processors. A stencil defines the value of a grid point in a d-dimensional spatial grid at time t as a function of neighboring grid points at recent times before t. A stencil computation computes the stencil for each grid point over many time steps. Using Pochoir, a user specifies a computing kernel and boundary conditions using a simple stencil language embedded in C++. The Pochoir compiler produces cache-efficient multithreaded C++ code that can be compiled with the Intel 12.0 compiler for C++ with the Cilk multithreading extensions, which is available as part of the Intel Parallel Computer suite. The Pochoir package contains two main components: a C++ template library for debugging and testing Pochoir compliance and a domain-specific compiler written in Haskell that produces highly optimized code. (Currently, the Pochoir package has only been tested on Linux systems.)

Here is an example of a 2D heat equation coded in Pochoir:

#define mod(r,m) ((r)%(m) + ((r)<0)? (m):0)
Pochoir_Boundary_2D(heat_bv, a, t, x, y)
return a.get(t,mod(x,a.size(1)),mod(y,a.size(0)));
Pochoir_Boundary_End

int main(void) {
Pochoir_Shape_2D 2D_five_pt[] = {{1,0,0}, {0,1,0}, {0,-1,0}, {0,-1,-1}, {0,0,-1}, {0,0,1}};
Pochoir_2D heat(2D_five_pt);

Pochoir_Array_2D(double) u(X, Y);
u.Register_Boundary(heat_bv);
heat.Register_Array(u);

Pochoir_Kernel_2D(heat_fn, t, x, y)
u(t+1, x, y) = CX * (u(t, x+1, y) - 2 * u(t, x, y) + u(t, x-1, y)) + CY * (u(t, x, y+1) - 2 * u(t, x, y) + u(t, x, y-1)) + u(t, x, y);
Pochoir_Kernel_End

for (int x = 0; x < X; ++x)
for (int y = 0; y < Y; ++y)
u(0, x, y) = rand();

heat.Run(T, heat_fn);

for (int x = 0; x < X; ++x)
for (int y = 0; y < Y; ++y)
cout << u(T, x, y);

return 0;
}


Pochoir is an open-source software project hosted by Supertech group at CSAIL, MIT. You are invited to contribute in any form (documentation, translation, writing code, fixing bugs, porting to other platforms, etc.). We are particularly interested in developing a set of real-world example stencil computations.

## Performance Graphs

Comparing the number of grid points processed per second (semilogarithmic scale) for Pochoir-generated code on 12 cores versus serial- and parallel-loop implementations. In all figures, the top curve is for the Pochoir-generated code, the middle curve is for parallel loops, and the bottom curve is for serial loops. (a) A 3D wave equation with a nonperiodic boundary condition executing for 1000 time steps. (b) A 2D heat equation on a torus executing for 3200 time steps. (c) 1D pairwise sequence alignment (no time step). (d) A Lattice Boltzmann method with a nonperiodic boundary condition for 3000 time steps.

## Pochoir Team

The Pochoir project is joint research by the Supertech Research Group at MIT, Intel Corporation, Department of Computer Science, State University of New York at Stony Brook, Nanostructures and Computation Group at MIT, and Fudan University in China. The core team includes the following researchers:

## Current Release

Pochoir 0.5 [1] is now released (Feb, 2011)

Please send your name and affiliation to Pochoir Development List to let us know that you are interested in using Pochoir, so that we can provide better technical support to all our known customers, which includes bug fix, new release notification, new feature incorporation, etc.

Pochoir is released under the GNU Public License version 3.0.

## Documentation

The Pochoir Stencil Compiler, Yuan Tang, Rezaul Alam Chowdhury, Bradley C. Kuszmaul, Chi-Keung Luk, and Charles E. Leiserson, to appear in 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'2011), 2011.

Coding Stencil Computations Using the Pochoir Stencil-Specification Language, Yuan Tang, Rezaul Alam Chowdhury, Chi-Keung Luk, Charles E. Leiserson, to appear in 3rd USENIX Workshop on Hot Topics in Parallelism (HotPar'11), 2011.

## Acknowledgment

The Pochoir project is supported in part by a grant from Intel Corporation and in part by NSF Grants CCF-0937860 and CNS-1017058.