Implementing Scalable Parallel Programming Models with Hybrid Address Spaces

RDF 

 
Το τεκμήριο παρέχεται από τον φορέα :
Πανεπιστήμιο Κρήτης
Αποθετήριο :
E-Locus Ιδρυματικό Καταθετήριο
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο



Σημασιολογικός εμπλουτισμός/ομογενοποίηση από το EKT
2013 (EL)
Υλοποίηση κλιμακώσιμων παράλληλων προγραμματιστικών μοντέλων με υβριδικούς χώρους διευθύνσεων
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)

2013-03-15




*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.