Abstract: Graph algorithms have important application value in many fields.With the development of social informatization,the amount of graph data to be processed has become larger and larger,the performance of graph algorithms has become a research hotspot.Breadth-first search algorithm is an important graph algorithm,studying its performance optimization techniques can provide reference for the performance optimization of other graph algorithms.The current work on new generation Xeon Phi many-core processors are based on top-down algorithm and do not take into account NUMA effects on performance.Based on the hybrid breadth-first search algorithm and the NUMA topology,this paper optimized Breadth-first search algorithm from the perspective of tasks allocation,vectorization and data preprocessing,designed and implemented a high-performance parallel breadth-first search algorithm on the Xeon Phi platform.A series of experimental results show that the optimized algorithm has gained 50%~145% improvement compared with Graph500 official tuned algorithm on different scales of test data.

Key words: Breadth-first search, Many-core architecture, NUMA, Performance optimization, Vectorization