| We present a hardware implementation of the population-based Scatter-Search optimization on a Field Programmable Gate Array (FPGA). Scatter-search is derived from strategies originally proposed for combining decision rules and constraints in the context of Integer-Linear Programming (ILP). In particular, scatter search is based on the belief that (i) useful information about the form (location) of optimal solutions is typically contained in a suitably diverse collection of elite solutions; and (ii) that the information in these elite solutions can be best exploited by combining multiple solutions simultaneously to extrapolate beyond the (convex and non-convex) regions spanned by the solutions considered.;We present a circuit architecture for scatter search that facilitates efficient FPGA implementations, modeled using Handel-C a synchronous programming language that has the fundamental aspect of time. Handel-C captures the digital design at the level of simple transformations on data and movement of data between variables and registers. An important aspect of our study is exploring how much speedup (over software) can be achieved through simple language-level transformations (i.e., fine-grained parallelism). We also explore how data parallelism and pipelining can be further used to improve performance. Our results show that the proposed architecture can achieve a 26x speedup over software. |
