Exploiting Parallelism and Vectorisation in Breadth-First Search for the Intel Xeon Phi

被引:2
作者
Paredes, Mireya [1 ]
Riley, Graham [1 ]
Lujan, Mikel [1 ]
机构
[1] Univ Manchester, Sch Comp Sci, Kilburn Bldg,Oxford Rd, Manchester M13 9PL, Lancs, England
基金
英国工程与自然科学研究理事会;
关键词
Breadth-first search; graph algorithms; hybrid BFS; vectorisation; parallel architecture; Graph; 500; Xeon Phi;
D O I
10.1109/TPDS.2019.2927451
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Modern applications generate massive amounts of data that is challenging to process or analyse. Graph algorithms have emerged as a solution for the analysis of such data because they can represent the entities participating in the generation of large-scale datasets in terms of vertices and their relationships in terms of edges. Graph analysis algorithms are used for finding patterns within these relationships, aiming to extract information to be further analysed. The breadth-first search (BFS) is one of the main graph search algorithms used for graph analysis and its optimisation has been widely researched using different parallel computers. However, the parallelisation of BFS has been shown to be challenging because of its inherent characteristics, including irregular memory access patterns, data dependencies and workload imbalance, that limit its scalability. This paper investigates the optimisation of the BFS on the Xeon Phi (Knights Corner), a modern parallel architecture provided with an advanced vector processor supporting the AVX-512 instruction set, using a bespoke development framework integrated with the Graph 500 benchmark. In addition, to demonstrate portability, we show results for a direct port of the algorithms to a more recent version of the Xeon Phi (Knights Landing) and to a Skylake CPU which supports most of the AVX-512 instruction set. Optimised parallel versions of two high-level algorithms for BFS were created using vectorisation, starting with the conventional top-down BFS algorithm and, building on this, a hybrid BFS algorithm. On the KNC our best implementations result in speedups of 1.37x (top-down) and 1.37x (hybrid), for a one million vertices graph, compared to the state-of-the-art. On the KNL and Skylake, the performance is higher than on KNC. In addition, we show results of our best hybrid algorithm on real-world graphs from the SNAP datasets with speedups up to 1.3x on KNC. Performance on KNL and Skylake is again higher, demonstrating the robustness and portability of our algorithm. The hybrid BFS algorithm can be further used to speed up other graph analysis algorithms and the lessons learned from vectorisation can be applied to other algorithms targeting existing and future models of the Xeon Phi and other advanced vector architectures.
引用
收藏
页码:111 / 128
页数:18
相关论文
共 50 条
[41]   A fewest-turn-and-shortest path algorithm based on breadth-first search [J].
Zhou, Yan ;
Wang, Weisheng ;
He, Di ;
Wang, Zhe .
GEO-SPATIAL INFORMATION SCIENCE, 2014, 17 (04) :201-207
[42]   Heuristic algorithms for reliability estimation based on breadth-first search of a grid tree [J].
Chen, Xuyong ;
Xu, Zhifeng ;
Wu, Yushun ;
Wu, Qiaoyun .
RELIABILITY ENGINEERING & SYSTEM SAFETY, 2023, 232
[43]   Breadth-first search oriented symbolic picture representation for spatial match retrieval [J].
Lee, CF ;
Chang, CC .
JOURNAL OF SYSTEMS AND SOFTWARE, 2000, 52 (01) :11-23
[44]   BREADTH-FIRST SEARCH APPROACH TO ENUMERATION OF TREE-LIKE CHEMICAL COMPOUNDS [J].
Zhao, Yang ;
Hayashida, Morihiro ;
Jindalertudomdee, Jira ;
Nagamochi, Hiroshi ;
Akutsu, Tatsuya .
JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, 2013, 11 (06)
[45]   Fast and Scalable NUMA-based Thread Parallel Breadth-first Search [J].
Yasui, Yuichiro ;
Fujisawa, Katsuki .
PROCEEDINGS OF THE 2015 INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING & SIMULATION (HPCS 2015), 2015, :377-385
[46]   An OpenMP-based breadth-first search implementation using the bag data structure [J].
de Oliveira, S. L. Gonzaga ;
Santana, M. I. ;
Brandao, D. N. ;
Osthoff, C. .
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2024, 36 (16)
[47]   Comparative Study of Complexities of Breadth-First Search and Depth-First Search Algorithms using Software Complexity Measures [J].
Akanmu, T. A. ;
Olabiyisi, S. O. ;
Omidiora, E. O. ;
Oyeleye, C. A. ;
Mabayoje, M. A. ;
Babatunde, A. O. .
WORLD CONGRESS ON ENGINEERING, WCE 2010, VOL I, 2010, :203-208
[48]   Direction-Optimizing Breadth-First Search on CPU-GPU heterogeneous platforms [J].
Zou, Dan ;
Dou, Yong ;
Wang, Qiang ;
Xu, Jinbo ;
Li, Baofeng .
2013 IEEE 15TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS & 2013 IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND UBIQUITOUS COMPUTING (HPCC_EUC), 2013, :1064-1069
[49]   Optimizing Breadth-First Search at Scale Using Hardware-Accelerated Space Consistency [J].
Ibrahim, Khaled Z. .
2019 IEEE 26TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING, DATA, AND ANALYTICS (HIPC), 2019, :23-33
[50]   A New Chaotic Image Encryption Scheme Using Breadth-First Search and Dynamic Diffusion [J].
Yin, Qi ;
Wang, Chunhua .
INTERNATIONAL JOURNAL OF BIFURCATION AND CHAOS, 2018, 28 (04)