Using MIC to Accelerate a Typical Data-Intensive Application: The Breadth-first Search

Data-intensive applications draw more and more attentions in the last few years. The breadth-first search (BFS), a typical data-intensive application, is so widely used that the Graph 500 benchmark uses it to rank supercomputers´ performance. The Intel MIC (Many Integrated Core), which is designed for highly parallel computing, hasn´t been fully evaluated for data-intensive applications. In this paper, we discuss how to use MIC to accelerate the BFS. Optimizations both for native mode and for offload mode are discussed. About native mode, we propose optimizations for thread level and data-level parallelism. We exploit the thread-level parallelism by relaxing inter-thread dependence. The optimized algorithm is proved to be more scalable. Data-level parallelism is exploited by 512-bits single instruction multiple data (SIMD) instructions. The maximum speedup we further gain is up to 3.4 times. About offload mode, we present an offload algorithm. By careful task partition and communication optimizations, it can gain speedup for large graphs which can´t run natively on MIC as the limited memory size. We believe that the work is valuable for using MIC to accelerate the BFS. Meanwhile, it´s a general evaluation of the MIC for data-intensive applications.