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

Frédéric Gava; Ilias Garnier

doi:10.1109/IPDPS.2009.5160876

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

Frédéric Gava, Ilias Garnier

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

BSML is a ML based language designed to code bulk synchronous parallel (BSP) algorithms. It allows an estimation of execution time, avoids deadlocks and non-determinism. BSML proposes an extension of ML programming 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 used system threads and have unjustified limitations. This paper presents a new implementation of this primitive based on a continuation-passing-style (CPS) transformation guided by a flow analysis. To test it and show its usefulness, we also have implemented the OCamlP3l algorithmic skeletons and compared their efficiencies with the original ones.

Original language	English
Title of host publication	23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	1-8
Number of pages	8
ISBN (Electronic)	978-1-4244-3750-4
ISBN (Print)	978-1-4244-3751-1
DOIs	https://doi.org/10.1109/IPDPS.2009.5160876
Publication status	Published - 2009

Access to Document

10.1109/IPDPS.2009.5160876

http://dx.doi.org/10.1109/IPDPS.2009.5160876

Cite this

Gava, F., & Garnier, I. (2009). New implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons. In 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009 (pp. 1-8). Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/IPDPS.2009.5160876

@inproceedings{31bfe299334a4afa82b95848122df259,

title = "New implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons",

abstract = "BSML is a ML based language designed to code bulk synchronous parallel (BSP) algorithms. It allows an estimation of execution time, avoids deadlocks and non-determinism. BSML proposes an extension of ML programming 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 used system threads and have unjustified limitations. This paper presents a new implementation of this primitive based on a continuation-passing-style (CPS) transformation guided by a flow analysis. To test it and show its usefulness, we also have implemented the OCamlP3l algorithmic skeletons and compared their efficiencies with the original ones.",

author = "Fr{\'e}d{\'e}ric Gava and Ilias Garnier",

year = "2009",

doi = "10.1109/IPDPS.2009.5160876",

language = "English",

isbn = "978-1-4244-3751-1 ",

pages = "1--8",

booktitle = "23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

Gava, F & Garnier, I 2009, New implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons. in 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009. Institute of Electrical and Electronics Engineers (IEEE), pp. 1-8. https://doi.org/10.1109/IPDPS.2009.5160876

New implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons. / Gava, Frédéric; Garnier, Ilias.

23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009. Institute of Electrical and Electronics Engineers (IEEE), 2009. p. 1-8.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - New implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons

AU - Gava, Frédéric

AU - Garnier, Ilias

PY - 2009

Y1 - 2009

N2 - BSML is a ML based language designed to code bulk synchronous parallel (BSP) algorithms. It allows an estimation of execution time, avoids deadlocks and non-determinism. BSML proposes an extension of ML programming 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 used system threads and have unjustified limitations. This paper presents a new implementation of this primitive based on a continuation-passing-style (CPS) transformation guided by a flow analysis. To test it and show its usefulness, we also have implemented the OCamlP3l algorithmic skeletons and compared their efficiencies with the original ones.

AB - BSML is a ML based language designed to code bulk synchronous parallel (BSP) algorithms. It allows an estimation of execution time, avoids deadlocks and non-determinism. BSML proposes an extension of ML programming 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 used system threads and have unjustified limitations. This paper presents a new implementation of this primitive based on a continuation-passing-style (CPS) transformation guided by a flow analysis. To test it and show its usefulness, we also have implemented the OCamlP3l algorithmic skeletons and compared their efficiencies with the original ones.

U2 - 10.1109/IPDPS.2009.5160876

DO - 10.1109/IPDPS.2009.5160876

M3 - Conference contribution

SN - 978-1-4244-3751-1

SP - 1

EP - 8

BT - 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

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

Abstract

Access to Document

Fingerprint

Cite this