Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/394343F6-3076-4337-B988-AFD4B156D1AD | - |
| Αναγνωριστικό | https://doi.org/10.1109/FCCM.2007.40 | - |
| Γλώσσα | en | - |
| Τίτλος | A fast FPGA-Based 2-Opt solver for small-scale euclidean traveling salesman problem | en |
| Δημιουργός | Papaefstathiou Ioannis | en |
| Δημιουργός | Παπαευσταθιου Ιωαννης | el |
| Δημιουργός | Pnevmatikatos Dionysios | en |
| Δημιουργός | Πνευματικατος Διονυσιος | el |
| Δημιουργός | Mavroidis I. | en |
| Εκδότης | Institute of Electrical and Electronics Engineers | en |
| Περίληψη | In this paper we discuss and analyze the FPGA-based implementation of an algorithm for the traveling salesman problem (TSP), and in particular of 2-Opt, one of the most famous local optimization algorithms, for Euclidean TSP instances up to a few hundred cities. We introduce the notion of "symmetrical 2-Opt moves" which allows us to uncover fine-grain parallelism when executing the specified algorithm. We propose a novel architecture that exploits this parallelism, and demonstrate its implementation in reconfigurable hardware. We evaluate our proposed architecture and its implementation on a state-of-the-art FPGA using a subset of the TSPLIB benchmark, and find that our approach exhibits better quality of final results and an average speedup of 600% when compared with the state-of-the-art software implementation. Our approach produces, to the best of our knowledge, the fastest to date TSP 2-Opt solver for small-scale Euclidean TSP instances. | en |
| Τύπος | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Τύπος | Conference Full Paper | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2015-11-15 | - |
| Ημερομηνία Δημοσίευσης | 2007 | - |
| Βιβλιογραφική Αναφορά | I. Papaefstathiou, D. Pnevmatikatos, I. Mavroidis, "A Fast FPGA-Based 2-Opt Solver for Small-Scale Euclidean Traveling Salesman Problem," in 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2007, pp. 13 - 22. doi: 10.1109/FCCM.2007.40 | en |
Copyright © DIAS 2013
