Ypnos: Declarative, Parallel Structured Grid Programming
A fully automatic, compiler-driven approach to parallelisation can
result in unpredictable time and space costs for compiled code.
On the other hand, a fully manual approach to
parallelisation can be long, tedious, prone to errors, hard to debug,
and often architecture-specific.
We present a declarative domain-specific language, Ypnos, for expressing
structured grid computations which encourages manual specification of
causally sequential operations but then allows a simple, predictable,
static analysis to generate optimised, parallel implementations.
We introduce the language and provide some discussion on the
theoretical aspects of the language semantics, particularly the structuring
of computations around the category theoretic notion of a comonad.
- For DAMP'10 © ACM, with minor revisions (see below)
Errors and corrections made to the revised version are listed below:
- Section 5, "Solving the Laplace Equation": laplace (X*Y):... instead of laplace @(X*Y):
- Section 5, "Conway's Game of Life Example":
- life (X*Y):... instead of life @(X*Y):
- blankGrid = (replicate 10 (replicate 10 0.0)) removed
- initalState = grid <X=10, Y=10> randomConfiguration instead of initalState = grid <X=10, Y=10> blankGrid
- Added initialState' = (defaults 0.0 initialState)
- Section 7.1 (end), the definition of coKleisli composition should be
(g . (cobind f)) not g (cobind f)
- Section 7.2, shiftLeft and shiftRight have type
"D' -> Grid D a -> Grid D a" not "D -> Grid D a -> Grid D
a". Similarly in Section 7.2.1
- Section 10, typo "gird" -> "grid"