Μεθοδολογίες μεταγλώττισης σε επαναπροσδιοριζόμενα συστήματα αρχιτεκτονικών πίνακα.

Abstract

The object of this PhD thesis focuses on developing efficient mapping techniquesfor coarse grain reconfigurable build arrays. Data intensive applications were used toevaluate the proposed methodologies. The aim is to optimize the applications’performance on characteristics targeting reconfigurable characteristics such asperformance, instructions per cycle, area of integration and processing resourceutilization. This is achieved by introducing novel mapping techniques and findingoptimal architectures.In the first part of the thesis research, development and automation of mappingtechniques was carried out targeting coarse grain reconfigurable arrays. The mainfeature of these architectures is the presence of a large number of processing elementsworking in parallel thus speeding up the execution of applications featuring paralleloperations. The function of these processing elements in embedded systems resemblesthat of a coprocessor.The research on reconfigurable array architectures has gained considerable interestbecause of their flexibility, scalability and performance, particularly in data intensiveapplications. Nevertheless, compiling these applications on reconfigurable architecturesis characterized by high degree of complexity. Appropriate tools and special mappingmethodologies are needed to exploit the characteristics of these architectures. Bearingthis in mind, we proposed a novel reconfigurable methodology for mappingapplications, which has also been automated with the use of a prototype compiler toolaiming at a parametric architectural model. The result was finding the best architectureson the basis of performance, the instructions per cycle term and the tool execution timefor a sample set of applications.It is difficult to evaluate the efficiency of a reconfigurable array architecture table interms of speed and area of integration, so there have been few cases studying the effectof architectural parameters on factors such as surface integration and the number ofinstructions per clock cycle. Moreover, no work has examined the multipliers’ impact embedded in reconfigurable architectures processing elements. Using the existingreconfigurable mapping methodology and a parametric implementation of thearchitecture in hardware description language, we examine the effect of multipliers onthe part of the mapping phase and architecture.We also describe an original mapping methodology introduced for the purpose ofefficiently mapping the Fast Fourier Transform (FFT) algorithm on reconfigurable arrayarchitectures. The FFT algorithm is characterized by a large number of operationsprimarily multiplications that slow the performance of a reconfigurable architecture.Exploiting the existence of an internal structure inside the FFT algorithm and by the useof a reconfigurable architecture template of 16 processing elements, we developed anovel mapping technique. Additionally, our technique takes into account the memoryhierarchy between main memory and reconfigurable architecture in order to furtheraccelerate the implementation of the FFT algorithm. Using the proposed mappingtechnique results in processing elements utilization of over 90% value which is at least37% better than the best value of the related literature.

