Ανάπτυξη αρχιτεκτονικών και τεχνικών μεταφραστών για διαχείριση μνήμης σε ενσωματωμένα συστήματα

Abstract

Today the continuously increasing requirements of applications in processing power as well as their frequent upgrade with new, are the spark for the promotion of research for the growth of systems that will respond to the increased needs for processing power, fast implementation, and low cost. In order to satisfy all three objectives the growth and automation of optimised design techniques is required. With the new techniques of compilation the systems will become more efficient while the automation of techniques will accelerate the designing process. The object of the present thesis is related with the development of architectures and compiler techniques for memory management perspective in embedded systems. The main objective is the optimisation of execution of applications as for the speed, area and power consumption in the embedded systems. This is achieved with the development of original compiler techniques but also finding of most optimal architectures. Moreover fundamental objective of the thesis is the automation of these techniques for the fast determination of most optimal solutions. The automation is achieved with model tools for compiling and evaluating of architectures. a) Development of Architectures for Memory Management. A decoupled processors architecture with a memory hierarchy is presented consisting only of scratch–pad memories, and a main memory. This architecture exploits both the benefits of scratch-pad memories and the parallelism between address computation and application data processing. The application code is split in two programs the first for computing the addresses of the data in the memory hierarchy and the second for processing the application data. The first program is executed by one of the decoupled processors called Access which uses compiler methods for placing data in the memory hierarchy. In parallel, the other processor called Execute runs the second program. The decoupled processors and the memory hierarchy are all synchronized through the use of a simple handshake protocol. The Access processor requires strong communication with the memory hierarchy which strongly differentiates it from traditional uniprocessors. The architecture is compared in performance with the MIPS architecture with cache and also with scratch-pad memory hierarchies and with the existing decoupled architectures showing its higher normalized performance. Experimental results show that the performance is increased up to 3.7 times. Compared with MIPS the proposed architecture achieves the above performance without having penalties in energy delay product costs. Continuing, more research is done on Scratch-pad memories. They are used today in data dominated applications of embedded systems for gaining system’s energy and performance. However, when the execution flow depends on the application’s inputs there is not always possible to be sure about the exact data contents of a scratch-pad as the compiler cannot predict the input randomness. Moreover, portions of already stored data cannot be efficiently combined with new random data entries of scratchpad. This is because all data blocks are copied to scratch-pad without considering whether data portions of those blocks have already been stored in it. Temporal locality that occurs randomly at these cases is not exploited. In this paper, we present an architecture that is able to provide the information about the exact data contents of scratch-pad during execution and can also do all the necessary operations for placing the new data blocks in scratch-pad. Thereby, the temporal locality which occurs randomly and cannot be identified by the compiler is exploited. The proposed architecture is strongly connected to the system’s scratch-pad and the processor’s compiler. It operates in a time and energy efficient manner. It is compared with the MIPS architecture with cache and with scratch-pad memories showing its higher normalized performance and lower normalized energy consumption. Experimental results show that the performance is increased up to 5 times compared to cache architectures and 2,5 times compared to existing scratch-pad architectures while the energy decreases up to 3,9 times and 1,9 times respectively. We explain that our architecture behaves better than existing ones in most of the cases while as a worst case it behaves similar to them. The energy delay product results prove the benefits of our architecture compared to the existing ones. b) Development of Compiler Techniques for Management of Memory. Initially, an automated framework is presented that partitions the code and data types for the needs of data management in an object-oriented source code. The goal is to identify the crucial data types from data management perspective and separate these from the rest of the code. In this way, the design complexity is reduced allowing the designer to easily focus on the important parts of the code to perform further refinements and optimizations. To achieve this, static and dynamic analysis is performed on the initial C++ specification code. Based on the analysis results, the data types of the application are characterized as crucial or non-crucial. Continuing, the initial code is rewritten automatically in such a way that the crucial data types and the code portions that manipulate them are separated from the rest of the code. Experiments on well-known multimedia and telecom applications demonstrate the correctness of the performed automated analysis and code rewriting as well as the applicability of the introduced framework in terms of execution time and memory requirements. Comparisons with Rational’s Quantify™ suite show the failure of Quantify™ to analyze correctly the initial code for the needs of data management. A power aware data type refinement performed on the Data Link Control layer of the HIPERLAN 2 protocol is presented. Applying static and dynamic analysis on the initial specification code, the crucial data types in terms of memory access and storage are identified. Then proper data structures are selected and an efficient memory architecture is derived meeting the time constraints and reducing the energy of the system’s memories. Experimental results show a reduction of the memory energy consumption up to 37% compared with the energy consumption of the memory architecture imposed by the initial specification code.

