Back to search

Technical University of Crete (TUC)

Optimizing algorithmic workloads and data structures for hardware accelerators

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/34856

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Chrysos, Grigorios; Χρυσός, Γρηγόριος. Optimizing algorithmic workloads and data structures for hardware accelerators. Technical University of Crete (TUC), 2014. http://hdl.handle.net/10442/hedi/34856