A Matlab to C vectorizing compiler exploiting custom instructions of targeted processors

Abstract

Στην παρούσα διδακτορική διατριβή παρουσιάζεται ένας μεταγλωττιστής της γλώσσας MATLAB ο οποίος παράγει κώδικα C αξιοποιώντας εντολές ειδικού σκοπού του εκάστοτε επεξεργαστή στόχου όπως εντολές επεξεργασίας πολλαπλών δεδομένων (SIMD) και βαθμωτές (scalar) εντολές μαθηματικών συναρτήσεων/λειτουργιών που υποστηρίζονται από το υλικό. Ο μεταγλωττιστής παράγει ANSI C κώδικα και οι εντολές ειδικού σκοπού αναπαρίστανται από εσωτερικές (intrinsic) συναρτήσεις επιτρέποντας τη συμβατότητα του μεταγλωττιστή σε οποιοδήποτε επεξεργαστή (και το μεταγλωττιστή του). Αρχικά, παρουσιάζεται ένα παραμετρικό μοντέλο επεξεργαστή, το οποίο χρησιμοποιείται για την περιγραφή των εντολών ειδικού σκοπού. Το μοντέλο αυτό επιτρέπει την περιγραφή εξειδικευμένων εντολών, λειτουργίες εισαγωγής δεδομένων σε διανύσματα (packing) για παράλληλη επεξεργασία και εσωτερικές δομές δεδομένων όπως οι τύποι δεδομένων των διανυσμάτων ενός επεξεργαστή. Το μοντέλο επεξεργαστή χρησιμοποιείται από έναν αλγόριθμο επιλογής εντολών (instruction selection) με σκοπό να αντιστοιχήσει τον πηγαίο κώδικα εισόδου με τις διαθέσιμες μονάδες του υλικού της αρχιτεκτονικής-στόχου. Το μοντέλο του επεξεργαστή χρησιμοποιείται επίσης από το στάδιο της εξαγωγής τύπων δεδομένων (type inference) ώστε να εξάγεται ο τύπος του αποτελέσματος των συναρτήσεων που αναπαριστόνται από εντολές ειδικού σκοπού. Το παραμετρικό μοντέλο επεξεργαστή διαμορφώνει ένα πλαίσιο μεταγλώττισης υποστηρίζοντας διαφορετικούς επεξεργαστές-στόχους κάτι που έχει ως αποτέλεσμα την παραγωγή βελτιστοποιημένου κώδικα για οποιαδήποτε αρχιτεκτονική. Στην συνέχεια, περιγράφεται η υποδομή του μεταγλωττιστή με έμφαση στα τμήματα υποστήριξης της παράλληλης επεξεργασίας δεδομένων και παραγωγής διανυσματικούCκώδικα. Αρχικά, παρουσιάζεται ο αλγόριθμος επιλογής εντολών ο οποίος αντιστοιχίζει τις εντολές και συναρτήσεις MATLAB με τις εντολές ειδικού σκοπού της αρχιτεκτονικής-στόχου. Ο αλγόριθμος επιλέγει την κατάλληλη από τις εντολές που περιλαμβάνονται στο μοντέλο του επεξεργαστή. Στη συνέχεια, λειτουργίες εισαγωγής και εξαγωγής δεδομένων σε μεταβλητές διανύσματα εισάγονται στην ενδιάμεση αναπαράσταση για να επιτρέψουν την παραγωγή κώδικα παράλληλης επεξεργασίας. Η διαδικασία αφορά την εισαγωγή των συγκεκριμένων λειτουργιών ώστε να μετατρέπονται τα δεδομένα σε κατάλληλη μορφή για παράλληλη επεξεργασία. Στη συνέχεια, ένας αλγόριθμος αρίθμησης των τοπικών μεταβλητών (localvalue numbering) εκτελείται με σκοπό την αφαίρεση από την ενδιάμεση αναπαράσταση των περιττών λειτουργιών εισαγωγής/εξαγωγής δεδομένων σε διανύσματα οι οποίες εισάγονται από το προηγούμενο στάδιο μεταγλώττισης. Τέλος, περιγράφεται το στάδιο παραγωγής κώδικα, εστιάζοντας στην παραγωγή κώδικα για παράλληλη επεξεργασίας δεδομένων και την παραγωγή κώδικα για τύπους δεδομένων σταθερής υποδιαστολής. Η παραγωγή διανυσματικού κώδικα περιλαμβάνει την παραγωγή βρόχων οι οποίοι αναπαριστούν τα τμήματα του κώδι 5 6 κα που περιλαμβάνουν διανυσματικές εντολές ειδικού σκοπού, την παραγωγή λειτουργιών εισαγωγής/εξαγωγής δεδομένων σε διανύσματα καθώς επίσης και τις εντολές παράλληλης επεξεργασίας. Η παραγωγή κώδικα για τύπους δεδομένων σταθερής υποδιαστολής αφορά την παραγωγή επιπλέον C κώδικα για τη διαχείριση της αριθμητικής δεδομένων σταθερής υποδιαστολής (π.χ. λειτουργίες ολίσθησης). Ο μεταγλωττιστής υποστηρίζει την παράλληλη επεξεργασία δεδομένων και επιτρέπει την παραγωγή διανυσματικού κώδικα αξιοποιώντας τις εντολές ειδικού σκοπού του εκάστοτε επεξεργαστή-στόχου. Ο παραγόμενος κώδικας επιτυγχάνει αξιοσημείωτη βελτίωση ως προς το χρόνο εκτέλεσης έναντι άλλων τεχνικών οι οποίες δεν παράγουν διανυσματικό κώδικα και/ή δεν αξιοποιούν εντολές ειδικού σκοπού ενός επεξεργαστή. Στην παρούσα διδακτορική διατριβή παρουσιάζεται επίσης η αξιολόγηση του μεταγλωττιστή σε διαφορετικές αρχιτεκτονικές. Για την αξιολόγηση του μεταγλωττιστή χρησιμοποιήθηκαν δύο επεξεργαστές ειδικών εφαρμογών (ASIP) εκ των οποίων ο ένας περιλαμβάνει εντολές επεξεργασίας πολλαπλών δεδομένων, και τέσσερις επεξεργαστές αρχιτεκτονικών ARM και x86. Για την αξιολόγηση του μεταγλωττιστή, χρησιµοποιήθηκαν οκτώ εφαρμογές ψηφιακής επεξεργασίας σήματος χρησιμοποιώντας διαφορετικά πλάτη παραλληλίας, τύπους δεδομένων κινητής και σταθερής υποδιαστολής καθώς επίσης και τύπους/μορφές δεδομένων για παράλληλη επεξεργασία. Η απόδοση ως προς το χρόνο εκτέλεσης του παραγόμενου κώδικα συγκρίθηκε με την απόδοση του κώδικα που παράγεται από τονMathWorks Coder. Ο προτεινόμενος μεταγλωττιστής επιτυγχάνει σημαντική βελτίωση της απόδοσης (ταχύτητας) σε όλες τις εξεταζόμενες αρχιτεκτονικές και ειδικά όταν χρησιμοποιούνται εντολές επεξεργασίας πολλαπλών δεδομένων. Επιπλεόν πραγματοποιήθηκαν δοκιμές για την αξιολόγηση της αυτόματης διανυσματοποίησης κώδικα (auto-vectorization) από δημοφιλείς μεταγλωττιστές της γλώσσας C όπως οι Clang/LLVM, GCC και MSVC. Οι δοκιμές πραγματοποιήθηκαν στους κώδικες οι οποίοι παράγονται από τον MathWorks Coder και τον προτεινόμενο μεταγλωττιστή. Τα πειραματικά αποτελέσματα έδειξαν ότι οι C μεταγλωττιστές διανυσματοποιουν ένα μικρό ποσοστό των βρόχων που μπορούν πραγματικά να διανυσματοποιηθούν οδηγώντας στο συμπέρασμα ότι οι μονάδες των επεξεργαστών που υποστηρίζουν την παράλλήλη επεξεργασία δεδομένων δεν μπορούν να αξιοποιηθούν πλήρως από αυτούς. Αντίθετα ο προτεινόμενος μεταγλωττιστής υποστηρίζει μια ευρύτερη κατηγορία περιπτώσεων.