Back to search

Technical University of Crete (TUC)

Algorithm mapping to reconfigurable systems and systems with multiple embedded processors

Abstract

dc:description

The Traveling Salesman Problem (TSP) is probably the most-studied combinatorial optimization problem of all time. TSP applications range from logistics, and job scheduling, to computing DNA sequences, designing and testing VLSI circuits, x-ray crystallography, and many others. Many researchers, both mathematicians and computer scientists, have attacked the TSP problem for decades resulting in a plethora of heuristics that offer a broad range of tradeoffs between running time and quality of solution. These heuristics are typically classified as either tour construction procedures that gradually build a feasible tour, or tour improvement procedures that try to optimize an existing tour by performing various tour modifications. Probably the best-known such tour modification is the 2-Opt. In this thesis we attack the 2-Opt algorithm from a novel perspective and manage to uncover previously unknown fine-grain parallelism. We propose a baseline architecture that exploits this type of parallelism and demonstrate the implementation of various versions of this architecture on an FPGA as well as on a multi-threaded GPU. Our algorithm guarantees the 2-Optimality of the final resulting tour. We evaluate our implementations and find that the FPGA implementation manages to outperform Concorde, the current state-of-the-art software implementation, for small-scale TSP problems, in both speed and quality of final results. The GPU implementation is able to handle bigger-scale TSP problems and achieve similar quality of final results, but lags behind Concorde in speed.

Degree

thesis:*
Grantor dc:publisher
Technical University of Crete (TUC)
Year dc:date
2011

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Mavroidis, Ioannis
  • Μαυροειδής, Ιωάννης

Subjects

dc:subject × 13

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/26343

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Mavroidis, Ioannis; Μαυροειδής, Ιωάννης. Algorithm mapping to reconfigurable systems and systems with multiple embedded processors. Technical University of Crete (TUC), 2011. http://hdl.handle.net/10442/hedi/26343