Title :
Hardware acceleration of Scatter Search
Author :
Walton, Maxwell ; Grewal, Gary ; Darlington, Gerarda
Author_Institution :
Sch. of Comp. Sci., Univ. of Guelph, Guelph, ON, Canada
fDate :
June 28 2010-July 2 2010
Abstract :
In this paper, we share our experience implementing the well-known meta-heuristic, Scatter Search, on a Field-Programmable Gate-Array (FPGA). Our objective is to improve the runtime of scatter search by exploiting the potential performance benefits that are available through the native parallelism in hardware. When implementing scatter search we employ Handel-C - a programming language specifically designed to enable software developers to easily synthesize C-like programs into synchronous hardware. A total of 31 different Handel-C implementations, all based on different language level optimizations, are considered. A full-factorial experiment is performed to test the interactions between different combinations of language-level optimizations with respect to the performance of scatter search compared with software.
Keywords :
Clocks; Field programmable gate arrays; Hardware; Optimization; Random access memory; Runtime; Search problems; 0–1Knapsack Problem; FPGA; Hardware Acceleration; Parallelism; Scatter Search;
Conference_Titel :
High Performance Computing and Simulation (HPCS), 2010 International Conference on
Conference_Location :
Caen, France
Print_ISBN :
978-1-4244-6827-0
DOI :
10.1109/HPCS.2010.5547101
