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

Abstract

This Ph.D. dissertation discusses a software profiling and optimization tool that infers source code optimizations for algorithms implemented in high level languages like C and MATLAB. Reuse distance analysis forms the main part of the optimization process. C has already been extensively used as the input specification on most similar systems. MATLAB is a high level array programming language used broadly for prototyping algorithms in scientific and engineering settings. Reuse distance analysis is the process of calculating the number of distinct data elements accessed between two consecutive uses of the same memory element during program execution. The notion of reuse distance is equivalent to temporal data reuse but in a machine independent manner. Reuse distance analysis provides quantitative measures of program locality that can be used to drive locality optimization. The optimizations proposed by the tool are mainly loop transformations which target the reduction of reuse distances and thus the improvement of temporal locality, the reduction of data cache misses and the improvement of the execution speed of a specific program. A framework for the efficient development of code analysis software has also been developed. This framework includes a tool for automatically generating the front end of analysis tools for a given language grammar expressed in the BNF notation. It also provides a domain specific language to concisely express queries on the internal representation generated by the front end. This language tackles the problem of writing complex code in a general purpose programming language in order to retrieve information from the internal representation. Both tools of this framework have been developed and used primarily for the construction of the proposed optimization tool. The required reuse distance analysis is always performed at C code level. To support MATLAB input sources, a MATLAB-to-C compiler has been developed. This compiler can relate the input MATLAB variables with output C code. Then reuse distance analysis is performed on the C code and the relevant optimization proposals are mapped back to the input MATLAB code. A thorough performance evaluation (in terms of execution time and cache performance) has been performed on six different algorithms that were optimized using the proposed tool. Measurements have been carried out on four different processors with ARM, MIPS and x86 ISAs and different memory hierarchies but also using a memory simulator. The results show that a reduction of memory accesses up to 42% has been achieved, leading to a speedup up to 3x for locality related optimizations and up to 68x for optimizations regarding the reduction of recomputations. Furthermore, the C code generated from the optimized MATLAB code, using MathWorks MATLAB Coder, is also optimized compared to the code that is generated from the original MATLAB code.

Στην παρούσα διδακτορική διατριβή παρουσιάζεται ένα εργαλείο για την εξαγωγή προτάσεων βελτιστοποίησης του πηγαίου κώδικα αλγορίθμων υλοποιημένων σε γλώσσες υψηλού επιπέδου και συγκεκριμένα στις γλώσσες 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.