A DSL for graph parallel programming with vertex subsets
A DSL for graph parallel programming with vertex subsets
复制标题
用于使用顶点子集进行图并行编程的 DSL
DOI：
10.1007/s11227-019-02821-w
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Fumihisa Sadahira
中科院分区：
文献类型：
--
作者：
Kento Emoto;Fumihisa Sadahira
顶点中心（VC）计算模型已经成为一种很有前途的方法，易于并行编程和大规模并行执行的大型图形处理。一个简单的图计算可以很容易地在VC模型中实现，但有些算法不容易在VC模型中实现。后者的算法的例子是那些使用顶点子集或子图作为操作单元。这种“全局视图风格”对于程序员设计图算法是很自然的，但是VC模型要求我们以“局部视图风格”重新设计算法，重点是一个顶点。这些风格之间的差距使我们无法为有用的图形计算编写并行程序。在本文中，我们提出了一种新的DSL的图形处理，可用于编写并行程序的大型图形处理的“全局视图风格”。它被编译到VC模型中，以便它可以在各种并行计算环境中享受大规模并行性，包括Amazon EC2等商业云服务。我们在我们的DSL中展示了非平凡的例子，我们的实验结果表明，编译后的程序实现了良好的可扩展性。
The vertex-centric (VC) computation model has emerged as a promising approach for easy parallel programming and massive parallel execution for big graph processing. A simple graph computation can easily be implemented in the VC model, but some algorithms cannot easily be implemented in the VC model. Examples of the latter algorithms are those that use vertex subsets or subgraphs as a manipulation unit. Such a “global view style” is natural for programmers to design graph algorithms, but the VC model requires us to redesign algorithms in the “local view style” focusing on a vertex. The gap between these styles prevents us from writing parallel programs for useful graph computations. In this paper, we propose a novel DSL for graph processing that can be used to write parallel programs for big graph processing in the “global view style”. It is compiled into the VC model so that it can enjoy massive parallelism in various parallel computing environments including commercial cloud services like Amazon EC2. We show non-trivial examples in our DSL, and our experimental results show that the compiled program achieves good scalability.