Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/04C248C6-A018-4AA5-949F-7D96D82278EF | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.67171 | - |
| Language | en | - |
| Extent | 119 pages | en |
| Title | Design and implementation of the OPT-2 algorithm in recent technology FPGA logic | en |
| Title | Σχεδίαση και υλοποίηση αλγορίθμων OPT-2 σε νέας γενιάς αναδιατασσόμενη λογική | el |
| Creator | Malandrakis-Miller Georgios | en |
| Creator | Μαλανδρακης-Μιλλερ Γεωργιος | el |
| Contributor [Thesis Supervisor] | Dollas Apostolos | en |
| Contributor [Thesis Supervisor] | Δολλας Αποστολος | el |
| Contributor [Committee Member] | Papaefstathiou Ioannis | en |
| Contributor [Committee Member] | Παπαευσταθιου Ιωαννης | el |
| Contributor [Committee Member] | Pnevmatikatos Dionysios | en |
| Contributor [Committee Member] | Πνευματικατος Διονυσιος | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content Summary | The Traveling Salesman Problem (TSP) is one of the most well-known and thoroughly studied problems within the domain of combinatorial optimization. The number of its practical, real-life applications is sheer: Manufacturing, logistics, telecommunications, statistics, scheduling, and even psychology are some of them, to name a few. Since it is an NP-Hard problem, solving it to optimality requires an exponentially-increasing time as its size grows, thus rendering its exact solution prohibitive for large datasets or when time constitutes a crucial factor. This has ultimately led to the development of an abundance of heuristics, specifically designed to address this issue, providing orders of magnitude reduced running times at the cost of sub- or near-optimal results. One of the oldest and most recognized such heuristic is 2-OPT. The aim of this thesis is the design and implementation of 2-OPT in recent technology reconfigurable logic (FPGA), through the utilization of both the newly-(re)emerged High Level Synthesis flow (HLS) and the classic HDL-based flow as well; the corresponding tools are part of the Xilinx Vivado Design Suite. Experimental results show that the implemented hardware architectures are capable of delivering speedups of up to nearly 10x (5x on average) for small to medium scale problem sizes. These speedups are obtained when comparing the performance of the aforementioned architectures against the highly optimized Concorde TSP software package running on a 3.4GHz Intel Core-i7 6700 CPU with 16GB RAM. The presented work originates from research conducted nearly a decade ago in the Microprocessor & Hardware Lab at the School of ECE, Technical University of Crete. | en |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by-nc-sa/4.0/ | en |
| Date of Item | 2016-12-16 | - |
| Date of Publication | 2016 | - |
| Subject | Field programmable gate array | en |
| Subject | FPGA | en |
| Subject | TSP | en |
| Subject | Traveling salesman problem | en |
| Subject | 2-OPT | en |
| Subject | Συνδυαστική βελτιστοποίηση | el |
| Subject | Combinatorial optimization | en |
| Subject | High level synthesis | en |
| Subject | HLS | en |
| Subject | Hardware description language | en |
| Subject | HDL | en |
| Subject | Αναδιατασσόμενη λογική | el |
| Bibliographic Citation | Georgios Malandrakis-Miller, "Design and implementation of the OPT-2 algorithm in recent technology FPGA logic", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2016 | en |
| Bibliographic Citation | Γεώργιος Μαλανδράκης-Μίλλερ, "Σχεδίαση και υλοποίηση αλγορίθμων OPT-2 σε νέας γενιάς αναδιατασσόμενη λογική", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2016 | el |
Copyright © DIAS 2013
