Evaluating NUMA-Aware optimizations for the reduce phase of the Phoenix++ MapReduce runtime
Φόρτωση...
Ημερομηνία
Συγγραφείς
Σουρής, Αναστάσιος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
MapReduce is a programming model used to process large volumes of data. To
implement an algorithm in the MapReduce programming model we need to provide
two methods called map and reduce. The map function transforms the input to a set
of (key, value) pairs. The reduce function receives as input all values associated with
a key, as they were produced by the map function, aggregates them according to
a user-supplied function and produces a single value as output. Phoenix++ is an
implementation of the MapReduce parallel programming model for shared memory
systems.
In this thesis we evaluate NUMA-aware optimization techniques for the reduce phase of the Phoenix++ implementation of the MapReduce parallel programming model for shared memory systems. A NUMA machine is comprised of a set of NUMA nodes that are linked together with interconnect links. Each NUMA node consists of its own local memory (i.e DRAM) and a number of CPUs. In this way, a CPU can access memory in its own NUMA node faster than memory located in other NUMA nodes.
To begin with, we evaluate two sets of methods that are based on the well-known and historical tournament-based barrier algorithm, whereby we hierarchically reduce the (key,value) pairs first within NUMA nodes and then among all NUMA nodes. The
second set of methods we evaluate are extensions of the current implementation of the reduce phase in the Phoenix++ runtime, whereby we implement various reduce task distribution policies that dictate to which thread a reduce task should be executed, where a reduce task implies the reduction over a specific range of keys.
We evaluate those methods against synthetic workloads and deduce that for the case where the workload exhibits a specific kind of locality we observe performance advantages of up to 30.85%.
Το MapReduce είναι ένα μοντέλο προγραμματισμού που χρησιμοποιείται για την επεξεργασία μεγάλων όγκων δεδομένων. Προκειμένου να προγραμματίσουμε έναν αλγόριθμο στο μοντέλο προγραμματισμού MapReduce, πρέπει να παρέχουμε δύο μεθόδους που ονομάζονται map και reduce. Η συνάρτηση map μετατρέπει την είσοδο σε ένα σύνολο ζευγών (κλειδί, τιμή). Η συνάρτηση reduce λαμβάνει ως είσοδο όλες τις τιμές που σχετίζονται με ένα κλειδί, όπως παρήχθησαν από τη συνάρτηση map, τις συγκεντρώνει σύμφωνα με μια συνάρτηση παρεχόμενη απο τον χρήστη και πα- ράγει μία μόνο τιμή ως έξοδο. Το Phoenix++ είναι μια υλοποίηση του μοντέλου παράλληλου προγραμματισμού MapReduce για κοινόχρηστα συστήματα μνήμης. Σε αυτή τη διατριβή αξιολογούμε τις τεχνικές βελτιστοποίησης για αρχιτεκτονικές NUMA στην φάση μείωσης του Phoenix++ που είναι υλοποίηση του μοντέλου πα- ράλληλου προγραμματισμού MapReduce για κοινόχρηστα συστήματα μνήμης. Ένα μηχάνημα NUMA αποτελείται από ένα σύνολο κόμβων NUMA που συνδέονται μαζί με συνδέσμους διασύνδεσης. Κάθε κόμβος NUMA αποτελείται από τη δική του το- πική μνήμη (δηλαδή DRAM) και έναν αριθμό CPU. Με αυτόν τον τρόπο, μια CPU μπορεί να αποκτήσει πρόσβαση στη μνήμη στον δικό της κόμβο NUMA ταχύτερα από τη μνήμη που βρίσκεται σε άλλους κόμβους NUMA. Κατ ’αρχά ., αξιολογούμε δύο σύνολα από μεθόδους που βασίζονται στον γνωστό και ιστορικό ιεραρχικό αλγόριθμο για barriers (tournament barrier algorithm), όπου μειώνουμε ιεραρχικά τα ζεύγη (κλειδί, τιμή) πρώτα μέσα στους κόμβους NUMA και μετά μεταξύ όλων των κόμβων NUMA. Το δεύτερο σύνολο μεθόδων που αξιολο- γούμε είναι οι επεκτάσεις της τρέχουσας εφαρμογής της φάσης μείωσης στο χρόνο εκτέλεσης του phoenix++, όπου εφαρμόζουμε διάφορες πολιτικές διανομής εργα- σιών reduce που υπαγορεύουν σε ποιο νήμα πρέπει να εκτελεστεί μια εργασία reduce, όπου μια εργασία reduce συνεπάγεται τη μείωση σε ένα συγκεκριμένο εύ- ρος κλειδιών. Αξιολογούμε αυτές τις μεθόδους έναντι συνθετικών φορτίων εργασίας και συμπεραίνουμε ότι στην περίπτωση όπου ο φόρτος εργασίας εμφανίζει ένα συ- γκεκριμένο είδος locality παρατηρούμε πλεονεκτήματα απόδοσης έως και 30,85%.
Το MapReduce είναι ένα μοντέλο προγραμματισμού που χρησιμοποιείται για την επεξεργασία μεγάλων όγκων δεδομένων. Προκειμένου να προγραμματίσουμε έναν αλγόριθμο στο μοντέλο προγραμματισμού MapReduce, πρέπει να παρέχουμε δύο μεθόδους που ονομάζονται map και reduce. Η συνάρτηση map μετατρέπει την είσοδο σε ένα σύνολο ζευγών (κλειδί, τιμή). Η συνάρτηση reduce λαμβάνει ως είσοδο όλες τις τιμές που σχετίζονται με ένα κλειδί, όπως παρήχθησαν από τη συνάρτηση map, τις συγκεντρώνει σύμφωνα με μια συνάρτηση παρεχόμενη απο τον χρήστη και πα- ράγει μία μόνο τιμή ως έξοδο. Το Phoenix++ είναι μια υλοποίηση του μοντέλου παράλληλου προγραμματισμού MapReduce για κοινόχρηστα συστήματα μνήμης. Σε αυτή τη διατριβή αξιολογούμε τις τεχνικές βελτιστοποίησης για αρχιτεκτονικές NUMA στην φάση μείωσης του Phoenix++ που είναι υλοποίηση του μοντέλου πα- ράλληλου προγραμματισμού MapReduce για κοινόχρηστα συστήματα μνήμης. Ένα μηχάνημα NUMA αποτελείται από ένα σύνολο κόμβων NUMA που συνδέονται μαζί με συνδέσμους διασύνδεσης. Κάθε κόμβος NUMA αποτελείται από τη δική του το- πική μνήμη (δηλαδή DRAM) και έναν αριθμό CPU. Με αυτόν τον τρόπο, μια CPU μπορεί να αποκτήσει πρόσβαση στη μνήμη στον δικό της κόμβο NUMA ταχύτερα από τη μνήμη που βρίσκεται σε άλλους κόμβους NUMA. Κατ ’αρχά ., αξιολογούμε δύο σύνολα από μεθόδους που βασίζονται στον γνωστό και ιστορικό ιεραρχικό αλγόριθμο για barriers (tournament barrier algorithm), όπου μειώνουμε ιεραρχικά τα ζεύγη (κλειδί, τιμή) πρώτα μέσα στους κόμβους NUMA και μετά μεταξύ όλων των κόμβων NUMA. Το δεύτερο σύνολο μεθόδων που αξιολο- γούμε είναι οι επεκτάσεις της τρέχουσας εφαρμογής της φάσης μείωσης στο χρόνο εκτέλεσης του phoenix++, όπου εφαρμόζουμε διάφορες πολιτικές διανομής εργα- σιών reduce που υπαγορεύουν σε ποιο νήμα πρέπει να εκτελεστεί μια εργασία reduce, όπου μια εργασία reduce συνεπάγεται τη μείωση σε ένα συγκεκριμένο εύ- ρος κλειδιών. Αξιολογούμε αυτές τις μεθόδους έναντι συνθετικών φορτίων εργασίας και συμπεραίνουμε ότι στην περίπτωση όπου ο φόρτος εργασίας εμφανίζει ένα συ- γκεκριμένο είδος locality παρατηρούμε πλεονεκτήματα απόδοσης έως και 30,85%.
Περιγραφή
Λέξεις-κλειδιά
Parallel programming, Map reduce, NUMA architectures, Phoenix++, Παράλληλος προγραμματισμός
Θεματική κατηγορία
MapReduce (Computer file)
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Δημακόπουλος, Βασίλειος Β.
Εξεταστική επιτροπή
Δημακόπουλος, Βασίλειος Β.
Ευθυμίου, Αριστείδης
Πιτουρά, Ευαγγελία
Ευθυμίου, Αριστείδης
Πιτουρά, Ευαγγελία
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 69-73
Ονόματα συντελεστών
Αριθμός σελίδων
73 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States