Στη σημερινή εποχή οι μεταγλωττιστές κατέχουν έναν σημαντικό ρόλο στην υψηλή απόδοση των υπολογιστικών συστημάτων είτε επιτραπέζιων, είτε εξυπηρετητών, είτε ενσωματωμένων. Ο λόγος είναι ότι στη σημερινή εποχή όλες σχεδόν οι εφαρμογές γράφονται σε γλώσσες υψηλού επιπέδου και συνεπώς απαιτείται μεταγλώττιση ώστε τα προγράμματα να τρέξουν σε γλωσσά μηχανής. Η ραγδαία όμως αύξηση της απόδοσης των υπολογιστικών συστημάτων όμως έχει δημιουργήσει την απαίτηση για αποδοτικές εφαρμογές. Έτσι ποιότητα του παραγομένου κώδικα που προκύπτει είναι κρίσιμη για την ορθή και γρήγορη εκτέλεση τους για αυτό το λόγω γίνεται σημαντική ερευνά στη συγγραφή μεταγλωττιστών που θα ικανοποιεί τις παραπάνω απαιτήσεις. Αν και σήμερα υπάρχει μέλλον στην ανάπτυξη των μεταγλωττιστών υπάρχει ζήτημα για τα ενσωματωμένα συστήματα. Λόγω του ότι πρέπει να είναι έχουν χαμηλό κόστος, χαμηλή κατανάλωση ισχύος χρησιμοποιούν υποτυπώδεις μεταγλωττιστές. Επειδή όμως τα ενσωματωμένα συστήματα είναι μεγάλος κλάδος των υπολογιστικών συστημάτων με εφαρμογές σε πληθώρα θεμάτων πρέπει οι εφαρμογές αυτές να είναι σωστές και να «τρέχουν» γρήγορα. Αυτό έχει ωθήσει τους προγραμματιστές στην μελέτη των compilers και των μετασχηματισμών που κάνουν και έχει δώσει μια νέα κατεύθυνση στη βελτιστοποίηση προγραμμάτων με το χέρι με χρήση τεχνικών μεταγλωττιστών αλλά και με υψηλοτέρου επιπέδου βελτιστοποιήσεις που δεν γίνονται ακόμα από μεταγλωττιστές. Σκοπός αυτής της εργασίας είναι η μελέτη και βελτιστοποίηση της εφαρμογής για πολυμέσα motion estimation by 4 με στόχο την αύξηση της ταχύτητας εκτέλεσης σε ένα πλήθος αρχιτεκτονικών διατάξεων λαμβάνοντας υπόψη το πλήθος των πράξεων και την ιεραρχία μνήμης. Η εξομοίωση των βελτιωμένων προγραμμάτων έδειξε ότι μπορούμε να επιτύχουμε σημαντική μείωση του χρόνου εκτέλεσης ακόμα και σε αρχιτεκτονικές που δεν αξιοποιούν στο μέγιστο δυνατό τις απαιτήσεις που έχουν αυτά. / In our days compilers play a crucial role in the performance of computer systems (desktop PCs, servers, embedded systems). The reason is that almost every application is created in high level programming languages and compilation is required so that the program will eventually run in machine language. However the rapid increase of computer systems’ performance demands more efficient applications. The quality of the code that is created is critical for fast and correct execution of the applications. For this reason much research is done in the area of creating compilers that fulfill the above requirements. Although there is much future in the development of compilers, important issues arise about the embedded systems. Such systems should be characterized by low cost and low power. For this reason the compilers used are quite simple. However, the embedded systems are a very important branch of computer systems with a variety of applications, which should be executed fast and correctly. These requirements are a motivation for the programmers to study the compilers and the transformations they use and lead to program optimization “by hand” using compiler techniques, as well as higher level optimization techniques that are not used by compilers yet. The purpose of this thesis is the study and optimization of the multimedia application “motion estimation by 4”. Our main goal is to increase the execution speed in a variety of different architectural designs taking into account the amount of computation and the memory hierarchy. The simulation of the improved programs proved that we can accomplish important reduction of the execution time even in architectures that are not suitable for these specific programs.

