Ανάλυση της απόστασης επαναχρησιμοποίησης δεδομένων σε επίπεδο πηγαίου κώδικα για την βελτιστοποίηση της τοπικότητας αναφοράς σε αλγορίθμους όπου κυριαρχούν βρόχοι επανάληψης

Abstract

Στην παρούσα διδακτορική διατριβή παρουσιάζεται ένα εργαλείο για την εξαγωγή προτάσεων βελτιστοποίησης του πηγαίου κώδικα αλγορίθμων υλοποιημένων σε γλώσσες υψηλού επιπέδου και συγκεκριμένα στις γλώσσες C και MATLAB. Βασικό μέρος της διαδικασίας εξαγωγής αυτών των προτάσεων αποτελεί η ανάλυση της απόστασης επαναχρησιμοποίησης δεδομένων. Η γλώσσα C έχει χρησιμοποιηθεί ευρέως σαν γλώσσα εισόδου στην πλειονότητα των συναφών εργασιών. Η γλώσσα MATLAB είναι μια υψηλού επιπέδου γλώσσα, η οποία απλοποιεί κατά πολύ τις πράξεις μεταξύ πινάκων (array language) και χρησιμοποιείται κατά κόρον για την πρωτοτυποποίηση αλγορίθμων από επιστήμονες και μηχανικούς. Η ανάλυση της απόστασης επαναχρησιμοποίησης δεδομένων αφορά τη μέτρηση του αριθμού των μοναδικών στοιχείων δεδομένων του κώδικα που μεσολαβούν μεταξύ μιας επαναχρησιμοποίησης δεδομένων. Οι προτάσεις βελτιστοποίησης που παράγει το προτεινόμενο εργαλείο αφορούν κατά κύριο λόγο μετασχηματισμούς βρόχων επανάληψης και έχουν ως στόχο την μείωση των αποστάσεων επαναχρησιμοποίησης δεδομένων και την επακόλουθη βελτίωση της χρονικής τοπικότητας αναφοράς, τη μείωση των αστοχιών της λανθάνουσας μνήμης δεδομένων και τελικά τη βελτίωση της ταχύτητας εκτέλεσης ενός αλγορίθμου. Στο πλαίσιο της διδακτορικής διατριβής αναπτύχθηκε επίσης ένα σύνολο διασυνδεδεμένων εργαλείων για την αυτόματη ανάπτυξη εργαλείων ανάλυσης και χειρισμού πηγαίου κώδικα, το οποίο περιλαμβάνει μια αυτόματη γεννήτρια εμπρόσθιων τμημάτων μεταγλωττιστών και μια γλώσσα προγραμματισμού ειδικού σκοπού για την εφαρμογή ερωτημάτων (query language) σε πηγαίο κώδικα. Τα εργαλεία αυτά αναπτύχθηκαν με σκοπό να χρησιμοποιηθούν για την κατασκευή του προτεινόμενου εργαλείου βελτιστοποίησης. Η γεννήτρια εμπρόσθιων τμημάτων παράγει έναν λεκτικό και συντακτικό αναλυτή για οποιαδήποτε δοθείσα γραμματική η οποία περιγράφεται με τη μορφή συμβολισμού BNF. Η γλώσσα ειδικού σκοπού μπορεί να χρησιμοποιηθεί για την εφαρμογή ερωτημάτων στο αφηρημένο συντακτικό δέντρο που παράγεται από το εμπρόσθιο τμήμα που δημιουργείται αυτόματα. Το προτεινόμενο εργαλείο πραγματοποιεί ανάλυση σε C κώδικα και όχι σε MATLAB. Για το λόγο αυτό αναπτύχθηκε ένας MATLAB-σε-C μεταγλωττιστής για την υποστήριξη πηγαίου κώδικα σε γλώσσα MATLAB. Τα αποτελέσματα της ανάλυσης αντιστοιχίζονται έπειτα στον αρχικό MATLAB κώδικα. Εκτός από τη χρήση του στο πλαίσιο λειτουργίας του προτεινόμενου εργαλείου, ο συγκεκριμένος μεταγλωττιστής έχει τη δυνατότητα να παράγει C κώδικα με δυναμικά δεσμευμένους πίνακες, ο οποίος έχει κάποιες ιδιαιτερότητες και πλεονεκτήματα σε σχέση με αντίστοιχες υλοποιήσεις της βιβλιογραφίας. Τέλος, αξιολογήθηκε η επίδοση (ως προς το χρόνο εκτέλεσης και την απόδοση των λανθανουσών μνημών) του βελτιστοποιημένου κώδικα χρησιμοποιώντας μια σειρά από ρεαλιστικούς αλγορίθμους σε τέσσερεις διαφορετικούς επεξεργαστές αρχιτεκτονικών ARM, MIPS και x86 με διαφορετικές ιεραρχίες μνήμης, καθώς και στον προσομοιωτή λανθανουσών μνημών Cachegrind για τρεις διαφορετικές ιεραρχίες μνήμης. Τα αποτελέσματα έδειξαν ότι ο βελτιστοποιημένος κώδικας επιτυγχάνει σημαντικές βελτιώσεις σε σχέση με την απόδοση του αρχικού κώδικα. Πιο συγκεκριμένα, επιτυγχάνεται μείωση των προσπελάσεων της κύριας μνήμης έως και 42%, με αντίστοιχη βελτίωση του χρόνου εκτέλεσης (speedup) έως και 3x για βελτιστοποιήσεις που αφορούν την τοπικότητα αναφοράς δεδομένων και έως 68x για βελτιστοποιήσεις που αφορούν την μείωση των περιττών επανυπολογισμών. Για την περίπτωση του MATLAB κώδικα, ο κώδικας C που παράγεται από τον βελτιστοποιημένο κώδικα MATLAB μέσω του MATLAB-σε-C μεταγλωττιστή MathWorks MATLAB Coder είναι επίσης αποδοτικότερος από αυτόν που παράγεται από την αρχική έκδοση του κώδικα MATLAB.