Scalable b-Matching on GPUs
Md. Naim, Fredrik Manne · 2018
We present a new greedy b-MATCHING algorithm suitable for running on a GPU. Our algorithm differs from previous efforts at designing parallel algorithms for this problem in that it does not use software locks and that it also exploits substantially more of the available concurrency. We achieve this by allowing the same vertex to concurrently match with several other vertices and also by letting multiple vertices simultaneously match with the same target vertex. We have compared our algorithm using a Pascal P100 GPU with the previous best shared memory algorithm for this problem both when running on a 16 core Xeon E5 and on a Xeon Phi. On average our algorithm outperforms the Xeon E5 by a factor of 4.6 and the Xeon Phi by a factor of 2.3. We also show that our algorithm using an NVIDIA DGX-1 multi-GPU system is highly competitive compared to a distributed memory implementation running on one of the top ten computers from the current TOP500 list.