Dynamic Load Balancing Strategies for Graph Applications on GPUs
Dynamic Load Balancing Strategies for Graph Applications on GPUs
复制标题
GPU 上图形应用程序的动态负载平衡策略
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Pingali
中科院分区：
文献类型：
--
作者：
Ananya Raval;R. Nasre;Vivek Kumar;R. Vasudevan;Sathish S. Vadhiyar;K. Pingali
GPU上图应用程序的加速度由于在各个域中无处不在使用图形处理，因此发现了很大的兴趣。图形应用程序中的固有{不规则性}导致并行化的几个挑战。我们在本文中解决的一个主要挑战是负载不平衡。如果对线程的工作分配使用基于节点的图形分区，则可能导致任务分布偏斜，从而导致负载较差。相反，如果工作分配使用基于边缘的图形分区，则负载平衡效果更好，但是内存要求相对较高。这使其不适合大图。在这项工作中，我们提出了三种技术，以改善GPU上图应用程序的负载平衡。每种技术都具有独特的优势，用户可能必须根据要求采用特定技术。使用广度的第一次搜索和单一源最短路径作为我们的处理内核，我们说明了与现有基于节点和基于边缘的机制相比，每种提出的技术的有效性。
Acceleration of graph applications on GPUs has found large interest due to the ubiquitous use of graph processing in various domains. The inherent extit{irregularity} in graph applications leads to several challenges for parallelization. A key challenge, which we address in this paper, is that of load-imbalance. If the work-assignment to threads uses node-based graph partitioning, it can result in skewed task-distribution, leading to poor load-balance. In contrast, if the work-assignment uses edge-based graph partitioning, the load-balancing is better, but the memory requirement is relatively higher. This makes it unsuitable for large graphs. In this work, we propose three techniques for improved load-balancing of graph applications on GPUs. Each technique brings in unique advantages, and a user may have to employ a specific technique based on the requirement. Using Breadth First Search and Single Source Shortest Paths as our processing kernels, we illustrate the effectiveness of each of the proposed techniques in comparison to the existing node-based and edge-based mechanisms.