Βελτιστοποίηση και αυτοματοποίηση τεχνικών μεταγλώττισης μέσω μοντελοποίησης σε επαναπροσδιοριζόμενα συστήματα

Abstract

The research material that is presented in this PhD Thesis is related with the development ofcompiling optimization techniques for reconfigurable systems and application specific integrated circuits. The objective is the optimisation of the execution of applications in terms of speed, area and power consumption in these architectures. This is achieved by developing original compiling techniques and efficient architecture instances. Moreover, one of the fundamental objectives of this thesis is the automation of these techniques for the fast determination of most optimal solutions. The automation is achieved with a set of prototype tools for fast compiling and evaluation of the reconfigurable architectures. The largest part of the Thesis is devoted with development of compilation and evaluation techniques for coarse grain reconfigurable array architectures. These architectures consist of a big number of processing elements which work in parallel for exploiting the inherent parallelism existing in the algorithms making their execution faster and more efficient. These systems are used as coprocessors (accelerators) in embedded systems aiming at the acceleration of applications that execute on them. The higher level of control of these systems is implement most commonly by Instruction Set Processors. The mapping of applications on reconfigurable array architectures is characterized by high complexity. As result, the realisation without suitable tools makes it very time-consuming. Moreover, specialized compiling techniques are required in order to overcome the factors that constitute a bottleneck in the exploitation of the computational power of these architectures. For the optimised compilation in these architectures an original-automated-reconfigurable and formalized methodology was proposed. The automation was realized with a set of prototype compiling tools which target on a parametric template of coarse grain reconfigurable array architecture. This allowed fast exploration of the design space aiming at the determination of the most optimal architectures in terms of speed area for different categories of algorithms. Moreover, the incorporation of the reconfigurable array architecture in embedded systems on chip with Instruction Set Processor and Fine Grain reconfigurable hardware was also studied. For compiling applications in these systems a partitioning methodology was proposed for identifying the critical parts of applications that will be executed in the reconfigurable array architecture and ultimately will accelerate the execution of the overall application. The experiments showed important speedups in the execution of applications by the use of the reconfigurable array architecture as an accelerator. Also, an application specific processor was developed for the realization of the forward wavelet transform according to the JPEG2000 standard. The realization of the system includes the 1-dimensional convolutional digital filters that implement the forward wavelet transform and the architectural interconnection of these with memories. For the scheduling of calculations in the architecture a scheduling algorithm is proposed that aims the minimisation of memory requirements and the maximisation of speed. The description of architecture and the scheduling algorithm is parametric so that it is applied on pictures of different dimensions and for any of the convolutional filters that have been proposed in the JPEG 2000 for implementing the wavelet transform. Also, the optimization methodology that was introduced for the optimisation of the HIPERLAN/2 network standard and the determination of its memory architecture is also described. Also, this methodology can be applied to the optimization of other network protocols with characteristics similar to the ones of HIPERLAN/2. The methodology consists of three stages. In first, analysis partitions the application in layers according to their criticality in the optimization stage. The objective is to reduce the optimization time since the actual optimizable code is much less than the original application code. Hence, the designer’s scope reduces significantly. For the analysis a prototype compiler tool was realized. The second stage refers to the optimization of the protocol for which existing tools where used. The optimization targets the refinement of the application data types and the way their accessed for achieving more efficient memory operation. Finally, based on the new implementation of the application’s data types a power aware memory architecture is derived in the third stage that meets the timing constraints. The application of methodology resulted in improvements up to 37% in terms of the power consumption.

