TY - EJOU
AU - Zhou, Yang
AU - He, Jinhui
AU - Yang, Hao
TI - BFS Parallel Algorithm Based on Sunway TaihuLight
T2 - Journal of New Media
PY - 2021
VL - 3
IS - 2
SN - 2579-0129
AB - 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.
KW - Sunway TaihuLight; breadth first search algorithm; parallel computing
DO - 10.32604/jnm.2021.018829