Mapping loop-based programs onto a multithreaded processor

Abstract

This thesis offers some insight into the automatic parallelization of loops by introducing and describing a source-to-source parallelizing compiler developed from scratch called C2μTC/SL. Once basic notions and ideas on the field of automatic parallelization have been introduced, the SVP system is described in great detail. It is a novel proposal on multi-core architectures and is what C2μTC/SL targets as output. The SVP is a novel design for a multi-threaded processor that can be bundled together with an OS-on-chip as part of the chip's ISA (Instruction Set Architecture). Several of those SVP cores together form a microgrid. The programming paradigm followed by the microgrid is that of a family of threads. Each family executes independently and all the threads belonging in such a family run in parallel. A thread can create more ad-hoc families so a whole hierarchy of families can exist at any given time. Synchronization is achieved by a series of synchronizing channels that can carry information from one thread in the family to its neighbors. The whole system can revert back to complete sequential execution once all resources are taken. Two programming languages were created for the high level programming / abstraction layer of the SVP: μTC and SL. Both are explained later in the text however they both are extensions of the basic C language. They extend the language with a series of directives for the creation and execution of families of threads.The C2μTC/SL source-to-source compiler is described afterwards: its purpose is to take as input any legacy C code and transform it into a parallel SL program. Originally its output was the μTC language but with the advent of SL it changed to that, hence the name C to μTC / SL (C2μTC/SL). The compiler’s main target constructs are loops since a loop is where most of the execution time of an application takes place. Since SVP works with families of threads that resemble single-dimentional loops, transforming any kind of loop into a meaningful construct for the SVP is an important step. For that reason, loops are divided into single-dimensional and multi-dimensional ones with each category requiring a different transformation method.Single-dimentional loops are further categorized by the number of the so-called loop carried dependencies that they have and are treated accordingly. Loops with no dependencies are just translated simply into parallel families. Loops with dependencies utilize the SVP’s synchronizing channels to transfer data from one thread to the next in a dataflow manner. This action alleviates the weight of each thread having to access the global memory for a particular piece of data since whatever it needs is simply transferred over via the synchronizing / shared channel. Once each thread finishes computation it pushes all relevant data back to the shared channel for use by the next thread. The combination of parallel executing independent data-flows (data-chains) and the synchronizing channel to reduce accesses to the main global memory brings tremendous increases in speedup and efficiency.Multi-dimensional loops are also subcategorized into two groups. The first group is the one that contains no dependencies. Again each loop of the loop nesting is simply transformed to a fully parallel family and it is up to the SVP to run the code effectively. The second and most interesting group contains the perfect loop nestings with a static dependency vector. Lamport’s hyperplane idea is applied in this case however there is a novelty: Instead of precomputing any loop transformation, it is up to the run-time environment to intuitively follow the dependency vector over the index space and discover the different hyperplanes per cycle. This novel idea gave birth to our first run-time algorithm: The fixed-size algorithm. It has the ability to apply the hyperplane idea, discovered while running the actual computation code, into the various tiles of a fixed size which divide the innermost dimension of the loop. The fixed size algorithm proved to work properly, however for optimal or even good results the size of the tile was needed to be known beforehand, effectively making the whole algorithm not particularly useful except as a stepping stone and also a great tool for comparisons.This glaring weakness of the Fixed-Size algorithm was covered by its evolutionary “descendant”: the Self-Adaptive algorithm. Working on the same principles as the Fixed-Size one, it can, at run-time, determine the optimal tile size to use at any given computation cycle by reducing it or increasing it according to the current needs.Experimental results indicate that not only the Self-Adaptive algorithm fares very well with near-optimal results when compared with the Fixed-Size one, it is also shown that for that particular type of parallelism (run-time execution of parallel families discovered on the spot) the results obtained are the best possible results that can be obtained. The algorithms were also compared with a standard compile-time method (the hyperplane method) and it was found that their speedup is relatively close to each other. This combined with the versatility offered by a run-time system (like dealing with irregular index spaces) makes the Self-Adaptive algorithm especially appealing.

Η παρούσα διατριβή προσφέρει μία περιήγηση στον κόσμο της αυτόματης παραλληλοποίησης των βρόχων παρουσιάζοντας και περιγράφοντας παράλληλα ένα εργαλείο αυτόματου παραλληλισμού (πηγαίο σε πηγαίο) που δημιουργήθηκε εκ του μηδενός και ονομάζεται C2μTC/SL. Αφού παρουσιαστούν βασικές ένοιες στον χώρο του αυτόματου παραλληλισμού, το σύστημα SVP περιγράφεται: Μια καινοτόμος πρόταση στις πολύ-πύρηνες αρχιτεκτονικές και αποτελεί στόχο - έξοδο του C2μTC/SL. Το SVP αποτελεί το σχέδιο για έναν πολύ-πύρηνο επεξεργαστή και έχει την ιδιότητα να εκτελεί ένα ολόκληρο λειτουργικό σύστημα το οποίο μπορεί να καταλαμβάνει μέρος του ISA (Instruction Set Architecture) του πυρήνα. Πολλοί από αυτούς τους πυρήνες μπορούν να συνδυαστούν στο λεγόμενο μικροπλέγμα (microgrid). Ο προγραμματισμός του microgrid στηρίζεται σε οικογένειες από νήματα. Κάθε οικογένεια εκτελείται αυτόνομα και όλα τα νήματα που ανήκουν σε αυτήν την οικογένεια μπορούν να εκτελεστούν παράλληλα. Επίσης, κάθε νήμα μπορεί να δημιουργήσει όσες οικογένειες χρειάζεται κατά βούληση. Με αυτόν τον τρόπο, μια ολόκληρη ιεραρχία από νήματα μπορεί να εκτελείται ανά πάσα στιγμή στο microgrid. Ο συγχρονισμός μεταξύ των νημάτων επιτυγχάνεται από την ύπαρξη μιας σειράς καναλιών που μπορούν να μεταφέρουν πληροφορίες από ένα νήμα σε μια οικογένεια στα γειτονικά του. Εάν οι πόροι του συστήματος εξαντληθούν, τότε το σύστημα είναι ικανό να επιστρέψει σε κατάσταση σειριακής εκτέλεσης. Δύο γλώσσες προγραμματισμού δημιουργήθηκαν για τον προγραμματισμό του microgrid σε ένα υψηλότερο επίπεδο: μTC και SL. Και οι δύο περιγράφονται στο κείμενο, και η βασική τους λειτουργία είναι να επεκτείνουν την γλώσσα C με τέτοιο τρόπο ώστε να μπορούν να ελέγχουν την δημιουργία και την εκτέλεση των οικογενειών από νήματα.Στην συνέχεια ο αυτόματος μεταφραστής C2μTC/SL παρουσιάζεται και περιγράφεται: Ο σκοπός του είναι να δέχεται ως είσοδο ένα οποιοδήποτε πρόγραμμα γραμμένο σε C και να το μεταμορφώνει σε ένα παράλληλο πρόγραμμα SL. Αρχικά η έξοδός του ήταν η γλώσσα μTC αλλά με την εμφάνιση της SL ο μεταφραστής προσαρμόστηκε ανάλογα, οπότε και το όνομά του C2μTC/SL. Η βασική δομή για την οποία ενδιαφέρεται ο μεταφραστής είναι οι βρόχοι μιας και το μεγαλύτερο ποσοστό του χρόνου εκτέλεσης σε ένα πρόγραμμα είναι οι βρόχοι. Εφ’ όσων το SVP δουλεύει με οικογένειες από νήματα που μοιάζουν με μονοδιάστατους βρόχους, η μετατροπή ενός οποιοδήποτε βρόχου σε οικογένεια νημάτων είναι ένα σημαντικό βήμα. Για τον λόγο αυτό, οι βρόχοι χωρίζονται σε μονοδιάστατους και πολυδιάστατους με κάθε κατηγορία να χρειάζεται και διαφορετική αντιμετώπιση όσον αφορά την μετατροπή του κώδικα που χρειάζεται.Οι μονοδιάστατοι βρόχοι χωρίζονται περαιτέρω σε κατηγορίες ανάλογα με τις εξαρτήσεις που βρίσκονται στον βρόχο (loop carried dependencies). Βρόχοι χωρίς εξαρτήσεις απλά μετατρέπονται σε πλήρως παράλληλες οικογένειες ενώ οι βρόχοι με εξαρτήσεις μετατρέπονται σε οικογένειες που χρησιμοποιούν τα ειδικά κανάλια συγχρονισμού του SVP για να μεταφέρουν δεδομένα από τον ένα νήμα στο επόμενο με την μορφή της ροής δεδομένων (data flow). Αυτού του είδους η μετατροπή επιτρέπει στα νήματα να έχουν τα δεδομένα που χρειάζονται χωρίς να χρειάζεται να τα αναζητήσουν στην κεντρική κοινή μνήμη, πράγμα «ακριβό» από άποψη χρόνου. Όταν κάθε νήμα τελειώσει τον υπολογισμό που του αναλογεί, όλα τα σχετικά δεδομένα μεταφέρονται στο επόμενο νήμα μέσω του ειδικού καναλιού επικοινωνίας του SVP. Ο συνδιασμός της εκτέλεσης παράλληλων ροών δεδομένων με την χρήση των ειδικών καναλιών επικοινωνίας προσφέρει μεγάλες αυξήσεις στην αποδοτικότητα και στην επιτάχυνση ενός προγράμματος.Οι πολυδιάστατοι βρόχοι επίσης χωρίζονται σε υποκατηγορίες. Η πρώτη δεν περιέχει εξαρτήσεις και κάθε επίπεδο στον βρόχο μπορεί να μετατραπεί σε μια πλήρως παράλληλη οικογένεια αναθέτοντας στο περιβάλλον εκτέλεσης του SVP την εξισορρόπηση βάρους μεταξύ των πυρήνων του microgrid. Η δεύτερη (και πιο ενδιαφέρουσα) κατηγορία περιλαμβάνει βρόχους που περιέχουν στατικές εξαρτήσεις. Η προσέγγιση του Lamport με τα υπερεπίπεδα (hyperplanes) χρησιμοποιείται σε αυτήν την περίπτωση αλλά με μια καινοτομία: Αντί να γίνουν οι απαραίτητοι (δύσκολοι σε πολλές περιπτώσεις) υπολογισμοί σε χρόνο μετάφρασης, το περιβάλλον εκτέλεσης αναλαμβάνει να εντοπίσει όλα τα στοιχεία που μπορούν να εκτελεστούν παράλληλα ανά κύκλο εκτέλεσης ακολουθώντας διαισθητικά τον πίνακα εξαρτήσεων. Αυτή η ιδέα οδήγησε στην δημιουργία του πρώτου μας αλγορίθμου χρόνου εκτέλεσης: Τον αλγόριθμο σταθερού μεγέθους (Fixed Sized Algorithm). Είχε την δυνατότητα να εντοπίζει τα κρυμμένα υπερεπίπεδα την ίδια ώρα που εκτελούσε τον ίδιο τον κώδικα του προγράμματος. Ο χώρος αναζήτησης των δεικτών των βρόχων χωρίζεται σε μεγέθη σταθερού μήκους κατά το πιο εσωτερικό βρόχο. Ο παραλληλισμός επιτυγχάνεται μεταξύ των κομματιών σταθερού μήκους ενώ κάθε τμήμα εσωτερικά εκτελείται σειριακά. Ενώ ο αλγόριθμος δούλεψε σωστά, καλές επιταχύνσεις επιτυγχάνονταν μόνο εάν το σταθερό μήκος ήταν κατάλληλα επιλεγμένο εκ των προτέρων, κάτι πρακτικά αδύνατον αφού κάθε πρόβλημα έχει το δικό του βέλτιστο μέγεθος. Αυτό το πρόβλημα μετέτρεψε τον αλγόριθμο σε ένα καλό πρώτο βήμα και σε ένα εργαλείο για συγκρίσεις.Αυτή η αδυναμία του αλγορίθμου σταθερού μεγέθους καλύφθηκε με τον αλγόριθμο που υπήρξε ο εξελικτικός απόγονος του αρχικού. Τον αλγόριθμο αυτό-μεταβαλλόμενου μεγέθους (Self-Adaptive Algorithm). Χρησιμοποιώντας τις ίδιες αρχές με τον αλγόριθμου σταθερού μεγέθους, μπορούσε σε χρόνο εκτέλεσης να μεταβάλλει το μέγεθος τον τμημάτων βάσει κάποιων μετρικών από κύκλο σε κύκλο.Τα πειραματικά αποτελέσματα δείχνουν ότι ο αλγόριθμος μεταβαλλόμενου μεγέθους επιτυγχάνει επιταχύνσεις σχεδόν ίσες με τα βέλτιστα αποτελέσματα για αυτού του τύπου τον παραλληλισμό. Οι αλγόριθμοι επίσης συγκρίθηκαν με μια τυπική μέθοδο χρόνου μετάφρασης και βρέθηκε ότι σε κάποιες περιστάσεις τα αποτελέσματα είναι κοντά. Αυτό μαζί με την ευελιξία της μεθόδου του χρόνου εκτέλεσης (π.χ. αντιμετώπιση μη ορθοκανονικών βρόχων) κάνει τον αυτό-μεταβαλλόμενο αλγόριθμο ειδικά ελκυστικό.