Με την εξέλιξη της τεχνολογίας, ο κύριος στόχος των υπολογιστικών συστημάτων, επιτραπέζιων, εξυπηρετητών και ενσωματωμένων είναι η υψηλή απόδοση. Όμως, το σύνολο σχεδόν των εφαρμογών στις μέρες μας είναι γραμμένο σε κάποια γλώσσα υψηλού επιπέδου, με αποτέλεσμα να απαιτείται μεταγλώττιση ώστε να μεταφραστούν σε γλώσσα μηχανής και για να μπορέσουν στη συνέχεια να εκτελεστούν σε κάποιον επεξεργαστή. Η ποιότητα του κώδικα που παράγεται είναι κρίσιμος παράγοντας για την ορθή και γρήγορη εκτέλεσή του. Επομένως, η χρήση ενός μεταγλωττιστή που ικανοποιεί τις παραπάνω απαιτήσεις είναι εξαιρετικά σημαντική. Αν και η ανάπτυξη όλο και πιο αποδοτικών μεταγλωττιστών είναι γεγονός, δεν είναι δυνατό να χρησιμοποιηθούν από όλα τα υπολογιστικά συστήματα. Για παράδειγμα, τα ενσωματωμένα συστήματα, που αποτελούν μεγάλο κλάδο των υπολογιστικών συστημάτων και χρησιμοποιούνται σε πληθώρα θεμάτων, λόγω της απαίτησης τους για χαμηλό κόστος και χαμηλή κατανάλωση ισχύος χρησιμοποιούν υποτυπώδεις μεταγλωττιστές. Παρόλα αυτά η απαίτηση για υψηλή απόδοση παραμένει. Έτσι, έχει δοθεί ιδιαίτερη ώθηση στη μελέτη των μεταγλωττιστών και των τεχνικών βελτιστοποίησης προγραμμάτων που χρησιμοποιούν. Αυτό οδήγησε στη χρήση των τεχνικών μεταγλωττιστών από τους προγραμματιστές με στόχο την επίτευξη βελτιστοποίησης στο υψηλότερο επίπεδο, κάτι που είναι ιδιαίτερα χρήσιμο για τα ενσωματωμένα συστήματα όπου δεν χρησιμοποιούνται ακριβοί μεταγλωττιστές. Σκοπός της εργασίας είναι η μελέτη και βελτιστοποίηση μιας εφαρμογής σάρωσης πίνακα με στόχο την αύξηση της ταχύτητας εκτέλεσης και τη μείωση των μετακινήσεων στη μνήμη σε διαφορετικές αρχιτεκτονικές. / As technology changes, the main goal of every computer system (PCs, servers, embedded systems) is high performance. Nowadays, the majority of applications is written in high level languages and compiling is appropriate for their execution in a processor. The quality of binary code produced by a compiler is a critical factor for its correct and fast execution. So, it is extremely significant to use compilers that fulfill the requirements above. Even though the production of compilers which produce high quality binary code is a fact, they cannot be used by every computer system. For instance, embedded systems which are a big part of computer systems and are used in a wide range of applications, use simple compilers. This is because embedded systems are of low cost and low power. Nevertheless, the requirement for high performance remains. As a result, research moved towards compilers’ structure and optimization methods that are used by them. This lead to the use of compilers’ optimization methods by programmers in order to achieve high level optimization in their codes. This is very useful for embedded systems where simple compilers are used and the quality of produced code is not the desired. The aim of this work is the optimization of an application which scans a matrix (filter image) in order to achieve better performance which contains reducing memory accesses and increasing the execution time.

