Τεχνικές χρονοπρογραμματισμού σε βελτιστοποιητικούς μεταγλωττιστές

Abstract

Οι μεταγλωττιστές διαδραματίζουν αναμφίβολα κυρίαρχο ρόλο στην εξελικτική πορεία των υπολογιστικών συστημάτων, καθώς η ποιότητα του κώδικα που παράγει ένας μεταγλωττιστής, αντανακλά την αποδοτικότητα του ίδιου του υπολογιστικού συστήματος. Ένας μεταγλωττιστής μεταφράζει ουσιαστικά ένα πρόγραμμα από μια γλώσσα υψηλού επιπέδου σε μια γλώσσα μηχανής, επιχειρώντας τη βελτιστοποίηση του κώδικα που θα προκύψει, ώστε να επιτευχθεί η καλύτερη δυνατή απόδοση μιας εφαρμογής στο δεδομένο επεξεργαστή. Η παρούσα διπλωματική εργασία, έχει ως θέμα τις «Τεχνικές χρονοπρογραμματισμού σε βελτιστοποιητικούς μεταγλωττιστές». Ειδικότερα, η εργασία αποτελείται από την παρουσίαση και την ανάλυση μεθόδων αποδοτικού χρονοπρογραμματισμού ενός προγράμματος, κάτω από περιορισμούς χρόνου και των διαθέσιμων πόρων του επεξεργαστή. Το ενδιαφέρον μας εστιάζεται στους γράφους προγραμμάτων και στους μετασχηματισμούς στους οποίους αυτοί υπόκεινται, προκειμένου να επιτευχθεί αποδοτικός χρονοπρογραμματισμός εντολών. Μέσα από μια αναφορά σε γενικές έννοιες και ορισμούς στο αρχικό κεφάλαιο, επιδιώκεται μια εισαγωγή στον κόσμο των μεταγλωττιστών καθώς επίσης και στις τεχνικές χρονοπρογραμματισμού εντολών. Θέματα όπως η δέσμευση καταχωρητών, ο παραλληλισμός επιπέδου εντολών και τα διάφορα είδη εξαρτήσεων, εξετάζονται εκτενώς. Η μετάβαση στο κυρίως θέμα της διπλωματικής συντελείται στα αμέσως επόμενα κεφάλαια (2 και 3), όπου περιγράφεται αναλυτικά η διαδικασία του χρονοπρογραμματισμού μέσω μετασχηματισμών σε ένα γράφο προγράμματος, αφού πρώτα οριστεί το σύνολο των λογικών προτεραιοτήτων για το δεδομένο γράφο. Στο τρίτο κεφάλαιο παρατίθενται οι ανωτέρω μετασχηματισμοί για γράφους εξάρτησης δεδομένων, σε συνδυασμό με τους αντίστοιχους αλγορίθμους. Στο τελευταίο κεφάλαιο η εργασία αναδεικνύει με παραδείγματα τους βασικούς αλγορίθμους χρονοπρογραμματισμού, ASAP και ALAP (για προβλήματα χωρίς περιορισμούς) καθώς και τον αλγόριθμο χρονοπρογραμματισμού λίστας (με περιορισμούς). Τέλος πραγματοποιείται μια σύντομη αναφορά στην περίπτωση χρονοπρογραμματισμού πολλαπλών γράφων σε ετερογενή συστήματα.