Στη σημερινή εποχή οι μεταγλωττιστές κατέχουν έναν σημαντικό ρόλο στην υψηλή απόδοση των υπολογιστικών συστημάτων είτε επιτραπέζιων, είτε εξυπηρετητών, είτε ενσωματωμένων. Ο λόγος είναι ότι στη σημερινή εποχή όλες σχεδόν οι εφαρμογές γράφονται σε γλώσσες υψηλού επιπέδου και συνεπώς απαιτείται μεταγλώττιση ώστε τα προγράμματα να τρέξουν σε γλωσσά μηχανής. Η ραγδαία όμως αύξηση της απόδοσης των υπολογιστικών συστημάτων όμως έχει δημιουργήσει την απαίτηση για αποδοτικές εφαρμογές. Έτσι ποιότητα του παραγομένου κώδικα που προκύπτει είναι κρίσιμη για την ορθή και γρήγορη εκτέλεση τους για αυτό το λόγω γίνεται σημαντική ερευνά στη συγγραφή μεταγλωττιστών που θα ικανοποιεί τις παραπάνω απαιτήσεις. Αν και σήμερα υπάρχει μέλλον στην ανάπτυξη των μεταγλωττιστών υπάρχει ζήτημα για τα ενσωματωμένα συστήματα. Λόγω του ότι πρέπει να είναι έχουν χαμηλό κόστος, χαμηλή κατανάλωση ισχύος χρησιμοποιούν υποτυπώδεις μεταγλωττιστές. Επειδή όμως τα ενσωματωμένα συστήματα είναι μεγάλος κλάδος των υπολογιστικών συστημάτων με εφαρμογές σε πληθώρα θεμάτων πρέπει οι εφαρμογές αυτές να είναι σωστές και να «τρέχουν» γρήγορα. Αυτό έχει ωθήσει τους προγραμματιστές στην μελέτη των 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%.

Refactoring wird angewandt, wenn eine Software-Inspektion Defekte im Programmcode feststellt. Code-Smells sind Beispiele solcher Defekte im Programmcode. Clean-Code ist ein neuerer Ansatz, der genauso wie das Code-Smell-Konzept festlegt, wann Defekte im Programmcode vorliegen. Für Code-Smells gibt es bereits zahlreiche Code-Analyse-Tools, die die automatische Erkennung solcher Defekte ermöglicht. Die vorliegende Arbeit implementiert ein Clean-Code-Analyse-Tool für Programmcode mithilfe von statischer Code-Analyse, das Refactoring-Hinweise ausgibt. Für diesen Zweck werden ein Lexer und ein Parser zur syntaktischen Analyse eines Subsets der Programmiersprache C++ implementiert. Die Evaluation durch quantitative Datenanalyse zeigt, wie nützlich die automatische Erkennung von Clean-Code mithilfe eines statischen Code-Analyse-Tools bei der Erstellung von Programmcode mit höherer Lesbarkeit für Entwicklerinnen und Entwickler ist.:Inhaltsverzeichnis 6 Abbildungsverzeichnis 9 Tabellenverzeichnis 10 Akronyme 13 1. Einleitung 14 2. Theoretische Grundlagen 17 2.1. Wichtige Begriffe und Definitionen 17 2.1.1. Software-Inspektion 17 2.1.2. Fagan-Inspektion 18 2.1.3. Checklistenbasiertes Code-Review 19 2.1.4. Statische vs. dynamische Code-Analyse-Tools 21 2.1.5. Refactoring 24 2.1.6. Code-Smells 24 2.1.7. Clean-Code 25 2.2. Code-Smell-Heuristiken im Detail 27 2.3. Einführung in den Compilerbau 32 2.3.1. Kurze Einführung in die Sprachtheorie 32 2.3.2. Die lexikalische Analyse 34 2.3.3. Die syntaktische Analyse 35 3. Forschungsstand 38 3.1. Code-Smell-Analyse-Tools auf Grundlage von Strukturinformationen 42 3.2. Code-Smell-Analyse durch maschinelles Lernen 50 3.3. Code-Smell-Suche mithilfe von Änderungsdaten 52 3.4. Code-Smell-Erkennung durch Textanalyse 54 4. Forschungsfragen und Konzeptentwicklung 56 4.1. Clean-Code: Welche Teile sind messbar? - Die Konzeptionalisierung hin zu einem maschinenlesbaren Ansatz 56 4.1.1. Größe von Entitäten im Clean-Code 57 4.1.2. Clean-Code und Zugriffsmodifikatoren 59 4.1.3. Bezeichner von Entitäten im Clean-Code 60 4.1.4. Formatierungskonventionen des Clean-Codes 62 4.1.5. Funktionsparameterübergabe im Clean-Code-Konzept 63 4.1.6. Clean-Code-Kommentare 65 4.1.7. Clean-Code — Was nicht geht 66 4.1.8. Platzierung von Entitäten im Clean-Code 67 4.2. Forschungsfragen und Hypothesen 69 5. Methodik 71 5.1. Implementierung des statischen Clean-Code-Analyse-Tools 71 5.1.1. Abhängigkeiten 72 5.1.2. Umsetzung des statischen Clean-Code-Analyse-Tools 72 5.1.3. Abhängige Variablen 78 5.2. Checklistenbasiertes Code-Review 80 5.2.1. Begründung der Methodenauswahl 80 5.2.2. Fragebogen 81 5.2.3. Unabhängige Variablen 85 5.2.4. Ablauf der Studie 86 6. Ergebnisse 87 6.1. Populationsbeschreibung 88 6.2. Deskriptive Werte der Evaluationsitems aus der Lesbarkeitsstudie 88 6.3. Deskriptive Werte der Evaluation des statischen Clean-Code-Analyse-Tools 90 6.4. Inferenzstatistik 91 7. Diskussion 96 7.1. Beantwortung der Forschungsfrage 96 7.2. Bedrohungen der Validität 97 7.3. Ausblick und Vergleich mit ähnlichen Code-Analyse-Tools 98 8. Fazit 100 Literaturverzeichnis 102 A. Anhang 112 A.1. Tabellen 112 A.2. Clean-Code Analyse-Tool Ein- und Ausgabe 124 A.3. Lesbarkeitsstudie 135 A.4. Regressionsergebnisse 144 B. CD 148 C. Selbstständigkeitserklärung 148

Οι υπάρχοντες μεταγλωττιστές, έχουν τρία βασικά μειονεκτήματα i) όλα τα υπό-προβλήματα της μεταγλώττισης (π.χ. μετασχηματισμοί, εύρεση χρονοπρογραμματισμού, ανάθεση καταχωρητών) βελτιστοποιούνται ξεχωριστά (εκτός από μεμονωμένες περιπτώσεις όπου βελτιστοποιούνται κάποια στάδια μαζί - συνήθως 2), παρόλο που υπάρχει εξάρτηση μεταξύ τους, ii) δεν εκμεταλλεύονται αποδοτικά όλα τα χαρακτηριστικά του προγράμματος εισόδου (π.χ. δομή του εκάστοτε αλγορίθμου, επαναχρησιμοποίηση δεδομένων), iii) δεν εκμεταλλεύονται αποδοτικά τις παραμέτρους της αρχιτεκτονικής. Στη παρούσα διδακτορική διατριβή, αναπτύχθηκαν μεθοδολογίες οι οποίες αντιμετωπίζουν τα προβλήματα εύρεσης χρονοπρογραμματισμών με τον ελάχιστο αριθμό i) προσβάσεων στην κρυφή μνήμη δεδομένων L1, ii) προσβάσεων στην κρυφή μνήμη L2, iii) προσβάσεων στην κύρια μνήμη, iv) πράξεων διευθυνσιοδότησης, μαζί σαν ενιαίο πρόβλημα και όχι ξεχωριστά, για ένα kernel. Αυτό επιτυγχάνεται αντιμετωπίζοντας τα χαρακτηριστικά του λογισμικού και τις τις βασικές παραμέτρους της αρχιτεκτονικής μαζί σαν ενιαίο πρόβλημα. Είναι η πρώτη φορά που μια μεθοδολογία αντιμετωπίζει τα παραπάνω προβλήματα με αυτό τον τρόπο. Οι προτεινόμενες μεθοδολογίες εκμεταλλεύονται τα χαρακτηριστικά του προγράμματος εισόδου. Η δομή του εκάστοτε αλγορίθμου (π.χ. ο FFT αποτελείται από πράξεις πεταλούδων ενώ ο αλγόριθμος αφαίρεσης θορύβου - Gauss Blur αποτελείται από πράξεις μάσκας στοιχείων), τα ιδιαίτερα χαρακτηριστικά του (π.χ. συμμετρία Toeplitz πίνακα), η ύπαρξη προτύπων-patterns (π.χ. στοιχεία πινάκων πολλαπλασιάζονται με μάσκα), η επαναχρησιμοποίηση των δεδομένων, η παραγωγή-κατανάλωση ενδιάμεσων αποτελεσμάτων και η παραλληλία του αλγορίθμου, αντιμετωπίζονται μαζί σαν ενιαίο πρόβλημα. Οι προτεινόμενες μεθοδολογίες εκμεταλλεύονται τις βασικές παραμέτρους της αρχιτεκτονικής. Η αρχιτεκτονική της μνήμης (π.χ. κοινή L2, L3), το πλήθος των καταχωρητών, ο αριθμός των κρυφών μνημών δεδομένων, τα μεγέθη, οι συσχετιστικότητες (assosiativity) και τα μεγέθη των γραμμών των κρυφών μνημών, ο αριθμός των λειτουργικών μονάδων, ο αριθμός των λειτουργικών μονάδων που λειτουργούν παράλληλα και ο αριθμός των πυρήνων (cores) του επεξεργαστή, αντιμετωπίζονται μαζί σαν ενιαίο πρόβλημα. Με την αξιοποίηση των χαρακτηριστικών του εκάστοτε αλγορίθμου και των παραμέτρων της αρχιτεκτονικής, αποκλείονται πιθανές λύσεις και ο χώρος εξερεύνησης μειώνεται ραγδαία (τάξεις μεγέθους). Στη παρούσα διδακτορική διατριβή, αναπτύχθηκαν μεθοδολογίες αύξησης της ταχύτητας του λογισμικού α) του Πολλαπλασιασμού Πίνακα επί Πίνακα (ΠΠΠ), β) του Πολλαπλασιασμού Πίνακα επί διάνυσμα (ΠΠΔ), γ) του Fast Fourier Transform (FFT), δ) του αλγορίθμου Canny και του μετασχηματισμού του Hough (αλγόριθμοι ανίχνευσης ακμών και ευθειών αντίστοιχα). Επίσης, αναπτύχθηκε μεθοδολογία μεταγλώττισης η οποία εκμεταλλεύεται τα χαρακτηριστικά του λογισμικού και τις παραμέτρους της ιεραρχίας μνήμης. Η μεθοδολογία μπορεί να εφαρμοστεί σε πυρήνες λογισμικού, στους οποίους α) τα μονοπάτια εκτέλεσης είναι γνωστά κατά τη μεταγλώττιση και συνεπώς δεν εξαρτώνται από τα δεδομένα, β) οι δείκτες όλων των sub- scripts να είναι γραμμικές εξισώσεις των iterators (που ισχύει στις περισσότερες περιπτώσεις). Οι μεθοδολογίες αφορούν ενσωματωμένους και γενικού σκοπού επεξεργαστές (χρήση μονάδας SIMD για περαιτέρω αύξηση της ταχύτητας). Ακολουθεί σύντομη περίληψη αυτών. Μεθοδολογία αύξησης της ταχύτητας του Πολλαπλασιασμού Πίνακα επί Πίνακα (ΠΠΠ): Αναπτύχθηκε μεθοδολογία αύξησης της ταχύτητας του ΠΠΠ για α) μονοπύρηνους επεξεργαστές (1 core), β) επεξεργαστές με πολλούς πυρήνες οι οποίοι συνδέονται με κοινή μνήμη. Η προτεινόμενη μεθοδολογία χωρίζει του πίνακες του αλγορίθμου σε μικρότερους οι οποίοι χωράνε στις κρυφές μνήμες και στο αρχείο καταχωρητών. Είναι η πρώτη φορά για τον ΠΠΠ που εισάγονται εξισώσεις οι οποίες αξιοποιούν τα associativities των κρυφών μνημών. Για τη πλήρη αξιοποίηση της ιεραρχίας της μνήμης προτείνεται νέος τρόπος αποθήκευσης των στοιχείων στη κύρια μνήμη (data array layout). Επίσης, προτείνεται διαφορετικός χρονοπρογραμματισμός σε επίπεδο στοιχείων και σε επίπεδο υπό-πινάκων. Η προτεινόμενη μεθοδολογία επιτυγχάνει από 1.1 έως 3.5 φορές μικρότερο χρόνο εκτέλεσης από τη βιβλιοθήκη του ATLAS, η οποία αποτελεί μια από τις ταχύτερες βιβλιοθήκες. Μεθοδολογία αύξησης της ταχύτητας του Fast Fourier Transform (FFT): Αναπτύχθηκε μεθοδολογία αύξησης της ταχύτητας του FFT αξιοποιώντας πλήρως τα ιδιαίτερα χαρακτηριστικά του αλγορίθμου και τις παραμέτρους της ιεραρχίας της μνήμης. Το διάγραμμα ροής δεδομένων (Data Flow Graph – DFG) του FFT, χωρίζεται σε πρότυπα (patterns) και σε υπό- FFTs. Κάθε πρότυπο, αποτελείται από πεταλούδες, σύμφωνα με το πλήθος των καταχωρητών του επεξεργαστή. Η επιλογή των πεταλούδων κάθε προτύπου έχει γίνει με τέτοιο τρόπο ώστε να μεγιστοποιείται η παραγωγή-κατανάλωση των ενδιάμεσων αποτελεσμάτων. Η σειρά εκτέλεσης των προτύπων είναι αυτή η οποία δίνει τη μέγιστη επαναχρησιμοποίηση των συντελεστών του FFT. Ο DFG του FFT χωρίζεται σε υπό-FFTs σύμφωνα με τον αριθμό και τα μεγέθη των κρυφών μνημών δεδομένων. Η προτεινόμενη μεθοδολογία δίνει από 1.1 μέχρι 1.8 φορές μικρότερο χρόνο εκτέλεσης από τη βιβλιοθήκη του FFTW, η οποία παρέχει ταχύτατο χρόνο εκτέλεσης. Είναι η πρώτη φορά για τον FFT που μια μεθοδολογία λαμβάνει υπόψη τις παραμέτρους της ιεραρχίας μνήμης και του αρχείου καταχωρητών. Μεθοδολογία αύξησης της ταχύτητας του Πολλαπλασιασμού Πίνακα επί Διάνυσμα (ΠΠΔ) για Toeplitz, Bisymetric (BT), Toeplitz (Τ) και κανονικούς πίνακες: Αναπτύχθηκε μεθοδολογία αύξησης της ταχύτητας του ΠΠΔ. Οι παραπάνω πίνακες έχουν ιδιαίτερη δομή, μικρό αριθμό διαφορετικών στοιχείων και μεγάλη επαναχρησιμοποίηση, χαρακτηριστικά τα οποία αξιοποιούνται πλήρως. Η προτεινόμενη μεθοδολογία χωρίζει τους πίνακες του αλγορίθμου σε μικρότερους οι οποίοι χωράνε στις κρυφές μνήμες και στο αρχείο καταχωρητών σύμφωνα με τον αριθμό τα μεγέθη και τα associativities των κρυφών μνημών. Για τη πλήρη αξιοποίηση της ιεραρχίας μνήμης προτείνεται νέος τρόπος αποθήκευσης των στοιχείων του πίνακα (data array layout) στη κύρια μνήμη. Η προτεινόμενη μεθοδολογία χρησιμοποιεί τον κανονικό αλγόριθμο ΠΠΔ (γραμμή επί στήλη). Ωστόσο, για BT και T πίνακες, ο ΠΠΔ μπορεί να υλοποιηθεί με χρήση του FFT επιτυγχάνοντας μικρότερη πολυπλοκότητα για μεγάλα μεγέθη πινάκων (έγινε ανάλυση και σύγκριση των δύο αλγορίθμων θεωρητικά και πειραματικά). Η προτεινόμενη μεθοδολογία για κανονικούς πίνακες συγκρίνεται με τη βιβλιοθήκη του ATLAS, επιτυγχάνοντας από 1.2 μέχρι 4.4 φορές μικρότερο χρόνο εκτέλεσης. Μεθοδολογία αύξησης της ταχύτητας του αλγόριθμου ανίχνευσης ακμών και ευθειών (αλγόριθμος του Canny και μετασχηματισμός του Hough): Αναπτύχθηκε μεθοδολογία η οποία επιτυγχάνει i) μικρότερο αριθμό εντολών ανάγνωσης/εγγραφής και διευθυνσιοδότησης, ii) μικρότερο αριθμό προσβάσεων και αστοχιών στην ιεραρχία μνήμης και iii) μικρότερο μέγεθος απαιτούμενης μνήμης του αλγορίθμου, εν συγκρίσει με την βιβλιοθήκη OpenCV η οποία παρέχει ταχύτατο χρόνο εκτέλεσης στους αλγορίθμους επεξεργασίας εικόνων. Τα παραπάνω επιτυγχάνονται: α) αξιοποιώντας την παραγωγή-κατανάλωση των στοιχείων των πινάκων και την παραλληλία του αλγορίθμου - τα τέσσερα kernels του Canny συγχωνεύονται σε ένα, διασωληνώνοντας (pipelining) τους πυρήνες για να διατηρηθούν οι εξαρτήσεις των δεδομένων, β) μειώνοντας τον αριθμό και το μέγεθος των πινάκων, γ) γράφοντας τα δεδομένα σε νέους μειωμένων διαστάσεων πίνακες με κυκλικό τρόπο, δ) χωρίζοντας τους πίνακες σε μικρότερους οι οποίοι χωράνε στο αρχείο καταχωρητών και στη κρυφή μνήμη δεδομένων σύμφωνα με το μέγεθος των κρυφών μνημών και του associativity, ε) βρίσκοντας τον βέλτιστο τρόπο αποθήκευσης των πινάκων (data array layout) στην κύρια μνήμη σύμφωνα με τη συσχετιστικότητα (associativity) της κρυφής μνήμης. Η προτεινόμενη μεθοδολογία δίνει από 1.27 μέχρι 2.2 φορές μικρότερο χρόνο εκτέλεσης από τη βιβλιοθήκη OpenCV (αναπτύχθηκε από την Intel και είναι γραμμένη σε χαμηλό επίπεδο), η οποία παρέχει ταχύτατο χρόνο εκτέλεσης. Μεθοδολογία μεταγλώττισης: Αναπτύχθηκε μεθοδολογία μεταγλώττισης η οποία αντιμετωπίζει τα προβλήματα εύρεσης χρονοπρογραμματισμών με τον ελάχιστο αριθμό i) προσβάσεων στην κρυφή μνήμη δεδομένων L1, ii) προσβάσεων στην κρυφή μνήμη L2, iii) προσβάσεων στην κύρια μνήμη, iv) πράξεων διευθυνσιοδότησης, μαζί σαν ενιαίο πρόβλημα και όχι ξεχωριστά, για ένα kernel. Η προτεινόμενη μεθοδολογία λαμβάνει ως είσοδο ker- nels σε C-κώδικα και παράγει νέα επιτυγχάνοντας είτε υψηλή απόδοση είτε τον ελάχιστο αριθμό προσβάσεων σε δεδομένη μνήμη. Αρχικά βρίσκεται ο χώρος εξερεύνησης με βάση τα χαρακτηριστικά του λογισμικού. Ο χώρος εξερεύνησης περιγράφεται από μαθηματικές εξισώσεις και ανισότητες οι οποίες προέρχονται από τα subscripts των πινάκων, τους iterators, τα όρια των βρόχων και τις εξαρτήσεις των δεδομένων. Αυτός ο χώρος εξερεύνησης δεν μπορεί να παραχθεί με την εφαρμογή υπαρχόντων μετασχηματισμών στον αρχικό C-κώδικα. Κατόπιν, ο χώρος εξερεύνησης μειώνεται τάξεις μεγέθους εφαρμόζοντας διάδοση περιορισμών (constraint propagation) των παραμέτρων του λογισμικού και αυτών της αρχιτεκτονικής της μνήμης. Το αρχείο καταχωρητών (register file) και τα μεγέθη των κρυφών μνημών αξιοποιούνται πλήρως παράγοντας ανισότητες για κάθε μνήμη οι οποίες περιέχουν α) τα μεγέθη των tiles που απαιτούνται για κάθε πίνακα, β) το σχήμα κάθε tile. Επίσης, βρίσκεται ο βέλτιστος τρόπος αποθήκευσης των στοιχείων των πινάκων στη κύρια μνήμη, σύμφωνα με τη συσχετιστικότητα (associativity) των κρυφών μνημών. Η προτεινόμενη μεθοδολογία εφαρμόστηκε σε 5 ευρέως διαδεδομένους αλγορίθμους και επιτυγχάνει αύξηση της ταχύτητας (speedup) από 2 έως 18 φορές (έγινε σύγκριση του αρχικού C κώδικα και του C κώδικα έπειτα από την εφαρμογή της προτεινόμενης μεθοδολογίας – η μεταγλώττιση έγινε με τον gcc compiler). / The existing state of the art (SOA) compilers, have 3 major disadvantages. Firstly, the back-end compiler phases - subproblems (e.g. transformations, scheduling, register allocation) are optimized separately; these subproblems depend on each other and they should be optimized together as one problem and not separately. Secondly, the existing SOA compilers do not effectively utilize the software characteristics (e.g. algorithm structure, data reuse). Thirdly, they do not effectively utilize the hardware parameters. In this PhD dissertation, new methodologies have been developed speeding up software kernels, by solving the sub-problems of finding the schedules with the minimum numbers of i) L1 data cache accesses, ii) L2 data cache accesses, iii) main memory accesses and iv) addressing instructions, as one problem and not separately. This is achieved by fully exploiting the software information and the memory hierarchy parameters. This is the first time a methodology optimizes the above sub-problems in this way. The proposed methodologies fully utilize the software characteristics. The algorithm structure (e.g. FFT data flow graph consists of butterfly operations while the gauss blur algorithm consists of array mask operations), the algorithm individual characteristics (e.g. symmetry of Toeplitz matrix), the data patterns (e.g. matrix elements are multiplied by a mask), data reuse, production-consumption of intermediate results and algorithm's parallelism, are utilized as one problem and not separately. The proposed methodologies fully utilize the major architecture parameters. The memory archi- tecture (e.g. shared L2/L3 cache), the size of the register file, the number of the levels of data cache hierarchy, the data cache sizes, the data cache associativities, the data cache line sizes, the number of the function units, the number of the function units can run in parallel and the number of the CPU cores are utilized as one problem and not separately. By utilizing the hardware and software constraints the exploration space is orders of magnitude decreased. In this PhD dissertation, new speeding-up methodologies are developed for i) Matrix Matrix Multi- plication (MMM) algorithm, ii) Matrix Vector Multiplication (MVM) algorithm, iii) Fast Fourier Trans- form (FFT), iv) Canny algorithm and Hough Transform. Also, a new compilation methodology which fully exploits the memory architecture and the software characteristics, is developed. This methodology can be applied in software kernels whose i) execution paths are known at compile time and thus they do not depend on the data, ii) all array subscripts are linear equations of the iterators (which in most cases do). The above methodologies refer to both embedded and general purpose processors (usage of the SIMD technology). The summary of the above methodologies is given below. A Methodology for speeding-up Matrix Matrix Multiplication (MMM) algorithm: A new methodol- ogy for Matrix Matrix Multiplication using SIMD (Single Instruction Multiple Data) unit and not, at one and more cores having a shared cache, is presented. The proposed methodology partitions the MMM matrices into smaller sub-matrices fitting in the data cache memories and into register file according to the memory hierarchy architecture parameters. This is the first time for MMM algorithm that equations containing the data cache associativity values, are given. To fully utilize the memory hierarchy, a new the data array layout is proposed. The proposed methodology is from 1.1 up to 3.5 times faster than one of the SOA software libraries for linear algebra, ATLAS. A Fast Fourier Transform (FFT) speeding-up methodology: A new Fast Fourier Transform method- ology is presented which fully utilizes the individual algorithm characteristics and the memory hierarchy architecture parameters. FFT data flow graph (DFG) is partitioned into patterns and into sub-FFTs. Each pattern consists of butterflies according to the number of the registers. The selection of the exact butter- flies each pattern contains, has been made by maximizing the production-consumption of the butterflies intermediate results. Also, the patterns are executed in that order, minimizing the data reuse of the FFT twiddle factors. The FFT data flow graph is partitioned into sub-FFTs according to the number of the levels and the sizes of data cache. The proposed methodology is faster from 1.1 up to 1.8 times in con- trast to the SOA FFT library, FFTW. This is the first time that an FFT methodology fully utilizes the memory hierarchy architecture parameters. A methodology for speeding-up Matrix Vector Multiplication (MVM) algorithm for regular, Toeplitz and Bisymmetric Toeplitz matrices: A new methodology for MVM including different types of matrices, is presented. The above matrices have a special structure, a small number of different elements and large data reuse. The proposed methodology partitions the MVM matrices into smaller sub-matrices fitting in the data cache memories and into register file according to the memory hierarchy architecture parameters. To fully utilize the memory hierarchy, a new data array layout is proposed. The proposed methodology uses the standard algorithm for matrix vector multiplication, i.e. each row of A is multiplied by X. However, for Bisymmetric Toeplitz (BT) and Toeplitz (T) matrices, MVM can also be implemented by using FFT; although in this paper we use the standard MVM algorithm, we show that for large input sizes, the MVM using FFT performs much better. The proposed methodology achieves speedup from 1.2 up to 4.4 over the SOA libraries, ATLAS. A Methodology for Speeding Up Edge and Line Detection Algorithms: A new Methodology for Speeding Up Edge and Line Detection Algorithms focusing on memory architecture utilization is pre- sented. This methodology achieves i) a smaller number of load/store and arithmetic instructions, ii) a smaller number of data cache accesses and data cache misses in memory hierarchy and iii) a smaller algorithm memory size, in contrast to the SOA library of OpenCV. This is achieved by: i) utilizing the production-consumption of intermediate results - merging all Canny kernels to one and pipelining the kernels to comply with the data dependences, ii) reducing the number and the size of the arrays, iii) writing the data into the new reduced size arrays in a circular way, iv) applying loop tiling for the register file and data cache, according to the size of the memories and associativity and v) finding the data arrays layout according to the data cache associativity. The proposed methodology achieves speedup from 1.27 up to 2.2 over the OpenCV SOA library. Compilation methodology: A new compilation methodology which fully exploits the memory archi- tecture and the software characteristics is presented. This is the first time that a methodology optimizes the subproblems explained above as one problem and not separately, for a loop-kernel. The proposed methodology takes as input C-code kernels and it produces new software kernels with a new iteration space, which may not be given by applying existing compiler transformations to original code. Firstly, the exploration space is found according to the s/w characteristics; it is described by mathematical equations and inequalities that are derived from the array subscripts, the combination of common array references, loop iterators, loop bounds and data dependences. Then, the exploration space is orders of magnitude decreased by applying constraint propagation of the h/w and s/w parameters. The register file and the data cache sizes are fully exploited by producing register file and data cache inequalities which contain i) the tiles sizes of each array, ii) the shape of each array tile. Also, new data array layouts are found, according to the data cache associativity. The final schedule is found by choosing the best combination of the number of i) L1 data cache accesses, ii) L2 data cache accesses, iii) main memory data accesses and iv) addressing instructions. The proposed methodology is evaluated to five well-known algorithms and speedups from 2 up to 18 over the target gcc compiler are obtained.

Η εργασία αυτή ασχολείται με την υλοποίηση ενός μεταφραστή για το μοντέλο παράλληλου προγραμματισμού OpenMP. Το μοντέλο αυτό χρησιμοποιείται για την υλοποίηση παράλληλων εφαρμογών για την αρχιτεκτονική κοινής μνήμης, και δίνει έμφαση στην ευκολία του προγραμματισμού και την μεταφερσιμότητα των παράλληλων εφαρμογών που αναπτύσσονται μ’ αυτό. Στην εργασία αυτή παρουσιάζεται η σχεδίαση και η υλοποίηση ενός μεταγλωττιστή παράλληλων εφαρμογών OpenMP για τη γλώσσα προγραμματισμού C σύμφωνα με την έκδοση 2.0 του προτύπου OpenMP. Ο μεταγλωττιστής που υλοποιήθηκε ανήκει στην κατηγορία των μεταφραστών, δηλαδή μεταφράζει τον πηγαίο κώδικα σε γλώσσα προγραμματισμού C με τις επεκτάσεις OpenMP, σε ισοδύναμο πηγαίο κώδικα σε γλώσσα προγραμματισμού C, στον οποίο οι επεκτάσεις OpenMP έχουν αντικατασταθεί από ισοδύναμα τμήματα κώδικα τα οποία χρησιμοποιούν κλήσεις βιβλιοθήκης νημάτων για την υλοποίηση του παραλληλισμού. Ο μεταφραστής έχει σχεδιαστεί με τέτοιο τρόπο ώστε να είναι μεταφέρσιμος, υποστηρίζοντας πολλαπλές πλατφόρμες εκτέλεσης, και επεκτάσιμος, υποστηρίζοντας πολλαπλές βιβλιοθήκες νημάτων κατά τη μετάφραση των οδηγιών OpenMP. Η υλοποίηση του μεταφραστή έγινε στη γλώσσα προγραμματισμού Java, χρησιμοποιώντας το γλωσσικό εργαλείο ANTLR για την υλοποίηση του λεκτικού και συντακτικού αναλυτή. Ο μεταφραστής συνοδεύεται, επίσης, από μια βιβλιοθήκη χρόνου εκτέλεσης, η οποία περιέχει τις συναρτήσεις που ορίζονται από το πρότυπο OpenMP v2.0, καθώς και άλλες συναρτήσεις που είναι απαραίτητες για την εκτέλεση των μεταφρασμένων παράλληλων εφαρμογών. Επίσης, στη βιβλιοθήκη υλοποιούνται οι πολιτικές χρονοδρομολόγησης, επιτρέπωντας εύκολα την υλοποίηση κάποιας νέας πολιτικής. Η βιβλιοθήκη έχει υλοποιηθεί σε γλώσσα προγραμματισμού C. Στα πλαίσια της εργασίας αυτής, έχει υλοποιηθεί η υποστήριξη των βιβλιοθηκών νημάτων POSIX και NANOS σε πολυεπεξεργαστικά συστήματα κοινής μνήμης, καθώς και οι πολιτικές χρονοδρομολόγησης που ορίζονται στο πρότυπο OpenMP v2.0. / The subject of this thesis is the implementation of a translator for the OpenMP parallel programming model. This model is used for the development of parallel applications for the shared memory model and emphasizes on the ease of programming and the portability of the applications developed with it. This thesis describes the design and the implementatino of a compiler for OpenMP parallel applications for the C programming language according to version 2.0 of the OpenMP model. The compiler that has been implemented belongs to the translator class, that is translates the source code in C programming language with the OpenMP extensions to equivalent source code in C programming language where the OpenMP extensions have been replaced with equivalent code segments which use thread library calls to implement the parallelism. The translator has been designed in order to be portable, supporting multiple execution platforms, and extensible, supporting multiple thread libraries during the translation of the OpenMP directives. The translator has been implemented using the Java language and using the language tool ANTLR for the implementation of the lexer and the parser. The translator comes with a run-time library, which contains all of the functions which are defined by the OpenMP v2.0, as well as other functions which are needed for the execution of the translated parallel applications. Also, the library contains the scheduling policies allowing easy implementation of a new one. The library has been implemented using the C language. The current implementation supports the POSIX and NANOS thread libraries in shared memory SMPs, as well as all the scheduling policies defined in OpenMP v2.0

Les applications informatiques sont de plus en plus présentes dans nos vies. Pour les applications critiques (médecine, transport, . . .), les conséquences d’une erreur informatique ont un coût inacceptable, que ce soit sur le plan humain ou financier. Une des méthodes pour éviter la présence d’erreurs dans les programmes est la vérification déductive. Celle-ci s’applique à des programmes écrits dans des langages de haut-niveau transformés, par des compilateurs, en programmes écrits en langage machine. Les compilateurs doivent être corrects pour ne pas propager d’erreurs au langage machine. Depuis 2005, les processeurs multi-coeurs se sont répandus dans l’ensemble des systèmes informatiques. Ces architectures nécessitent des compilateurs et des preuves de correction adaptées. Notre contribution est l’extension modulaire d’un compilateur vérifié pour un langage parallèle ciblant des architectures parallèles multi-coeurs. Les spécifications des langages (et leurs sémantiques opérationnelles) présents aux divers niveaux du compilateur ainsi que les preuves de la correction du compilateur sont paramétrées par des modules spécifiant des éléments de parallélisme tels qu’un modèle mémoire faible et des notions de synchronisation et d’ordonnancement entre processus légers. Ce travail ouvre la voie à la conception d’un compilateur certifié pour des langages parallèles de haut-niveau tels que les langages à squelettes algorithmiques. / Nowadays, we are using an increasing number of computer applications. Errors in critical applications (medicine, transport, . . .) may carry serious health or financial issues. Avoiding errors in programs is a challenge and may be achieved by deductive verification. Deductive verification applies to program written in a high-level languages, which are transformed into machine language by compilers. These compilers must be correct to ensure the nonpropagation of errors to machine code. Since 2005, multicore processors have spread in all electronic devices. So, these architectures need adapted compilers and proofs of correctness. Our work is the modular extension of a verified compiler for parallel languages targeting multicore architectures. Specifications of these languages (and their operational semantics) needed at all levels of the compiler and proofs of correctness of this compiler are parameterized by modules specifying elements of parallelism such as a relaxed memory model and notions of synchronization and scheduling between threads. This work is the first step in the conception of a certified compiler for high-level parallel languages such as algorithmic skeletons.

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

Οι σημερινές εφαρμογές έχουν ολοένα και μεγαλύτερες ανάγκες επεξεργαστικής ισχύος προκειμένου να εκτελεστούν σε συντομότερο χρονικό διάστημα. Για να την ικανοποίηση αυτών των χρονικών περιορισμών απαιτείται η ανάπτυξη βελτιστοποιημένων τεχνικών σχεδιασμού. Το αντικείμενο της παρούσας διατριβής σχετίζεται με την ανάπτυξη αρχιτεκτονικών και τεχνικών μεταφραστών με σκοπό την γρηγορότερη τροφοδότηση του επεξεργαστή με δεδομένα από την ιεραρχία μνήμης. α) Μεθοδολογία επιτάχυνσης εκτέλεσης εφαρμογής πολλαπλασιασμού πινάκων Παρουσιάζεται μία μεθοδολογία που βασίζεται στην τοπικότητα των δεδομένων με σκοπό την επιτάχυνση εκτέλεσης του πολλαπλασιασμού πινάκων. Μετά από διερεύνηση, παράγεται ο βέλτιστος τρόπος χρονοπρογραμματισμού των προσπελάσεων στη μνήμη λαμβάνοντας υπόψη την τοπικότητα των δεδομένων και τα μεγέθη των επιπέδων ιεραρχίας μνήμης. Ο χρόνος διερεύνησης είναι σύντομος καθώς απορρίπτονται όλες οι μη-βέλτιστες λύσεις. Η προτεινόμενη μεθοδολογία συγκρίνεται με άλλες υπάρχουσες και παρατηρείται αύξηση της απόδοσης μέχρι 55%. β)Mεθοδολογία αποδοτικής υλοποίησης του Fast Fourier Transform (FFT) Παρουσιάζεται μια νέα μεθοδολογία, που επιτυγχάνει βελτιωμένη απόδοση στην υλοποίηση του FFT, έχοντας ως γνώμονα την ελαχιστοποίηση των προσπελάσεων που πραγματοποιούνται στα δεδομένα. Η προτεινόμενη μεθοδολογία έχει σημαντικά πλεονεκτήματα. Πρώτον, την πλήρη αξιοποίηση της παραγωγής και της κατανάλωσης των αποτελεσμάτων των πεταλούδων του FFT αλγορίθμου, της επαναχρησιμοποίησης δεδομένων και της συμμετρίας των twiddle συντελεστών του FFT αλγορίθμου. Δεύτερον, η βέλτιστη λύση χρονοπρογραμματισμού βρίσκεται λαμβάνοντας υπόψη τόσο τον αριθμό των καταχωρητών, όσο και το μέγεθος της κρυφής μνήμης κάθε επιπέδου, αναζητώντας μόνο τον αριθμό του επιπέδου του tiling του FFT. Τρίτον, ο χρόνος μετάφρασης και το μέγεθος του πηγαίου κώδικα είναι πολύ μικροί συγκρινόμενοι με την SOA βιβλιοθήκη υλοποίησης του FFT αλγορίθμου, την FFTW. Η προτεινόμενη μεθοδολογία επιτυγχάνει αύξηση της απόδοσης μέχρι και 63% σε σχέση με την βιβλιοθήκη FFTW. γ)Ανάπτυξη Αρχιτεκτονικών για Διαχείριση Μνήμης Παρουσιάζεται μια αποσυζευγμένη αρχιτεκτονική επεξεργαστών με μια ιεραρχία μνήμης που αποτελείται μόνο από μνήμες scratch-pad, και μια κύρια μνήμη. Η αρχιτεκτονική αυτή εκμεταλλεύεται τα οφέλη των scratch-pad μνημών και τον παραλληλισμό μεταξύ της επεξεργασίας δεδομένων και υπολογισμού διευθύνσεων. Η αρχιτεκτονική συγκρίνεται στην απόδοση με την αρχιτεκτονική MIPS με cache και με scratch-pad ιεραρχίες μνήμης και παρουσιάζεται η υψηλότερη απόδοσή της. Τα πειραματικά αποτελέσματα δείχνουν ότι η απόδοση αυξάνεται μέχρι 3,7 φορές. Στη συνέχεια γίνεται περαιτέρω έρευνα σε αρχιτεκτονικές με Scratch-pad μνήμες. Παρουσιάζεται μια αρχιτεκτονική που είναι σε θέση να παρέχει πληροφορίες για το ακριβές περιεχόμενο δεδομένων της scratch-pad, κατά τη διάρκεια της εκτέλεσης και μπορεί επίσης να εκτελέσει όλες τις απαραίτητες ενέργειες για την τοποθέτηση των νέων δεδομένων στη scratch-pad. Με αυτόν τον τρόπο, αξιοποιείται η επαναχρησιμοποίηση δεδομένων που εμφανίζεται τυχαία και δεν μπορεί να προσδιοριστεί από το μεταγλωττιστή. Συγκρίνεται με αρχιτεκτονική MIPS που περιέχει cache και με scratch-pad μνήμες και αναδεικνύεται η μεγαλύτερη απόδοσή της. Τα πειραματικά αποτελέσματα δείχνουν ότι η απόδοση αυξάνεται μέχρι 5 φορές έναντι των αρχιτεκτονικών με scratch-pad και 2.5 φορές έναντι των αρχιτεκτονικών με cache. / Modern applications have indence needs in processing power in order to be executed in short time. For satisfying the time limits, there have to be generated new techniques for optimizing the designs. The object of the present thesis is about developing new compiler techniques and hardware architectures which aim to transfer data faster, from the memory hierarchy to the CPU. a) Methdology for accelerating the execution of matrix multiplications A new methodology using the standard MMM algorithm is presented, achieving improved performance by focusing on data locality (both temporal and spatial). This methodology finds the scheduling which conforms with the optimum memory management. The scheduling used for the tile level is different from the element level’s one, having better data locality, suited to the sizes of memory hierarchy. Its exploration time is short, because it searches only for the number of the level of tiling used for finding the best tile size for each cache level. Compared with the best existing related work, which we implemented, better performance up to 55% β)Methodology for increasing performance on Fast Fourier Transform (FFT) A new methodology is presented based on minimizing the memory accesses for FFT. It exploits, the production and comsumption of the FFT batterfly results and the reuse of data. The optimum scheduling solution is found taking into account the number of registers and the cache memory size. The compile time and source code size are short comparing to SOA library. The methodology performance gains are up to 63% comparing to FFTW library. γ)Ανάπτυξη Αρχιτεκτονικών για Διαχείριση Μνήμης 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 architecture is compared in performance with the MIPS architecture with cache and 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. Continuing, more research is done on Scratch-pad memories. We present an architecture that is able to provide 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 can not be identified by the compiler is exploited. It is compared with the MIPS architecture with cache and with scratch-pad memories showing its higher normalized performance. 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.

Το αντικείμενο της παρούσας διδακτορικής διατριβής εστιάζεται στην ανάπτυξη αποδοτικών τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα ολοκληρωμένα συστήματα αρχιτεκτονικών πίνακα. Χρησιμοποιήθηκαν εφαρμογές που κυριαρχούνται από δεδομένα για τον έλεγχο των μεθοδολογιών. Σκοπός είναι να βελτιστοποιηθεί η εκτέλεση των εφαρμογών ως προς χαρακτηριστικά των επαναπροσδιοριζόμενων συστημάτων όπως η απόδοση, ο αριθμός εντολών ανά κύκλο ρολογιού, η επιφάνεια ολοκλήρωσης και ο βαθμός χρησιμοποίησης των επεξεργαστικών πόρων. Αυτό επιτυγχάνεται με την εισαγωγή πρωτότυπων τεχνικών χαρτογράφησης αλλά και την εύρεση βέλτιστων αρχιτεκτονικών. Στο πρώτο τμήμα της διατριβής υλοποιήθηκε η έρευνα, ανάπτυξη και αυτοματοποίηση τεχνικών μεταγλώττισης για επαναπροσδιοριζόμενα συστήματα αρχιτεκτονικών πίνακα. Κύριο χαρακτηριστικό αυτών των αρχιτεκτονικών είναι ύπαρξη μεγάλου αριθμού επεξεργαστικών στοιχείων που δουλεύουν παράλληλα με αποτέλεσμα να επιταχύνουν την εκτέλεση εφαρμογών που εμφανίζουν παραλληλία πράξεων. Η λειτουργία τους σε ενσωματωμένα συστήματα είναι αυτή ενός συνεπεξεργαστή. Η έρευνα πάνω σε επαναπροσδιοριζόμενες αρχιτεκτονικές πίνακα έχει αποκτήσει μεγάλο ενδιαφέρον λόγω της ευελιξίας, της επεκτασιμότητας και της απόδοσής τους, ιδιαίτερα σε εφαρμογές που κυριαρχούνται από δεδομένα. Η μεταγλώττιση, όμως, εφαρμογών πάνω σε αυτές χαρακτηρίζεται από υψηλή πολυπλοκότητα. Απαιτούνται κατάλληλα εργαλεία και ειδικές μεθοδολογίες χαρτογράφησης για την εκμετάλλευση των χαρακτηριστικών αυτών των αρχιτεκτονικών. Με αυτό το σκεπτικό, προτάθηκε μια πρωτότυπη επαναστοχεύσιμη μεθοδολογία χαρτογράφησης εφαρμογών, η οποία επιπλέον έχει αυτοματοποιηθεί με τη χρήση ενός πρότυπου εργαλείου μεταγλώττισης που στοχεύει σε ένα αρχιτεκτονικό παραμετρικό πρότυπο. Αποτέλεσμα ήταν η εύρεση των βέλτιστων αρχιτεκτονικών με βάσει την απόδοση, τον αριθμό των εντολών ανά κύκλο ρολογιού και το χρόνο εκτέλεσης του εργαλείου, για μια ομάδα εφαρμογών. Η αποδοτικότητα μιας επαναπροσδιοριζόμενης αρχιτεκτονικής πίνακα ως προς την ταχύτητα και το κόστος σε υλικό είναι δύσκολο να μετρηθεί, για αυτό έχουν υπάρξει λίγες έρευνες που μελετούν την επίδραση αρχιτεκτονικών παραμέτρων πάνω σε παράγοντες όπως η επιφάνεια ολοκλήρωσης και ο αριθμός εντολών ανά κύκλο ρολογιού. Επιπλέον, καμιά εργασία δεν έχει εξετάσει την επίδραση πολλαπλασιαστών ενσωματωμένων στα επεξεργαστικά στοιχεία των επαναπροσδιοριζόμενων αρχιτεκτονικών. Χρησιμοποιώντας την υπάρχουσα επαναστοχεύσιμη μεθοδολογία μεταγλώττισης και μια παραμετρική υλοποίηση της αρχιτεκτονικής σε γλώσσα περιγραφής υλικού, εξετάζουμε την επίδραση των πολλαπλασιαστών από τη μεριά της χαρτογράφησης και της αρχιτεκτονικής. Επίσης, περιγράφεται η πρωτότυπη μεθοδολογία χαρτογράφησης που εισήχθη με σκοπό την αποδοτική λειτουργία του αλγορίθμου 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.