A Performance Comparison of a Naïve Algorithm to Solve the Party Problem using GPUs

Volume 3, Issue 2 (December 2012), pp. 41–48

Download PDF

@article{jocse-3-2-6,
  author={Michael V.E. Bryant and David Toth},
  title={A Performance Comparison of a Na\"{i}ve Algorithm to Solve the Party Problem using GPUs},
  journal={The Journal of Computational Science Education},
  year=2012,
  month=dec,
  volume=3,
  issue=2,
  pages={41--48},
  doi={https://doi.org/10.22369/issn.2153-4136/3/2/6}
}

The R(m, n) instance of the party problem asks how many people must attend a party to guarantee that at the party, there is a group of m people who all know each other or a group of n people who are all complete strangers. GPUs have been shown to significantly decrease the running time of some mathematical and scientific applications that have embarrassingly parallel portions. A brute force algorithm to solve the R(5, 5) instance of the party problem can be parallelized to run on a number of processing cores many orders of magnitude greater than the number of cores in the fastest supercomputer today. Therefore, we believed that this currently unsolved problem is so computationally intensive that GPUs could significantly reduce the time needed to solve it. In this work, we compare the running time of a naive algorithm to help make progress solving the R(5, 5) instance of the party problem on a CPU and on five different GPUs ranging from low-end consumer GPUs to a high-end GPU. Using just the GPUs computational capabilities, we observed speedups ranging from 1.9 to over 21 in comparison to our quad-core CPU system.