Efficient openMP runtime support for general-purpose and embedded multi-core platforms
Φόρτωση...
Ημερομηνία
Συγγραφείς
Αγάθος, Σπυρίδων Ν.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
OpenMP is the standard programming model for shared memory multiprocessors
and is currently expanding its target range beyond such platforms. The tasking
model of OpenMP has been used successfully in a wide range of parallel applications.
With tasking, OpenMP expanded its applicability beyond loop-level parallelization.
Tasking allows efficient expression and management of irregular and dynamic parallelism.
Recently, another significant addition to OpenMP was the introduction of
device directives that target systems consisting of general-purpose hosts and accelerator
devices that may execute portions of a unified application code. OpenMP thus
encompasses heterogeneous computing, as well.
This dissertation deals with the problem of designing and implementing a productive
and performance-oriented infrastructure to support the OpenMP parallel programming
model. The first group of contributions refers to the efficient support of
the OpenMP tasking model and its application to provide a novel solution to the
problem of nested loop parallelism. We present the design and implementation of
a tasking subsystem in the context of the ompi OpenMP compiler. Portions of this
subsystem were re-engineered, and fast work-stealing structures were exploited, resulting
a highly efficient implementation of OpenMP tasks for numa systems. Then we
show how the tasking subsystem can be used to handle difficult problems such as
nested loop parallelism. We provide a novel technique, whereby the nested parallel
loops can be transparently executed by a single level of threads through the existing
tasking subsystem. The second group of contributions is related to the design and implementation of
efficient OpenMP infrastructures for embedded and heterogeneous multicore systems.
Here we present the way we enabled OpenMP exploitation of the sthorm accelerator.
An innovative feature of our design is the deployment of the OpenMP model both at
the host and the fabric sides, in a seamless way. Next we present the first implementation
of the OpenMP 4.0 accelerator directives for the Parallella board, a very popular
credit-card sized multicore system consisting of a dual-core arm host processor and
a distinct 16-core Epiphany co-processor.
Finally, we propose a novel compilation technique which we term CARS; it features
a Compiler-assisted Adaptive Runtime System which results in application-specific
support by implementing each time only the required OpenMP functionality. The
technique is of general applicability and can lead to dramatic reduction in executable
sizes and/or execution times.
Η συνεχής ανάγκη για περισσότερη επεξεργαστική ισχύ, σε συνδυασμό με φυσι- κούς περιορισμούς στην κατασκευή μικροηλεκτρονικών διατάξεων πολύ μεγάλης κλίμακας ολοκλήρωσης, οδήγησαν στη εμφάνιση πολυπύρηνων επεξεργαστών. Οι πολυπύρηνοι επεξεργαστές αποτελούν πια μονόδρομο στην κατασκευή υπολογιστι- κών συστημάτων. Οι μεγάλες εταιρίες κατασκευής επεξεργαστών κατασκευάζουν επεξεργαστές με δύο, τέσσερις ή οκτώ πυρήνες επεξεργασίας. Οι σύγχρονοι υπερ- υπολογιστές αποτελούνται πλέον από χιλιάδες πολυπύρηνους κόμβους οι οποίοι διασυνδέονται μέσω ταχύτατων δικτύων. Τα σύγχρονα υπολογιστικά συστήματα χαρακτηρίζονται επίσης από την ανομοιογένεια, την χρήση δηλαδή επεξεργαστών διαφορετικών τύπων και δυνατοτήτων, όπως παραδείγματος χάριν πολυπύρηνους επεξεργαστές και μονάδες γραφικής επεξεργασίας γενικού σκοπού (gpgpu). Στην καθημερινότητά μας έχουν εισέλθει επίσης τα ενσωματωμένα συστήματα (embedded systems), δηλαδή υπολογιστές με σχετικά περιορισμένους πόρους, σχε- διασμένοι να εκτελούν ορισμένες εξειδικευμένες λειτουργίες. Παραδείγματα τέ- τοιων συσκευών είναι οι ψηφιακοί βοηθοί, mp3/mp4 players, κινητά τηλέφωνα, κονσόλες βιντεοπαιχνιδιών, ψηφιακές φωτογραφικές μηχανές, καθώς και οικιακές συσκευές. Μέχρι πρόσφατα τα ενσωματωμένα συστήματα διέθεταν έναν πυρήνα επεξεργασίας που είχε συνήθως την μορφή μικροελεγκτή ή επεξεργαστή ψηφιακού σήματος (dsp). Οι ολοένα αυξανόμενες απαιτήσεις σε ταχύτητα και λειτουργικότητα είχαν ως αποτέλεσμα την καθιέρωση ενσωματωμένων συστημάτων τα οποία πλέον σχεδιάζονται βάσει πολυπύρηνων επεξεργαστών γενικού σκοπού. Το βασικό μειονέκτημα των παράλληλων συστημάτων ήταν ανέκαθεν η δυσκολία που υπάρχει στον προγραμματισμό τους. Η μετάβαση από τα σειριακά προγραμμα- τιστικά μοντέλα στα παράλληλα είναι μια αρκετά επίπονη διαδικασία και εισάγει πολλά προβλήματα τόσο στην σχεδίαση όσο και στην ανάπτυξη/αποσφαλμάτωση των εφαρμογών. Το OpenMP αποτελεί το πλέον διαδεδομένο και αποδεκτό πρότυπο για ανάπτυξη πολυνηματικών εφαρμογών σε συστήματα κοινόχρηστης μνήμης. Είναι βασισμένο στις γλώσσες C/C++ και Fortran και σήμερα βρίσκεται στην έκδοση 4.5. Στην έκδοση 3.0, που παρουσιάστηκε το 2008, προστέθηκαν αρκετές νέες δυνατότητες έκφρα- σης παραλληλισμού. Η κυριότερη αλλαγή ήταν η προσθήκη των αυτόνομων εργασιών (tasks), χάρη στις οποίες μπορεί εύκολα να εκφραστεί αναδρομικός και ακανόνι- στος (irregular) παραλληλισμός. Το 2013 παρουσιάστηκε η έκδοση 4.0, όπου προ- στέθηκε η δυνατότητα αξιοποίησης ανομοιογενών επεξεργαστικών μονάδων όπως για παράδειγμα gpgpus και διάφορων τύπων επιταχυντών (accelerators) όπως για παράδειγμα ο Intel Xeon Phi. Η διατριβή αυτή ασχολείται με την σχεδίαση και υλοποίηση μιας υποδομής για τον προγραμματισμό παράλληλων συστημάτων η οποία στοχεύει σε υψηλές επιδό- σεις. Το πρώτο μέρος της διατριβής αναφέρεται στην αποδοτική υποστήριξη του μοντέλου εργασιών του OpenMP και στην αξιοποίησή του στην περίπτωση του εμ- φωλευμένου παραλληλισμού (nested parallelism). Αρχικά παρουσιάζεται ο σχεδιασμός και η υλοποίηση μιας βιβλιοθήκης για την υποστήριξη των εργασιών στον ερευνητικό μεταφραστή ompi. Στην συνέχεια παρου- σιάζονται οι αλλαγές που έγιναν στη βιβλιοθήκη αυτή με στόχο να βελτιστοποιηθούν οι επιδόσεις της κατά την εκτέλεση εφαρμογών σε συστήματα που έχουν χαρακτηρι- στικά numa (Non Uniform Memory Access). Στο πλαίσιο αυτό επανασχεδιάστηκαν κρίσιμα μέρη της και αναπτύχθηκε ένας βελτιστοποιημένος μηχανισμός κλεψίμα- τος εργασιών (work-stealing mechanism). Στην συνέχεια αναλύεται ο τρόπος με τον οποίο ένα σύστημα εκτέλεσης εργασιών μπορεί διαχειριστεί το πρόβλημα του εμφωλευμένου παραλληλισμού. Προτείνουμε μια καινοτόμα τεχνική, όπου βρόχοι εμφωλευμένου παραλληλισμού (nested parallel loops) μπορούν να εκτελεστούν από νήματα μιας ομάδας OpenMP, χωρίς την ανάγκη δημιουργίας νέων εμφωλευμένων νημάτων. Η τεχνική αυτή μπορεί να υλοποιηθεί διαφανώς στο σύστημα εκτέλεσης εργασιών ενός μεταφραστή OpenMP. Το δεύτερο μέρος της διατριβής σχετίζεται με τον σχεδιασμό και την υλοποίηση αποδοτικών υποδομών για ενσωματωμένα και πολυπύρηνα ετερογενή συστήματα. Αρχικά σχεδιάσαμε και αναπτύξαμε μια υποδομή η οποία θα υποστηρίζει την εκτέ- λεση κώδικα OpenMP σε ετερογενή συστήματα τα οποία διαθέτουν τον πολυπύρηνο ενσωματωμένο συν-επεξεργαστή sthorm. Η καινοτομία της συγκεκριμένης εργα- σίας έγκειται στην υποστήριξη της εκτέλεσης οδηγιών OpenMP τόσο στον κεντρικό επεξεργαστή του συστήματος (host) όσο και στον sthorm. Στην συνέχεια παρουσιά- ζεται η πρώτη υλοποίηση των οδηγιών OpenMP 4.0 για επιταχυντές στο ετερογενές σύστημα Parallella. Πρόκειται για ένα πολυπύρηνο σύστημα μεγέθους πιστωτικής κάρτας, το οποίο διαθέτει έναν διπύρηνο επεξεργαστή arm ως κεντρικό (host) και έναν 16-πύρηνο συν-επεξεργαστή Epiphany. Τέλος, παρουσιάζεται μια καινοτόμα τεχνική που μπορεί να εφαρμοστεί σε με- ταφραστές OpenMP. Η τεχνική αυτή ονομάζεται CARS (Compiler-assisted Adaptive Runtime System) και αποσκοπεί στην δημιουργία βιβλιοθηκών υποστήριξης OpenMP κατάλληλα προσαρμοσμένων στις απαιτήσεις της εκάστοτε εφαρμογής. Σύμφωνα με την προτεινόμενη τεχνική, κατά την ανάλυση του κώδικα υπολογίζονται ορισμέ- νες μετρικές που σκιαγραφούν την συμπεριφορά της εφαρμογής. Έπειτα οι μετρι- κές αυτές αξιοποιούνται από υπομονάδα του μεταφραστή ώστε να επιλεγεί ή να δημιουργηθεί δυναμικά μια προσαρμοσμένη/βελτιστοποιημένη έκδοση των βιβλιο- θηκών υποστήριξης για την συγκεκριμένη εφαρμογή. Η τεχνική αυτή είναι γενικού σκοπού, όμως μπορεί να αποδειχθεί ιδιαίτερα χρήσιμη στην περίπτωση όπου κώ- δικας OpenMP εκτελείται σε κάποιος είδος συν-επεξεργαστή, οδηγώντας σε δρα- ματική μείωση του μεγέθους του παραγόμενου εκτελέσιμου καθώς και σε αύξηση επιδόσεων.
Η συνεχής ανάγκη για περισσότερη επεξεργαστική ισχύ, σε συνδυασμό με φυσι- κούς περιορισμούς στην κατασκευή μικροηλεκτρονικών διατάξεων πολύ μεγάλης κλίμακας ολοκλήρωσης, οδήγησαν στη εμφάνιση πολυπύρηνων επεξεργαστών. Οι πολυπύρηνοι επεξεργαστές αποτελούν πια μονόδρομο στην κατασκευή υπολογιστι- κών συστημάτων. Οι μεγάλες εταιρίες κατασκευής επεξεργαστών κατασκευάζουν επεξεργαστές με δύο, τέσσερις ή οκτώ πυρήνες επεξεργασίας. Οι σύγχρονοι υπερ- υπολογιστές αποτελούνται πλέον από χιλιάδες πολυπύρηνους κόμβους οι οποίοι διασυνδέονται μέσω ταχύτατων δικτύων. Τα σύγχρονα υπολογιστικά συστήματα χαρακτηρίζονται επίσης από την ανομοιογένεια, την χρήση δηλαδή επεξεργαστών διαφορετικών τύπων και δυνατοτήτων, όπως παραδείγματος χάριν πολυπύρηνους επεξεργαστές και μονάδες γραφικής επεξεργασίας γενικού σκοπού (gpgpu). Στην καθημερινότητά μας έχουν εισέλθει επίσης τα ενσωματωμένα συστήματα (embedded systems), δηλαδή υπολογιστές με σχετικά περιορισμένους πόρους, σχε- διασμένοι να εκτελούν ορισμένες εξειδικευμένες λειτουργίες. Παραδείγματα τέ- τοιων συσκευών είναι οι ψηφιακοί βοηθοί, mp3/mp4 players, κινητά τηλέφωνα, κονσόλες βιντεοπαιχνιδιών, ψηφιακές φωτογραφικές μηχανές, καθώς και οικιακές συσκευές. Μέχρι πρόσφατα τα ενσωματωμένα συστήματα διέθεταν έναν πυρήνα επεξεργασίας που είχε συνήθως την μορφή μικροελεγκτή ή επεξεργαστή ψηφιακού σήματος (dsp). Οι ολοένα αυξανόμενες απαιτήσεις σε ταχύτητα και λειτουργικότητα είχαν ως αποτέλεσμα την καθιέρωση ενσωματωμένων συστημάτων τα οποία πλέον σχεδιάζονται βάσει πολυπύρηνων επεξεργαστών γενικού σκοπού. Το βασικό μειονέκτημα των παράλληλων συστημάτων ήταν ανέκαθεν η δυσκολία που υπάρχει στον προγραμματισμό τους. Η μετάβαση από τα σειριακά προγραμμα- τιστικά μοντέλα στα παράλληλα είναι μια αρκετά επίπονη διαδικασία και εισάγει πολλά προβλήματα τόσο στην σχεδίαση όσο και στην ανάπτυξη/αποσφαλμάτωση των εφαρμογών. Το OpenMP αποτελεί το πλέον διαδεδομένο και αποδεκτό πρότυπο για ανάπτυξη πολυνηματικών εφαρμογών σε συστήματα κοινόχρηστης μνήμης. Είναι βασισμένο στις γλώσσες C/C++ και Fortran και σήμερα βρίσκεται στην έκδοση 4.5. Στην έκδοση 3.0, που παρουσιάστηκε το 2008, προστέθηκαν αρκετές νέες δυνατότητες έκφρα- σης παραλληλισμού. Η κυριότερη αλλαγή ήταν η προσθήκη των αυτόνομων εργασιών (tasks), χάρη στις οποίες μπορεί εύκολα να εκφραστεί αναδρομικός και ακανόνι- στος (irregular) παραλληλισμός. Το 2013 παρουσιάστηκε η έκδοση 4.0, όπου προ- στέθηκε η δυνατότητα αξιοποίησης ανομοιογενών επεξεργαστικών μονάδων όπως για παράδειγμα gpgpus και διάφορων τύπων επιταχυντών (accelerators) όπως για παράδειγμα ο Intel Xeon Phi. Η διατριβή αυτή ασχολείται με την σχεδίαση και υλοποίηση μιας υποδομής για τον προγραμματισμό παράλληλων συστημάτων η οποία στοχεύει σε υψηλές επιδό- σεις. Το πρώτο μέρος της διατριβής αναφέρεται στην αποδοτική υποστήριξη του μοντέλου εργασιών του OpenMP και στην αξιοποίησή του στην περίπτωση του εμ- φωλευμένου παραλληλισμού (nested parallelism). Αρχικά παρουσιάζεται ο σχεδιασμός και η υλοποίηση μιας βιβλιοθήκης για την υποστήριξη των εργασιών στον ερευνητικό μεταφραστή ompi. Στην συνέχεια παρου- σιάζονται οι αλλαγές που έγιναν στη βιβλιοθήκη αυτή με στόχο να βελτιστοποιηθούν οι επιδόσεις της κατά την εκτέλεση εφαρμογών σε συστήματα που έχουν χαρακτηρι- στικά numa (Non Uniform Memory Access). Στο πλαίσιο αυτό επανασχεδιάστηκαν κρίσιμα μέρη της και αναπτύχθηκε ένας βελτιστοποιημένος μηχανισμός κλεψίμα- τος εργασιών (work-stealing mechanism). Στην συνέχεια αναλύεται ο τρόπος με τον οποίο ένα σύστημα εκτέλεσης εργασιών μπορεί διαχειριστεί το πρόβλημα του εμφωλευμένου παραλληλισμού. Προτείνουμε μια καινοτόμα τεχνική, όπου βρόχοι εμφωλευμένου παραλληλισμού (nested parallel loops) μπορούν να εκτελεστούν από νήματα μιας ομάδας OpenMP, χωρίς την ανάγκη δημιουργίας νέων εμφωλευμένων νημάτων. Η τεχνική αυτή μπορεί να υλοποιηθεί διαφανώς στο σύστημα εκτέλεσης εργασιών ενός μεταφραστή OpenMP. Το δεύτερο μέρος της διατριβής σχετίζεται με τον σχεδιασμό και την υλοποίηση αποδοτικών υποδομών για ενσωματωμένα και πολυπύρηνα ετερογενή συστήματα. Αρχικά σχεδιάσαμε και αναπτύξαμε μια υποδομή η οποία θα υποστηρίζει την εκτέ- λεση κώδικα OpenMP σε ετερογενή συστήματα τα οποία διαθέτουν τον πολυπύρηνο ενσωματωμένο συν-επεξεργαστή sthorm. Η καινοτομία της συγκεκριμένης εργα- σίας έγκειται στην υποστήριξη της εκτέλεσης οδηγιών OpenMP τόσο στον κεντρικό επεξεργαστή του συστήματος (host) όσο και στον sthorm. Στην συνέχεια παρουσιά- ζεται η πρώτη υλοποίηση των οδηγιών OpenMP 4.0 για επιταχυντές στο ετερογενές σύστημα Parallella. Πρόκειται για ένα πολυπύρηνο σύστημα μεγέθους πιστωτικής κάρτας, το οποίο διαθέτει έναν διπύρηνο επεξεργαστή arm ως κεντρικό (host) και έναν 16-πύρηνο συν-επεξεργαστή Epiphany. Τέλος, παρουσιάζεται μια καινοτόμα τεχνική που μπορεί να εφαρμοστεί σε με- ταφραστές OpenMP. Η τεχνική αυτή ονομάζεται CARS (Compiler-assisted Adaptive Runtime System) και αποσκοπεί στην δημιουργία βιβλιοθηκών υποστήριξης OpenMP κατάλληλα προσαρμοσμένων στις απαιτήσεις της εκάστοτε εφαρμογής. Σύμφωνα με την προτεινόμενη τεχνική, κατά την ανάλυση του κώδικα υπολογίζονται ορισμέ- νες μετρικές που σκιαγραφούν την συμπεριφορά της εφαρμογής. Έπειτα οι μετρι- κές αυτές αξιοποιούνται από υπομονάδα του μεταφραστή ώστε να επιλεγεί ή να δημιουργηθεί δυναμικά μια προσαρμοσμένη/βελτιστοποιημένη έκδοση των βιβλιο- θηκών υποστήριξης για την συγκεκριμένη εφαρμογή. Η τεχνική αυτή είναι γενικού σκοπού, όμως μπορεί να αποδειχθεί ιδιαίτερα χρήσιμη στην περίπτωση όπου κώ- δικας OpenMP εκτελείται σε κάποιος είδος συν-επεξεργαστή, οδηγώντας σε δρα- ματική μείωση του μεγέθους του παραγόμενου εκτελέσιμου καθώς και σε αύξηση επιδόσεων.
Περιγραφή
Λέξεις-κλειδιά
OMPi compiler
Θεματική κατηγορία
Embedded multi-core systems
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Δημακόπουλος, Βασίλειος Β.
Εξεταστική επιτροπή
Δημακόπουλος, Βασίλειος Β.
Φατούρου, Παναγιώτα
Φούντος, Ιωάννης
Χατζηδούκας, Παναγιώτης
Μαγκούτης, Κωνσταντίνος
Μανής, Γεώργιος
Νικολόπουλος, Δημήτριος
Φατούρου, Παναγιώτα
Φούντος, Ιωάννης
Χατζηδούκας, Παναγιώτης
Μαγκούτης, Κωνσταντίνος
Μανής, Γεώργιος
Νικολόπουλος, Δημήτριος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογράφία : σ. 153-163
Ονόματα συντελεστών
Αριθμός σελίδων
167 σ.