Medusa: Simplified Graph Processing on GPUs
Medusa: Simplified Graph Processing on GPUs
复制标题
DOI：
10.1109/tpds.2013.111
复制
发表时间：
2014-06
影响因子：
5.3
通讯作者：
Jianlong Zhong;Bingsheng He
中科院分区：
文献类型：
--
作者：
Jianlong Zhong;Bingsheng He
图是许多应用中常见的数据结构，高效的图处理对于应用性能至关重要。最近，图形处理单元（GPU）已被用于加速各种图处理算法，如广度优先搜索（BFS）和最短路径算法。然而，编写正确且高效的GPU程序是困难的，由于图结构的不规则性，图处理更是难上加难。为了简化在GPU上的图处理，我们提出了一个名为美杜莎（Medusa）的编程框架，它使开发人员能够通过编写顺序的C/C++代码来利用GPU的能力。美杜莎提供了一小组用户定义的应用程序编程接口（API），并包含一个运行时系统，以便在GPU上自动并行执行这些API。我们基于GPU的架构特征开发了一系列以图为中心的优化方法以提高效率。此外，美杜莎被扩展为可在一台机器内的多个GPU上执行。我们的实验表明：1）美杜莎极大地简化了用于图处理的通用GPU计算（GPGPU）程序的实现，开发人员编写的源代码行数大幅减少；2）优化技术显著提高了运行时系统的性能，使其性能与手动调优的GPU图操作相当或更优。
Graphs are common data structures for many applications, and efficient graph processing is a must for application performance. Recently, the graphics processing unit (GPU) has been adopted to accelerate various graph processing algorithms such as BFS and shortest paths. However, it is difficult to write correct and efficient GPU programs and even more difficult for graph processing due to the irregularities of graph structures. To simplify graph processing on GPUs, we propose a programming framework called Medusa which enables developers to leverage the capabilities of GPUs by writing sequential C/C++ code. Medusa offers a small set of user-defined APIs and embraces a runtime system to automatically execute those APIs in parallel on the GPU. We develop a series of graph-centric optimizations based on the architecture features of GPUs for efficiency. Additionally, Medusa is extended to execute on multiple GPUs within a machine. Our experiments show that 1) Medusa greatly simplifies implementation of GPGPU programs for graph processing, with many fewer lines of source code written by developers and 2) the optimization techniques significantly improve the performance of the runtime system, making its performance comparable with or better than manually tuned GPU graph operations.