Technical University of Crete (TUC)
Optimizing algorithmic workloads and data structures for hardware accelerators
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- Technical University of Crete (TUC)
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Chrysos, Grigorios
- Χρυσός, Γρηγόριος
Subjects
dc:subject × 20- Συστήματα υψηλής απόδοσης
- Σχεδίαση και υλοποίηση σε FPGA και GPU (αναδιατασσόμενο υλικό)
- Αναδιατασσόμενη αρχιτεκτονική
- Εξόρυξη πληροφορίας
- Βιοπληροφορική
- Εύρεση γονιδίων
- Ταξινόμηση με χρήση δένδρων αποφάσεων
- Εξόρυξη συχνών υπογράφων
- High performance system
- FPGA and GPU-based systems
- Reconfigurable architecture
- Large scale data mining
- Bioinformatics
- Gene finding
- Decision tree classification
- Frequent Subgraph Mining
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/34856