Το αντικείμενο της παρούσας διδακτορικής σχετίζεται με την ανάπτυξη βελτιστοποιητικών τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα ολοκληρωμένα συστήματα αλλά και για ολοκληρωμένα συστήματα ειδικού σκοπού. Στόχος, είναι η βελτιστοποίηση της εκτέλεσης των εφαρμογών ως προς την ταχύτητα, επιφάνεια ολοκλήρωσης και κατανάλωση ισχύος στα προαναφερόμενα συστήματα. Αυτό επιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών μεταγλώττισης αλλά και ανεύρεση βέλτιστων αρχιτεκτονικών. Επιπλέον βασικό στόχος της διατριβής είναι η αυτοματοποίηση των τεχνικών αυτών για τον γρήγορο προσδιορισμό βέλτιστων λύσεων. Η αυτοματοποίηση επιτυγχάνεται με μια σειρά από πρότυπα εργαλεία μεταγλώττισης και αποτίμησης αρχιτεκτονικών. Το πρώτο τμήμα της διατριβής αναφέρεται στην ανάπτυξη και αυτοματοποίηση τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενες αρχιτεκτονικές πίνακα. Οι αρχιτεκτονικές αυτές αποτελούνται από ένα μεγάλο αριθμό επεξεργαστικών στοιχείων τα οποία δουλεύοντας παράλληλα εκμεταλλεύονται την ενδογενή παραλληλία των αλγόριθμων καθιστώντας την εκτέλεση των τελευταίων ταχύτερη. Τα συστήματα αυτά χρησιμοποιούνται ως συνεπεξεργαστές (επιταχυντές) σε ενσωματωμένα συστήματα με σκοπό την επιτάχυνση των εφαρμογών του εκτελούνται σε αυτά. Η βασικές επεξεργαστικές μονάδες στα ενσωματωμένα συστήματα αυτά είναι κατά κανόνα επεξεργαστές γενικού σκοπού. Η μεταγλώττιση εφαρμογών στις επαναπροσδιοριζόμενες αρχιτεκτονικές πίνακα χαρακτηρίζεται από υψηλή πολυπλοκότητα. Ως αποτέλεσμα η πραγματοποίηση της χωρίς κατάλληλα εργαλεία την καθιστά απαγορευτικά χρονοβόρα. Επιπλέον, απαιτούνται ειδικές τεχνικές για να ξεπεραστούν οι παράγοντες που αποτελούν τροχοπέδη στην εκμετάλλευση της επεξεργαστικής ισχύος αυτών των αρχιτεκτονικών. Για την βελτιστοποιημένη μεταγλώττιση σε αυτές τις αρχιτεκτονικές προτάθηκε μια πρωτότυπη αυτοματοποιημένη και επαναστοχεύσιμη μεθοδολογία χαρτογράφησης εφαρμογών. Η αυτοματοποίηση της έγινε με ένα πρότυπο εργαλείο μεταγλώττισης το οποίο στοχεύει σε ένα παραμετρικό πρότυπο αυτού του τύπου αρχιτεκτονικής. Αυτό επέτρεψε την γρήγορη εξερεύνηση του χώρου λύσεων με σκοπό την ανεύρεση βέλτιστών αρχιτεκτονικών ως προς ταχύτητα και επιφάνεια ολοκλήρωσης για διαφορετικές ομάδες αλγορίθμων. Επιπλέον, πραγματοποιήθηκε ενσωμάτωση της επαναπροσδιοριζόμενης αρχιτεκτονικής σε ενσωματωμένα συστήματα με επεξεργαστή γενικού σκοπού αλλά και σε συστήματα με επαναπροσδιοριζόμενα συστήματα λεπτής υφής. Για την μεταγλώττιση εφαρμογών σε αυτά τα συστήματα προτάθηκε μια πρωτότυπη μεθοδολογία διαχωρισμού των κρίσιμων τμημάτων κώδικα με σκοπό την επιτάχυνση τους στην επαναπροσδιοριζόμενη αρχιτεκτονική πίνακα. Και σε αυτή την περίπτωση τα πειράματα έδειξαν σημαντικές βελτιώσεις στην εκτέλεση εφαρμογών από την χρήση της επαναπροσδιοριζόμενης αρχιτεκτονικής πίνακα. Επίσης, αναπτύχθηκε αρχιτεκτονική για την υλοποίηση του ευθύ κυματιδιακού μετασχηματισμού σύμφωνα με το πρότυπο JPEG 2000. Η υλοποίηση του συστήματος περιλαμβάνει την υλοποίηση των ψηφιακών φίλτρων και της αρχιτεκτονικής διασύνδεσης αυτών με τις απαραίτητες μνήμες. Για την διεκπεραίωση των υπολογισμών της αρχιτεκτονικής προτείνεται ένας πρωτότυπος αλγόριθμος χρονοπρογραμματισμού που σκοπό έχει την ελαχιστοποίηση των απαιτήσεων μνήμης και την μεγιστοποίηση της ταχύτητας. Η περιγραφή της αρχιτεκτονικής είναι παραμετρική ώστε να εφαρμόζεται για εικόνες οποιονδήποτε διαστάσεων και για οποιαδήποτε από τα φίλτρα που έχουν προταθεί για την υλοποίησης του διδιάστατου κυματιδιακού μετασχηματισμού για το πρότυπο JPEG 2000. Ο αλγόριθμος χρονοπρογραμματισμού είναι αντιστοίχως επαναστοχεύσιμος ως προς οποιοδήποτε σενάριο αρχιτεκτονικής προέρχεται από αλλαγή των προαναφερθέντων παραμέτρων. Επίσης περιγράφεται η μεθοδολογία μεταγλώττισης που εισήχθη για την βελτιστοποίηση και τον προσδιορισμό της αρχιτεκτονικής μνήμης για το δικτυακό πρότυπο HIPERLAN/2. Η βελτιστοποίηση και η αρχιτεκτονική μνήμης σκοπό έχουν την αποδοτική λειτουργία του προτύπου ως προς ταχύτητα και κατανάλωση ισχύος. Η μεθοδολογία αποτελείται από τρία στάδια. Στο πρώτο γίνεται ανάλυση του κώδικα περιγραφής του δικτυακού προτύπου με ένα πρότυπο εργαλείο ανάλυσης. Σε αυτό το στάδιο προσδιορίζονται τα κρίσιμα ως προς κατανάλωση ισχύος τμήματα του αλγορίθμου Στην συνέχεια εφαρμόστηκε η μεθοδολογία MATISSE, της εταιρίας IMEC, για την βελτιστοποίηση των κρίσιμων τμημάτων, παράγοντας ένα νέο κώδικα βελτιστοποιημένο ως προς την κατανάλωση ισχύος. Στο τρίτο βήμα προσδιορίζεται η αρχιτεκτονική μνήμης σύμφωνα με την βελτιστοποιημένη έκδοση του κώδικα της εφαρμογής. Από την εφαρμογή της μεθοδολογίας προέκυψαν βελτιώσεις έως και 37% ως προς την κατανάλωση ισχύος.