Algorithm mapping to reconfigurable systems and systems with multiple embedded processors

Abstract

The Traveling Salesman Problem (TSP) is probably the most-studied combinatorial optimization problem of all time. TSP applications range from logistics, and job scheduling, to computing DNA sequences, designing and testing VLSI circuits, x-ray crystallography, and many others. Many researchers, both mathematicians and computer scientists, have attacked the TSP problem for decades resulting in a plethora of heuristics that offer a broad range of tradeoffs between running time and quality of solution. These heuristics are typically classified as either tour construction procedures that gradually build a feasible tour, or tour improvement procedures that try to optimize an existing tour by performing various tour modifications. Probably the best-known such tour modification is the 2-Opt. In this thesis we attack the 2-Opt algorithm from a novel perspective and manage to uncover previously unknown fine-grain parallelism. We propose a baseline architecture that exploits this type of parallelism and demonstrate the implementation of various versions of this architecture on an FPGA as well as on a multi-threaded GPU. Our algorithm guarantees the 2-Optimality of the final resulting tour. We evaluate our implementations and find that the FPGA implementation manages to outperform Concorde, the current state-of-the-art software implementation, for small-scale TSP problems, in both speed and quality of final results. The GPU implementation is able to handle bigger-scale TSP problems and achieve similar quality of final results, but lags behind Concorde in speed.