Research On Breadth First Search For Many Core Architecture

As a basic graph algorithm, breadth-first search(BFS) is a core component of many algorithms and has been widely used in many fields, such as network security, medical information, data mining, social networks, semantic web and so on. Breadth-first search algorithm is also a typical data-intensive application and the Graph 500 benchmark uses it to rank supercomputers’ performance for handling data-intensive applications.In recent years, thanks to the low power consumption and high cost performance,the accelerator with many-core architecture has been widely used in the field of high performance computing. As the latest many-core architecture coprocessor, compared with other accelerator product, MIC(Many Integreated Core) has the advantage of having the similar programming environment with the multi-core system. With the “Milky Way II”, which contains CPUs and MICs, ranking first in the Top 500 list, MIC draws wide attention in high performance computing.The parallel implementation of breadth-first search has some features, like exits data races, is irregular and has poor memory access locality. MIC has the capabilities of many threads and wide vector processing. As a result, to make full use of MIC to implement breadth-first search efficiently, we have to face problems like high data race overhead, low vector utilization and poor cache utilization. In this paper, the efficient implementation of breadth-first search on MIC is researched. The paper mainly achieves the following results:1) A top-down and bottom-up hybrid BFS algorithm is designed and implemented.According to characteristics of graphs, the algorithm uses different strategies in different search levels and can combine advantages of top-down and bottom-up methods. The performance is about 3.21 and 2.15 times compared with top-down and bottom-up method respectively.2) A optimized multi-thread BFS algorithm for MIC is proposed. Based on the hybrid algorithm, by reducing data races, eliminating atomic operations and combining the static schedule with the dynamic schedule, it can make full use of many threads processing capability.3)A further method of using wide vector component to accelerate BFS is proposed.By using SIMD to scan vertex’s neighbours simultaneously in the top-down search and seek unvisited vertexes in parallel in the bottom-up search, this method can further accelerate the BFS and the maximum speedup reaches 1.85 x.4)A heterogeneous hybrid BFS algorithm with CPU and MIC is designed and implemented. Based on the hybrid BFS algorithm, by task division with adjustable ratio and communication design with overlapping computing, it solves problems like load imbalance and high communication overhead in collaborative computing. The speedup compared with CPU reaches about 1.4x.Experimental results show that the performance of the BFS algorithm on MIC implemented in this paper is about 5.31 times compared with GPU. The maximum speedup of the heterogeneous hybrid BFS algorithm reaches 1.46 x.