Hardware acceleration of Scatter Search

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.