8060

A GPU implementation of the Simulated Annealing Heuristic for the Quadratic Assignment Problem

Gerald Paul
Center for Polymer Studies and Dept. of Physics, Boston University
arXiv:1208.2675v1 [cs.DC] (13 Aug 2012)

@article{2012arXiv1208.2675P,

   author={Paul, Gerald},

   title={"{A GPU implementation of the Simulated Annealing Heuristic for the Quadratic Assignment Problem}"},

   journal={ArXiv e-prints},

   archivePrefix={"arXiv"},

   eprint={1208.2675},

   primaryClass={"cs.DC"},

   keywords={Distributed, Parallel, and Cluster Computing},

   year={2012},

   month={aug}

}

Download Download (PDF)   View View   Source Source   

925

views

The quadratic assignment problem (QAP) is one of the most difficult combinatorial optimization problems. An effective heuristic for obtaining approximate solutions to the QAP is simulated annealing (SA). Here we describe an SA implementation for the QAP which runs on a graphics processing unit (GPU). GPUs are composed of low cost commodity graphics chips which in combination provide a powerful platform for general purpose parallel computing. For SA runs with large numbers of iterations, we find performance 50-100 times better than that of a recent non-parallel but very efficient implementation of SA for the QAP.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: