High-performance multi-GPU concurrent queues: Case study with parallel Bellman-Ford SSSP

This thesis presents a novel implementation of a concurrent FIFO queue algorithm for both single-GPU and multi-GPU environments, applied to the Single-Source Shortest Path (SSSP) Bellman-Ford algorithm. The primary contribution of this work is the design and implementation of a multi-GPU concurrent queue system using NVIDIA's NVSHMEM, which has not been previously explored. The Bellman-Ford algorithm is used as a case study to evaluate the performance of the proposed queue system, with this multi-GPU implementation being the first known instance of its kind. Experimental results demonstrate that the multi-GPU queue implementation achieves a maximum speedup of 3.92x and an average speedup of 3.04x over the single-GPU baseline on four NVIDIA A100 GPUs. When applied to the Bellman-Ford algorithm, the multi-GPU system achieves a maximum speedup of 3.794× and an average speedup of 3.573× compared to the single-GPU implementation, tested on a generated benchmark and 10 graphs of different kinds taken from the SuiteSparse Matrix Collection. These findings highlight the efficiency of the multi-GPU queue system for graph processing tasks and contribute to advancements in high-performance computing by addressing practical challenges in parallel computing.