Optimizing algorithmic workloads and data structures for hardware accelerators
Authors: Χρυσός Γρηγόριος 
Published: August 2021

Η επεξεργασία μεγάλου όγκου δεδομένων θεωρείται μία ταχέως αναπτυσσόμενη και επεξεργαστικά πολύ απαιτητική κατηγορία προβλημάτων. Η παρούσα διατριβή επικεντρώνεται στην αποδοτική αναπαράσταση, σε υλικό πολύπλοκων και με μεγάλες απαιτήσεις δεδομένων αλγορίθμων, εκμεταλλευόμενη τον παραλληλισμό και την υψηλών ταχυτήτων επικοινωνία που οι διάφορες πλατφόρμες υλικού προσφέρουν. Επίσης, παρουσιάζει τα οφέλη στην απόδοση που μπορεί να προσφέρει η απεικόνιση τέτοιου είδους αλγορίθμων σε πλατφόρμες υλικού όταν συγκριθούν με τις υπάρχουσες “βέλτιστες” λύσεις λογισμικού. Αυτή η εργασία παρουσιάζει την αποδοτικότητα της απεικόνισης αλγορίθμων στο υλικό από τρία διαφορετικά πεδία εφαρμογών, την βιοπληροφορική, την περιοχή “εξόρυξης” πληροφορίας και την περιοχή “εξόρυξης” γράφων. Μία ιδιαίτερα αναπτυσσόμενη επιστημονική περιοχή που συνδυάζει την επεξεργασία μεγάλου όγκου με πολύπλοκες δομές δεδομένων είναι ο τομέας της βιοπληροφορικής. Σε αυτή την εργασία παρουσιάζεται το πρόβλημα της εύρεσης γονιδίων, το οποίο χρησιμοποιεί Μαρκοβιανά μοντέλα για την αναγνώριση προτύπων. Οι προτεινόμενες αρχιτεκτονικές για τα Μαρκοβιανά μοντέλα προσφέρουν μέχρι και μία τάξη μεγέθους καλύτερη απόδοση σε σύγκριση με την βέλτιστη των αλγορίθμων σε έναν σύγχρονης τεχνολογίας υπολογιστή. Το δεύτερο πεδίο εφαρμογών στο οποίο επικεντρώνεται αυτή η εργασία είναι το πεδίο της “εξόρυξης” δεδομένων. Οι συγκεκριμένοι αλγόριθμοι εξαγάγουν χρήσιμες πληροφορίες, για παράδειγμα αναγνώριση προτύπων από μεγάλους όγκους δεδομένων. H Decision Tree ταξινόμηση (DTC) είναι μία απλή και ευρέως χρησιμοποιούμενη μέθοδος ταξινόμησης στον τομέα της “εξόρυξης” δεδομένων. Παρουσιάζονται δύο αρχιτεκτονικές για το DTC πρόβλημα, οι οποίες απεικονίζονται σε μία τελευταίας τεχνολογίας πλατφόρμα με πολλαπλές FPGAs, η οποία υποστηρίζει γρήγορη είσοδο/έξοδο μεταφοράς δεδομένων. Τα αποτελέσματα δείχνουν ότι το σύστημα μας έχει καλύτερη απόδοση για τουλάχιστον μία τάξη μεγέθους από κάθε άλλη υπάρχουσα υλοποίηση, είτε σε λογισμικό είτε σε υλικό, για το DTC πρόβλημα.Η τρίτη εφαρμογή με την οποία ασχοληθήκαμε είναι η εύρεση συχνών κοινών υπογράφων (FSM) από την περιοχή της “εξόρυξης” γράφων. Υλοποιήθηκε ένας από τους πιο αποδοτικούς FSM αλγορίθμους, gSpan αλγόριθμος, σε μία πλατφόρμα με πολλαπλές FPGAs και επιτεύχθηκε μία τάξης μεγέθους επιτάχυνση της απόδοσης σε σύγκριση με την βέλτιστη έκδοση του αλγορίθμου στο software. Τέλος, αυτή η εργασία παρουσιάζει μία διαφορετική αλγοριθμική προσέγγιση του FSM προβλήματος χρησιμοποιώντας αναδρομή και την αποδοτική απεικόνιση στο υλικό. Όλες οι προτεινόμενες υβριδικές αρχιτεκτονικές υλικού/λογισμικού σε αυτή την εργασία είναι επεκτάσιμες και μπορούν χρησιμοποιηθούν σε διάφορες υλοποιήσεις λογισμικού βελτιώνοντας την απόδοση του τελικού συστήματος. Επίσης, οι περιγραφόμενες αρχιτεκτονικές είναι γενικές και δίνουν αποδοτικές λύσεις για πολλά προβλήματα σε διαφορετικά πεδία εφαρμογών. Τέλος, τα υλοποιημένα συστήματα είναι σημαντικά αποδοτικότερα ως προς την κατανάλωση ενέργειας σε σύγκριση με άλλα σύγχρονα συστήματα. Συμπερασματικά, αυτή η εργασία υποστηρίζει ότι οι πλατφόρμες υλικού προσφέρουν γρηγορότερες και ενεργειακά αποδοτικότερες λύσεις για τα απαιτητικά και ευρέως εξαπλωμένα προβλήματα που σχετίζονται με την επεξεργασία μεγάλου όγκου δεδομένων.