Gluon-Async: A Bulk-Asynchronous System for Distributed and Heterogeneous Graph Analytics
Gluon-Async: A Bulk-Asynchronous System for Distributed and Heterogeneous Graph Analytics
复制标题
DOI：
10.1109/pact.2019.00010
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Roshan Dathathri;G. Gill;Loc Hoang;Vishwesh Jatala;K. Pingali;V. K. Nandivada;Hoang-Vu Dang;M. Snir-M.
中科院分区：
文献类型：
--
作者：
Roshan Dathathri;G. Gill;Loc Hoang;Vishwesh Jatala;K. Pingali;V. K. Nandivada;Hoang-Vu Dang;M. Snir-M.
用于cpu的分布式图形分析系统，如D-Galois和Gemini，以及用于gpu的分布式图形分析系统，如D-IrGL和Lux，都使用大容量同步并行（BSP）编程和执行模型。BSP允许批量通信，并使用当前消息传输层有效支持的大消息，但批量同步可能会加剧负载不平衡对性能的影响，因为直到每个主机都完成该轮才能完成一轮。异步分布式图分析系统通过允许主机以自己的速度前进来规避这个问题，但是现有的系统要么使用全局锁并发送小消息，要么发送大消息，但不支持一般的分区策略，如顶点切割。因此，它们的性能比大容量同步系统差得多。此外，它们的编程或执行模型都不能很容易地适应gpu这样的异构设备。在本文中，我们设计并实现了一个无锁、非阻塞、批量异步运行时，称为Gluon-Async，用于分布式和异构图分析。运行时支持任何分区策略并使用大容量通信。我们提出了批量异步并行（BASP）模型，该模型允许程序员通过指定所需的抽象通信来利用运行时。用该模型编写的应用程序与使用(1)D-Galois和D-IrGL编写的BSP程序进行了比较，D-Galois和D-IrGL分别是用于cpu和GPU的最先进的分布式图形分析系统（它们是批量同步的），以及(2)Lux，另一个（批量同步的）分布式GPU图形分析系统。我们的评估表明，在实际的大直径图上，使用basp风格执行编写的程序比使用D-Galois和D-IrGL编写的程序平均快1.5倍。它们的平均速度也比力士快12倍。据我们所知，Gluon-Async是第一个异步分布式GPU图形分析系统。
Distributed graph analytics systems for CPUs, like D-Galois and Gemini, and for GPUs, like D-IrGL and Lux, use a bulk-synchronous parallel (BSP) programming and execution model. BSP permits bulk-communication and uses large messages which are supported efficiently by current message transport layers, but bulk-synchronization can exacerbate the performance impact of load imbalance because a round cannot be completed until every host has completed that round. Asynchronous distributed graph analytics systems circumvent this problem by permitting hosts to make progress at their own pace, but existing systems either use global locks and send small messages or send large messages but do not support general partitioning policies such as vertex-cuts. Consequently, they perform substantially worse than bulk-synchronous systems. Moreover, none of their programming or execution models can be easily adapted for heterogeneous devices like GPUs. In this paper, we design and implement a lock-free, non-blocking, bulk-asynchronous runtime called Gluon-Async for distributed and heterogeneous graph analytics. The runtime supports any partitioning policy and uses bulk-communication. We present the bulk-asynchronous parallel (BASP) model which allows the programmer to utilize the runtime by specifying only the abstract communication required. Applications written in this model are compared with the BSP programs written using (1) D-Galois and D-IrGL, the state-of-the-art distributed graph analytics systems (which are bulk-synchronous) for CPUs and GPUs, respectively, and (2) Lux, another (bulk-synchronous) distributed GPU graph analytical system. Our evaluation shows that programs written using BASP-style execution are on average ~1.5x faster than those in D-Galois and D-IrGL on real-world large-diameter graphs at scale. They are also on average ~12x faster than Lux. To the best of our knowledge, Gluon-Async is the first asynchronous distributed GPU graph analytics system.