Back to Search
Start Over
SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration.
- Source :
- International Journal of Production Research; Feb2010, Vol. 48 Issue 4, p1035-1047, 13p, 2 Diagrams, 6 Charts
- Publication Year :
- 2010
-
Abstract
- This paper presents a single instruction multiple data tabu search (SIMD-TS) algorithm for the quadratic assignment problem (QAP) with graphics hardware acceleration. The QAP is a classical combinatorial optimisation problem that is difficult to solve optimally for even small problems with over 30 items. By using graphic hardware acceleration, the developed SIMD-TS algorithm executes 20 to 45 times faster than traditional CPU code. The computational improvement is made possible by the utilisation of the parallel computing capability of a graphics processing unit (GPU). The speed and effectiveness of this algorithm are demonstrated on QAP library problems. The main contribution of this paper is a fast and effective SIMD-TS algorithm capable of producing results for large QAPs on a desktop personal computer equivalent to the results achieved with a CPU cluster. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00207543
- Volume :
- 48
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- International Journal of Production Research
- Publication Type :
- Academic Journal
- Accession number :
- 49143854
- Full Text :
- https://doi.org/10.1080/00207540802555744