A Dual-Buffer Based Acceleration Strategy for FW Block Algorithm on GPUS

The Floyd-warshall (FW) algorithm is a classical algorithm for finding the shortest path of the directed graph. Its main idea is to find the shortest distance between every two vertices according to the weight matrix of the graph. In the largescale simulation application, the FW algorithm requires the use of a GPU to speed up the computation. The existing FW transplantation method uses shared memory for block optimization, which can achieve a better speedup than simple parallelization on GPU does. However, there is still an instruction pipeline cut off problem. This paper proposes an optimization strategy based on dual-buffer for accelerating FW block algorithm on GPU. The strategy uses dual buffer, and inserts the instruction of accessing a buffer into the computationally intensive portion of the thread. The other buffer is located to hide the delay caused by the data access, effectively reducing the instruction pipeline cut off time. Experiments show that the optimization strategy based on the dual buffer can achieve 10% to 20% acceleration on FW block algorithm when GPU computing capacity is greater than 2.0.