Μεθοδολογίες αυτοματοποιημένης εξερεύνησης και σύνθεσης επαναδιατάξιμων συνεπεξεργαστών υλικού

Abstract

Technological advances in micro-electronics, enabled the development of complex embedded computing devices, i.e. mobile phones, digital cameras, etc., which dominate the modern everyday life. Such type of systems usually execute a large but specific set of applications, which combine highly dynamic behavior together with high demands in computing power. The designers have to deal with the increased system complexity, in order to provide design solutions that satisfy a set of stringent functional and financial constraints. Today, it is broadly accepted that without the use of automated tools to optimize the hardware and software system's coefficients, designers are led to the adoption of sub-optimal design solutions. This thesis addresses the above problem by developing a set of methodologies for efficient design space exploration and architectural synthesis for digital signal processing coprocessors. Specifically, the proposed techniques target to (i) the development of customized software solutions for dynamic memory management of multi-threaded applications and (ii) the design of efficient customized and reconfigurable coprocessor architectures. Regarding to the automated design space exploration methodologies, we model and analyze the basic building blocks of multi-threaded dynamic memory management for multi-core platforms with shared memory. We propose new algorithms for exploring and traversing the defined parameter space based on constrained orthogonal design space partitioning, which enables multi-objective optimization and automated code generation of application specific dynamic memory management. In addition, we propose a new approach for defining an extended design space for hardware coprocessor synthesis, which takes into account the combined impact of behavioral-algorithmic and architectural level parameters. New exploration algorithms are developed to enable fast and efficient exploration that converges to more globally optimal design solutions. Regarding to the architectural synthesis of reconfigurable coprocessors, we introduce the Flexibility Inlining technique for designing coarse-grained reconfigurable architectures at the circuit level. The proposed technique exploits the mirror symmetry found in ASIC implementations of arithmetic circuits and through appropriate RTL transformations achieves the design of a new reconfigurable micro-architectural template that exploits in a combined manner the architectural optimizations of horizontal parallelism, vertical parallel and operation chaining. In addition, we present a second micro-architectural template that use advanced arithmetic optimization techniques for designing flexible coprocessor datapaths. Each of the aforementioned reconfigurable architectures is complemented with new high level synthesis algorithms in order to enable automated mapping of applications onto the introduced datapaths. We study the effectiveness of the proposed methodologies through multiple and extensive experimental evaluations of the proposed solutions in comparison with state-of-the-art design solutions. In any case, it seems that the adoption of the proposed methodologies leads to a significant shift of the design solutions towards more efficient implementations.

