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 describe 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.
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 describe 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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of Computer Architecture |
| Publisher | Springer |
| Pages | 29-43 |
| Publication status | Published - 1997 |
| Externally published | Yes |