Exploiting Parallelism in Iterative Irregular Maxflow Computations on GPU Accelerators
Exploiting Parallelism in Iterative Irregular Maxflow Computations on GPU Accelerators
复制标题
在 GPU 加速器上迭代不规则 Maxflow 计算中利用并行性
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
R. Thulasiram
中科院分区：
文献类型：
--
作者：
Steven Solomon;P. Thulasiraman;R. Thulasiram
图形处理单元（GPU）是一种非对称、异构的多核架构，可用于高性能并行计算应用。然而，人们的兴趣主要集中在解决常规问题的算法上，因为这些应用程序通常很好地映射到GPU上。依赖于指针或基于图形的数据结构的不规则应用程序尚未得到广泛研究，并且在GPU上以有效的方式实现或映射显着更困难。在本文中，我们考虑一个基于图的最大值？？该算法在网络优化问题中有应用。在文献中，推标签最大值？？如何算法已经考虑在GPU上。我们相信Malhotra， Pramodh Kumar和Maheshwari的算法更适合GPU，因为该算法具有同步，迭代的特性。因此，我们选择这个算法作为我们的研究。我们证明了GPU算法的性能远远超过顺序CPU算法。
The Graphics Processing Unit (GPU) is an asymmetric, heterogeneous multi-core architecture that can be used for high performance parallel computing applications. However, a significant level of interest has been focused on algorithms for solving regular problems, as these applications typically map well to the GPU. Irregular applications, which rely on pointer or graph-based data structures, have not been as extensively studied and are significantly more difficult to implement or map in an efficient fashion on the GPU. In this paper, we consider a graph-based maximum ???ow algorithm that has applications in network optimization problems. In the literature, the push-relabel maximum ???ow algorithm has been considered on the GPU. We believe that Malhotra, Pramodh Kumar and Maheshwari’s algorithm is better suited for the GPU due to the synchronous, iterative nature of the algorithm. As a result, we choose this algorithm for our study. We show that the performance of the GPU algorithm far exceeds that of a sequential CPU algorithm.