Οι τεχνολογικές εξελίξεις στον τομέα της μικρο-ηλεκτρονικής επιτρέπουν σήμερα την ανάπτυξη πολύπλοκων ενσωματωμένων υπολογιστικών συσκευών π.χ. κινητά τηλέφωνα, ψηφιακές κάμερες, που κυριαρχούν τη σύγχρονη καθημερινότητα. Οι σχεδιαστές καλούνται να αντιμετωπίσουν την αυξημένη πολυπλοκότητα παρέχοντας σχεδιαστικές λύσεις που ικανοποιούν ένα αντικρουόμενο σύνολο αυστηρών λειτουργικών και οικονομικών περιορισμών. Σήμερα είναι γενικά αποδεκτό ότι χωρίς τη χρήση αυτοματοποιημένων εργαλείων που βελτιστοποιούν αισθητά τις συνιστώσες υλικού και λογισμικού του συστήματος οι σχεδιαστές οδηγούνται στην υιοθέτηση υπο-βέλτιστων σχεδιαστικών λύσεων. Η παρούσα διατριβή στοχεύει στην αντιμετώπιση του παραπάνω προβλήματος μέσω της ανάπτυξης ενός συνόλου μεθοδολογιών σχεδίασης που επιτρέπουν αποδοτική εξερεύνηση και σύνθεση αρχιτεκτονικών λύσεων υλικού και λογισμικού. Πιο συγκεκριμένα οι προτεινόμενες μεθοδολογίες αφορούν (i) την ανάπτυξη εξειδικευμένων λύσεων λογισμικού για δυναμική διαχείριση μνήμης πολύ-νηματικών εφαρμογών και (ii) τη σχεδίαση αποδοτικών λύσεων υλικού τόσο για επαναδιατάξιμες όσο και εξειδικευμένες αρχιτεκτονικές συνεπεξεργαστή. Σε ότι αφορά στις μεθοδολογίες αυτοματοποιημένης εξερεύνησης παρουσιάζεται η μοντελοποίηση και η ανάλυση σε βασικές συνιστώσες του χώρου σχεδίασης των δυναμικών διαχειριστών μνήμης για πολύ-νηματικές εφαρμογές. Προτείνονται νέοι αλγόριθμοι εξερεύνησης και διάσχισης του παραπάνω χώρου σχεδίασης βάσει μεθόδων ορθογώνιου διαχωρισμού των αποφάσεων που επιτρέπουν την πολύ-κριτηριακή εξειδίκευση και την αυτοματοποιημένη παραγωγή λογισμικού των δυναμικών διαχειριστών μνήμης. Επιπλέον προτείνεται μια νέα θεώρηση για την παραμετρική μοντελοποίηση του χώρου σχεδίασης εξειδικευμένων συνεπεξεργαστών υλικού η οποία λαμβάνει υπόψη τις επιδράσεις των σχεδιαστικών αποφάσεων από τα επίπεδα αφαίρεσης συμπεριφοράς αλγορίθμου και αρχιτεκτονικής με στόχο τη συνδυασμένη βελτιστοποίηση της επίδοσης και της επιφάνειας υλικού. Νέοι αλγόριθμοι εξερεύνησης αναπτύχθηκαν ώστε να επιτυγχάνεται γρήγορη αναζήτηση με αποδοτική σύγκλιση στις καθολικά βέλτιστες σχεδιαστικές λύσεις. Σε ότι αφορά στις μεθοδολογίες αρχιτεκτονικής σύνθεσης επαναδιατάξιμων συνεπεξεργαστών υλικού παρουσιάζεται η τεχνική Εισαγωγή Ευελιξίας για κυκλωματική σχεδίαση επαναδιατάξιμων αρχιτεκτονικών αδρομερούς υφής. Η προτεινόμενη τεχνική εκμεταλλεύεται την κατοπτρική συμμετρία στις διασυνδέσεις εξειδικευμένων (μη-επαναδιατάξιμων) αριθμητικών κυκλωμάτων και μέσω κατάλληλων μετασχηματισμών επιτυγχάνει τη σχεδίαση ενός νέου επαναδιατάξιμου μικρο-αρχιτεκτονικού πρότυπου το οποίο συνδυάζει τον οριζόντιο και κάθετο παραλληλισμό με δυνατότητες υπολογιστικής αλυσίδωσης λειτουργιών. Επιπροσθέτως, προτείνεται και μια δεύτερη επαναδιατάξιμη αρχιτεκτονική συνεπεξεργαστή, η οποία βασίζεται στη χρήση μεθόδων αριθμητικής βελτιστοποίησης για σχεδίαση ευέλικτων συνεπεξεργαστών με αλυσίδωση λειτουργιών. Για κάθε επαναδιατάξιμο συνεπεξεργαστή αναπτύχθηκαν νέοι αλγόριθμοι σχεδίασης για αυτοματοποιημένη απεικόνιση εφαρμογών στις προτεινόμενες αρχιτεκτονικές. Η μελέτη της αποδοτικότητας των προτεινόμενων μεθοδολογιών πραγματοποιήθηκε μέσω εκτενών πειραματικών αξιολογήσεων και συγκρίσεων με τις αντίστοιχες σχεδιαστικές λύσεις αιχμής. Σε κάθε περίπτωση, διαπιστώνεται πως η υιοθέτηση των μεθοδολογιών που αναπτύχθηκαν στην παρούσα διατριβή, οδηγεί σε σημαντική μετατόπιση των σχεδιαστικών λύσεων προς πιο αποδοτικές υλοποιήσεις.