Στη σημερινή εποχή, η πλειοψηφία των εφαρμογών που προορίζονται για επιτραπέζια υπολογιστικά συστήματα, ενσωματωμένα συστήματα και εξυπηρετητές, υλοποιείται χρησιμοποιώντας κάποια γλώσσα υψηλού επιπέδου. Το γεγονός αυτό αναδεικνύει την τεράστια σημασία των μεταγλωττιστών, οι οποίοι μεταφράζουν τον κώδικα υψηλού επιπέδου σε γλώσσα μηχανής. Η γνώση της τεχνολογίας των μεταγλωττιστών αποτελεί σημαντικό εφόδιο στην προσπάθεια αύξησης της απόδοσης ενός υπολογιστικού συστήματος. Σκοπός της παρούσας διπλωματικής εργασίας είναι η βελτιστοποίηση δύο γνωστών εφαρμογών, του μετασχηματισμού Gauss και του αλγορίθμου πολλαπλασιασμού μήτρας Toeplitz με διάνυσμα. Για τη βελτιστοποίηση χρησιμοποιήθηκε πληθώρα τεχνικών που ενσωματώνονται σε διάφορους μεταγλωττιστές, καθώς επίσης και μέθοδοι που οι τρέχοντες μεταγλωττιστές δεν μπορούν ακόμα να εφαρμόσουν. Για την αξιολόγηση των πειραματικών αποτελεσμάτων χρησιμοποιήθηκε το εργαλείο εξομοίωσης Simplescalar και πραγματοποιήθηκε σύγκριση της εκτέλεσης των αρχικών με τις βελτιστοποιημένες εκδόσεις των εφαρμογών. Η επιτάχυνση που επετεύχθη είναι σημαντική, έως και 55%. / Nowadays, the majority of applications designed for desktop and embedded systems and servers is implemented using a high level programming language. This fact proves the huge importance of compilers, which translate high level language into machine language. The knowledge of compiler technology is a useful tool for increasing efficiency of a computer system. The purpose of this Diploma Thesis is to optimize two well-known applications, the Gauss elimination algorithm and the algorithm for multiplying a Toeplitz matrix and a vector. In order to optimize these two algorithms, a variety of techniques present in many compilers was utilized, as well as techniques that current compilers cannot yet apply. For the evaluation of our technique we used Simplescalar simulator and we compared the results between the unoptimized and the optimized versions of the algorithms. The speedup achieved was very significant, up to 55%.

