Relation-based computations in a monadic BSP model

We propose a Haskell monadic model of bulk synchronous parallel programs and apply it to the analysis of relation-based computations.

Relation-based computations are simple but general patterns found in scientific computing applications. They are easy to implement sequentially, but difficult to parallelize.

We use the model to give high-level specifications of distributed relation-based algorithms and outline how to obtain testable parallel implementations from these specifications via equational reasoning.

We sketch the architecture of a C++ library of components for distributed relation-based computations. We argue that the model can be used to provide a concise and consistent library documentation.

Full paper