期刊论文

中文

计算机科学

1002-137X

2015

42

1

82-85

10.11896/j.issn.1002-137X.2015.1.019

61370095:国家自然科学基金 61370098:国家自然科学基金 61070057:国家自然科学基金 90715029:国家自然科学基金 13C074:湖南省教育厅科学研究项目 2011KJ22:衡阳市科技局科技发展计划

本校为第一机构

深度优先搜索算法在GPU集群中大型图上的简单执行,会导致线程间的负载不平衡和无法合并内存访问的情况,这使得算法的性能较低。为了明显提高算法在单个GPU和多个GPU环境下的性能,在处理数据之前通过采取一系列有效的操作来进行重新编排。提出了构造线程和数据之间映射的新技术,通过利用前缀求和及二分查找操作来达到完美的负载平衡。为了降低通信开销,对DFS各分支中需要进行交换的边集执行修剪操作。实验结果表明,算法在单个GPU上可以尽可能地实现最佳的并行性,在多GPU环境下可以最小化通信开销。在一个GPU集群中,它可以对含有数十亿节点的图有效地执行分布式DFS。

Straightforward implementation of depth first search algorithm for large graph on GPU cluster,may lead to load imbalance between threads and un-coalesced memory accesses,giving rise to the low performance of the algorithm.In order to achieve improvement of the performance in a single GPU and multi-GPUs environment,a series of effective operations were used to reschedule before processing the data.A novel strategy for mapping between threads and data was proposed,and by using the prefix sum and binary search operations,load balancing was achieved perfectly.In order to reduce the communication o...