Application Specific Computers For Combinatorial Optimisation

Publication
Abramson, D, Logothetis, P., Randall, M and Postula, A. "Application Specific Computers for Combinatorial Optimisation", The Australian Computer Architecture Workshop, Sydney, Feb 1997, Springer-Verlag Singapore Pty. Ltd., Singapore, pp 29 - 43.
Abstract
Solving large combinatorial optimisation problems is often time consuming, and thus there is interest in accelerating current algorithms by building application specific computers. This paper focuses on accelerating general local search meta-heuristics, such as simulated annealing and tabu search, and presents an architecture for this class of algorithms. As a design case study we descrive a specific machine which implements a simulated annealing based algorithm for solving the Travelling Salesman Problem (TSP). This processor which is built with XILINX field programmable logic and APTIX interconnection matrices achieves a speedup of about 37 times over an IBM RS6000 workstation. The paper highlights the use of reconfigurable memory as a key for obtaining high performance.
Download
appspec_comb.pdf