Πρωτότυπος Αλγόριθμος Επίλυσης Του Προβλήματος Της Τοποθέτησης Σε Επαναδιαμορφούμενες Αρχιτεκτονικές Τριών Διαστάσεων Με Χρήση Αλγορίθμων Αποικιών Μυρμηγκιών

Abstract

Placement is considered one of the most arduous and time-consuming processes in physical implementation flows for reconfigurable architectures, while it highly affects the quality of derived application implementation as it has impact on the maximum operating frequency. This problem becomes more acute for three-dimensional (3-D) architectures, because the complexity of these architectures imposes additional challenges that have to be sufficiently addressed. Throughout this thesis we introduced a novel placement algorithm, targeting 3-D reconfigurable architectures, based on Ant Colony Metaheuristics. Ant colonies are distributed systems that, in spite of the simplicity of their individuals, present a highly structured social organization and as a result can accomplish complex tasks using the collective intelligence of the group. One of the most successful examples of ant based algorithms is known as Ant Colony Optimization (ACO). ACO is inspired by the foraging behavior of ants. Our proposed algorithm incorporates concepts from both $MAX-MIN$ Ant System and Ant Colony System, the two best performing algorithms of the ACO family. It exhibits numerous advantages, such as inherent parallelism, direct enforcement of legality constrains into the cost function and support of heterogeneous architectures. Experimental results validate the effectiveness of our algorithm since it achieves on average 10% reduction on the critical path delay. This results to designs with increased maximum operating frequency and reduced power consumption. Additionally our placer can achieve speedup in multi-core architectures very close to the theoretical one. This means that our proposed algorithm can take full advantage of todays multi-core CPUs, further decreasing the execution run-time.