Το αντικείμενο της παρούσας διδακτορικής διατριβής εστιάζεται στην ανάπτυξηαποδοτικών τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα ολοκληρωμένασυστήματα αρχιτεκτονικών πίνακα. Χρησιμοποιήθηκαν εφαρμογές που κυριαρχούνταιαπό δεδομένα για τον έλεγχο των μεθοδολογιών. Σκοπός είναι να βελτιστοποιηθεί ηεκτέλεση των εφαρμογών ως προς χαρακτηριστικά των επαναπροσδιοριζόμενωνσυστημάτων όπως η απόδοση, ο αριθμός εντολών ανά κύκλο ρολογιού, η επιφάνειαολοκλήρωσης και ο βαθμός χρησιμοποίησης των επεξεργαστικών πόρων. Αυτόεπιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών χαρτογράφησης αλλά και τηνεύρεση βέλτιστων αρχιτεκτονικών.Στο πρώτο τμήμα της διατριβής υλοποιήθηκε η έρευνα, ανάπτυξη καιαυτοματοποίηση τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα συστήματααρχιτεκτονικών πίνακα. Κύριο χαρακτηριστικό αυτών των αρχιτεκτονικών είναιύπαρξη μεγάλου αριθμού επεξεργαστικών στοιχείων που δουλεύουν παράλληλα μεαποτέλεσμα να επιταχύνουν την εκτέλεση εφαρμογών που εμφανίζουν παραλληλίαπράξεων. Η λειτουργία τους σε ενσωματωμένα συστήματα είναι αυτή ενόςσυνεπεξεργαστή.Η έρευνα πάνω σε επαναπροσδιοριζόμενες αρχιτεκτονικές πίνακα έχει αποκτήσειμεγάλο ενδιαφέρον λόγω της ευελιξίας, της επεκτασιμότητας και της απόδοσής τους,ιδιαίτερα σε εφαρμογές που κυριαρχούνται από δεδομένα. Η μεταγλώττιση, όμως,εφαρμογών πάνω σε αυτές χαρακτηρίζεται από υψηλή πολυπλοκότητα. Απαιτούνταικατάλληλα εργαλεία και ειδικές μεθοδολογίες χαρτογράφησης για την εκμετάλλευσητων χαρακτηριστικών αυτών των αρχιτεκτονικών. Με αυτό το σκεπτικό, προτάθηκε μιαπρωτότυπη επαναστοχεύσιμη μεθοδολογία χαρτογράφησης εφαρμογών, η οποίαεπιπλέον έχει αυτοματοποιηθεί με τη χρήση ενός πρότυπου εργαλείου μεταγλώττισηςπου στοχεύει σε ένα αρχιτεκτονικό παραμετρικό πρότυπο. Αποτέλεσμα ήταν η εύρεση των βέλτιστων αρχιτεκτονικών με βάσει την απόδοση, τον αριθμό των εντολών ανάκύκλο ρολογιού και το χρόνο εκτέλεσης του εργαλείου, για μια ομάδα εφαρμογών.Η αποδοτικότητα μιας επαναπροσδιοριζόμενης αρχιτεκτονικής πίνακα ως προς τηνταχύτητα και το κόστος σε υλικό είναι δύσκολο να μετρηθεί, για αυτό έχουν υπάρξειλίγες έρευνες που μελετούν την επίδραση αρχιτεκτονικών παραμέτρων πάνω σεπαράγοντες όπως η επιφάνεια ολοκλήρωσης και ο αριθμός εντολών ανά κύκλορολογιού. Επιπλέον, καμιά εργασία δεν έχει εξετάσει την επίδραση πολλαπλασιαστώνενσωματωμένων στα επεξεργαστικά στοιχεία των επαναπροσδιοριζόμενωναρχιτεκτονικών. Χρησιμοποιώντας την υπάρχουσα επαναστοχεύσιμη μεθοδολογίαμεταγλώττισης και μια παραμετρική υλοποίηση της αρχιτεκτονικής σε γλώσσαπεριγραφής υλικού, εξετάζουμε την επίδραση των πολλαπλασιαστών από τη μεριά τηςχαρτογράφησης και της αρχιτεκτονικής.Επίσης, περιγράφεται η πρωτότυπη μεθοδολογία χαρτογράφησης που εισήχθη μεσκοπό την αποδοτική λειτουργία του αλγορίθμου Fast Fourier Transform (FFT) πάνωσε επαναπροσδιοριζόμενα συστήματα αρχιτεκτονικών πίνακα. Ο αλγόριθμος FFTχαρακτηρίζεται από μεγάλο αριθμό πράξεων κυρίως πολλαπλασιασμών πουεπιβραδύνουν την απόδοση μιας επαναπροσδιοριζόμενης αρχιτεκτονικής.Εκμεταλλευόμενοι την ύπαρξη εσωτερικής επαναληπτικής δομής μέσα στον αλγόριθμοκαι χρησιμοποιώντας μια επαναπροσδιοριζόμενη αρχιτεκτονική 16 επεξεργαστικώνστοιχείων, αναπτύξαμε μια πρωτότυπη τεχνική χαρτογράφησης. Επιπρόσθετα, ητεχνική μας λαμβάνει υπόψη την ιεραρχία μνήμης μεταξύ κύριας μνήμης καιεπαναπροσδιοριζόμενης αρχιτεκτονικής για την περαιτέρω επιτάχυνση εκτέλεσης τουαλγορίθμου FFT. Η χρήση της προτεινόμενης τεχνικής χαρτογράφησης οδηγεί σεεπίτευξη βαθμού χρησιμοποίησης των επεξεργαστικών στοιχείων άνω του 90%, τιμήπου είναι τουλάχιστον 37% υψηλότερη από την καλύτερη τιμή της βιβλιογραφίας.