BFS算法与众核处理器的适应性研究

以图计算为代表的数据密集型应用获得越来越广泛的关注，而传统的高性能计算机处理这类应用的效率较低.面向未来高性能计算机体系结构要有效支持数据密集型计算，深入研究以广度优先搜索(breadth-first search, BFS)算法为代表的图计算的典型特征，设计实现轻量级启发式切换BFS算法，该算法通过基本搜索方式的自动切换，避免冗余内存访问，提高搜索效率；针对BFS算法的离散随机数据访问特征以及众核处理器执行机制，建立面向BFS算法的众核处理器体系结构分析模型；全面、深入研究了BFS算法在典型众核处理器上的运行特征和性能变化趋势.测试结果表明：Cache命中率、内存带宽、流水线利用效率等相关参数均处于较低水平，无法完全满足BFS算法的需求，因此需要能够支持大量离散随机访问和简单执行机制的新型众核处理器体系结构.

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.