1115201300045 - Ζαμπάτης Θεόδωρος
1115201500080 - Κωστακόντη Σοφία
1115201500128 - Πελεκούδας Ιωάννης
Στην εργασία αυτή καλούμαστε να υλοποιήσουμε τον αλγόριθμο ζεύξης πινάκων Radix Hash Join (RHS), ο οποίος κομματιάζει τα δεδομένα σε κατάλληλο μέγεθος έτσι ώστε κατά την επεξεργασία τους να μπορούν να χωρέσουν στην cache μνήμη του επεξεργαστή.
Το πρόγραμμα εκτελείται απευθείας χρησιμοποιώντας τα δεδομένα που υπάρχουν στον κατάλογο small
> make runή χρησιμοποιόντας κάποια άλλα αρχεία εισόδου (ονόματος file στο παράδειγμα)
> cat file.init file.work | ./joinόπου κατά συνθήκη, η τελευταία γραμμή του αρχείου init είναι 'Done'.
Το πρόγραμμα, ενώ διαβάζει τα filepaths, τα προσθέτει σε μια δομή με όνομα relations (vector<relList>) με την βοήθεια της emplace_back. Η emplace_back καλεί τον constructor της relList και μετά εκτελεί την push_back. Ο contructor αυτός κάνει map του αρχείου στην μνήμη και υπολογίζει τα στατιστικά του.
Αφού τελειώσει το διάβασμα των αρχείων, αρχίζει το διάβασμα των batches. Το διάβασμα αυτό γίνεται με τον ίδιο τρόπο (emplace_back) για κάθε ένα batch.
Ύστερα δημιουργούμε τον Job Scheduler. Ο scheduler αυτός είναι τύπου MainScheduler. Στην αρχικοποίησή του, δημιουργεί NUM_OF_THREADS JobSchedulers, όπου ο καθένας από αυτούς χειρίζεται NUM_OF_THREADS threads.
Για την πιο αποδοτική εκτέλεση των Queries, το πρόγραμμα παραλληλοποιείται σε 4 σημεία: στο histogram, στο partition, στο join των buckets, καθώς και στα queries στην main. Για το τελευταίο σημείο, δημιουργείται ένας κύριος job scheduler με NUM_OF_THREADS threads, ο οποίος προγραμματίζει τα queries δίνοντας τους έναν νέο job scheduler. Με αυτόν, παραλληλοποιούνται και τα άλλα 3 σημεία. Τα δεδομένα που επιστρέφονται μετά από κάθε παραλληλοποιημένο σημείο ενώνονται στο σύνολο τους και χρησιμοποιούνται στο επόμενο μέρος. Στο τέλος, τα αποτελέσματα κάθε παράλληλης εκτέλεσης αντιγράφονται στα αποτελέσματα του query. Αυτό θα μπορούσε να γίνεται και πιο αποδοτικά σε ορισμένες περιπτώσεις, ελέγχοντας αν το page είναι γεμάτο ή μισοάδειο και αλλάζοντας τους δείκτες, χωρίς να αντιγραφούν όλα τα results.
Για κάθε query δημιουργείται ένα QueryJob το οποίο γίνεται scheduled. Όταν μπει στην ουρά, το αναλαμβάνει ένα thread για την εκτέλεσή του. Κατά την εκτέλεση αυτή, γίνεται αντίστοιχη δημιουργία και δρομολόγηση στην multiRadixHashJoin, με την δημιουργία HistogramJobs, PartitionJobs και JoinJobs που στο σύνολο της εκτέλεσής τους υλοποιούν την συνάρτηση radixHashJoin.
Μετά την εκτέλεση ενός non-empty join δύο πινάκων για κάποιο query, εισάγεται η έννοια του intermediate results. Υπάρχουν τρεις περιπτώσεις. Η πρώτη είναι κανένας από τους δύο πίνακες να μην είχε συμμετάσχει σε προηγούμενο join οπότε οι intermediates τους είναι άδειοι. Σε αυτή την περίπτωση, για κάθε αποτέλεσμα στην δομή results γίνεται push back τα αντίστοιχα vectors στους intermediate πίνακές τους. Στην δεύτερη περίπτωση, ένας από τους δύο πίνακες είναι άδειος, Ενώ διασχίζουμε τα results, ψάχνουμε τις αντίστοιχες τιμές στον intermediate του πίνακα που υπάρχει ήδη και δημιουργούμε έναν νέο intermediate με τις αντιστίστοιχες πλειάδες για όλους τους πίνακες που υπήρχαν στον intermediate. Στην τρίτη και τελευταία περίπτωση, οι δύο πίνακες των results είναι ήδη στον intermediate οπότε δημιουργείται νέος με κάθε πλειάδα από τον παλιό όπου τα ζευγάρια των vector των πινάκων του join αντιστοιχούν με τα ζευγάρια των results.
Τα αποτελέσματα του κάθε query μένουν αποθηκευμένα στην δομή Query οπότε και εκτυπώνονται όλα μαζί μετά την εκτελεσή όλων.
Τα στατιστικά στοιχεία για κάθε σχέση, υπολογίζονται στην άρχη, όταν διαβάζουμε τη σχέση και παίρνουμε τα υπόλοιπα στοιχεία της. Επιπλεόν, για κάθε query, ανανεώνονται αφού εκτελεστούν τα φίλτρα. Δυστυχώς, λόγω χρόνου, δεν ήταν δυνατή η υλοιποίηση των υπόλοιπων ζητουμένων και του enumeration. :(
Στα μηχανήματα Linux της σχολής είχαμε τους εξής χρόνους:
Χωρίς profiler:
make runΧρόνος εκτέλεσης: Περίπου 3:17.81 λεπτά
Για την μείωση του χρόνου εκτέλεσης καταφύγαμε στην λύση της δημιουργίας profiler, ο οποίος κρατάει δεδομένα για την εκτέλεση του προγράμματος.
Έτσι, με δημιουργία profiler και εκτέλεση χωρίς το τελευταίο batch (περίπου 15 λεπτά):
g++ -std=c++11 *.cpp -pthread -Ofast -march=native -funroll-loops -fprofile-generate
cat small/small.init small/small.work | ./a.outτελικό compile (χρησιμοποιώντας τον profiler):
g++ -std=c++11 *.cpp -pthread -Ofast -march=native -funroll-loops -fprofile-use -fprofile-correction
cat small/small.init small/small.work | ./a.outΧρόνος εκτέλεσης: Περίπου 2 λεπτά
Για περαιτέρω μείωση του χρόνου εκτέλεσης θα πρέπει να προσεγγίσουμε την υλοποίηση του Intermediate με διαφορετικό τρόπο.