Title
A SIMD Solution for the Quadratic Assignment Problem with GPU Acceleration
Abstract
In the Quadratic Assignment Problem (QAP), n units (usually departments, machines, or electronic components) must be assigned to n locations given the distance between the locations and the flow between the units. The goal is to find the assignment that minimizes the sum of the products of distance traveled and flow between units. The QAP is a combinatorial problem difficult to solve to optimality even for problems where n is relatively small (e.g., n = 30). In this paper, we solve the QAP problem using a parallel algorithm that employs a 2-opt heuristic and leverages the compute capabilities of current GPUs. The algorithm is implemented on the Stampede cluster hosted by the Texas Advanced Computing Center (TACC) at the University of Texas at Austin and on a GPU-equipped server housed at Texas State University. We enhance our implementation by fine tuning the occupancy levels and by exploiting inter-thread data locality through improved shared memory allocation. On a series of experiments on the well-known QAPLIB data sets, our algorithm, on average, outperforms an OpenMP implementation by a factor of 16.31 and a Tabu search based GPU implementation by a factor of 58.61. Given the wide applicability of QAP, the algorithm we propose has very good potential to accelerate the discovery in scholarly research in Engineering, particularly in the fields of Operations Research and design of electronic devices.
Year
DOI
Venue
2014
10.1145/2616498.2616521
XSEDE
Keywords
Field
DocType
gpu computing,algorithms,experimentation,parallel programming,2-opt heuristic,random search,quadratic assignment problem,heuristic methods,parallel computing,performance
Random search,Heuristic,Shared memory,Quadratic assignment problem,Computer science,Parallel algorithm,Parallel computing,SIMD,General-purpose computing on graphics processing units,Tabu search
Conference
Citations 
PageRank 
References 
3
0.42
15
Authors
3
Name
Order
Citations
PageRank
Abhilash Chaparala151.12
Clara Novoa2715.34
Apan Qasem312716.34