Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

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

Malandrakis-Miller Georgios

Full record

---

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.

Available Files

Services