Skip to main content

Banery wysuwane

Liternicza seryjna okładka w pomarańczowym kolorze
Data-Intensive Processing on FPGAs

Author
Product category
nauki techniczne » elektronika
ISBN
ISBN 978-83-7464-800
ISSN
ISNN 0867-6631
Publication type
monografia
Format
B5
Binding
miękka
Number of pages
154
Publication date
2015
Description

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.

Contents

Summary  9
Streszczenie  10
List of symbols and abbreviations  11
Introduction  15

1. 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  45

2. 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  79

3. 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  106

4. 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  114

5. 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  132

6. Final remarks  133

Bibliography  143
 

Fragments
Contents
Price
0.00
In order to arrange international shipping details and cost please contact wydawnictwa@agh.edu.pl