Technical University of Crete (TUC)
Algorithm mapping to reconfigurable systems and systems with multiple embedded processors
Abstract
dc:descriptionThe 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- Πρόβλημα περιοδεύοντος πωλητή
- Υλοποίηση αλγορίθμων σε hardware
- Traveling salesman problem
- TSP
- 2-Opt
- Algorithm mapping
- Reconfigurable systems
- FPGAs
- CUDA
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/26343