Title :
Blocked All-Pairs Shortest Paths Algorithm for Hybrid CPU-GPU System
Author :
Matsumoto, Kazuya ; Nakasato, Naohito ; Sedukhin, Stanislav G.
Author_Institution :
Grad. Sch. of Comput. Sci. & Eng., Univ. of Aizu, Wakamatsu, Japan
Abstract :
This paper presents a blocked algorithm for the all-pairs shortest paths (APSP) problem for a hybrid CPU-GPU system. In the blocked APSP algorithm, the amount of data communication between CPU (host) memory and GPU memory is minimized. When a problem size (the number of vertices in a graph) is large enough compared with a blocking factor, the blocked algorithm virtually requires CPU⇋GPU exchanging of two block matrices for a block computation on the GPU. We also estimate a required memory/communication bandwidth to utilize the GPU efficiently. On a system containing an Intel West mere CPU (Core i7 970) and an AMD Cypress GPU (Radeon HD 5870), our implementation of the blocked APSP algorithm achieves the performance up to 1 TFlop/s in single precision.
Keywords :
coprocessors; graph theory; CPU memory; GPU memory; block computation; block matrices; blocked all-pairs shortest paths algorithm; data communication; hybrid CPU-GPU system; Algorithm design and analysis; Bandwidth; Graphics processing unit; Kernel; Memory management; Partitioning algorithms; Tiles; Floyd-Warshall algorithm; all-pairs shortest paths problem; blocked algorithm; data communication bandwidth; hybrid CPU-GPU system; matrix multiplication;
Conference_Titel :
High Performance Computing and Communications (HPCC), 2011 IEEE 13th International Conference on
Conference_Location :
Banff, AB
Print_ISBN :
978-1-4577-1564-8
Electronic_ISBN :
978-0-7695-4538-7
DOI :
10.1109/HPCC.2011.28
