Open Access

ARTICLE

BFS Parallel Algorithm Based on Sunway TaihuLight

Yang Zhou¹, Jinhui He¹, Hao Yang^1,2,*

1 School of Computer Science, Chengdu University of Information Technology, Chengdu, 610225, China
2 School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, 610054, China

* Corresponding Author: Hao Yang. Email:

Journal of New Media 2021, 3(2), 63-72. https://doi.org/10.32604/jnm.2021.018829

Received 22 March 2021; Accepted 30 March 2021; Issue published 23 April 2021

Abstract

In recent years, more and more attention has been paid to the research and application of graph structure. As the most typical representative of graph structure algorithm, breadth first search algorithm is widely used in many fields. However, the performance of traditional serial breadth first search (BFS) algorithm is often very low in specific areas, especially in large-scale graph structure traversal. However, it is very common to deal with large-scale graph structure in scientific research. At the same time, the computing performance of supercomputer has also made great progress. China’s self-developed supercomputer system Sunway TaihuLight (SW) has won the top 500 list for three consecutive times. The huge computing performance of supercomputer is the key to solve this problem. It can be seen that if we use the computing power of supercomputing to solve the problem of large-scale graph structure traversal, the efficiency of graph structure traversal will be greatly improved. This paper expounds how to realize the breadth first search algorithm of graph structure on the Sunway TaihuLight, and achieved some results. In this way, MPI and thread library called athread of SW platform are used, and the traversal performance is improved dozens of times through the above related technologies and some partition methods of graph structure.

---

Keywords

---