Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/04C248C6-A018-4AA5-949F-7D96D82278EF | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.67171 | - |
| Γλώσσα | en | - |
| Μέγεθος | 119 pages | en |
| Τίτλος | Design and implementation of the OPT-2 algorithm in recent technology FPGA logic | en |
| Τίτλος | Σχεδίαση και υλοποίηση αλγορίθμων OPT-2 σε νέας γενιάς αναδιατασσόμενη λογική | el |
| Δημιουργός | Malandrakis-Miller Georgios | en |
| Δημιουργός | Μαλανδρακης-Μιλλερ Γεωργιος | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Dollas Apostolos | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Δολλας Αποστολος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Papaefstathiou Ioannis | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Παπαευσταθιου Ιωαννης | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Pnevmatikatos Dionysios | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Πνευματικατος Διονυσιος | el |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Εκδότης | Technical University of Crete | en |
| Ακαδημαϊκή Μονάδα | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περίληψη | 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 |
| Τύπος | Διπλωματική Εργασία | el |
| Τύπος | Diploma Work | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by-nc-sa/4.0/ | en |
| Ημερομηνία | 2016-12-16 | - |
| Ημερομηνία Δημοσίευσης | 2016 | - |
| Θεματική Κατηγορία | Field programmable gate array | en |
| Θεματική Κατηγορία | FPGA | en |
| Θεματική Κατηγορία | TSP | en |
| Θεματική Κατηγορία | Traveling salesman problem | en |
| Θεματική Κατηγορία | 2-OPT | en |
| Θεματική Κατηγορία | Συνδυαστική βελτιστοποίηση | el |
| Θεματική Κατηγορία | Combinatorial optimization | en |
| Θεματική Κατηγορία | High level synthesis | en |
| Θεματική Κατηγορία | HLS | en |
| Θεματική Κατηγορία | Hardware description language | en |
| Θεματική Κατηγορία | HDL | en |
| Θεματική Κατηγορία | Αναδιατασσόμενη λογική | el |
| Βιβλιογραφική Αναφορά | 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 |
| Βιβλιογραφική Αναφορά | Γεώργιος Μαλανδράκης-Μίλλερ, "Σχεδίαση και υλοποίηση αλγορίθμων OPT-2 σε νέας γενιάς αναδιατασσόμενη λογική", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2016 | el |
Copyright © DIAS 2013
