Palovca: Describing and Executing Graph Algorithms in Haskell
Palovca: Describing and Executing Graph Algorithms in Haskell
复制标题
Palovca：用 Haskell 描述和执行图算法
DOI：
10.1007/978-3-642-27694-1_12
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Michael Lesniak
中科院分区：
文献类型：
--
作者：
Michael Lesniak
图算法在真实的世界中具有基本的应用，但是在传统语言中实现起来很麻烦，并且难以在现代多核硬件上有效地执行。批量同步并行计算模型最近已被用来定义顶点为中心的计算图。我们描述了一个嵌入式域特定的语言（使用Haskell作为底层主机语言），用于指定这样的算法，并显示了一个执行平台，允许执行他们在多核系统上并行实现。对于算法、图大小和边缘分布不同的几个基准测试，我们在16个线程中实现了从9到11的加速比。
Graph algorithms have fundamental applications in the real world but can be both cumbersome to implement in traditional languages and difficult to execute efficiently on modern multicore hardware. The Bulk Synchronous Parallel model of computation has recently been used to define vertex-centric computations on graphs. We describe an em- bedded domain specific language (using Haskell as the underlying host language) for specifying such algorithms, and show an implementation of an execution platform that allows to execute them on multicore systems in parallel. For several benchmarks varying in algorithm, graph size and edge distribution, we achieved speedups ranging from 9 up to 11 for 16 threads.