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

Ilias Garnier, Frédéric Gava

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Pages (from-to)251-273
Number of pages23
JournalInternational Journal of Parallel, Emergent and Distributed Systems
Volume26
Issue number4
DOIs
Publication statusPublished - 30 Mar 2011

Fingerprint

Dive into the research topics of 'CPS implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons'. Together they form a unique fingerprint.

Cite this