Implementing Scalable Parallel Programming Models with Hybrid Address Spaces

 
This item is provided by the institution :
University of Crete
Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share




2013 (EN)
Υλοποίηση κλιμακώσιμων παράλληλων προγραμματιστικών μοντέλων με υβριδικούς χώρους διευθύνσεων
Implementing Scalable Parallel Programming Models with Hybrid Address Spaces

Παπαγιάννης, Αναστάσιος Ελευθέριος.

Κατεβαίνης, Μανόλης

Η εργασία αυτή εισάγει τους υβριδικούς χώρους διευθύνσεων ως τεχνική για την υλοποίηση κλιμακώσιμων συστημάτων χρόνου εκτέλεσης σε πολυπύρηνες αρχιτεκτονικές χωρίς την υποστήριξη υλικού για την συνοχή των κρυφών μνημών. Παρουσιάζουμε τους υβριδικούς χώρους διευθύνσεων για την υλοποίηση του MapReduce, ενός καθιερωμένου μοντέλου προγραμματισμού για μεγάλης κλίμακας, με ανοχή σε σφάλματα, επεξεργασία δεδομένων. Χρησιμοποιώντας τον επεξεργαστή Intel Single-Chip-Cloud ως πειραματική πλατφόρμα δοκιμών παρουσιάζουμε το HyMR, ένα σύστημα χρόνου εκτέλεσης MapRecuce για το οποίο διαφορετικά στάδια εκτέλεσης εναλλάσσονται μεταξύ κατανεμημένης μνήμης χώρου διευθύνσεων και κοινόχρηστης μνήμης χώρου διευθύνσεων για την βελτίωση της επίδοσης και της κλιμακωσιμότητας. Στην εξερεύνηση των υβριδικών χώρων διευθύνσεων εισάγουμε τέσσερις βελτιώσεις στην υλοποίηση του MapReduce: (1) Παράλληλους αλγόριθμους, χωρίς την χρήση συγχρονισμού (lock-free), για τον διαμοιρασμό δεδομένων, χρησιμοποιώντας συναρτήσεις που ορίζονται από τον χρήστη. (2) Μια κλιμακώσιμη, χωρίς διακοπές (interrupts), υλοποίηση του αλγορίθμου έργου-κλοπή (work-stealing) για αρχιτεκτονικές χωρίς την υποστήριξη υλικού για την συνοχή των κρυφών μνημών, χρησιμοποιώντας μόνο μνήμη που βρίσκεται μέσα στον επεξεργαστή για την ελαχιστοποίηση της αδράνειας (latency). (3) Βελτιστοποιημένη υλοποίηση αλγορίθμων φραγμάτων (barriers) χρησιμοποιώντας μνήμη που βρίσκεται μέσα στον επεξεργαστή για πολυπύρινες αρχιτεκτονικές χωρίς την υποστήριξη υλικού για την συνοχή των κρυφών μνημών. (4) Ένα νέο μηχανισμό που επιτρέπει την γρήγορη πρόσβαση από έναν πυρήνα στην τοπική μνήμη κάποιου άλλου πυρήνα, το οποίο επιταγχύνει την καθολική ανταλαγή δεδομένων. Συγκρίνουμε το HyMR με μία βελτιστοποιημένη υλοποίηση αναφοράς η οποία χρησιμοποιεί μόνο κατανεμημένους χώρους διευθύνσεων και βρίσκουμε ότι οι υβριδικοί χώροι διευθύνσεων βελτιώνουν την επίδοση κατά 1.71 χ. Επίσης συγκρίνουμε το HyMR με το Phoenix++, την καλύτερη υλοποίηση για συστήματα με υποστήριξη υλικού για την συνοχή των κρυφών μνημών, σε όρους κλιμακωσιμότητας και αποδοτικότητας σε σύγκριση με τον μέγιστο ρυθμό επεξεργασίας δεδομένων, όπου το HyMR αποδεικνύει βελτιώσεις κατά 3.1χ και 3.2χ αντίστοιχα. (EL)
This thesis introduces hybrid address spaces as a design methodology for implementing scalable runtime systems on many-core architectures without hardware support for cache coherence. We demonstrate hybrid address spaces in an implementation of MapReduce, a well-established programming model for large-scale, fault-tolerant data processing. Using the Intel Single- Chip Cloud Computer as an experimental testbed, we present HyMR, a staged MapReduce runtime system whereby different stages alternate between a distributed memory address space and a shared memory address space to improve performance and scalability. In exploring hybrid address spaces, we introduce four improvements in the implementation of MapReduce: (1) Lock-free data distribution algorithms, using user-defined splitter functions. (2) A scalable, interrupt-less implementation of work-stealing for non-coherent architectures using exclusively on-chip communication to minimize latency. (3) Optimized implementation for on-chip barrier algorithms for non-coherent many-core processors. (4) A new mechanism to enable fast access from a core to the private memory of another core on-chip, which accelerates global exchange operations. We compare HyMR to an optimized reference implementation using exclusively distributed address spaces and find that hybrid address spaces improve performance by a factor of 1.71 x (geometric mean). We also compare HyMR with Phoenix++, a state-of-art implementation for systems with hardware-managed cache coherence in terms of scalability and sustained to peak data processing bandwidth, where HyMR demonstrates improvements of a factor of 3.1x and 3.2x (geometric mean) respectively. (EN)

text
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης

Parallel Progmamming Models
Συστήματα χρόνου εκτέλεσης
Εκτίμηση πόζας
Single-Chip-Cloud
Παράλληλα προγραμματιστικά μοντέλα
MapReduce
Runtime Systems

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

English

2013-03-15


Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)