Application Specific Computers for Combinatorial Optimisation

David Abramson, Paul Logothetis, Adam Postula, Marcus Randall

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of Computer Architecture
PublisherSpringer
Pages29-43
Publication statusPublished - 1997
Externally publishedYes

Fingerprint

Combinatorial optimization
Traveling salesman problem
Computer workstations
Simulated annealing
Data storage equipment

Cite this

Abramson, D., Logothetis, P., Postula, A., & Randall, M. (1997). Application Specific Computers for Combinatorial Optimisation. In Proceedings of Computer Architecture (pp. 29-43). Springer.
Abramson, David ; Logothetis, Paul ; Postula, Adam ; Randall, Marcus. / Application Specific Computers for Combinatorial Optimisation. Proceedings of Computer Architecture. Springer, 1997. pp. 29-43
@inproceedings{86cd1bc46b7d4204b760bbdf814fb78c,
title = "Application Specific Computers for Combinatorial Optimisation",
abstract = "Solving large combinatorial optimisation problems is often timeconsuming, and thus there is interest in accelerating current algorithms bybuilding application specific computers. This paper focuses on acceleratinggeneral local search meta-heuristics, such as simulated annealing and tabusearch, and presents an architecture for this class of algorithms. As a designcase study we describe a specific machine which implements a simulatedannealing 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 37times over an IBM RS6000 workstation. The paper highlights the use ofreconfigurable memory as a key for obtaining high performance.",
author = "David Abramson and Paul Logothetis and Adam Postula and Marcus Randall",
year = "1997",
language = "English",
pages = "29--43",
booktitle = "Proceedings of Computer Architecture",
publisher = "Springer",
address = "Germany",

}

Abramson, D, Logothetis, P, Postula, A & Randall, M 1997, Application Specific Computers for Combinatorial Optimisation. in Proceedings of Computer Architecture. Springer, pp. 29-43.

Application Specific Computers for Combinatorial Optimisation. / Abramson, David; Logothetis, Paul; Postula, Adam; Randall, Marcus.

Proceedings of Computer Architecture. Springer, 1997. p. 29-43.

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - Application Specific Computers for Combinatorial Optimisation

AU - Abramson, David

AU - Logothetis, Paul

AU - Postula, Adam

AU - Randall, Marcus

PY - 1997

Y1 - 1997

N2 - Solving large combinatorial optimisation problems is often timeconsuming, and thus there is interest in accelerating current algorithms bybuilding application specific computers. This paper focuses on acceleratinggeneral local search meta-heuristics, such as simulated annealing and tabusearch, and presents an architecture for this class of algorithms. As a designcase study we describe a specific machine which implements a simulatedannealing 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 37times over an IBM RS6000 workstation. The paper highlights the use ofreconfigurable memory as a key for obtaining high performance.

AB - Solving large combinatorial optimisation problems is often timeconsuming, and thus there is interest in accelerating current algorithms bybuilding application specific computers. This paper focuses on acceleratinggeneral local search meta-heuristics, such as simulated annealing and tabusearch, and presents an architecture for this class of algorithms. As a designcase study we describe a specific machine which implements a simulatedannealing 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 37times over an IBM RS6000 workstation. The paper highlights the use ofreconfigurable memory as a key for obtaining high performance.

M3 - Conference contribution

SP - 29

EP - 43

BT - Proceedings of Computer Architecture

PB - Springer

ER -

Abramson D, Logothetis P, Postula A, Randall M. Application Specific Computers for Combinatorial Optimisation. In Proceedings of Computer Architecture. Springer. 1997. p. 29-43