Με την ολοένα και αυξανόμενη τάση για ενσωματωμένα (embedded) και φορητά υπολογιστικά συστήματα της σύγχρονης εποχής, έχειδημιουργηθεί ένας ολόκληρος επιστημονικός κλάδος γύρω από τεχνικές βελτιστοποίησης μεταγλωττιστών για ειδικούς πυρήνες λογισμικού που εκτελούνται στα συστήματα αυτά. Κάνοντας χρήση τεχνικών βελτιστοποίησης τα κέρδη είναι πολλαπλά. Καταρχήν οι πυρήνες μπορούν να ολοκληρώσουν το χρόνο που απαιτείται για να ολοκληρωθεί η εκτέλεση τους σε πολύ μικρότερο διάστημα, έχοντας πολύ μικρότερες απαιτήσεις μνήμης. Επίσης μειώνονται οι ανάγκες τους σε επεξεργαστική ισχύ κάτι το οποίο άμεσα οδηγεί στη μείωση κατανάλωσης ενέργειας, στην αύξηση αυτονομίας τους σε περίπτωση που μιλάμε για φορητά συστήματα και στις ανάγκες για ψύξη των συστημάτων αυτών καθώς εκλύονται πολύ μικρότερα ποσά ενέργειας. Έτσι λοιπόν επιτυγχάνονται κέρδη σε πολλούς τομείς (χρόνος εκτέλεσης, ανάγκες μνήμης, αυτονομία, έκλυση θερμότητας) καθιστώντας τον κλάδο των βελτιστοποιήσεων ένα από τους πιο ταχέως αναπτυσσόμενους κλάδους. Εκτός όμως από την σκοπιά της αύξησης επιδόσεων, στην περίπτωση των ενσωματωμένων συστημάτων πραγματικού χρόνου (real time operations) που όταν ξεπερνιούνται οι διορίες χρόνου εκτέλεσης οδηγούνται σε υποβαθμισμένες επιδόσεις (soft real time) και ειδικότερα στην περίπτωση αυτών που οδηγούνται σε αποτυχία όταν ξεπερνιούνται οι διορίες αυτές (hard real time operations), οι τεχνικές αυτές αποτελούν ουσιαστικά μονόδρομο για την υλοποίηση των συστημάτων αυτών σε λογικά επίπεδα κόστους. Η διαδικασία όμως της ανάπτυξης βελτιστοποιήσεων δεν είναι αρκετή καθώς είναι εξίσου σημαντικό το κατά πόσο οι βελτιστοποιήσεις αυτές ταιριάζουν στην εκάστοτε αρχιτεκτονική του συστήματος. Εάν δε ληφθεί υπόψη η αρχιτεκτονική του συστήματος που θα εφαρμοστούν, τότε οι βελτιστοποιήσεις μπορούν να οδηγήσουν σε αντίθετα αποτελέσματα υποβαθμίζοντας την απόδοση του συστήματος. Στην παρούσα διπλωματική εργασία βελτιστοποιείται η διαδικασία πολλαπλασιασμού διανύσματος με πίνακα toeplitz. Κατά την εκπόνηση της αναπτύχθηκε πληθώρα χρονοπρογραμματισμών που στοχεύουν στην βελτιστοποίηση της διαδικασίας αυτής. Μετά από μια εις βάθους μελέτη της ιεραρχίας μνήμης και των τεχνικών βελτιστοποίησης που προσφέρονται για αποδοτικότερη εκμετάλλευσή της, αλλά και των κυριότερων τεχνικών βελτιστοποίησης μεταγλωττιστών, παρουσιάζονται οι κυριότεροι χρονοπρογραμματισμοί, από όσους αναπτύχθηκαν, με τον κάθε ένα να προσφέρει κέρδος σε διαφορετικές αρχιτεκτονικές συστημάτων. Κατά αυτό τον τρόπο αναπτύσσεται ένα εργαλείο που δέχεται σαν είσοδο την αρχιτεκτονική του συστήματος πάνω στο οποίο πρόκειται να γίνει βελτιστοποίηση του εν λόγω πυρήνα, αποκλείονται αρχικά οι χρονοπρογραμματισμοί που δεν είναι κατάλληλοι για την συγκεκριμένη αρχιτεκτονική, ενώ για τους υποψήφιους πιο αποδοτικούς γίνεται εξερεύνηση ούτως ώστε να επιλεγεί ο αποδοτικότερος. / --

Το αντικείμενο που πραγματεύεται η παρούσα διδακτορική διατριβή σχετίζεται με την ανάπτυξη βελτιστοποιητικών τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα ολοκληρωμένα συστήματα γενικού και ειδικού σκοπού. Στόχος είναι η βελτιστοποίηση της εκτέλεσης των εφαρμογών ως προς την ταχύτητα, την επιφάνεια ολοκλήρωσης και την κατανάλωση ισχύος. Αυτό επιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών μεταγλώττισης αλλά και από την ανεύρεση βέλτιστων αρχιτεκτονικών. Η αυτοματοποίηση των μεθοδολογιών επιτυγχάνεται με την ανάπτυξη εργαλείων βελτιστοποίησης που υλοποιούν την μεθοδολογία μεταγλώττισης. Τα πειράματα έδειξαν γρήγορο προσδιορισμό βέλτιστων λύσεων και σημαντικές βελτιώσεις στην ταχύτητα, επιφάνεια ολοκλήρωσης και κατανάλωση ισχύος για μια σειρά από εφαρμογές ψηφιακής επεξεργασίας σήματος. / The research material that is presented in this PhD Phesis is related with developement of compilation techniques for reconfigurable systems and application specific integrated circuits. The objective is the optimization of the execution of the 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 fast solution determination. Experiments showed that applications are executed faster while keeping the area and power overhead low. The experiments are based on a set of Digital Signal Processing applications.

Το αντικείμενο της παρούσας διδακτορικής διατριβής εστιάζεται στην ανάπτυξη αποδοτικών τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα ολοκληρωμένα συστήματα αρχιτεκτονικών πίνακα. Χρησιμοποιήθηκαν εφαρμογές που κυριαρχούνται από δεδομένα για τον έλεγχο των μεθοδολογιών. Σκοπός είναι να βελτιστοποιηθεί η εκτέλεση των εφαρμογών ως προς χαρακτηριστικά των επαναπροσδιοριζόμενων συστημάτων όπως η απόδοση, ο αριθμός εντολών ανά κύκλο ρολογιού, η επιφάνεια ολοκλήρωσης και ο βαθμός χρησιμοποίησης των επεξεργαστικών πόρων. Αυτό επιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών χαρτογράφησης αλλά και την εύρεση βέλτιστων αρχιτεκτονικών. Στο πρώτο τμήμα της διατριβής υλοποιήθηκε η έρευνα, ανάπτυξη και αυτοματοποίηση τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα συστήματα αρχιτεκτονικών πίνακα. Κύριο χαρακτηριστικό αυτών των αρχιτεκτονικών είναι ύπαρξη μεγάλου αριθμού επεξεργαστικών στοιχείων που δουλεύουν παράλληλα με αποτέλεσμα να επιταχύνουν την εκτέλεση εφαρμογών που εμφανίζουν παραλληλία πράξεων. Η λειτουργία τους σε ενσωματωμένα συστήματα είναι αυτή ενός συνεπεξεργαστή. Η έρευνα πάνω σε επαναπροσδιοριζόμενες αρχιτεκτονικές πίνακα έχει αποκτήσει μεγάλο ενδιαφέρον λόγω της ευελιξίας, της επεκτασιμότητας και της απόδοσής τους, ιδιαίτερα σε εφαρμογές που κυριαρχούνται από δεδομένα. Η μεταγλώττιση, όμως, εφαρμογών πάνω σε αυτές χαρακτηρίζεται από υψηλή πολυπλοκότητα. Απαιτούνται κατάλληλα εργαλεία και ειδικές μεθοδολογίες χαρτογράφησης για την εκμετάλλευση των χαρακτηριστικών αυτών των αρχιτεκτονικών. Με αυτό το σκεπτικό, προτάθηκε μια πρωτότυπη επαναστοχεύσιμη μεθοδολογία χαρτογράφησης εφαρμογών, η οποία επιπλέον έχει αυτοματοποιηθεί με τη χρήση ενός πρότυπου εργαλείου μεταγλώττισης που στοχεύει σε ένα αρχιτεκτονικό παραμετρικό πρότυπο. Αποτέλεσμα ήταν η εύρεση των βέλτιστων αρχιτεκτονικών με βάσει την απόδοση, τον αριθμό των εντολών ανά κύκλο ρολογιού και το χρόνο εκτέλεσης του εργαλείου, για μια ομάδα εφαρμογών. Η αποδοτικότητα μιας επαναπροσδιοριζόμενης αρχιτεκτονικής πίνακα ως προς την ταχύτητα και το κόστος σε υλικό είναι δύσκολο να μετρηθεί, για αυτό έχουν υπάρξει λίγες έρευνες που μελετούν την επίδραση αρχιτεκτονικών παραμέτρων πάνω σε παράγοντες όπως η επιφάνεια ολοκλήρωσης και ο αριθμός εντολών ανά κύκλο ρολογιού. Επιπλέον, καμιά εργασία δεν έχει εξετάσει την επίδραση πολλαπλασιαστών ενσωματωμένων στα επεξεργαστικά στοιχεία των επαναπροσδιοριζόμενων αρχιτεκτονικών. Χρησιμοποιώντας την υπάρχουσα επαναστοχεύσιμη μεθοδολογία μεταγλώττισης και μια παραμετρική υλοποίηση της αρχιτεκτονικής σε γλώσσα περιγραφής υλικού, εξετάζουμε την επίδραση των πολλαπλασιαστών από τη μεριά της χαρτογράφησης και της αρχιτεκτονικής. Επίσης, περιγράφεται η πρωτότυπη μεθοδολογία χαρτογράφησης που εισήχθη με σκοπό την αποδοτική λειτουργία του αλγορίθμου Fast Fourier Transform (FFT) πάνω σε επαναπροσδιοριζόμενα συστήματα αρχιτεκτονικών πίνακα. Ο αλγόριθμος FFT χαρακτηρίζεται από μεγάλο αριθμό πράξεων κυρίως πολλαπλασιασμών που επιβραδύνουν την απόδοση μιας επαναπροσδιοριζόμενης αρχιτεκτονικής. Εκμεταλλευόμενοι την ύπαρξη εσωτερικής επαναληπτικής δομής μέσα στον αλγόριθμο και χρησιμοποιώντας μια επαναπροσδιοριζόμενη αρχιτεκτονική 16 επεξεργαστικών στοιχείων, αναπτύξαμε μια πρωτότυπη τεχνική χαρτογράφησης. Επιπρόσθετα, η τεχνική μας λαμβάνει υπόψη την ιεραρχία μνήμης μεταξύ κύριας μνήμης και επαναπροσδιοριζόμενης αρχιτεκτονικής για την περαιτέρω επιτάχυνση εκτέλεσης του αλγορίθμου FFT. Η χρήση της προτεινόμενης τεχνικής χαρτογράφησης οδηγεί σε επίτευξη βαθμού χρησιμοποίησης των επεξεργαστικών στοιχείων άνω του 90%, τιμή που είναι τουλάχιστον 37% υψηλότερη από την καλύτερη τιμή της βιβλιογραφίας. / The object of this PhD thesis focuses on developing efficient mapping techniques for coarse grain reconfigurable build arrays. Data intensive applications were used to evaluate the proposed methodologies. The aim is to optimize the applications’ performance on characteristics targeting reconfigurable characteristics such as performance, instructions per cycle, area of integration and processing resource utilization. This is achieved by introducing novel mapping techniques and finding optimal architectures. In the first part of the thesis research, development and automation of mapping techniques was carried out targeting coarse grain reconfigurable arrays. The main feature of these architectures is the presence of a large number of processing elements working in parallel thus speeding up the execution of applications featuring parallel operations. The function of these processing elements in embedded systems resembles that of a coprocessor. The research on reconfigurable array architectures has gained considerable interest because of their flexibility, scalability and performance, particularly in data intensive applications. Nevertheless, compiling these applications on reconfigurable architectures is characterized by high degree of complexity. Appropriate tools and special mapping methodologies are needed to exploit the characteristics of these architectures. Bearing this in mind, we proposed a novel reconfigurable methodology for mapping applications, which has also been automated with the use of a prototype compiler tool aiming at a parametric architectural model. The result was finding the best architectures on the basis of performance, the instructions per cycle term and the tool execution time for a sample set of applications. It is difficult to evaluate the efficiency of a reconfigurable array architecture table in terms of speed and area of integration, so there have been few cases studying the effect of architectural parameters on factors such as surface integration and the number of instructions per clock cycle. Moreover, no work has examined the multipliers’ impact embedded in reconfigurable architectures processing elements. Using the existing reconfigurable mapping methodology and a parametric implementation of the architecture in hardware description language, we examine the effect of multipliers on the part of the mapping phase and architecture. We also describe an original mapping methodology introduced for the purpose of efficiently mapping the Fast Fourier Transform (FFT) algorithm on reconfigurable array architectures. The FFT algorithm is characterized by a large number of operations primarily multiplications that slow the performance of a reconfigurable architecture. Exploiting the existence of an internal structure inside the FFT algorithm and by the use of a reconfigurable architecture template of 16 processing elements, we developed a novel mapping technique. Additionally, our technique takes into account the memory hierarchy between main memory and reconfigurable architecture in order to further accelerate the implementation of the FFT algorithm. Using the proposed mapping technique results in processing elements utilization of over 90% value which is at least 37% better than the best value of the related literature.