Τεχνικές χρονοπρογραμματισμού σε βελτιστοποιητικούς μεταγλωττιστές
Μεταπτυχιακή διπλωματική εργασία
Συγγραφέας
Ανδρινόπουλος, Παναγιώτης Γ.
Ημερομηνία
2011-12Επιβλέπων
Καββαδίας, ΝικόλαοςΘεματική επικεφαλίδα
Μεταγλωττιστές (Προγράμματα ηλεκτρονικών υπολογιστών)Λέξεις κλειδιά
Μεταγλωττιστές ; Παραλληλισμός Επιπέδου Εντολών ; Γράφος ; Μετασχηματισμός γράφου ; Χρονοπρογραμματισμός εντολών ; ASAP ; ALAP ; Χρονοπρογραμματισμός λίστας ; Πολυπλοκότητα αλγορίθμων ; Βασικό ΜπλοκΠερίληψη
Οι μεταγλωττιστές διαδραματίζουν αναμφίβολα κυρίαρχο ρόλο στην εξελικτική πορεία των υπολογιστικών συστημάτων, καθώς η ποιότητα του κώδικα που παράγει ένας μεταγλωττιστής, αντανακλά την αποδοτικότητα του ίδιου του υπολογιστικού συστήματος. Ένας μεταγλωττιστής μεταφράζει ουσιαστικά ένα πρόγραμμα από μια γλώσσα υψηλού επιπέδου σε μια γλώσσα μηχανής, επιχειρώντας τη βελτιστοποίηση του κώδικα που θα προκύψει, ώστε να επιτευχθεί η καλύτερη δυνατή απόδοση μιας εφαρμογής στο δεδομένο επεξεργαστή.
Η παρούσα διπλωματική εργασία, έχει ως θέμα τις «Τεχνικές χρονοπρογραμματισμού σε βελτιστοποιητικούς μεταγλωττιστές». Ειδικότερα, η εργασία αποτελείται από την παρουσίαση και την ανάλυση μεθόδων αποδοτικού χρονοπρογραμματισμού ενός προγράμματος, κάτω από περιορισμούς χρόνου και των διαθέσιμων πόρων του επεξεργαστή. Το ενδιαφέρον μας εστιάζεται στους γράφους προγραμμάτων και στους μετασχηματισμούς στους οποίους αυτοί υπόκεινται, προκειμένου να επιτευχθεί αποδοτικός χρονοπρογραμματισμός εντολών.
Μέσα από μια αναφορά σε γενικές έννοιες και ορισμούς στο αρχικό κεφάλαιο, επιδιώκεται μια εισαγωγή στον κόσμο των μεταγλωττιστών καθώς επίσης και στις τεχνικές χρονοπρογραμματισμού εντολών. Θέματα όπως η δέσμευση καταχωρητών, ο παραλληλισμός επιπέδου εντολών και τα διάφορα είδη εξαρτήσεων, εξετάζονται εκτενώς. Η μετάβαση στο κυρίως θέμα της διπλωματικής συντελείται στα αμέσως επόμενα κεφάλαια (2 και 3), όπου περιγράφεται αναλυτικά η διαδικασία του χρονοπρογραμματισμού μέσω μετασχηματισμών σε ένα γράφο προγράμματος, αφού πρώτα οριστεί το σύνολο των λογικών προτεραιοτήτων για το δεδομένο γράφο. Στο τρίτο κεφάλαιο παρατίθενται οι ανωτέρω μετασχηματισμοί για γράφους εξάρτησης δεδομένων, σε συνδυασμό με τους αντίστοιχους αλγορίθμους.
Στο τελευταίο κεφάλαιο η εργασία αναδεικνύει με παραδείγματα τους βασικούς αλγορίθμους χρονοπρογραμματισμού, ASAP και ALAP (για προβλήματα χωρίς περιορισμούς) καθώς και τον αλγόριθμο χρονοπρογραμματισμού λίστας (με περιορισμούς). Τέλος πραγματοποιείται μια σύντομη αναφορά στην περίπτωση χρονοπρογραμματισμού πολλαπλών γράφων σε ετερογενή συστήματα.
Περίληψη
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.
Αριθμός σελίδων
85 σελ.Σχολή
Σχολή Θετικών Επιστημών και ΤεχνολογίαςΑκαδημαϊκό Τμήμα
Τμήμα Επιστήμης και Τεχνολογίας ΥπολογιστώνΤίτλος Προγράμματος Μεταπτυχιακών Σπουδών
Επιστήμη και Τεχνολογία ΥπολογιστώνΓλώσσα
ΕλληνικάΠεριγραφή
Μ.Δ.Ε. 12Οι παρακάτω άδειες σχετίζονται με αυτό το τεκμήριο: