Advanced Joins on GPUs

Abstract

Over the past years, the rise of General Purpose GPU (GPGPU) paradigm has become more evident in high-performance computing. The massive parallelism that GPUs offer at low cost is the catalyst for its adoption in numerous computational intensive applications, where tremendous speedup gains are reported due to the ease of parallelization of the algorithms they encapsulate. This thesis studied more advanced data management problems such as inequality and set similarity joins, along with the set intersection and containment operators on the GPGPU paradigm. Due to the inherent quadratic complexity of these problems, direct performance gains are unachievable. However, as shown in this thesis by designing co-processing techniques that take advantage of the different and complementary characteristics offered by CPUs and GPUs, tangible speedup gains are achieved over standalone implementations and other multi-threaded CPU solutions. More specifically, for the inequality or theta joins, efficient implementations on a GPU are provided along with several optimizations to further improve performance. The best performing technique adopts a sliding window approach, and by resource reuse and through memory hierarchy exploitation, manages to achieve speedups of an order of magnitude for the aggregation query and of 2.7X for the select query over other CPU alternatives.For the set similarity join, a co-processing CPU-GPU technique is proposed with the goal to utilize both processors. As a result, due to the execution overlap between the CPU and GPU tasks, significant speedups, which can reach up to 2.6X, are achieved over other alternatives in several cases. Furthermore, an empirical evaluation of the state-of-the-art GPU-enabled set similarity techniques is also presented, along with several key insights into under which circumstances each technique performs better. The main outcome is that there is no dominant solution; each technique has its own pros and cons based on specific dataset characteristics. Based on these findings, a hybrid framework for the set similarity join problem his proposed, which encapsulates the state-of-the-art CPU and GPU set similarity join techniques. By introducing two workload allocation strategies, the hybrid framework manages to utilize both the CPU and the GPU with high efficiency and achieves speedups of up to 3.25X over standalone techniques and of an order of magnitude over other parallel CPU solutions. Finally, by adapting techniques initially proposed for graph analytics and matrix multiplication on the GPU, several hybrid GPU techniques for the set intersection operator on large sets are proposed. In addition, the first known technique for the set containment operator in the GPGPU paradigm, which involves a co-processing scheme between the CPU and the GPU, is introduced. In a thorough experimental evaluation, the proposed techniques for both operators manage to achieve performance speedup of an order of magnitude over the respective multi-threaded CPU alternatives.

