Η εργασία αυτή εισάγει τους υβριδικούς χώρους διευθύνσεων ως τεχνική για την υλοποίηση κλιμακώσιμων συστημάτων χρόνου εκτέλεσης σε πολυπύρηνες αρχιτεκτονικές χωρίς την υποστήριξη υλικού για την συνοχή των κρυφών μνημών. Παρουσιάζουμε τους υβριδικούς χώρους διευθύνσεων για την υλοποίηση του 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)
