A MATLAB to C vectoring compiler exploiting custom instructions of targeted processors

Abstract

This Ph.D. dissertation presents a MATLAB to C vectorizing compiler exploiting custom instructions of the target processor such as SIMD instructions or scalar math instructions which are supported by hardware. The compiler generates ANSI C code and the derived custom instructions are represented via intrinsic C functions enabling the compatibility of the compiler to any target processor.Firstly, a parameterized target processor model which is used for the specification of the specialized instruction set is presented. The processor model allows the description of the available customized instructions, operations for packing data to vectors ready for SIMD processing and native data structures such as vector data types. The processor model is used by an instruction selection algorithm to map the MATLAB source code with the available hardware modules of the target architecture. It is also utilized by the type inference compilation stage to infer the result type of the MATLAB function calls that are mapped to customized instructions. The parametrized processor model forms a multi-target MATLAB-to-C compilation framework allowing the generation of optimized code for any target architecture.Next, the compiler's infrastructure is described with emphasis to the parts that support the data parallel execution and the generation of the vectorized C code. Initially, an instruction selection algorithm is presented that matches the MATLAB operations and functions with the customized instructions of the target architecture. The algorithm selects a suitable intrinsic from that have been specified in the processor model. Subsequently, packing and unpacking statements are introduced in the intermediate representation to enable data parallel execution. The process concerns the insertion of packing (and unpacking) instructions to convert data in packed form (and vice versa) ready for SIMD execution. Afterwards local value numbering is performed to remove the redundant packing/unpacking statements that have been inserted from the previous compilation stage. The code generator is also discussed in the dissertation focusing on the production of the vectorized code and the fixed point code generation. The vectorized code generation includes the production of for-loops that correspond to SIMD blocks as well as the generation of packing instructions and the matched SIMD instructions with vector semantics. The code generation of fixed point data types concerns the production of additional C code to handle the fixed point arithmetic such as shift operations. The compilation framework supports the data parallel processing and it leads to the vectorized code generation exploiting the customized instructions of the target architecture. The generated code achieves significant speed-up against other approaches that don't produce vectorized code or any processor's special instruction.Finally, a comprehensive evaluation of the generated code by the MATLAB compiler is presented on diverse architectures. The experimental environment includes two ASIP processors (one of them supporting SIMD) that have been developed in IMEC research center and four processors from ARM and x86 architectures. The benchmark composed by eight representative DSP applications using different SIMD widths as well as a variety of data types including floating or fixed point and packed or unpacked types. The performance of the generated code by the compiler has been compared against the generated code by MathWorks Coder showing that the proposed approach achieves substantial speed-up across all target architectures especially when using SIMD processing. Further experiments have been conducted to evaluate the performance of the auto-vectorization of popular C compilers including Clang/LLVM, GCC and MSVC, on the generated code by MathWorks Coder and the scalarized code that have been produced by the MATLAB compiler. The experimental results show that the auto-vectorizing C compilers vectorize only a small percentage of the benchmark's loops concluding that the processor's SIMD units cannot be fully leveraged by auto-vectorization. In contrast, the approach developed in this thesis handles a much broader class of applications.

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