Συντάχθηκε 19-12-2011 14:16
από Galateia Malandraki
Email συντάκτη: gmalandraki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος ΑΡΜΗΧ.
Παρουσίαση Διδακτορικής Διατριβής
Παρασκευή 23 Δεκεμβρίου 2011, 11:00πμ
Αίθουσα Συνεδριάσεων
Τμήμα ΗΜΜΥ
Απεικόνιση Αλγορίθμων σε Αναδιατασσόμενα Συστήματα και Συστήματα με Πολλούς Ενσωματωμένους Επεξεργαστές
Algorithm Mapping to Reconfigurable Systems and
Systems with Multiple Embedded Processors
Ιωάννης Μαυροειδής
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.
Εξεταστική Επιτροπή
Καθ. Διονύσιος Πνευματικάτος, Επιβλέπων
Καθ. Απόστολος Δόλλας, Μέλος Τριμελούς Επιτροπής
Καθ. Κω/νος Καλαϊτζάκης
Διδάσκων ΠΔ407/80 Ευτύχιος Κουτρούλης
Αν. Καθ. Νικόλαος Μπέλλας, Παν/μιο Θεσσαλίας
Μον. Επ. Καθ. Ιωάννης Παπαευσταθίου, Μέλος Τριμελούς Επιτροπής
Μον. Επ. Καθ. Δημήτριος Σούντρης, ΕΜΠ
Συνημμένα:
-
Παρουσίαση Διδακτορικής Διατριβής.docx
Μεταφορτώσεις: 329,
Μέγεθος: 13 KB application/vnd.openxmlformats-officedocument.wordprocessingml.document
