high performance computing on graphics processing units: hgpu.org

Two well-known bipartite graph matching algorithms, the Gale-Shapley algorithm and the Hungarian (Kuhn-Munkres) algorithm, has been ported to run on General-Purpose Graphics Processing Units (GPGPU) using kernels written with the CUDA programming model. This was done with the goal of characterising and assessing the performance and behaviour of these matching algorithms on the GPU, and to determine which aspects (if any) of the GPU architecture caused difficulties. These algorithms were successfully examined using INDY, a HPC cluster which contained two NVIDIA Tesla K20 GPUs. For the Gale-Shapley algorithm, the CUDA implementation achieved was categorically slower. The Hungarian algorithm kernel was able to provide a performance speedup at larger-sized randomly-generated cost matrices, but was elsewhere slower. Significant impediments to performance included low memory throughput, warp divergence, and memory capacity issues. While several suggestions have been made to improve performance of both these algorithms on the GPU, it is likely that these algorithms will have to undergo a fundamental refactoring to become more suitable towards GPUs.