Characterising Bipartite Graph Matching Algorithms on GPUs

Stanley Tsang
The University of Edinburgh
The University of Edinburgh, 2014


   title={Characterising Bipartite Graph Matching Algorithms on GPUs},

   author={Tsang, Stanley},



Download Download (PDF)   View View   Source Source   



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.
Rating: 2.7/5. From 3 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: