Τεχνικές χρονοπρογραμματισμού σε βελτιστοποιητικούς μεταγλωττιστές
Μεταπτυχιακή διπλωματική εργασία
Author
Ανδρινόπουλος, Παναγιώτης Γ.
Date
2011-12Advisor
Καββαδίας, ΝικόλαοςKeywords
Μεταγλωττιστές ; Παραλληλισμός Επιπέδου Εντολών ; Γράφος ; Μετασχηματισμός γράφου ; Χρονοπρογραμματισμός εντολών ; ASAP ; ALAP ; Χρονοπρογραμματισμός λίστας ; Πολυπλοκότητα αλγορίθμων ; Βασικό ΜπλοκAbstract
Οι μεταγλωττιστές διαδραματίζουν αναμφίβολα κυρίαρχο ρόλο στην εξελικτική πορεία των υπολογιστικών συστημάτων, καθώς η ποιότητα του κώδικα που παράγει ένας μεταγλωττιστής, αντανακλά την αποδοτικότητα του ίδιου του υπολογιστικού συστήματος. Ένας μεταγλωττιστής μεταφράζει ουσιαστικά ένα πρόγραμμα από μια γλώσσα υψηλού επιπέδου σε μια γλώσσα μηχανής, επιχειρώντας τη βελτιστοποίηση του κώδικα που θα προκύψει, ώστε να επιτευχθεί η καλύτερη δυνατή απόδοση μιας εφαρμογής στο δεδομένο επεξεργαστή.
Η παρούσα διπλωματική εργασία, έχει ως θέμα τις «Τεχνικές χρονοπρογραμματισμού σε βελτιστοποιητικούς μεταγλωττιστές». Ειδικότερα, η εργασία αποτελείται από την παρουσίαση και την ανάλυση μεθόδων αποδοτικού χρονοπρογραμματισμού ενός προγράμματος, κάτω από περιορισμούς χρόνου και των διαθέσιμων πόρων του επεξεργαστή. Το ενδιαφέρον μας εστιάζεται στους γράφους προγραμμάτων και στους μετασχηματισμούς στους οποίους αυτοί υπόκεινται, προκειμένου να επιτευχθεί αποδοτικός χρονοπρογραμματισμός εντολών.
Μέσα από μια αναφορά σε γενικές έννοιες και ορισμούς στο αρχικό κεφάλαιο, επιδιώκεται μια εισαγωγή στον κόσμο των μεταγλωττιστών καθώς επίσης και στις τεχνικές χρονοπρογραμματισμού εντολών. Θέματα όπως η δέσμευση καταχωρητών, ο παραλληλισμός επιπέδου εντολών και τα διάφορα είδη εξαρτήσεων, εξετάζονται εκτενώς. Η μετάβαση στο κυρίως θέμα της διπλωματικής συντελείται στα αμέσως επόμενα κεφάλαια (2 και 3), όπου περιγράφεται αναλυτικά η διαδικασία του χρονοπρογραμματισμού μέσω μετασχηματισμών σε ένα γράφο προγράμματος, αφού πρώτα οριστεί το σύνολο των λογικών προτεραιοτήτων για το δεδομένο γράφο. Στο τρίτο κεφάλαιο παρατίθενται οι ανωτέρω μετασχηματισμοί για γράφους εξάρτησης δεδομένων, σε συνδυασμό με τους αντίστοιχους αλγορίθμους.
Στο τελευταίο κεφάλαιο η εργασία αναδεικνύει με παραδείγματα τους βασικούς αλγορίθμους χρονοπρογραμματισμού, ASAP και ALAP (για προβλήματα χωρίς περιορισμούς) καθώς και τον αλγόριθμο χρονοπρογραμματισμού λίστας (με περιορισμούς). Τέλος πραγματοποιείται μια σύντομη αναφορά στην περίπτωση χρονοπρογραμματισμού πολλαπλών γράφων σε ετερογενή συστήματα.
Abstract
There is no doubt that compilers play a dominant role in the evolutionary course of computing systems, as the quality of the code produced by a compiler reflects the efficiency of its own computing system. A compiler translates a program substantially from a high‐level language into a machine language, attempting to optimize the resulting code, to achieve the best possible performance of an application to a given processor.
The subject of this thesis is “Scheduling Techniques to Compilers for Optimization”. In particular, this thesis is constituded by the presentation and the analysis of efficient methods for program scheduling, under time constraints and available resources of the processor. Our interest is focused in program graphs and to the transformations of them, so that an efficient instruction scheduling to be achieved.
Through a reference to general concepts and definitions in the initial chapter, an introduction to the world of compilers is sought as well as with the techniques for instruction scheduling. Issues such as engagement of registers, instruction‐level parallelism and the different types of dependencies, are extensively examined. The transition to the main subject of this thesis takes place directly in the next chapters (2 and 3), where the instruction scheduling process is described analytically via transformations in a program graph, after the first set up of all rational priorities for the given graph. The third chapter sets out the above transformations, for data‐dependency graphs in combination with the corresponding algorithms.
The last chapter of this thesis sets off the basic scheduling algorithms via examples, ASAP and ALAP (for problems without restrictions) and the List Scheduling algorithm (with restrictions). Finally a short reference is realised, to the case of multiple graph scheduling onto heterogeneous systems.
Number of pages
85 σελ.Faculty
Σχολή Θετικών Επιστημών και ΤεχνολογίαςAcademic Department
Τμήμα Επιστήμης και Τεχνολογίας ΥπολογιστώνPost-graduate program
Επιστήμη και Τεχνολογία ΥπολογιστώνLanguage
GreekDescription
Μ.Δ.Ε. 12The following license files are associated with this item: