Task data-flow execution on many-core systems

Abstract

Η αύξηση της επίδοσης με ταυτόχρονη μείωση της κατανάλωσης ενέργειας επιτυγχάνεται με την παράλληλη επεξεργασία. Προκειμένου να αξιοποιηθεί ο παραλληλισμός μέσα από τις εφαρμογές και να βελτιστοποιηθεί η ενεργειακή απόδοση μεγάλων συστημάτων, η τάση είναι να αυξάνωνται οι πυρήνες μέσα στους επεξεργαστές. Ωστόσο, η αύξηση του αριθμού των πυρήνων από μόνη της δεν έχει ως αποτέλεσμα την βελτιωμένη επίδοση των εφαρμογών. Από την άποψη του λογισμικού, αυτό δημιουργεί νέες προκλήσεις καθώς χρειαζόμαστε ένα πλαίσιο που να μπορεί να εκμεταλλεύεται αποτελεσματικά τον παραλληλισμό των εφαρμογών στους διαθέσιμους πόρους που προσφέρει το υλικού. Η αύξηση της επίδοσης στα μελλοντικά συστήματα πολλαπλών πυρήνων θα επηρεαστεί από τους ακόλουθους παράγοντες: τον βαθμό παραλληλισμού στις εφαρμογές, τον τρόπο προγραμματισμού, τα χαμηλού κόστους συστήματα εκτέλεσης, την εκτέλεση των εργασιών με γνώμονα την τοποθεσία των δεδομένων, την αποτελεσματική χρήση των διαθέσιμων πόρων και τα επεκτάσιμα σχέδια αρχιτεκτονικής επεξεργαστών. Σε αυτήν την Διατριβή, το μοντέλο εργασιών χρησιμοποιείται ως υλοποίηση του μοντέλου ροής δεδομένων. Το μοντέλο ροης δεδομένων είναι το καταλληλότερο μοντέλο για την εκμετάλλευση μεγάλων ποσοτήτων παραλληλισμού, ενώ η υλοποίηση με τη χρήση εργασιών μειώνει το κόστος της εκτέλεσης και προσαρμόζεται εύκολα σε διαφορετικές εφαρμογές. Σε αυτή τη εργασία, η Συναλλακτική Μνήμη ενσωματώνεται στο μοντελο ροής δεδομένων για να μειώσει την αυστηρότητα του, διερευνώντας τον εικαστικό παραλληλισμό όταν οι εξαρτήσεις μεταξύ εργασίων είναι πολύ περίπλοκες για να εφαρμοστούν ή ακόμα και όταν δεν ισχύουν. Αυτή η Διατριβή παρουσιάζει την πρώτη εφαρμογή σε μεγάλους πολυ-επεξεργαστές του μοντέλου πολλαπλών σπειρωμάτων, μια υλοποίηση του μοντέλου ροής δεδομένων. Το μοντελο πολλαπλών σπειρωμάτων επανασχεδιάζεται για να υποστηρίξει τον πρώτο επεξεργαστή πολλαπλών πυρήνων από την Intel (Single-chip Cloud Computer) που παρέχει ένα ενιαίο χώρο διευθύνσεων χωρίς υποστήριξη υλικού για συνεκτικότητα της κρυφής μνήμης. Τα αποτελέσματα αυτής της εργασίας οδήγησαν στο σχεδιασμό και την ανάπτυξη ενός νέου πιο αποδοτικού, συστήματος εκτέλεσης που μπορεί να επεκταθεί σε ακόμα μεγαλύτερους επεξεργαστές. Το προτεινόμενο σύστημα περιλαμβάνεται σε μια πλατφόμρα προγραμματισμού και εκτέλεσης εφαρμογών. Το SWITCHES είναι λογισμικό που υλοποιεί το μοντέλο ροής δεδομένων που βασίζεται σε εργασίες για επεξεργαστές πολλών πυρήνων. Απαιτεί ενιάιο χώρο διευθύνσεων αλλά όχι απαραίτητα μηχανισμούς συνεκτικότητας της κρυφής μνήμης που θα μπορούσαν να περιορίσουν την επεκτασιμότητα του επεξεργαστή. Το SWITCHES υλοποιεί ένα ελαφρύ στατικό κατανεμημένο σύστημα ενεργοποίησης για την επίλυση εξαρτήσεων κατά τη διάρκεια εκτέλεσης εργασιών. Υποστηρίζει μηχανισμούς κατανομής των πόρων του συστήματος και ενσωματώνει τεχνικές εκμάθησης μηχανών για την αποτελεσματική αξιοποίηση τους. Για τη εύκολη υλοποίηση προγραμμάτων, το πλαίσιο υλοποιεί το πιο πρόσφατο πρότυπο από το OpenMP (ν4.5) και το επεκτείνει για να υποστηρίζει εργασίες σε βρόχους με εξαρτήσεις σε διαφορετικούς βρόχους. Παρέχει ένα εργαλείο (Translator) που παράγει αυτόματα κώδικα βασισμένο σε νήματα, ο οποίος μπορεί να μεταγλωττιστεί από οποιονδήποτε μεταγλωττιστή C/C++, εφαρμόζοντας όλες τις υπάρχουσες βελτιστοποιήσεις. Χρησιμοποιώντας το σύστημα αυτό, η επίδοση εφαρμογών με διαφορετικά χαρακτηριστικα σε μια μηχανή με Intel Xeon Phi επεξεργαστή ξεπερνά την επίδοση του OpenMP κατά μέσο όρο κατά 32% και βελτιώνει την αποδοτικότητα της πετυχαίνωντας μέγιστη επίδοση χρησιμοποιώντας 30% λιγότερους πυρήνες σε εφαρμογές με σύνθετες εξαρτήσεις.

Power-performance efficiency in High Performance Computing (HPC) systems is currently achieved by exploring parallel processing. Consequently, in order to exploit application parallelism and optimize energy efficiency, the trend is to include more cores in the processors. From the hardware perspective, many small and simple cores will be added in processor architectures, leading towards many-core chips with hundreds of cores. Nevertheless, scaling the number of cores alone does not result in improved application performance. From the software perspective, this creates new challenges as we need a framework that can efficiently exploit application parallelism on the available hardware resources. Overall, performance scalability in future many-core systems will be affected by the following factors: the degree of parallelism, programmability, low-overhead runtime systems, locality-aware execution, efficient use of the available resources and scalable architecture designs. In this thesis, the Task model is used as an implementation of the Data-flow paradigm. Data-flow is the most appropriate model for exploiting large amounts of software parallelism, while a task-based implementation reduces runtime overheads and easily adapts to different applications. In this work, Transactional Memory is integrated in Data-flow to reduce the strictness of the latter by exploring speculative parallelism when task dependences are too complex to apply or even when not applicable. This thesis presents the first many-core implementation of the Data-Driven Multi-threading (DDM) model, a task-based implementation of Data-flow. DDM is redesigned to support the first single-chip many-core processor from Intel (the Single-chip Cloud Computer) that provides a single address space with no hardware support for cache-coherence. The results from this work led to the design and development of a new more efficient, lightweight runtime system that is able to scale to larger many-core processors. The proposed runtime system (called SWITCHES) is included in a complete programming and execution framework. SWITCHES is a software implementation of the task-based Data-flow model for many-core processors. It requires global address space but not necessarily a hardware cache-coherence mechanisms that could limit the scalability of the architecture. SWITCHES implements a lightweight distributed triggering system for runtime task dependence resolution and uses static scheduling and compile time assignment policies to reduce overheads. It supports explicit task resource allocation mechanisms and incorporates machine-learning techniques within the framework to efficiently utilize the underlying resources. To maintain high-levels of programming productivity, the framework implements the latest API standard from OpenMP (v4.5) and extends it to support variable granularity loop-tasks with dependences across different loops as to favor data-locality in loops with inter-dependences. It provides a source-to-source tool that automatically produces thread-based code that can be compiled by any off-the-shelf C/C++ compiler, applying all existing optimizations. Performance evaluation of applications with different characteristics on an Intel Xeon Phi system shows good scalability that surpasses the state-of-the-art by an average of 32% and resource utilization is increased with maximum performance achieved using 30% fewer cores for applications with complex dependences.