Σήμερα η ολοένα αυξανόμενες απαιτήσεις των εφαρμογών σε επεξεργαστική ισχύ καθώς και συχνή αναβάθμιση τους με νέες, είναι το έναυσμα για την προώθηση έρευνας για την ανάπτυξη συστημάτων που θα ανταποκρίνονται ολοένα και περισσότερο στις αυξημένες ανάγκες για υπολογιστική ισχύ, γρήγορη υλοποίηση, και χαμηλό κόστος. Για να ικανοποιηθούν και οι τρεις στόχοι απαιτείται η ανάπτυξη και αυτοματοποίηση βελτιστοποιημένων τεχνικών σχεδιασμού. Με τις νέες τεχνικές μεταγλώττισης τα συστήματα θα γίνουν ποιο αποδοτικά ενώ η αυτοματοποίηση των τεχνικών θα επιταχύνει καθοριστικά την διαδικασία σχεδιασμού. Το αντικείμενο της παρούσας διδακτορικής διατριβής σχετίζεται με την ανάπτυξη αρχιτεκτονικών και τεχνικών μεταφραστών για διαχείριση μνήμης σε ενσωματωμένα συστήματα. Στόχος είναι η βελτιστοποίηση της εκτέλεσης των εφαρμογών ως προς την ταχύτητα, επιφάνεια ολοκλήρωσης και κατανάλωση ισχύος στα προαναφερόμενα συστήματα. Αυτό επιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών μεταγλώττισης αλλά και ανεύρεση βέλτιστων αρχιτεκτονικών. Επιπλέον βασικό στόχος της διατριβής είναι η αυτοματοποίηση των τεχνικών αυτών για τον γρήγορο προσδιορισμό βέλτιστων λύσεων. Η αυτοματοποίηση επιτυγχάνεται με μια σειρά από πρότυπα εργαλεία μεταγλώττισης και αποτίμησης αρχιτεκτονικών. α) Ανάπτυξη Αρχιτεκτονικών για Διαχείριση Μνήμης. Παρουσιάζεται μια αποσυζευγμένη αρχιτεκτονική επεξεργαστών με μια ιεραρχία μνήμης που αποτελείται μόνο από μνήμες scratch-pad, και μια κύρια μνήμη. Με τον όρο scratch-pad εννοούμε τις μνήμες προσωρινής αποθήκευσης όπως οι cache χωρίς όμως το κύκλωμα tag array και ελέχγου αυτού που δείχνει αν ένα δεδομένο βρίσκεται εντός ή εκτός των περιεχομένων της. Η αρχιτεκτονική αυτή εκμεταλλεύεται τα οφέλη των scratch-pad μνημών και τον παραλληλισμό μεταξύ της επεξεργασίας δεδομένων και υπολογισμού διευθύνσεων. Ο κώδικας εφαρμογής είναι χωρισμένος σε δύο προγράμματα τον πρώτο για τον υπολογισμό των διευθύνσεων των δεδομένων στην ιεραρχία μνήμης και το δεύτερου για την επεξεργασία των δεδομένων εφαρμογής. Το πρώτο πρόγραμμα εκτελείται από έναν από τους αποσυζευγμένους επεξεργαστές που ονομάζεται επεξεργαστής προσπέλασης (Access) και χρησιμοποιεί μεθόδους μεταγλωττιστών για την αποθήκευση των δεδομένων στην ιεραρχία μνήμης. Παράλληλα, ο άλλος επεξεργαστής ονομάζεται επεξεργαστής προσπέλασης (Execute) και εκτελεί το δεύτερο πρόγραμμα. Οι αποσυζευγμένοι επεξεργαστές και η ιεραρχία μνήμης είναι όλοι συγχρονισμένοι μέσω ενός απλού πρωτοκόλλου. Ο επεξεργαστής Access απαιτεί ισχυρή επικοινωνία με την ιεραρχία μνήμης που τον διαφοροποιεί έντονα από παραδοσιακά uniprocessors. Η αρχιτεκτονική συγκρίνεται στην απόδοση με την αρχιτεκτονική MIPS με cache και με scratch-pad ιεραρχίες μνήμης και παρουσιάζεται η υψηλότερη απόδοσή της. Τα πειραματικά αποτελέσματα δείχνουν ότι η απόδοση αυξάνεται μέχρι 3,7 φορές. Έναντι του MIPS η προτεινόμενη αρχιτεκτονική επιτυγχάνει την ανωτέρω απόδοση χωρίς επιβαρύνσεις σε κατανάλωση ενέργειας. Στη συνέχεια γίνεται περαιτέρω έρευνα σε αρχιτεκτονικές με Scratch-pad. Όταν εξαρτάται η ροή εκτέλεσης των εφαρμογών από τις εισόδους δεν υπάρχει πάντα η βεβαιότητα για το ακριβές περιεχόμενο δεδομένων στη scratch-pad δεδομένου ότι ο μεταγλωττιστής δεν μπορεί να προβλέψει την τυχαιότητα των εισόδων. Επιπλέον, τα τμήματα των ήδη αποθηκευμένων δεδομένων δεν μπορούν να συνδυαστούν αποτελεσματικά με τις νέες τυχαίες εγγραφές δεδομένων στη scratch-pad. Αυτό συμβαίνει επειδή όλα τα τμήματα δεδομένων αντιγράφονται στη scratch-pad χωρίς την εξέταση εάν μέρη αυτών είναι ήδη αποθηκευμένα στη scratch-pad. Η επαναχρησιμοποίηση δεδομένων που εμφανίζεται τυχαία σε αυτές τις περιπτώσεις δεν αξιοποιείται. Παρουσιάζεται λοιπόν, μια αρχιτεκτονική που είναι σε θέση να παρέχει τις πληροφορίες για το ακριβές περιεχόμενο στοιχείων της scratch-pad κατά τη διάρκεια της εκτέλεσης και μπορεί επίσης να κάνει όλες τις απαραίτητες διαδικασίες για την τοποθέτηση των νέων πακέτων δεδομένων στη scratch-pad. Με αυτόν τον τρόπο, αξιοποιείται η επαναχρησιμοποίηση δεδομένων που εμφανίζεται τυχαία και δεν μπορεί να προσδιοριστεί από το μεταγλωττιστή. Η προτεινόμενη αρχιτεκτονική σχετίζεται άμεσα με τη scratch-pad του συστήματος και το μεταγλωττιστή του επεξεργαστή. Λειτουργεί αποδοτικά όσον αφορά το χρόνου εκτέλεσης και την ενέργεια που καταναλώνεται. Συγκρίνεται με την αρχιτεκτονική MIPS με cache και με scratch-pad μνήμες και παρουσιάζει μεγαλύτερη απόδοση και μικρότερη κατανάλωση ενέργειας. Τα πειραματικά αποτελέσματα δείχνουν ότι η απόδοση αυξάνεται μέχρι 5 φορές έναντι των αρχιτεκτονικών με cache και 2.5 φορές έναντι των σύγχρονων αρχιτεκτονικών με scratch-pad ενώ η ενέργεια μειώνεται μέχρι 2.5 φορές και 1.3 φορές αντίστοιχα. β) Ανάπτυξη Τεχνικών Μεταφραστών για Διαχείριση Μνήμης. Παρουσιάζεται αρχικά μια αυτοματοποιημένη μεθοδολογία ανάλυσης που χωρίζει τα δεδομένα για τις ανάγκες της διαχείρισης δεδομένων σε έναν αντικειμενοστρεφή κώδικα. Ο στόχος είναι να προσδιοριστούν τα κρίσιμα δεδομέναόσον αφορά τη διαχείριση μνήμης και να χωριστούν αυτά από τον υπόλοιπο κώδικα. Κατ' αυτό τον τρόπο, η πολυπλοκότητα σχεδιασμού μειώνεται επιτρέποντας στο σχεδιαστή να εστιάσει εύκολα στα σημαντικά μέρη του κώδικα για να εκτελέσει τις βελτιστοποιήσεις. Για να επιτύχει αυτό, στατική και δυναμική ανάλυση εκτελείται στον αρχικό κώδικα C++. Με βάση τα αποτελέσματα ανάλυσης, τα δεδομένα των εφαρμογών χαρακτηρίζονται ως κρίσιμα ή μη-κρίσιμα. Ο αρχικός κώδικας ξαναγράφεται αυτόματα κατά τέτοιο τρόπο ώστε τα κρίσιμα δεδομένα και τα κομμάτια κώδικα που τα χειρίζονται να είναι χωρισμένα από τον υπόλοιπο κώδικα. Πειράματα σε γνωστές εφαρμογές πολυμέσων και εφαρμογές τηλεπικοινωνιών αναδεικνύουν την ακρίβεια της αυτοματοποιημένης ανάλυσης και επανεγγραφής κώδικα καθώς επίσης και τη δυνατότητα εφαρμογής της αυτοματοποιημένης μεθοδολογίας από άποψη απαιτήσεων χρόνου και μνήμης. Επίσης περιγράφεται η μεθοδολογία μεταφραστή που εισήχθη για την βελτιστοποίηση και τον προσδιορισμό της αρχιτεκτονικής μνήμης για το δικτυακό πρότυπο HIPERLAN/2. Η βελτιστοποίηση και η αρχιτεκτονική μνήμης σκοπό έχουν την αποδοτική λειτουργία του προτύπου ως προς την ταχύτητα και κατανάλωση ισχύος. Αρχικά, έγινε ανάλυση του κώδικα περιγραφής του δικτυακού προτύπου με την αυτοματοποιημένη μεθοδολογία ανάλυσης που περιγράφηκε παραπάνω. Σε αυτό το στάδιο προσδιορίζονται τα κρίσιμα ως προς κατανάλωση ισχύος τμήματα του αλγορίθμου. Στην συνέχεια εφαρμόστηκε μεθοδολογία βελτιστοποίησης των κρίσιμων αυτών τμημάτων, παράγοντας ένα νέο κώδικα βελτιστοποιημένο ως προς την κατανάλωση ισχύος. Τελικά, προσδιορίζεται η αρχιτεκτονική μνήμης σύμφωνα με την βελτιστοποιημένη έκδοση του κώδικα της εφαρμογής.