Parallelization of the Knapsack Problem as an Introductory Experience in Parallel Computing

Volume 4, Issue 1 (October 2013), pp. 35–39

Download PDF

@article{jocse-4-1-6,
  author={Michael Crawford and David Toth},
  title={Parallelization of the Knapsack Problem as an Introductory Experience in Parallel Computing},
  journal={The Journal of Computational Science Education},
  year=2013,
  month=oct,
  volume=4,
  issue=1,
  pages={35--39},
  doi={https://doi.org/10.22369/issn.2153-4136/4/1/6}
}

As part of a parallel computing course where undergraduate students learned parallel computing techniques and got to run their programs on a supercomputer, one student designed and implemented a sequential algorithm and two versions of a parallel algorithm to solve the knapsack problem. Performance tests of the programs were conducted on the Ranger supercomputer. The performance of the sequential and parallel implementations was compared to determine speedup and efficiency. We observed 82%-86% efficiency for the MPI version and 89% efficiency for the OpenMP version for sufficiently large inputs to the problem. Additionally, we discuss both the student and faculty member's reflections about the experience.