New implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons
New implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons
复制标题
BSP 组合原语的新实现及其应用于算法框架实现的应用
DOI：
10.1109/ipdps.2009.5160876
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
I. Garnier
中科院分区：
文献类型：
--
作者：
F. Gava;I. Garnier
BSML是一种基于ML的语言，旨在编码批量同步并行（BSP）算法。它允许估计执行时间，避免死锁和不确定性。BSML提出了ML编程的一个扩展，使用了一小部分原语。这些原语之一，称为并行叠加，允许两个BSP程序的并行组合。然而，它过去的实现使用系统线程，并有不合理的限制。本文提出了一种新的实现这种原语的基础上继续传递式（CPS）的转换引导的流分析。为了测试它并展示它的有用性，我们还实现了OCamlP3l算法框架，并将它们的效率与原始算法进行了比较。
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.