Τα τελευταία χρόνια υπάρχει μία μεγάλη αύξηση στη χρήση των μονάδων επεξεργαστών γραφικών (ΜΕΓ) για την επίλυση προβλημάτων. Συγκεκριμένα, πέρα από την απόδοση γραφικών, μέσω του ετερογενούς προγραμματιστικού μοντέλου που ονομάζεται Γενικού Σκοπού ΜΕΓ, μία ή περισσότερες ΜΕΓ μπορούν να χρησιμοποιηθούν συνεργατικά με παραδοσιακές κεντρικές μονάδες επεξεργασίας (ΚΜΕ) για την επίλυση προβλημάτων. Το κύριο πλεονέκτημα των ΜΕΓ είναι ο υψηλός βαθμός παραλληλισμού που προσφέρουν έναντι πολύ χαμηλού ενεργειακού κόστους λόγω της αρχιτεκτονικής τους. Πέρα από το χαμηλό ενεργειακό κόστος, η χρήση των ΜΕΓ έχει οδηγήσει και σε πάρα πολύ μεγάλες αυξήσεις των επιδόσεων, ειδικά στον τομέα της μηχανικής μάθησης και της βαθιάς γνώσης. Ο λόγος που συμβαίνει αυτό είναι επειδή οι τομείς αυτοί ενθυλακώνουν ομαλούς αλγορίθμους. Δηλαδή αλγορίθμους στους οποίους ο έλεγχος ροής αλλά και αναφορές σε θέσεις μνήμης δεν εξαρτώνται από δεδομένα εισόδου. Χαρακτηριστικά παραδείγματα ομαλών αλγορίθμων είναι ο πολλαπλασιασμός πινάκων και η συνέλιξη. Σε αυτά τα προβλήματα, το παράλληλο περιβάλλον των ΜΕΓ ευνοείται καθώς διαβάζει μεγάλους όγκους δεδομένων, κάνει τις απαραίτητες πράξεις και γράφει σε προκαθορισμένες θέσεις μνήμης χωρίς να υπάρχουν σύνθετες διακλαδώσεις.Στον αντίποδα, για μη ομαλούς αλγορίθμους, όπου ο έλεγχος και οι αναφορές σε θέσεις μνήμης καθορίζονται από τα δεδομένα εισόδου και τις δομές δεδομένων, η κατάσταση είναι πιο περίπλοκη. Συγκεκριμένα, λόγω της φύσης τους, αυτοί οι αλγόριθμοι απαιτούν αλληλοεπικοινωνία μεταξύ των εκτελούμενων νημάτων στην MEΓ, ανάγνωση και γράψιμο σε μη προκαθορισμένες θέσεις μνήμης, χαρακτηριστικά που δεν ευνοούν το παράλληλο περιβάλλον της ΜΕΓ. Αυτό έχει ως αποτέλεσμα την πολύ μικρότερη αύξηση των επιδόσεων σε σχέση με τους ομαλούς αλγορίθμους.Ένα χαρακτηριστικό παράδειγμα μη ομαλών αλγορίθμων είναι οι συνδέσεις, όπου αντικείμενα από δύο ή περισσότερες συλλογές συνδέονται βάσει μίας συνθήκης σύνδεσης. Οι συνδέσεις αποτελούν θεμέλιο λίθο στη διαχείριση δεδομένων με χαρακτηριστική εφαρμογή σε πεδία όπως οι βάσεις δεδομένων, η εξόρυξη δεδομένων και η ανάλυση οντοτήτων. Ο πιο μελετημένος τύπος σύνδεσης σε ΜΕΓ είναι οι συνδέσεις ισότητας για τις οποίες έχουν αναφερθεί σημαντικές αυξήσεις των επιδόσεων έναντι υλοποιήσεων που εκτελούνται σε ΚΜΕ.Υπάρχουν πιο περίπλοκοι τύποι συνδέσεων για τους οποίους αφενός δεν υπάρχει ενδελεχής μελέτη σε ΜΕΓ, αφετέρου παραλληλοποιούνται πιο δύσκολα. Το κίνητρο της παρούσας διατριβής ήταν η μελέτη τέτοιων τύπων συνδέσεων και στα πλαίσια αυτής τους χαρακτηρίζουμε προηγμένους. Για την ανάπτυξη των τεχνικών χρησιμοποιήθηκε η κλειστού κώδικα προγραμματιστική πλατφόρμα της CUDA η οποία είναι ιδιοκτησία της NVIDIA.Συγκεκριμένα μελετήθηκαν και αναπτύχθηκαν λύσεις στο παράλληλο περιβάλλον μιας ΜΕΓ που αφορούν τις θ-συνδέσεις όπου η συνθήκη σύνδεσης είναι αυθαίρετη και οι συνδέσεις ομοιότητας σε σύνολα, όπου βάσει μιας απόστασης ομοιότητας και ενός κατωφλιού, δύο σύνολα μπορούν να θεωρηθούν όμοια. Επιπρόσθετα, μελετήθηκαν και δύο τελεστές πάνω σε σύνολα: (α) ο τελεστής εύρεσης τομής μεταξύ δύο συνόλων, και (β) ο τελεστής σύνδεσης περιεκτικότητας μεταξύ δύο συνόλων, ο οποίος επιστρέφει το βαθμό που ένα σύνολο εμπεριέχεται σε ένα άλλο.Συγκεκριμένα, το πρώτο πρόβλημα που μελετήθηκε αφορούσε τις θ-συνδέσεις που είναι η πιο γενική μορφή σχεσιακών συνδέσεων, καθώς επιτρέπoυν τη χρήση τελεστών ανισότητας στη συνθήκη σύνδεσης. Σε μια γενική θ-σύνδεση μεταξύ δύο σχέσεων, όλοι οι πιθανοί συνδυασμοί πλειάδων, δηλαδή το καρτεσιανό γινόμενο τους, μπορεί να χρειαστεί να ελεγχθεί. Το γεγονός αυτό οδηγεί σε τετραγωνική χρονική πολυπλοκότητα. Επιπρόσθετα, χώρος τετραγωνικής πολυπλοκότητας απαιτείται να δεσμευτεί στη χειρότερη περίπτωση όπου η συνθήκη σύνδεσης είναι αληθής για όλους τους συνδυασμούς. Στην παρούσα διατριβή μελετήθηκαν και υλοποιήθηκαν λύσεις για δύο ερωτήματα θ-συνδέσεων ανάμεσα σε δύο σχέσεις: (α) ένα συναθροιστικό, του οποίου το αποτέλεσμα είναι μόνο μία τιμή, και (β) ένα γενικό ερώτημα το οποίο παράγει πολλαπλές πλειάδες εξόδου. Μέσα από μία σειρά βελτιστοποιήσεων που εκμεταλλεύονται την ιεραρχία μνημών της ΜΕΓ και αποδοτικού επιμερισμού του φόρτου εργασίας ανάμεσα στα εκτελούμενα νήματα της ΜΕΓ, οι τεχνικές της διατριβής καταφέρνουν αύξηση της απόδοσης αναφορικά με το χρόνο εκτέλεσης μέχρι και μία τάξη μεγέθους. Το δεύτερο πρόβλημα που μελετήθηκε αφορούσε τις συνδέσεις ομοιότητας σε σύνολα. Συγκεκριμένα, δοθέντων δύο συλλογών από σύνολα και ενός κατωφλιού, η σύνδεση ομοιότητας συνόλων υπολογίζει για κάθε ζεύγος συνόλων αν είναι όμοια. Δηλαδή αν ο βαθμός ομοιότητας τους βάσει μίας απόστασης είναι μεγαλύτερος ή ίσος από το κατώφλι. Στη βάση τους οι συνδέσεις ομοιότητας συνόλων είναι τετραγωνικής πολυπλοκότητας. Οι υπάρχουσες τεχνικές της βιβλιογραφίας είναι κυρίως ευριστικές και εστιάζουν στο πρώτο τους στάδιο όπου χρησιμοποιούν ένα μηχανισμό φιλτραρίσματος για να μειώσουν τον αριθμό ζευγών που πρέπει τελικά να ελεγχθούν για το αν είναι όμοια. Πιο συγκεκριμένα, για κάθε ζεύγος συνόλων ο βαθμός ομοιότητας μεταφράζεται σε έναν αριθμό που υποδηλώνει πόσα κοινά στοιχεία πρέπει να έχουν τα δύο σύνολα για να θεωρηθούν όμοια. Η πιο διαδεδομένη απόσταση που χρησιμοποιείται στη βιβλιογραφία και χρησιμοποιήθηκε και στην διατριβή είναι η Jaccard. Η συνεισφορά της παρούσας διατριβής για τις συνδέσεις ομοιότητας σε σύνολα είναι τρίπτυχη.Στο πρώτο στάδιο, αναπτύχθηκε μια συνεργατική τεχνική στην οποία μία ΚΜΕ και μία ΜΕΓ συνεργάζονται για την επίλυση τους προβλήματος της σύνδεσης ομοιότητας σε σύνολα. Συγκεκριμένα, η ΚΜΕ κάνει το φιλτράρισμα και έπειτα περνά στην ΜΕΓ για έλεγχο τα ζεύγη συνόλων που περνάνε όλα τα φίλτρα. Αυτό μπορεί να οδηγήσει σε επικάλυψη της εκτέλεσης μεταξύ της ΚΜΕ και της ΜΕΓ, γεγονός που οδηγεί σε σημαντική αύξηση των επιδόσεων, έως και 2.6 φορές έναντι των καλύτερων τεχνικών που τρέχουν σε ΚΜΕ, όταν τα πλήθη των ζευγών που ελέγχονται είναι στην τάξη των δισεκατομμυρίων. Επιπρόσθετα, ο χρόνος εκτέλεσης της ΜΕΓ κρύβεται τελείως από το χρόνο εκτέλεσης της ΚΜΕ. Οι επιδόσεις της συνεργατικής τεχνικής που προτείνεται στη διατριβή φράζονται από το χρόνο εκτέλεσης του φιλτραρίσματος στην ΚΜΕ.Στο δεύτερο στάδιο, πραγματοποιήθηκε μία εκτενής συγκριτική αξιολόγηση των καλύτερων τεχνικών της βιβλιογραφίας που αντιμετωπίζουν το πρόβλημα της σύνδεσης ομοιότητας σε σύνολα είτε εξ' ολοκλήρου σε μία ΚΜΕ ή ΜΕΓ, είτε με τη συνεργατική τεχνική που προτείνεται στην παρούσα διατριβή. Για την αξιολόγηση των τεχνικών χρησιμοποιήθηκαν δεδομένα πραγματικού κόσμου αλλά και τεχνητά. Το κύριο συμπέρασμα της συγκριτικής μας μελέτης είναι ότι δεν υπάρχει ξεκάθαρα καλύτερη λύση. Βάσει των χαρακτηριστικών που διέπουν τα δεδομένα εισόδου, όπως το μέγεθος της συλλογής των συνόλων, το μέσο μέγεθος των συνόλων της συλλογής αλλά και του βαθμού ομοιότητας που ορίζεται στο ερώτημα, η συμπεριφορά κάθε τεχνικής αλλάζει. Συνοπτικά, σε πολύ υψηλές τιμές του βαθμού ομοιότητας η χρήση της ΚΜΕ φαίνεται να είναι αρκετή με εξαίρεση όταν έχουμε μεγάλες συλλογές συνόλων και μεγάλο μέσο μέγεθος συνόλου όπου η συνεργατική λύση μπορεί να μειώσει τους χρόνους εκτέλεσης. Σε χαμηλότερες τιμές του βαθμού ομοιότητας και σε μικρές ή μεσαίου μεγέθους συλλογές συνόλων, η χρήση της ΜΕΓ αποδίδει καλύτερα. Αντίθετα, σε μεγαλύτερες συλλογές συνόλων, η συνεργατική λύση φαίνεται στην πλειοψηφία των περιπτώσεων να αποδίδει καλύτερα. Για πολύ χαμηλές τιμές του βαθμού ομοιότητας, όπου το φιλτράρισμα παύει να είναι ισχυρό, τις καλύτερες επιδόσεις έχουν τεχνικές ωμής βίας που εκτελούνται σε ΜΕΓ.Στο τρίτο στάδιο, τα αποτελέσματα της συγκριτικής αξιολόγησης μαζί με το γεγονός ότι άλλα παράλληλα περιβάλλοντα όπως το MapReduce δεν μπορούν να προσφέρουν αποδοτικότερες λύσεις στο πρόβλημα, αποτέλεσαν εφαλτήριο για την ανάπτυξη ενός υβριδικού εργαλείου που θα ενθυλακώνει τις καλύτερες ΚΜΕ και ΜΕΓ τεχνικές. Στόχος του υβριδικού εργαλείου είναι η διάσπαση του φόρτου εργασίας ανάμεσα σε μία ΚΜΕ και μία ΜΕΓ, αλλά και η μείωση του ανενεργού χρόνου των επεξεργάστων όσο το δυνατόν περισσότερο γίνεται. Η διάσπαση του φόρτου γίνεται μέσω δύο διαφορετικών στρατηγικών. Αρχικά, στη στρατηγική της ουράς, στην οποία όλο το πρόβλημα διασπάται σε συνδέσεις μικρότερου μεγέθους, οι οποίες εισάγονται σε μία ουρά από την οποία η ΚΜΕ και η ΜΕΓ τις εξάγουν για να έχουν συνεχώς φόρτο εργασίας. Η δεύτερη στρατηγική είναι η διχοτόμηση, στην οποία γίνεται η διάσπαση του φόρτου σε δύο μεγάλα τμήματα με τη ΚΜΕ και τη ΜΕΓ να αναλαμβάνουν από ένα. Το σημείο διχοτόμησης καθορίζεται από παράμετρο εισόδου μαζί με το βαθμό ομοιότητας. Έπειτα από εκτενή πειραματική αξιολόγηση, το υβριδικό εργαλείο που προτείνεται καταφέρνει να βελτιώσει τους χρόνους σε όλες τις περιπτώσεις. Γενικά, η στρατηγική της διχοτόμησης είναι πιο εύρωστη γιατί έχει μικρότερες απαιτήσεις σε μνήμη. Σε σύγκριση με μία πρόσφατη παράλληλη υλοποίηση που τρέχει εξ' ολοκλήρου σε ΚΜΕ, το υβριδικό εργαλείο καταφέρνει και πετυχαίνει ακόμα μεγαλύτερη αύξηση των επιδόσεων.Το τελευταίο πρόβλημα που μελετήθηκε αφορούσε την αποδοτική υλοποίηση δύο τελεστών, αυτόν της εύρεσης τομής, όπου δοθέντων δύο συνόλων παράγει ένα τρίτο που περιέχει όλα τα κοινά στοιχεία, και αυτόν της σύνδεσης περιεκτικότητας, όπου η έξοδος είναι ο βαθμός περιεκτικότητας του ενός συνόλου στο άλλο. Το πρόβλημα της εύρεσης τομής έχει μελετηθεί έμμεσα στο περιβάλλον της ΜΕΓ μέσω εργασιών που αφορούν γράφους και συγκεκριμένα στο πρόβλημα της μέτρησης τριγώνων ενός γράφου. Όλες οι τεχνικές στη βιβλιογραφία για ΜΕΓ είναι αποδοτικές σε σύνολα μικρού μεγέθους, καθώς ο μέσος βαθμός των γράφων του πραγματικού κόσμου είναι αρκετά μικρός. Όταν αυξάνονται όμως τα μεγέθη των συνόλων, στην τάξη των εκατοντάδων χιλιάδων ή εκατομμυρίων, χρειάζεται καλύτερη αξιοποίηση της ΜΕΓ για να υπάρχει κλιμάκωση. Ως εκ τούτου, μία από τις βασικές συνεισφορές της διατριβής είναι η εξαγωγή των υπαρχουσών τεχνικών της βιβλιογραφίας, η τροποποίηση τους, καθώς και η ανάπτυξη υβριδικών τεχνικών που μπορούν να διαχειρίζονται πολύ μεγάλα σύνολα πιο αποδοτικά. Η αξιολόγηση των τεχνικών και για τους δύο τελεστές έγινε σε δύο προβλήματα, αυτό του απλού ζεύγους, όπου ο τελεστής τρέχει πάνω σε ένα μόνο ζεύγος συνόλων, και αυτό των πολλαπλών ζευγών, όπου ο τελεστής εφαρμόζεται σε κάθε πιθανό ζεύγος ανάμεσα σε k σύνολα. Για το πρόβλημα του απλού ζεύγους, το κατώτερο όριο χρονικής πολυπλοκότητας είναι γραμμικό, ενώ για το πρόβλημα των πολλαπλών ζευγών, η χρονική πολυπλοκότητα είναι τετραγωνική ως προς k. Η πειραματική αξιολόγηση των τροποποιημένων τεχνικών αλλά και των υβριδικών που προτείνονται στη διατριβή φανερώνει σημαντική αύξηση των επιδόσεων έναντι τεχνικών που τρέχουν στην ΚΜΕ, η οποία μπορεί να φτάσει και τη μία τάξη μεγέθους.Συμπερασματικά, σύμφωνα με τα αποτελέσματα και τη γνώση που αποκομίστηκε κατά την εκπόνηση της διατριβής, για να επιτευχθεί καλή αύξηση των επιδόσεων σε προβλήματα διαχείρισης δεδομένων με χρήση ΜΕΓ, οι λύσεις πρέπει να υλοποιούνται προσεκτικά σε χαμηλό επίπεδο και να εκμεταλλεύονται στο έπακρο όλο το οπλοστάσιο της ΜΕΓ, από την ιεραρχία μνημών έως και τη διατήρηση ενός υψηλού βαθμού παραλληλισμού ανάμεσα στα εκτελούμενα νήματα. Επιπρόσθετα, για την επιτεύξη ακόμα καλύτερων επιδόσεων, ΚΜΕ και ΜΕΓ πρέπει να λειτουργούν συνεργατικά και συμπληρωματικά έτσι ώστε η ετερογενεία που προσφέρουν ως όμαδα να αξιοποιείται από λύσεις που στοχεύουν στην επίλυση μεγάλων προβλημάτων.