Adaptability of BFS Algorithm and Many-Core Processor

Data-intensive applications represented by graph computing are getting more and more attentions, but traditional high performance computer is unable to solve the problems in the data-intensive applications efficiently. In order that future high performance computer architecture effectively support the data-intensive computing, this paper studies the features of graph algorithm represented by breadth-first search (BFS), as well as designs and implements a lightweight heuristic switch BFS algorithm. Through automatically switching between two different search methods, this algorithm avoids redundant memory accesses and improves search efficiency. Based on the discrete and random data access features of BFS algorithm and the execution mechanism of many-core processor, an analytical model of many-core processor architecture for BFS algorithm is established to the instruct the research on adaptability of BFS algorithm and many-core processor. The operating characteristics and performance trends of BFS algorithm are intensively studied on the typical many-core processors, and the results show that cache hit ratio, memory bandwidth, pipeline utilization efficiency and other related parameters are at a low level, which mean the current many-core processor architecture doesn't fully meet the demands of BFS algorithm. Therefore, new many-core processor architecture needs to be able to support a large of discrete random data accesses and a more easier execution mechanism.