CPS implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons

Abstract

Bulk-synchronous parallel ML (BSML) is an ML-based language designed to code bulk synchronous parallel (BSP) algorithms. It allows an estimation of execution time, and avoids deadlocks and non-determinism. BSML proposes an extension of ML programing with a small set of primitives. One of these primitives, called parallel superposition, allows the parallel composition of two BSP programs. Nevertheless, its past implementation uses system threads and has a serious drawback, which is the cost of managing threads in ML-like languages. This work presents a new implementation of this primitive based on a continuation-passing-style transformation guided by a flow analysis. To test it and show its usefulness, we also have implemented the OCamlP3L's algorithmic skeletons and compared their efficiencies with the original ones. The work presented here is tightly related to the BSP model, but is not specific to ML. Hence, we reckon there would be little work involved in translating it to, for instance, Java or Python.

Keywords:

• ML programing
• BSP model
• CPS transformation
• flow analysis
• skeletons

Notes

^1. These properties are justified for concurrent computations but clearly not for parallel algorithms.

^2. Subset synchronisation of processors is usually justified by the necessity of the recursive decomposition of the computation into independent sub-problems; Tiskin and New [43] argued that it is not really useful for BSP computing.

^3. Determinism guarantees that program behaviour is identical on all nodes; this essentially eliminates an entire class of errors: data races.

^4. We know that OCaml code cannot be interrupted, so by adding an appropriate CPS in OCaml, we do not have to introduce some (inefficient) mechanism to save the execution context.