Accelerating Breadth First Search on GPU-BOX

The graph analysis has been applied in various fields related to big-data processing and actively researched in recent years. For processing a larger scale of graph, parallel computing with multi-GPU system is paid attention as an economical solution. Here, an efficient parallel method is proposed to solve a typical graph analysis, Breadth First Search (BFS) for multi-GPU systems. Our target system is GPU-BOX, a prototype of multi-GPU system using ExpEther which is a virtualization technology based on PCI Express and Ethernet. Although many vertices between GPUs must be exchanged to run BFS on multi-GPU system, GPU-BOX provides only small communication performance because of using Ethernet. Our parallel algorithm for BFS is designed so as to reduce the traffic between GPUs as possible. The proposed method reduced 30-40% traffic between GPUs and improved the traditional parallel method by 10%.