In this paper, the author presents his experiences in the area of the use of FPGA devices for data-intensive computing. Processing of the large volumes of data plays a significant role in today’s Internet and computing services. Also, big data processing has become a new pillar of science as a tool for knowledge discovery. Traditionally, high-performance computers help scientist to perform simulations and modelling that employ extensive calculations. Input data sets are relatively small, and processing dominates in these applications. Data-intensive problems set new requirements of computers’ users, as they require high data throughput rather than high computing power of the computing system. Now, users expect that, besides processing power, their computers provide the highly efficient data movement as well. Notably, these demands are often accompanied by concerns for energy-efficiency.
The solution that is commonly implemented to fulfill all those claims simultaneously is an introduction of heterogeneous computing architectures. Accordingly, commodity computers are enhanced by the task-oriented accelerators such as GPGPUS, DSPs, FPGAs, and other specialised devices. This technique leads to the improvement of computing capability of a computer system. The role of FPGA accelerators is discussed exclusively in this work. An important part of the text covers downsized computing platforms that combine energy-efficient processors with reconfigurable logic and particularly suit for data-intensive calculations.
It is always critical to characterise a class of algorithms that benefits from a use of a particular type of an accelerator device. The author identifies processing tasks that gain when they are ported to an FPGA-accelerated computers. Mainly, sorting and searching algorithms are elaborated in this paper. The author presents hardware structures for well-known, software-based algorithms but also gives new original solutions that particularly satisfy the FPGA-enabled systems.
The practical examples are reported as results of processing performance and energy consumption in the paper. They show that on average over two-fold processing speedup and order of magnitude reduction of electric power is possible in FPGAenhanced architectures if compared to traditional CPU-only solutions.
W monografii autor opisuje swoje doświadczenia dotyczące przetwarzania dużych zbiorów danych przy wykorzystaniu układów FPGA. Analiza danych odgrywa dziś wiodącą rolę w realizacji usług internetowych i przetwarzaniu informacji. Metody określane terminem Big Data Discovery uzyskały status jednego z głównych narzędzi nauki służącego do poznania i rozumienia procesów zachodzących w świecie. W przeszłości naukowcy wymagali, aby komputery dostarczały dużej mocy obliczeniowej, która umożliwiała symulację i modelowanie procesów fizycznych. Dzisiaj użytkownicy przetwarzający duże zbiory danych wymagają dodatkowo dużej przepustowości operacji wejścia-wyjścia. Ponadto powyższe oczekiwanie często idą w parze z koniecznością ograniczenia energii zasilania komputerów.
Spełnienie powyższych oczekiwań można osiągnąć, wdrażając architektury heterogeniczne. W tym rozwiązaniu komputery są dodatkowo wyposażane w karty akcelerujące zawierające urządzenia GPGPU, DSP, FPGA czy inne układy specjalizowane. Prowadzi to do poprawy wydajności wspieranych przez akcelerator zadań. Niniejsza praca ogranicza się do zagadnień związanych z układami FPGA. Ważna jej część dotyczy platform obliczeniowych o zredukowanej wydajności, które łącząc energooszczędne procesory i układy rekonfigurowalne, nadają się do zadań związanych z przetwarzaniem dużych zbiorów danych.
W przypadku wykorzystania akceleratorów istotne jest, aby scharakteryzować grupę algorytmów, które mogą zyskać na ich zastosowaniu. Autor przedstawia zadań nią obliczeniowe, których realizacja w układach FPGA może przynieść korzyści. Treść pracy dotyczy głównie zagadnień sortowania i wyszukiwania. Autor proponuje architektury sprzętowe odpowiadające znanym algorytmom software’owym, oraz wprowadza nowe oryginalne rozwiązania bazujące na zastosowaniu rekonfigurowalnych układów FPGA.
Przedstawione aplikacje dostarczają parametrów wydajnościowych i energetycznych. Pokazują one, że dzięki technologii FPGA, w porównaniu z rozwiązaniami bazującymi wyłącznie na CPU, jest możliwe uzyskanie średnio ponaddwukrotnego przyspieszenia i zredukowania zużycia energii elektrycznej o rząd wielkości.
Wydawnictwa AGH nie prowadzą sprzedaży książek z serii "Rozprawy Monografie".
Zainteresowanych prosimy o kontakt z ich autorami.
- Spis treści
-
Summary 9
Streszczenie 10
List of symbols and abbreviations 11
Introduction 151. Computing and FPGAs 19
1.1. Basics of FPGA devices 19
1.2. The challenges of efficient data processing 22
1.3. Massively parallel computing 24
1.4. Heterogeneous computing platforms 25
1.4.1. Graphics cards 27
1.4.2. FPGA accelerators 28
1.5. Data-intensive computing 30
1.5.1. The big O notation 31
1.5.2. Computational patterns 32
1.5.3. Distributed databases 33
1.6. FPGAs in data-intensive applications 34
1.7. Architectures for energy-efficient computing 38
1.8. Energy efficiency of FPGAs 41
1.9. Types of FPGA-enabled architectures 452. Custom processor design in FPGAs 51
2.1. The general architecture of a custom processor 51
2.1.1. Algorithm selection 51
2.1.2. An example of the SQL custom processor 52
2.1.3. The Finite-State Machine with Data 55
2.1.4. The controller and data path 57
2.2. Algorithm scheduling 60
2.3. Loop pipelining 62
2.4. Control statements pipelining 67
2.4.1. Conditional statement pipelining 67
2.4.2. Loop statement pipelining 69
2.4.3. Pipelining of the CFG 70
2.5. Memory handling 73
2.5.1. Local arrays of data 74
2.5.2. Explicit data caching 75
2.5.3. Sequential-Access Buffering 78
2.6. The FPGA-oriented algorithms 793. Data-intensive algorithms for FPGAs 82
3.1. Sorting and searching 82
3.2. The sorting nets 83
3.3. The merge sort tree 87
3.3.1. The FPGA-accelerated sorting system 89
3.4. The Bloom filter 91
3.4.1. The parallel Bloom filter 92
3.4.2. Enhancement of the Bloom filter 94
3.4.3. Modified Cuckoo hashing 96
3.5. A shifting substring search 98
3.6. The binary tree 100
3.6.1. The binary-tree processor 101
3.6.2. Mapping of patterns to memories 103
3.7. The prefix tree 104
3.8. The Aho-Corasick algorithm 1064. The Hash Binary Tree 109
4.1. Hashing of the binary tree patterns 109
4.2. Two-fold pipelined HBT architecture 110
4.3. Memory requirements of the HBT 111
4.4. The example application 112
4.5. Conclusions 1145. Acceleration of genome matching 116
5.1. Short-read alignment 116
5.2. Subsequences 117
5.3. The trie 118
5.4. The sequential co-processor 119
5.5. The pipelined co-processor 121
5.6. Inexact matching 123
5.7. The control block 127
5.8. Resource requirements 128
5.9. Reducing software memory requirements 130
5.10. Implementation results 130
5.11. Conclusions 1326. Final remarks 133
Bibliography 143