An adaptive breadth-first search algorithm on integrated architectures
An adaptive breadth-first search algorithm on integrated architectures
复制标题
集成架构上的自适应广度优先搜索算法
DOI：
10.1007/s11227-018-2525-0
复制
发表时间：
2018-08
影响因子：
3.3
通讯作者：
Du Xiaoyong
中科院分区：
文献类型：
--
作者：
Zhang Feng;Lin Heng;Zhai Jidong;Cheng Jie;Xiang Dingyi;Li Jizhong;Chai Yunpeng;Du Xiaoyong
在大数据时代，图形应用对于数据分析变得越来越重要。广度优先搜索是最具代表性的搜索算法之一，因此，利用图形处理器（GPU）加速广度优先搜索是一个热门的研究课题。然而，由于其随机数据访问模式，很难充分利用GPU的功能。最近，硬件设计人员将CPU和GPU集成在同一芯片上，允许两个设备共享物理内存，这提供了在CPU和GPU之间切换的便利性，成本很低。BFS处理可以分为几个级别，并且在每个级别上可以使用各种遍历顺序。在不同的设备（CPU或GPU）上使用不同的遍历顺序会导致不同的性能。因此，在集成架构上使用BFS的挑战是如何为每个级别选择遍历顺序和设备。以前的工作未能有效地解决这个问题。在这项研究中，我们提出了一个自适应的性能模型，自动找到一个合适的遍历顺序和设备的每个级别。我们在Graph500上评估了我们的方法，它不仅显示了最佳的能效，而且还实现了每秒千兆遍历边缘（GTEPS）性能约为2.1 GTEPS，这是集成架构上最先进的BFS的速度改进。
In the big data era, graph applications are becoming increasingly important for data analysis. Breadth-first search (BFS) is one of the most representative algorithms; therefore, accelerating BFS using graphics processing units (GPUs) is a hot research topic. However, due to their random data access pattern, it is difficult to take full advantage of the power of GPUs. Recently, hardware designers have integrated CPUs and GPUs on the same chip, allowing both devices to share physical memory, which provides the convenience of switching between CPUs and GPUs with little cost. BFS processing can be divided into several levels, and various traversal orders can be used at each level. Using different traversal orders on different devices (CPUs or GPUs) results in diverse performances. Thus, the challenge in using BFS on integrated architectures is how to select the traversal order and the device for each level. Previous works have failed to address this problem effectively. In this study, we propose an adaptive performance model that automatically finds a suitable traversal order and device for each level. We evaluated our method on Graph500, where it not only shows the best energy efficiency but also achieves a giga-traversed edges per second (GTEPS) performance of approximately 2.1 GTEPS, which is a speed improvement over the state-of-the-art BFS on integrated architectures.
登录
查看更多内容
影响因子：
1
作者：
Brandes, U
通讯作者：
Brandes, U
DOI：
10.1109/sc.2014.69
发表时间：
2014-11
期刊：
SC14: International Conference for High Performance Computing, Networking, Storage and Analysis
影响因子：
--
作者：
Arash Ashari;N. Sedaghati;John Eisenlohr;S. Parthasarathy;P. Sadayappan
通讯作者：
Arash Ashari;N. Sedaghati;John Eisenlohr;S. Parthasarathy;P. Sadayappan
DOI：
10.1145/2588555.2610518
发表时间：
2014-06
期刊：
Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data
影响因子：
--
作者：
N. Satish;N. Sundaram;Md. Mostofa Ali Patwary;Jiwon Seo;Jongsoo Park;M. A. Hassaan;Shubho Sengupta
通讯作者：
N. Satish;N. Sundaram;Md. Mostofa Ali Patwary;Jiwon Seo;Jongsoo Park;M. A. Hassaan;Shubho Sengupta
DOI：
10.1109/ipdpsw.2018.00052
发表时间：
2011-07
期刊：
2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
影响因子：
--
作者：
J. Gilbert
通讯作者：
J. Gilbert
影响因子：
5.3
作者：
Jianlong Zhong;Bingsheng He
通讯作者：
Jianlong Zhong;Bingsheng He