| Περίληψη |
Το ταίριασμα αλφαριθμητικών προτύπων (string pattern matching) είναι ένα πεδίο
έρευνας στο οποίο έχει αφιερώσει σημαντικό ποσοστό έρευνας η επιστημονική
κοινότητα ανά τα χρόνια. Ήδη, από το 1970, επιστήμονες από διάφορους φορείς και
ερευνητικά πεδία, προσπαθούν συνεχώς να αναπτύξουν αλγορίθμους, τόσο έξυπνους
όσο και αποδοτικούς. Ακόμα όμως, το πρόβλημα της αντιστοίχισης αλφαριθμητικών
προτύπων αποτελεί ανοιχτό πεδίο σκέψης και μελέτης. Ο λόγος της ραγδαίας αυτής
δημοτικότητας της αντιστοίχισης αλφαριθμητικών προτύπων στην επιστημονική
κοινότητα, είναι η ευρεία χρήση και εφαρμογή της σε πολλές και ποικίλες περιοχές, όπως για παράδειγμα στην πληροφορική, στη βιοπληροφορική, στην υπολογιστική βιοϊατρική και άλλες.
Πρόσφατα, καθώς η τεχνολογία συνεχώς εξελίσσεται, η χρήση των παράλληλων
επεξεργαστών έχει αποτελέσει σημαντικό παράγοντα για την ανάπτυξη όλο και πιο γρήγορων και αποδοτικών συστημάτων. Ο προγραμματισμός αυτών των παράλληλων
επεξεργαστών–είτε αυτοί είναι πολυπύρηνοι επεξεργαστές (CPUs) είτε είναι
επεξεργαστές γραφικών γενικού σκοπού (GPGPUs)–βασίζεται σε πλατφόρμες που
επιτρέπουν στο χρήστη την εποπτεία και τον προγραμματισμό τους. Σε αυτή τη δουλειά,
οι πλατφόρμες που χρησιμοποιούνται ονομάζονται CUDA και OpenCL. Συγκεκριμένα, η
CUDA απευθύνεται σε επεξεργαστές γραφικών γενικού σκοπού της εταιρίας NVIDIA, σε αντίθεση με την OpenCL, η οποία επιτρέπει τον προγραμματισμό οποιουδήποτε είδους επεξεργαστή.
Σε αυτή τη δουλειά, παρουσιάζουμε μία βιβλιοθήκη για αντιστοίχιση αλφαριθμητικών
προτύπων που μέσω μιας αφηρημένης προγραμματιστικής διεπαφής, επιτρέπει την
χρήση της σε κάθε είδους πολυπύρηνο επεξεργαστή. Πέρα από την αντιστοίχιση απλών
αλφαριθμητικών προτύπων, η βιβλιοθήκη αυτή επιτρέπει τον εντοπισμό και το
ταίριασμα προτύπων που προκύπτουν από κανονικές γραμματικές. Για αυτόν το σκοπό,
αναπτύξαμε μία μηχανή παράλληλης αναζήτησης αλφαριθμητικών και κανονικών
εκφράσεων με την χρήση πολυπύρηνων επεξεργαστών και καρτών γραφικών. Επι
πλέον, η μηχανή μπορεί να πετύχει ταυτόχρονη αναζήτηση πολλών αλφαριθμητικών και κανονικών εκφράσεων σε είσοδο πολλαπλών δεδομένων με μία μόνο προσπέλαση αυτών.
Τέλος, η αξιολόγηση της απόδοσης του συστήματος αυτού, μέσω της βιβλιοθήκης που
παρέχουμε, έδειξε ότι μπορεί να επιτύχει μέχρι και 21 φορές μεγαλύτερη απόδοση στην αναζήτηση απλών αλφαριθμητικών, καθώς και μέχρι 15 φορές μεγαλύτερη απόδοση στην αναζήτηση κανονικών εκφράσεων, σε σχέση με τις αντίστοιχες εκδόσεις των αλγορίθμων για κεντρικούς επεξεργαστές. Συγκεκριμένα, το σύστημά μας μπορεί να επιτύχει απόδοση έως και 65Gbits/s στην αναζήτηση αλφαριθμητικών και έως 50 Gbits/s στην αναζήτηση κανονικών εκφράσεων.
|
A Massively parallel regular expression and string matching engine for commodity hardware
