Breadth First Search on Cost-efficient Multi-GPU Systems
Takuji Mitsuishi, Jun Suzuki, Yuki Hayashi, Masaki Kan, Hideharu Amano · ACM SIGARCH Computer Architecture News · 2016
A parallel Breadth First Search (BFS) algorithm is proposed for cost-efficient multi-GPU systems without enough memory amount or communication performance. By using an improved data structure for the duplication elimination of local nodes, both required memory amount and processing time are reduced. By using Unified Virtual Addressing, time for communication can be hidden with the computation. The proposed algorithm is implemented on two costefficient multi-GPU systems: Express multi-GPU system which has a full of flexibility but the communication latency between GPU and host is limited, and a high-end gaming machine whose memory is limited. Both systems achieve good strong scaling with the proposed methods. On Express multi-GPU system, the communication overhead was almost completely hidden, and the aggregate communication throughput reached 4.77 GB/sec (38.16 Gbps), almost theoretical maximum.