Parallel and distributed implementations of multiple and two-dimensional pattern matching algorithms

Abstract

Η αναζήτηση προτύπων αποτελεί ένα θεμελιώδες πρόβλημα στον κλάδο της Επιστήμης της Πληροφορικής. Σε αυτήν την διατριβή εξετάζεται το πρόβλημα της αναζήτησης πολλαπλών και διδιάστατων προτύπων. Η αναζήτηση πολλαπλών προτύπων μπορεί να οριστεί γενικά ως η εύρεση όλων των θέσεων σε ένα μονοδιάστατο αλφαριθμητικό, το επονομαζόμενο και ως κείμενο (text), στις οποίες εμφανίζονται ένα ή περισσότερα αλφαριθμητικά, τα επονομαζόμενα και ως πρότυπα (patterns), από ένα πεπερασμένο σύνολο προτύπων. Η αναζήτηση διδιάστατων προτύπων μπορεί να οριστεί γενικά ως η εύρεση όλων των θέσεων σε ένα διδιάστατο κείμενο στις οποίες εμφανίζεται ένα διδιάστατο πρότυπο. Η διατριβή αυτή γράφτηκε έχοντας τρεις διαφορετικούς στόχους. Ο πρώτος στόχος περιλαμβάνει την ταξινόμηση και μελέτη των αλγορίθμων που επιλύουν τα προβλήματα της αναζήτησης πολλαπλών και διδιάστατων προτύπων και την αξιολόγηση των επιδόσεων μερικών από τους πιο γνωστούς αλγορίθμους ανά κατηγορία για διαφορετικές παραμέτρους, συμπεριλαμβανομένου του μεγέθους του κειμένου και της αλφαβήτου καθώς και του μήκους των προτύπων. Αν και η θεωρητική μόνο μελέτη των αλγορίθμων μπορεί να είναι χρήσιμη, είναι γνωστό ότι αλγόριθμοι με εξαιρετική θεωρητική απόδοση μπορεί να έχουν, σε αρκετές περιπτώσεις, υποδεέστερες επιδόσεις από αλγόριθμους πιο απλής φύσεως, ανάλογα με τις τεχνικές υλοποίησης ή βελτιστοποίησης, την αρχιτεκτονική του συστήματος και τον τύπο των δεδομένων που χρησιμοποιούνται. Ο δεύτερος στόχος της διατριβής, είναι η βελτίωση της απόδοσης μερικών από τους πιο γνωστούς αλγορίθμους διδιάστατης αναζήτησης προτύπων, του Baker and Bird και του Baeza-Yates and Regnier. Και οι δύο αλγόριθμοι χρησιμοποιούν τον αλγόριθμο αναζήτησης πολλαπλών προτύπων Aho-Corasick ώστε να μετατρέψουν ουσιαστικά το πρόβλημα της αναζήτησης διδιάστατων προτύπων σε πρόβλημα αναζήτησης πολλαπλών προτύπων. Η διατριβή αυτή παρουσιάζει αποτελεσματικές παραλλαγές των δύο αλγορίθμων και αξιολογεί τις επιδόσεις τους για διαφορετικά είδη δεδομένων. Ο τρίτος στόχος αποτελεί την αύξηση των επιδόσεων των αλγορίθμων που επιλύουν τα προβλήματα της αναζήτησης πολλαπλών και διδιάστατων προτύπων, αλλά μέσα από μια διαφορετική προσέγγιση. Καθώς τα μεγέθη των δεδομένων που καλούνται να επεξεργαστούν οι αλγόριθμοι που παρουσιάζονται στη διατριβή αυτή αυξάνονται τα τελευταία χρόνια με σχεδόν εκθετικό ρυθμο, συχνά είναι ανέφικτη η εκτέλεση τους σειριακά από συμβατικούς υπολογιστές. Τα τελευταία χρόνια δημιουργήθηκαν διάφορα εργαλεία και API με σκοπό τη διευκόλυνση των προγραμματιστών ώστε να αξιοποιήσουν την τεράστια επεξεργαστική ισχύ μιας μονάδας επεξεργασίας γραφικών (GPU). Η χρήση μονάδων επεξεργασίας γραφικών στη θέση των επεξεργαστών για την εκτέλεση υπολογισμών γενικού σκοπού είναι γνωστή ως Εκτέλεση Υπολογισμών Γενικού Σκοπού σε Μονάδες Επεξεργασίας Γραφικών (GPGPU). Οι αλ- γόριθμοι αναζήτησης πολλαπλών και διδιάστατων προτύπων που παρουσιάζονται σε αυτή τη διατριβή υλοποιούνται παράλληλα σε διαφορετικές αρχιτεκτονικές συμπεριλαμβανομένων μονάδων επεξεργασίας γραφικών και υβριδικών συστοιχίων υπολογιστών. Επίσης, αναλύονται διαφορετικές τεχνικές υλοποίη- σης και βελτιστοποίησης και η απόδοση των υλοποιήσεων αξιολογείται για διαφορετικές παραμέτρους.