SIMD-X: Programming and Processing of Graph Algorithms on GPUs
SIMD-X: Programming and Processing of Graph Algorithms on GPUs
复制标题
DOI：
--
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Hang Liu;Howie Huang
中科院分区：
文献类型：
--
作者：
Hang Liu;Howie Huang
图形处理单元（GPU）具有高计算能力和内存带宽，可加速数据密集型分析，尤其是当此类应用程序适合单指令多数据（SIMD）模型时。然而，由于内存访问和控制流的不规则性，诸如宽度优先搜索和k核之类的图形算法通常无法充分利用GPU。为了应对这一挑战，我们开发了SIMD-X，用于在GPU上编程和处理单指令多个复杂数据。具体来说，新的主动计算联合收割机（ACC）模型不仅为程序员提供了编程的便利，更重要的是为系统级优化创造了机会。为此，SIMD-X利用即时任务管理，在运行时过滤掉不活动的顶点，并智能地将各种任务映射到不同数量的GPU核心，以追求工作负载平衡。此外，SIMD-X利用基于推拉的内核融合，在新的无死锁全局屏障的帮助下，将大量的计算内核减少到非常少。使用SIMD-X，用户可以在数十行代码中编写图形算法，同时实现3？，六个？二十四？三个？Gunrock，Galois，CuSha和Ligra的加速。
With high computation power and memory bandwidth, graphics processing units (GPUs) lend themselves to accelerate data-intensive analytics, especially when such applications fit the single instruction multiple data (SIMD) model. However, graph algorithms such as breadth-first search and k-core, often fail to take full advantage of GPUs, due to irregularity in memory access and control flow. To address this challenge, we have developed SIMD-X, for programming and processing of single instruction multiple, complex, data on GPUs. Specifically, the new Active-Compute-Combine (ACC) model not only provides ease of programming to programmers, but more importantly creates opportunities for system-level optimizations. To this end, SIMD-X utilizes just-in-time task management which filters out inactive vertices at runtime and intelligently maps various tasks to different amount of GPU cores in pursuit of workload balancing. In addition, SIMD-X leverages push-pull based kernel fusion that, with the help of a new deadlock-free global barrier, reduces a large number of computation kernels to very few. Using SIMD-X, a user can program a graph algorithm in tens of lines of code, while achieving 3?, 6?, 24?, 3? speedup over Gunrock, Galois, CuSha, and Ligra, respectively.