Μην πάει αμέσως ο νους σας στο κακό, δεν μιλώ για τους "Πυρήνες της φωτιάς".
Μιλώ για πυρήνες επεξεργαστών, την πολυπύρηνη επεξεργασία δεδομένων και πώς μπορεί να τους θέσει κανείς στην υπηρεσία του.
Όσοι ασχολούνται με τον προγραμματισμό και την υπολογιστική επεξεργασία ασυνήθιστα μεγάλου όγκου δεδομένων όλο και κάτι θα έχουν διαβάσει για δομές δεδομένων και αλγορίθμους αναζήτησης Minimal Perfect Hashing.
Το πρόβλημα είναι το εξής:
Έχει κανείς μια τεράστια λίστα δεδομένων της τάξεως μερικών εκατοντάδων MegaBytes ή ακόμα μεγαλύτερη.
Θέλει να φτιάξει μια εφαρμογή για να προβάλει τα δεδομένα αυτά σε μια οργανωμένη μορφή.
Ακόμα κι αν διαθέτει κανείς έναν σύγχρονο υπολογιστή με αρκετή μνήμη RAM, θα ήταν τρέλα να επιχειρήσει να φορτώσει όλα αυτά τα δεδομένα στη μνήμη.
Στις περισσότερες των περιπτώσεων δε η μνήμη του υπολογιστή απλά θα εξαντληθεί με ό,τι αυτό συνεπάγεται.
Από την άλλη η αναζήτηση δεδομένων μέσα σ' ένα αρχείο αποθηκευμένο στο σκληρό δίσκο συγκρίνοντας μια γραμμή (ή εγγραφή) κάθε φορά είναι χαρακτηριστικά αργή και ατελέσφορη.
Φανταστείτε ένα αρχείο με μερικά εκατομμύρια γραμμές (ή εγγραφές) στο οποίο πρέπει να αναζητήσετε μια συγκεκριμένη λέξη, η οποία μπορεί να βρίσκεται σε οποιαδήποτε θέση.
Θα πρέπει να διατρέξει κανείς όλες τις γραμμές (ή εγγραφές) συγκρίνοντας τις μία μία μέχρι να εντοπίσει την επιθυμητή λέξη.
Απλά δεν γίνεται.
Επινόησαν, λοιπόν, οι μαθηματικοί - προγραμματιστές κάποιους αλγορίθμους κατατεμαχισμού (hashing algorithms) που λύνουν αυτό το πρόβλημα με τη δημιουργία ειδικών συμπιεσμένων πινάκων αναζήτησης.
Η επίλυση όμως αυτού του προβλήματος γεννά άλλα δευτερεύοντα προβλήματα, όπως η ίδια η κατασκευή αυτών των πινάκων και ο χρόνος που απαιτείται γι' αυτό.
Στην εποχή των πολυπύρηνων επεξεργαστών δεν υπήρχε περίπτωση να μην αποπειραθεί να αξιοποιήσει κανείς την ισχύ τους και γι' αυτό το πρόβλημα, που δεν είναι διόλου ασήμαντο για όποιον καταγίνεται μ' αυτά τα πράγματα.
Έχοντας ο ίδιος παρόμοιο πρόβλημα και αναζητώντας κάποια αξιοπρεπή λύση, πήρε το μάτι μου μια σχετικά πρόσφατη δημοσίευση που πραγματεύεται αυτό ακριβώς το ζήτημα: την πολυπύρηνη (παράλληλη ή πολυνηματική) υπολογιστική επεξεργασία δεδομένων μεγάλου όγκου και την κατασκευή συμπιεσμένων πινάκων αναζήτησης. Πρόκειται γι' αυτήν εδώ τη δημοσίευση (https://arxiv.org/abs/1702.03154) του πανεπιστημίου Cornell.
Μέχρι τώρα παιδευόμουν με έναν άλλο αλγόριθμο (https://blog.demofox.org/2015/12/14/o1-data-lookups-with-minimal-perfect-hashing/) για το ίδιο θέμα, ο οποίος όμως μπορεί να τρέξει μόνο σειριακά.
Έσπασα το κεφάλι μου μήπως και καταφέρω και τον τρέξω σε πολυνηματική λειτουργία, αλλά τζίφος η προσπάθεια.
Είναι δοκιμασμένος και λειτουργεί σωστά μεν, πλην όμως για την κατασκευή του πίνακα αναζήτησης απαιτείται χρόνος γύρω στη μία ώρα και κάτι. Μιλάμε για περίπου 3.500.000 γραμματικούς τύπους. Είναι να σε πιάνει απελπισία.
Κάποια στιγμή, λοιπόν, θέλοντας να αξιοποιήσω και τους 8 πυρήνες του υπολογιστή μου, είπα να δοκιμάσω τον νέο πολυνηματικό αλγόριθμο.
Παρότι είναι γραμμένος σε C++, αμέσως διαπίστωσα ότι υπάρχει ένα μικρό πρόβλημα, μια και ο κώδικας είναι γραμμένος για μεταγλωττιστή GCC.
Τέτοιο πράγμα εγώ δεν θυμάμαι να έχω χρησιμοποιήσει άλλη φορά στο παρελθόν και προσπάθησα να τον τροποποιήσω για να μπορεί να μεταγλωττιστεί με άλλον compiler και να τρέξει σε περιβάλλον Windows.
Γενικά όμως η μεταφορά κώδικα από μια πλατφόρμα σε κάποια άλλη δεν είναι πάντα και ό,τι ευκολότερο.
Κάποια στιγμή κατάλαβα ότι χάνω χρόνο χωρίς να είμαι βέβαιος για το όποιο αποτέλεσμα.
Κάτι άλλο έπρεπε να γίνει επομένως και αυτό δεν ήταν άλλο από το να προσαρμοστώ εγώ στις απαιτήσεις του αλγορίθμου.
Αυτό, με λίγα λόγια, σήμαινε ότι έπρεπε να χρησιμοποιήσω κάποια άλλα εργαλεία απ' αυτά που συνήθιζα μέχρι τώρα και να μάθω καινούργια πράγματα πατώντας στις ήδη υπάρχουσες γνώσεις.
Από μια γρήγορη έρευνα κατάλαβα ότι με εργαλεία όπως το CodeBlocks (http://www.codeblocks.org) και το wxWidgets (https://www.wxwidgets.org) θα άξιζε να ασχοληθεί κανείς και να επενδύσει κάποιον χρόνο.
Δεν είχα άδικο. Μέσα σε ένα δεκαήμερο περίπου κατάφερα να εξοικειωθώ με τα συγκεκριμένα εργαλεία που είναι και δωρεάν και τυγχάνουν και ευρείας χρήσης από την παγκόσμια κοινότητα προγραμματιστών.
Να μην τα πολυλογώ, η διαφορά μεταξύ των δύο αλγορίθμων από άποψη χρόνου κατασκευής του πίνακα αναζήτησης για τα 3.500.000 περίπου γραμματικών τύπων είναι σαν τη μέρα με τη νύχτα.
Ο χρόνος κατασκευής από τα 70 - 80 λεπτά που απαιτούνταν με τον πρώτο αλγόριθμο κατέβηκε γύρω στο δίλεπτο.
Όλα αυτά γίνονται σε ένα μεταχειρισμένο μηχάνημα της DELL (Dell Precision T5400, 2x Quad-Core XEON E5420) των 150 € με διπλό τετραπύρηνο εξεργαστή σαν κι αυτό εδώ: http://rmania.net/kompyutri-dell--precision-t5400-2x-quad-core-xeon-e5420-quadro-2814.html
Στιγμιότυπα οθόνης από τη χρήση του αλγορίθμου και το αποτέλεσμα:
Μιλώ για πυρήνες επεξεργαστών, την πολυπύρηνη επεξεργασία δεδομένων και πώς μπορεί να τους θέσει κανείς στην υπηρεσία του.
Όσοι ασχολούνται με τον προγραμματισμό και την υπολογιστική επεξεργασία ασυνήθιστα μεγάλου όγκου δεδομένων όλο και κάτι θα έχουν διαβάσει για δομές δεδομένων και αλγορίθμους αναζήτησης Minimal Perfect Hashing.
Το πρόβλημα είναι το εξής:
Έχει κανείς μια τεράστια λίστα δεδομένων της τάξεως μερικών εκατοντάδων MegaBytes ή ακόμα μεγαλύτερη.
Θέλει να φτιάξει μια εφαρμογή για να προβάλει τα δεδομένα αυτά σε μια οργανωμένη μορφή.
Ακόμα κι αν διαθέτει κανείς έναν σύγχρονο υπολογιστή με αρκετή μνήμη RAM, θα ήταν τρέλα να επιχειρήσει να φορτώσει όλα αυτά τα δεδομένα στη μνήμη.
Στις περισσότερες των περιπτώσεων δε η μνήμη του υπολογιστή απλά θα εξαντληθεί με ό,τι αυτό συνεπάγεται.
Από την άλλη η αναζήτηση δεδομένων μέσα σ' ένα αρχείο αποθηκευμένο στο σκληρό δίσκο συγκρίνοντας μια γραμμή (ή εγγραφή) κάθε φορά είναι χαρακτηριστικά αργή και ατελέσφορη.
Φανταστείτε ένα αρχείο με μερικά εκατομμύρια γραμμές (ή εγγραφές) στο οποίο πρέπει να αναζητήσετε μια συγκεκριμένη λέξη, η οποία μπορεί να βρίσκεται σε οποιαδήποτε θέση.
Θα πρέπει να διατρέξει κανείς όλες τις γραμμές (ή εγγραφές) συγκρίνοντας τις μία μία μέχρι να εντοπίσει την επιθυμητή λέξη.
Απλά δεν γίνεται.
Επινόησαν, λοιπόν, οι μαθηματικοί - προγραμματιστές κάποιους αλγορίθμους κατατεμαχισμού (hashing algorithms) που λύνουν αυτό το πρόβλημα με τη δημιουργία ειδικών συμπιεσμένων πινάκων αναζήτησης.
Η επίλυση όμως αυτού του προβλήματος γεννά άλλα δευτερεύοντα προβλήματα, όπως η ίδια η κατασκευή αυτών των πινάκων και ο χρόνος που απαιτείται γι' αυτό.
Στην εποχή των πολυπύρηνων επεξεργαστών δεν υπήρχε περίπτωση να μην αποπειραθεί να αξιοποιήσει κανείς την ισχύ τους και γι' αυτό το πρόβλημα, που δεν είναι διόλου ασήμαντο για όποιον καταγίνεται μ' αυτά τα πράγματα.
Έχοντας ο ίδιος παρόμοιο πρόβλημα και αναζητώντας κάποια αξιοπρεπή λύση, πήρε το μάτι μου μια σχετικά πρόσφατη δημοσίευση που πραγματεύεται αυτό ακριβώς το ζήτημα: την πολυπύρηνη (παράλληλη ή πολυνηματική) υπολογιστική επεξεργασία δεδομένων μεγάλου όγκου και την κατασκευή συμπιεσμένων πινάκων αναζήτησης. Πρόκειται γι' αυτήν εδώ τη δημοσίευση (https://arxiv.org/abs/1702.03154) του πανεπιστημίου Cornell.
Μέχρι τώρα παιδευόμουν με έναν άλλο αλγόριθμο (https://blog.demofox.org/2015/12/14/o1-data-lookups-with-minimal-perfect-hashing/) για το ίδιο θέμα, ο οποίος όμως μπορεί να τρέξει μόνο σειριακά.
Έσπασα το κεφάλι μου μήπως και καταφέρω και τον τρέξω σε πολυνηματική λειτουργία, αλλά τζίφος η προσπάθεια.
Είναι δοκιμασμένος και λειτουργεί σωστά μεν, πλην όμως για την κατασκευή του πίνακα αναζήτησης απαιτείται χρόνος γύρω στη μία ώρα και κάτι. Μιλάμε για περίπου 3.500.000 γραμματικούς τύπους. Είναι να σε πιάνει απελπισία.
Κάποια στιγμή, λοιπόν, θέλοντας να αξιοποιήσω και τους 8 πυρήνες του υπολογιστή μου, είπα να δοκιμάσω τον νέο πολυνηματικό αλγόριθμο.
Παρότι είναι γραμμένος σε C++, αμέσως διαπίστωσα ότι υπάρχει ένα μικρό πρόβλημα, μια και ο κώδικας είναι γραμμένος για μεταγλωττιστή GCC.
Τέτοιο πράγμα εγώ δεν θυμάμαι να έχω χρησιμοποιήσει άλλη φορά στο παρελθόν και προσπάθησα να τον τροποποιήσω για να μπορεί να μεταγλωττιστεί με άλλον compiler και να τρέξει σε περιβάλλον Windows.
Γενικά όμως η μεταφορά κώδικα από μια πλατφόρμα σε κάποια άλλη δεν είναι πάντα και ό,τι ευκολότερο.
Κάποια στιγμή κατάλαβα ότι χάνω χρόνο χωρίς να είμαι βέβαιος για το όποιο αποτέλεσμα.
Κάτι άλλο έπρεπε να γίνει επομένως και αυτό δεν ήταν άλλο από το να προσαρμοστώ εγώ στις απαιτήσεις του αλγορίθμου.
Αυτό, με λίγα λόγια, σήμαινε ότι έπρεπε να χρησιμοποιήσω κάποια άλλα εργαλεία απ' αυτά που συνήθιζα μέχρι τώρα και να μάθω καινούργια πράγματα πατώντας στις ήδη υπάρχουσες γνώσεις.
Από μια γρήγορη έρευνα κατάλαβα ότι με εργαλεία όπως το CodeBlocks (http://www.codeblocks.org) και το wxWidgets (https://www.wxwidgets.org) θα άξιζε να ασχοληθεί κανείς και να επενδύσει κάποιον χρόνο.
Δεν είχα άδικο. Μέσα σε ένα δεκαήμερο περίπου κατάφερα να εξοικειωθώ με τα συγκεκριμένα εργαλεία που είναι και δωρεάν και τυγχάνουν και ευρείας χρήσης από την παγκόσμια κοινότητα προγραμματιστών.
Να μην τα πολυλογώ, η διαφορά μεταξύ των δύο αλγορίθμων από άποψη χρόνου κατασκευής του πίνακα αναζήτησης για τα 3.500.000 περίπου γραμματικών τύπων είναι σαν τη μέρα με τη νύχτα.
Ο χρόνος κατασκευής από τα 70 - 80 λεπτά που απαιτούνταν με τον πρώτο αλγόριθμο κατέβηκε γύρω στο δίλεπτο.
Όλα αυτά γίνονται σε ένα μεταχειρισμένο μηχάνημα της DELL (Dell Precision T5400, 2x Quad-Core XEON E5420) των 150 € με διπλό τετραπύρηνο εξεργαστή σαν κι αυτό εδώ: http://rmania.net/kompyutri-dell--precision-t5400-2x-quad-core-xeon-e5420-quadro-2814.html
Στιγμιότυπα οθόνης από τη χρήση του αλγορίθμου και το αποτέλεσμα:
