Optimizing algorithmic workloads and data structures for hardware accelerators

Abstract

The data intensive computing is considered as a long standing, rapidly emerging and computationally demanding workload category. This thesis focuses mainly on the efficient hardware-based implementation of complex and data intensive algorithms, taking advantage of the leverage parallelism and the high throughput that various hardware platforms can offer. We, also, present the high performance advantages that the mapping of those data demanding algorithms on hardware-based platforms can offer, when compared to the existing official software solutions. This thesis presents the algorithm mapping procedure and effectiveness, derived from three different application domains; the bioinformatics research area, the data mining domain and the graph mining domain.An important scientific area that combines both the big data processing and the complex data structures is the bioinformatics area. We focused on the gene finding problem, which uses the Hidden Markov Models (HMM) that are considered as one of the most efficient tools for pattern recognition. The proposed HMM architectures can offer up to one order of magnitude performance acceleration when compared to the implementation of the basic HMM processes on a high-end server.The second application domain that this thesis focuses on is the data mining domain. The data mining algorithms extract useful information, e.g. data patterns, from huge datasets. The Decision Tree Classification (DTC) is a simple and widely-used classification technique in data mining. We present two hardware-based architectures for the DTC problem, which are mapped on a high end multi-FPGA platform supporting fast I/O data transmission. The performance results show that our system completely outperforms any other existing software or hardware based solutions on DTC problem for at least one order of magnitude.The third application that we focused on is the Frequent Subgraph Mining (FSM) problem from the graph mining research area. We mapped one of the most efficient FSM algorithms, gSpan, on a multi-FPGA platform and we achieved at least one order of magnitude performance speedup versus the official software solution. Finally, this work presents an algorithmic approach for implementing recursion on reconfigurable logic.All the proposed hybrid HW/SW architectures in this thesis are scalable so they can very efficiently boost the performance (at least one order of magnitude) achieved by the various existing single or multi-threaded software solutions. Also, the described architectures are designed to be generic in a manner that they can give effective solutions for many other problems in different application domains. Finally, regarding the studied problems, the implemented systems seem to totally outperform other high-end systems as far as the energy consumption is concerned. Concluding, this thesis shows that the hardware platforms have the potential to offer better and less time consuming solutions for the always demanding and continuously spread big data problems.

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