Efficient OpenMP runtime support for general - purpose and embedded multi - core platforms

Abstract

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.

Το OpenMP αποτελεί το πλέον διαδεδομένο και αποδεκτό πρότυπο για ανάπτυξη πολυνηματικών εφαρμογών σε συστήματα κοινόχρηστης μνήμης. Είναι βασισμένο στις γλώσσες C/C++ και Fortran και διαθέτει οδηγίες για εύκολη έκφραση αναδρομικού και ακανόνιστου παραλληλισμού. Το 2013 με την έκδοση 4.0 προστέθηκε η δυνατότητα αξιοποίησης ανομοιογενών επεξεργαστικών μονάδων όπως για παράδειγμα επεξεργαστών γραφικών γενικού σκοπού και διάφορων τύπων επιταχυντών.Η διατριβή αυτή ασχολείται με την σχεδίαση και υλοποίηση μιας υποδομής για τον προγραμματισμό παράλληλων συστημάτων η οποία στοχεύει σε υψηλές επιδόσεις.Αρχικά παρουσιάζεται ο σχεδιασμός και η υλοποίηση μιας βιβλιοθήκης για την υποστήριξη των εργασιών στον ερευνητικό μεταφραστή OMPi. Στην συνέχεια παρουσιάζονται οι αλλαγές που έγιναν στη βιβλιοθήκη αυτή με στόχο να βελτιστοποιηθούν οι επιδόσεις της κατά την εκτέλεση εφαρμογών σε συστήματα που έχουν χαρακτηριστικά NUMA (Non Uniform Memory Access). Στο πλαίσιο αυτό επανασχεδιάστηκαν κρίσιμα μέρη της και αναπτύχθηκε ένας βελτιστοποιημένος μηχανισμός κλεψίματος εργασιών. Στην συνέχεια αναλύεται ο τρόπος με τον οποίο ένα σύστημα εκτέλεσης εργασιών μπορεί διαχειριστεί το πρόβλημα του εμφωλευμένου παραλληλισμού. Προτείνουμε μια καινοτόμα τεχνική, όπου βρόχοι εμφωλευμένου παραλληλισμού μπορούν να εκτελεστούν από νήματα μιας ομάδας OpenMP, χωρίς την ανάγκη δημιουργίας νέων εμφωλευμένων νημάτων. Η τεχνική αυτή μπορεί να υλοποιηθεί διαφανώς στο σύστημα εκτέλεσης εργασιών ενός μεταφραστή OpenMP.Το δεύτερο μέρος της διατριβής σχετίζεται με τον σχεδιασμό και την υλοποίηση αποδοτικών υποδομών για ενσωματωμένα και πολυπύρηνα ετερογενή συστήματα. Αρχικά σχεδιάσαμε και αναπτύξαμε μια υποδομή η οποία θα υποστηρίζει την εκτέλεση κώδικα OpenMP σε ετερογενή συστήματα τα οποία διαθέτουν τον πολυπύρηνο ενσωματωμένο συν-επεξεργαστή STHORM. Η καινοτομία της συγκεκριμένης εργασίας έγκειται στην υποστήριξη της εκτέλεσης οδηγιών OpenMP τόσο στον κεντρικό επεξεργαστή του συστήματος (host) όσο και στον STHORM. Στην συνέχεια παρουσιάζεται η πρώτη υλοποίηση των οδηγιών OpenMP 4.0 για επιταχυντές στο ετερογενές σύστημα Parallella. Πρόκειται για ένα πολυπύρηνο σύστημα μεγέθους πιστωτικής κάρτας, το οποίο διαθέτει έναν διπύρηνο επεξεργαστή ARM ώς κεντρικό (host) και έναν 16-πύρηνο συν-επεξεργαστή Epiphany. Τέλος, παρουσιάζεται μια καινοτόμα τεχνική που μπορεί να εφαρμοστεί σε μεταφραστές OpenMP. Η τεχνική αυτή ονομάζεται CARS (Compiler-assisted Adaptive Runtime System) και αποσκοπεί στην δημιουργία βιβλιοθηκών υποστήριξης OpenMP κατάλληλα προσαρμοσμένων στις απαιτήσεις της εκάστοτε εφαρμογής. Σύμφωνα με την προτεινόμενη τεχνική, κατά την ανάλυση του κώδικα υπολογίζονται ορισμένες μετρικές που σκιαγραφούν την συμπεριφορά της εφαρμογής. Έπειτα οι μετρικές αυτές αξιοποιούνται από υπομονάδα του μεταφραστή ώστε να επιλεγεί ή να δημιουργηθεί δυναμικά μια προσαρμοσμένη/βελτιστοποιημένη έκδοση των βιβλιοθηκών υποστήριξης για την συγκεκριμένη εφαρμογή. Η τεχνική αυτή είναι γενικού σκοπού, όμως μπορεί να αποδειχθεί ιδιαίτερα χρήσιμη στην περίπτωση όπου κώδικας OpenMP εκτελείται σε κάποιος είδος συν-επεξεργαστή, οδηγώντας σε δραματική μείωση του μεγέθους του παραγόμενου εκτελέσιμου καθώς και σε αύξηση επιδόσεων.