Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Design and implementation of the OPT-2 algorithm in recent technology FPGA logic

Malandrakis-Miller Georgios

Simple record


URIhttp://purl.tuc.gr/dl/dias/04C248C6-A018-4AA5-949F-7D96D82278EF-
Identifierhttps://doi.org/10.26233/heallink.tuc.67171-
Languageen-
Extent119 pagesen
TitleDesign and implementation of the OPT-2 algorithm in recent technology FPGA logicen
TitleΣχεδίαση και υλοποίηση αλγορίθμων OPT-2 σε νέας γενιάς αναδιατασσόμενη λογικήel
CreatorMalandrakis-Miller Georgiosen
CreatorΜαλανδρακης-Μιλλερ Γεωργιοςel
Contributor [Thesis Supervisor]Dollas Apostolosen
Contributor [Thesis Supervisor]Δολλας Αποστολοςel
Contributor [Committee Member]Papaefstathiou Ioannisen
Contributor [Committee Member]Παπαευσταθιου Ιωαννηςel
Contributor [Committee Member]Pnevmatikatos Dionysiosen
Contributor [Committee Member]Πνευματικατος Διονυσιοςel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitTechnical University of Crete::School of Electrical and Computer Engineeringen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Content SummaryThe 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 ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by-nc-sa/4.0/en
Date of Item2016-12-16-
Date of Publication2016-
SubjectField programmable gate arrayen
SubjectFPGAen
SubjectTSPen
SubjectTraveling salesman problemen
Subject2-OPTen
SubjectΣυνδυαστική βελτιστοποίησηel
SubjectCombinatorial optimizationen
SubjectHigh level synthesisen
SubjectHLSen
SubjectHardware description languageen
SubjectHDLen
SubjectΑναδιατασσόμενη λογικήel
Bibliographic CitationGeorgios 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, 2016en
Bibliographic CitationΓεώργιος Μαλανδράκης-Μίλλερ, "Σχεδίαση και υλοποίηση αλγορίθμων OPT-2 σε νέας γενιάς αναδιατασσόμενη λογική", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2016el

Available Files

Services

Statistics