基本概念

異構(gòu)計(jì)算

異構(gòu)計(jì)算主要是指使用不同類型計(jì)算單元（CPU、GPU等協(xié)處理器、DSP、ASIC、FPGA等），不同類型的指令集和不同的體系結(jié)構(gòu)組成的一個(gè)混合的系統(tǒng)。
異構(gòu)計(jì)算是一種并行計(jì)算的特殊方式 ，采用分布式布局，它能將結(jié)構(gòu)不同、 性能不同的各種機(jī)器部件合理的分配安排 ，充分發(fā)揮各個(gè)硬件的特性來滿足計(jì)算的需求 ，并且使得代碼或者代碼段所支配的資源更加合理的使用，以達(dá)到性能最大化的目的。
異構(gòu)就是將CPU、圖形處理器（Graphics Processing Unit, GPU）、專用集成電路（Application Specific Integrated Circuit, ASIC）、數(shù)字信號(hào)處理器（Digital Signal Processing, DSP）、現(xiàn)場(chǎng)可編程門陣列（Field Programmable Gate Array, FPGA）、精簡(jiǎn)指令集計(jì)算機(jī)（Reduced Instruction Set Computer, RISC)等各種計(jì)算單元組合成一個(gè)混合的系統(tǒng)，充分發(fā)揮各個(gè)硬件性來滿足計(jì)算的需求，并且使得代碼或者代碼段所支配的資源更加合理的使用，以達(dá)到性能最大化的目的。
下圖是一個(gè)異構(gòu)計(jì)算加速平臺(tái)的結(jié)構(gòu)，四片F(xiàn)PGA芯片同時(shí)放置在一張F(tuán)PGA板卡上，四片F(xiàn)PGA芯片通過RapidIO互聯(lián)。

CPU

英文全稱：Central Processing Unit
中文全稱：中央處理器
功能：是一臺(tái) PC 的核心（運(yùn)算核心和控制核心）。
缺點(diǎn)：算力最弱，處理復(fù)雜性高的計(jì)算時(shí)，計(jì)算性能不理想；核處理數(shù)（最少）
優(yōu)點(diǎn)：

1. 主頻（最高）（3G、4G以上）；
2. 管理能力（最強(qiáng)），擅長(zhǎng)管理和調(diào)度，比如數(shù)據(jù)讀取，文件管理，人機(jī)交互等等。

GPU

英文全稱：Graphics Processing Unit
中文全稱：圖形處理器
功能：
傳說中的 “顯卡”，是一種專門在個(gè)人電腦、工作站、游戲機(jī)和一些移動(dòng)設(shè)備（如平板電腦、智能手機(jī)等）上圖像運(yùn)算工作的微處理器，同時(shí)也是顯卡的 “心臟”，專為執(zhí)行復(fù)雜的數(shù)學(xué)和幾何計(jì)算而設(shè)計(jì)的。
缺點(diǎn)：管理能力（最弱），功耗（最高）
優(yōu)點(diǎn)：

1. 核處理數(shù)（最多）（并行處理和塊處理的典型例子）；
2. 擅長(zhǎng)浮點(diǎn)運(yùn)算和并行計(jì)算
   

FPGA

英文全稱：Field Programmable Gate Array
中文全稱：現(xiàn)場(chǎng)可編程門陣列
功能：是作為專用集成電路（ASIC）領(lǐng)域中的一種半定制電路而出現(xiàn)的，既解決了定制電路的不足，又克服了原有可編程邏輯器件門電路數(shù)有限的缺點(diǎn)
缺點(diǎn)：

1. 成本高（這就是為什么全球大量生產(chǎn)的 iPhone7 出現(xiàn)了一小塊 FPGA 芯片就引發(fā)了巨大的討論）；
2. 資源貴（SRAM（靜態(tài)隨機(jī)存取存儲(chǔ)器） 工藝實(shí)現(xiàn)的查找表結(jié)構(gòu)）。
   優(yōu)點(diǎn)：
3. 既能管理又能運(yùn)算（如工業(yè)控制 FPGA）；
4. 實(shí)時(shí)性（最強(qiáng)?。。。壕哂泻軓?qiáng)的并行計(jì)算能力，處理速度快，流水線并行和數(shù)據(jù)并行（延遲低，流處理）（而 GPU 只有數(shù)據(jù)并行）；
5. 靈活性（最強(qiáng)?。。。嚎删幊踢壿嬈骷梢詫?shí)時(shí)地根據(jù)不同的算法做不同的硬件方面的電路優(yōu)化。
6. 功耗（相比之下較低）：?jiǎn)挝还南掠?jì)算性能優(yōu)于GPU的計(jì)算性能 ，功耗大約是GPU的十分之一 。

DSP

英文全稱：Digital Signal Processing
中文全稱：數(shù)字信號(hào)處理
功能：DSP 芯片，也稱數(shù)字信號(hào)處理器，是一種特別適合于進(jìn)行數(shù)字信號(hào)處理運(yùn)算的微處理器，其主要應(yīng)用是實(shí)時(shí)快速高性能地實(shí)現(xiàn)各種數(shù)字信號(hào)處理算法，而與通用微處理器相比，DSP芯片的其他通用功能相對(duì)較弱些。

ASIC

英文全稱：Application Specific Integrated Circuit
中文全稱：專用集成電路
功能：在集成電路界 ASIC 被認(rèn)為是一種為專門目的而設(shè)計(jì)的集成電路。是指應(yīng)特定用戶要求和特定電子系統(tǒng)的需要而設(shè)計(jì)、制造的集成電路；ASIC 的特點(diǎn)是面向特定用戶的需求，ASIC 在批量生產(chǎn)時(shí)與通用集成電路相比具有體積更小、功耗更低、可靠性更高、性能更高、保密性增強(qiáng)、成本降低等優(yōu)點(diǎn)。

內(nèi)存數(shù)據(jù)庫（重新定義一下）

In-memory database（IMDB）,即內(nèi)存數(shù)據(jù)庫，是一種依賴于主存作為數(shù)據(jù)存儲(chǔ)介質(zhì)的一種數(shù)據(jù)庫管理系統(tǒng)。相比傳統(tǒng)的基于磁盤的數(shù)據(jù)庫管理系統(tǒng)，IMDB速度快得多。這取決于CPU能夠直接訪問IMDB，在I/O路徑與延遲方面有了質(zhì)的飛躍。另外，CPU本身提供的原子操作，內(nèi)存柵障以及高速緩存沖刷指令可以為IMDB提供簡(jiǎn)單高效的原子性，一致性服務(wù)。

1 背景

FPGA在數(shù)據(jù)庫中出現(xiàn)的原因

1. CPU：傳統(tǒng)的數(shù)據(jù)庫系 統(tǒng) 中 ，CPU是核 心 ，負(fù)責(zé)整個(gè)數(shù)據(jù)庫系統(tǒng)的管理 、 調(diào) 度 、 運(yùn)算等工作 。 然而，CPU的 性能瓶頸主要是計(jì)算能力弱。提升CPU時(shí)鐘頻率和內(nèi)核數(shù)量來提高計(jì)算能力時(shí)，遇到了散熱和能耗瓶頸。
2. GPU：GPU雖然工作頻率較低，具有更多的內(nèi)核數(shù)和并行計(jì)算能力，總體性能/芯片面積的比，和性能/功耗比都很高。
3. FPGA：因其高并行性、可重構(gòu)性和低功耗而被數(shù)據(jù)庫社區(qū)認(rèn)可，并可作為IO設(shè)備連接到CPU上，來加速數(shù)據(jù)庫分析。
4. 許多研究已經(jīng)證明FPGA可以作為加速器來實(shí)現(xiàn)高吞吐量。例如：IBM Netezza 把FPGA部署在硬盤驅(qū)動(dòng)器（hdd）和CPU之間的數(shù)據(jù)路徑中，執(zhí)行解壓縮和預(yù)處理，減輕了CPU中的計(jì)算壓力，間接地放大了硬盤的帶寬以提高數(shù)據(jù)庫的分析性能。

FPGA的缺點(diǎn)

1. 通信開銷大：FPGA加速器的接口帶寬很低，成為高帶寬內(nèi)存數(shù)據(jù)庫的瓶頸。在主存和FPGA之間傳輸數(shù)據(jù)的成本已經(jīng)超過FPGA的計(jì)算成本。
2. GPU可替代性：GPU也可以提供高吞吐量，且支持更大的設(shè)備內(nèi)存（高達(dá)32 GB），并且更容易編程，已經(jīng)成為一個(gè)強(qiáng)大的加速器替代方案。
3. 可編程性差：設(shè)計(jì)高效的FPGA要求開發(fā)人員具有全堆棧技能，從高級(jí)算法設(shè)計(jì)到低級(jí)電路實(shí)現(xiàn)。

新技術(shù)的發(fā)展開始利好FPGA

1. 新的接口技術(shù)：如OpenCAPI、加速器緩存相干互連（CCIX）]和計(jì)算快速鏈路（CXL），接口技術(shù)發(fā)展快可以提高加速器的接口帶寬。
2. 新接口給FPGA帶來的另一個(gè)特性是共享內(nèi)存。FPGAs不作為IO設(shè)備連接到CPU上，F(xiàn)PGA和CPU共享相同的內(nèi)存空間。
3. 一些FPGA現(xiàn)在包含了高帶寬內(nèi)存（HBM），并具有更大的本地內(nèi)存容量以及更高的（本地）內(nèi)存帶寬。與帶有HBM的GPU類似，這種大容量的高帶寬內(nèi)存允許FPGA在本地存儲(chǔ)大量數(shù)據(jù)，從而減少主機(jī)內(nèi)存的訪問量，可以加速一些需要內(nèi)存多次訪問的數(shù)據(jù)密集型應(yīng)用程序。
4. FPGA開發(fā)工具鏈也在不斷改進(jìn)：
5. HLS工具： Vivado HLS，OpenCL，HLS是高層綜合（High level Synthesis），是將C或者c++語言編譯為FPGA能夠讀懂和運(yùn)行的RTL級(jí)別的語言，會(huì)自動(dòng)生成硬件電路；
6. SNAP 框架：為開發(fā)人員自動(dòng)化了CPU-FPGA界面的設(shè)計(jì)；
7. 編譯器：Glacier，可以將SQL查詢直接編譯為FPGA實(shí)現(xiàn)。

2 FPGA背景

2.1 FPGA結(jié)構(gòu)

如下圖所示，一塊 FPGA 芯片由可配置邏輯模塊（CLB）、互連結(jié)構(gòu)和本地內(nèi)存構(gòu)成，每個(gè) CLB 都包含特定的結(jié)構(gòu)，如：查找表（LUT）、多路復(fù)用器、進(jìn)位鏈、觸發(fā)器等。

每個(gè)LUT是一個(gè)n個(gè)輸入和一個(gè)輸出的表，根據(jù)n個(gè)輸入的組合產(chǎn)生一個(gè)期望的輸出。多個(gè)LUT可以通過可配置的互連結(jié)構(gòu)連接在一起，形成一個(gè)更復(fù)雜的模塊。LUT如下圖：

除此之外，一塊 FPGA 卡上還有 BRAM（Block RAM）來作為本地存儲(chǔ)器，存儲(chǔ)中間結(jié)果的寄存器。最近，F(xiàn)PGA芯片配備了更強(qiáng)大的資源，如內(nèi)置的CPU核、數(shù)字信號(hào)處理器（DSP）塊、UltraRAM（URAM）、高帶寬內(nèi)存（HBM）、預(yù)配置的I/O塊和內(nèi)存接口控制器。

2.2 FPGA的特點(diǎn)

1. FPGA是一種可編程的設(shè)備，可以配置為一個(gè)定制的電路來執(zhí)行特定的任務(wù)。
2. 流水線并行和數(shù)據(jù)并行（延遲低，流處理）（而 GPU 只有數(shù)據(jù)并行）
3. CPU、GPU 都屬于馮·諾依曼結(jié)構(gòu)，指令譯碼執(zhí)行、共享內(nèi)存。FPGA 之所以比 CPU 甚至 GPU 能效高，本質(zhì)上是無指令、無需共享內(nèi)存的體系結(jié)構(gòu)帶來的福利。
   2.3 FPGA的帶寬
4. 與CPU內(nèi)存層次結(jié)構(gòu)類似，F(xiàn)PGA內(nèi)部?jī)?nèi)存（Internal）具有最低的延遲和最高的帶寬，但容量最小。
5. on-board DRAM（動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器）設(shè)備可以提供數(shù)十GB/s的帶寬，HBM有數(shù)百GB/s的帶寬，兩者都需要數(shù)十到幾百納秒的延遲來獲取數(shù)據(jù)。
6. 訪問主機(jī)（host）內(nèi)存的帶寬是最低的帶寬，但提供了最大的內(nèi)存容量。
   

2.3 FPGA的編程

FPGA中的用戶定義邏輯通常是使用硬件描述語言（HDL）進(jìn)行編程：VHDL or Verilog。HDL是電子系統(tǒng)硬件行為描述、結(jié)構(gòu)描述、數(shù)據(jù)流描述的語言。利用這種語言，數(shù)字電路系統(tǒng)的設(shè)計(jì)可以從頂層到底層（從抽象到具體）逐層描述自己的設(shè)計(jì)思想，用一系列分層次的模塊來表示極其復(fù)雜的數(shù)字系統(tǒng)。然后，利用電子設(shè)計(jì)自動(dòng)化（ EDA ）工具，逐層進(jìn)行仿真驗(yàn)證，再把其中需要變?yōu)閷?shí)際電路的模塊組合，經(jīng)過自動(dòng)綜合工具轉(zhuǎn)換到門級(jí)電路網(wǎng)表。接下去，再用專用集成電路 ASIC 或現(xiàn)場(chǎng)可編程門陣列 FPGA 自動(dòng)布局布線工具，把網(wǎng)表轉(zhuǎn)換為要實(shí)現(xiàn)的具體電路布線結(jié)構(gòu)。

3 基于FPGA的數(shù)據(jù)庫系統(tǒng)

標(biāo)題3.1 FPGA作為帶寬放大器

• 在基于存儲(chǔ)和延遲敏感的數(shù)據(jù)庫系統(tǒng)中，瓶頸通常來自于存儲(chǔ)的數(shù)據(jù)傳輸，特別是硬盤（HDD）。與DRAM支持的數(shù)百個(gè)Gbit/s帶寬相比，HDD設(shè)備的數(shù)據(jù)速率保持在1 Gbit/s水平，這限制了系統(tǒng)的性能。在這些系統(tǒng)中，F(xiàn)PGA可以用來放大存儲(chǔ)帶寬。
• 如圖1所示，F(xiàn)PGA用作數(shù)據(jù)源（磁盤、網(wǎng)絡(luò)等）和CPU之間的解壓和濾波器來提高有效帶寬。在這種體系結(jié)構(gòu)中，壓縮數(shù)據(jù)存儲(chǔ)在磁盤上，并將直接通過SCSI、SATA、光纖通道或NVMe等接口傳輸?shù)紽PGA，或者間接用于網(wǎng)絡(luò)附加存儲(chǔ)或以太網(wǎng)上的NVMe或協(xié)議。
• 在FPGA中，根據(jù)某些特定的條件對(duì)數(shù)據(jù)進(jìn)行解壓縮和濾波，然后將數(shù)據(jù)發(fā)送到CPU進(jìn)行進(jìn)一步的計(jì)算。由于壓縮后的數(shù)據(jù)小于原始數(shù)據(jù)，需要從存儲(chǔ)傳輸?shù)臄?shù)據(jù)較少，間接提高了有效存儲(chǔ)帶寬。
  

3.2 FPGA作為IO連接加速器

對(duì)于計(jì)算密集型數(shù)據(jù)庫，cpu是其瓶頸。計(jì)算密集型任務(wù)的例子包括連接、排序、分組和聚合、壓縮等。這類任務(wù)一般是 FPGA被用作IO設(shè)備，CPU 把任務(wù)卸載（offload）給 FPGA 去執(zhí)行。

• 圖2說明了使用FPGA作為IO連接加速器的體系結(jié)構(gòu)。在這種體系結(jié)構(gòu)中，F(xiàn)PGA通過PCIe等總線連接到CPU，而FPGA和CPU都有自己的內(nèi)存空間。

• 當(dāng)FPGA從CPU接收到任務(wù)時(shí)，它首先將數(shù)據(jù)從主機(jī)內(nèi)存（host memory）復(fù)制到設(shè)備內(nèi)存（device memory）中。然后，F(xiàn)PGA從內(nèi)存中獲取數(shù)據(jù)，并在處理完數(shù)據(jù)后將結(jié)果寫回設(shè)備內(nèi)存，最后將結(jié)果復(fù)制回主機(jī)內(nèi)存中。
  

• 缺點(diǎn)：需要反復(fù)的復(fù)制（從主機(jī)內(nèi)存到設(shè)備內(nèi)存），這會(huì)導(dǎo)致更長(zhǎng)的處理延遲。

3.3 FPGA作為協(xié)同處理器

FPGA可以直接訪問主機(jī)內(nèi)存，CPU和FPGA之間的通信是通過共享內(nèi)存來實(shí)現(xiàn)的。

5 技術(shù)趨勢(shì)

5.1 數(shù)據(jù)庫系統(tǒng)趨勢(shì)

傳統(tǒng)數(shù)據(jù)庫的操作都在純CPU上進(jìn)行，計(jì)算壓力大====>需要更強(qiáng)大的處理器，GPU或者FPGA

• 傳統(tǒng)數(shù)據(jù)庫由HDD存儲(chǔ)轉(zhuǎn)為內(nèi)存或NVM存儲(chǔ)，需要更大帶寬，但FPGA-CPU互連帶寬較低，加速困難；使用FPGAs作為io連接的加速器復(fù)制數(shù)據(jù)的成本很高====>加速FPGA需要克服這些限制。

5.2 系統(tǒng)互連趨勢(shì)

5.2.1 增加系統(tǒng)互連帶寬來解決帶寬問題

• 為解決帶寬問題：DRAM、PCIe、網(wǎng)絡(luò)和存儲(chǔ)的帶寬都在逐年增加
  

5.2.2 使用共享內(nèi)存和一致性解決IO連接瓶頸

• 僅僅增加帶寬并不能解決我們所有的問題，因?yàn)閭鹘y(tǒng)的IO連接模型是瓶頸，這迫使業(yè)界推動(dòng)跨CPU核和連接設(shè)備之間的一致性和共享內(nèi)存。
• 使用共享內(nèi)存，系統(tǒng)允許FPGAs從主機(jī)內(nèi)存中讀取一小部分?jǐn)?shù)據(jù)，而無需將整個(gè)數(shù)據(jù)塊復(fù)制到設(shè)備內(nèi)存。

FPGAs使用高帶寬和低延遲的互連進(jìn)行連接，并且由于共享內(nèi)存編程模型而易于編程，這使得FPGAs在數(shù)據(jù)庫加速方面再次具有吸引力。

5.3 使用HBM（高帶寬內(nèi)存）來提高帶寬和內(nèi)存

DRAM帶寬改善有限===>新的高帶寬內(nèi)存技術(shù)HBM提供了更多的帶寬和更低的功耗，這使得FPGA也適用于數(shù)據(jù)密集型的工作。

6 查詢操作符的加速

盡管還沒有一個(gè)商業(yè)的FPGA加速內(nèi)存數(shù)據(jù)庫，但大量關(guān)于加速數(shù)據(jù)庫操作符或組件的工作正在推動(dòng)這個(gè)方向的進(jìn)展。FPGA能夠加速一些數(shù)據(jù)庫操作符，如解壓、聚合、算術(shù)、排序、連接等。

6.1 解壓縮算法

解壓縮算法廣泛應(yīng)用于數(shù)據(jù)庫中，以節(jié)省存儲(chǔ)和減少帶寬。解壓縮器讀取由tokens組成的壓縮流，將tokens轉(zhuǎn)換為數(shù)據(jù)，并輸出解壓縮流。

• 在數(shù)據(jù)庫系統(tǒng)中，最流行的兩種類型的無損壓縮算法是運(yùn)行長(zhǎng)度編碼（RLE）和Lempel-Ziv（LZ）系列。
• 基于FPGA的解壓縮算法實(shí)現(xiàn)可以幫助實(shí)現(xiàn)高吞吐量。

6.2 排序

排序是數(shù)據(jù)庫系統(tǒng)中用于對(duì)記錄進(jìn)行排序的一種常用操作。它可以在SQL中和更復(fù)雜的查詢中使用，以提高性能。大規(guī)模排序性能是衡量數(shù)據(jù)庫性能的關(guān)鍵指標(biāo)。傳統(tǒng)的基于cpu的排序算法，不僅算法速度較慢，且搶占cpu系統(tǒng)資源。近年提出了很多基于FPGA的排序算法或系統(tǒng)，充分利用FPGA的并行處理能力，極大的提升算法的速度，解決了傳統(tǒng)的基于cpu的排序算法的缺點(diǎn)。

6.2.1 排序網(wǎng)絡(luò)

• 排序網(wǎng)絡(luò)是一種高吞吐量的并行排序，可以同時(shí)對(duì)N個(gè)輸入進(jìn)行排序。比較和交換單元是排序網(wǎng)絡(luò)中的核心元素。比較和交換單元比較兩個(gè)輸入，并將它們排列成選定的順序（升序或降序），如果它們不按照期望的順序排列，則通過交換它們來保證。使用一組這些比較和交換單元，并按特定的順序排列它們，我們可以按照所需的順序?qū)Χ鄠€(gè)輸入進(jìn)行排序。
• 排序網(wǎng)絡(luò)可以通過將不同的數(shù)據(jù)集保存在不同的階段，同時(shí)對(duì)多個(gè)數(shù)據(jù)集進(jìn)行排序。N個(gè)輸入排序網(wǎng)絡(luò)能夠每FPGA周期處理N個(gè)元素。

6.2.2 FIFO歸并排序器

FIFO合并排序器可以將兩個(gè)預(yù)先排序好的數(shù)據(jù)流進(jìn)行合并，如圖7(a)。FIFO合并排序器的缺點(diǎn)是從小數(shù)據(jù)流合并到最終排序流需要多次經(jīng)過合并，數(shù)據(jù)需要在內(nèi)存和FPGA之間移動(dòng)多次，數(shù)據(jù)傳輸開銷大。
這個(gè)問題可以通過級(jí)聯(lián)多個(gè)FIFO合并排序器來解決。如圖7b所示，F(xiàn)IFO較小的FIFO在早期放置，而較大的FIFO在后期插入。

6.2.3 歸并樹

歸并樹可以在一次將幾個(gè)排序的流合并。

上述所有三種排序方法都可以通過制造更強(qiáng)的引擎或部署更多的引擎來充分利用接口帶寬。但是，大的排序可能需要多次傳遞，每次傳遞都需要訪問主機(jī)內(nèi)存。通過這種方式，整個(gè)排序的總體吞吐量取決于通過次數(shù)和每個(gè)通過的吞吐量，或者總體吞吐量不超過帶寬除以通過次數(shù)的帶寬。通過更廣泛的合并，合并更多的流，可以減少通過的數(shù)量。但是，由于每個(gè)輸入流都需要緩沖，因此構(gòu)建一個(gè)更廣泛的合并樹需要大量的分支，這使得設(shè)計(jì)分支受到了限制。

6.3 join（連接）

連接是數(shù)據(jù)庫系統(tǒng)中常用的一種操作，它在特定的約束下將兩個(gè)或多個(gè)表組合成一個(gè)復(fù)合表。最常見的一個(gè)是等連接，它通過一個(gè)公共字段組合兩個(gè)表。在本文的其余部分中，我們將等式連接稱為連接。有許多不同的連接算法，包括嵌套循環(huán)連接、哈希連接（HJ）和排序-合并連接（SMJ）。在本文中，我們主要關(guān)注HJ和SMJ，因?yàn)樗鼈兊乃惴◤?fù)雜度較低，因此對(duì)數(shù)據(jù)庫社區(qū)更感興趣

6.3.1 哈希連接

哈希連接是一種用于關(guān)系型數(shù)據(jù)庫中的連接算法，只能用于有等連接條件的連接中（on a.b = c.b）。它通常比嵌套循環(huán)算法更高效（探測(cè)端非常非常小除外），尤其是在沒有命中索引的情況下。
簡(jiǎn)單來說，哈希連接算法就是先把一張小表加載到內(nèi)存哈希表里，然后遍歷大表的數(shù)據(jù)，逐行去哈希表中匹配符合條件的數(shù)據(jù)，返回到客戶端。

在cpu中，哈希函數(shù)很難同時(shí)具有很強(qiáng)的魯棒性和高速性。在FPGA允許在一個(gè)電路中實(shí)現(xiàn)復(fù)雜的代數(shù)函數(shù)，計(jì)算速度比CPU快。
分區(qū)哈希連接可以通過將數(shù)據(jù)劃分為小的分區(qū)來避免隨機(jī)訪問，這樣每個(gè)分區(qū)的哈希表就可以存儲(chǔ)在FPGA內(nèi)存中。
設(shè)計(jì)一個(gè)基于FPGA的哈希連接算法的關(guān)鍵之一是有一個(gè)有效的哈希表結(jié)構(gòu)。一方面，哈希表結(jié)構(gòu)會(huì)影響哈希連接引擎的性能。不適當(dāng)?shù)纳⒘斜碓O(shè)計(jì)可能會(huì)導(dǎo)致停頓，從而降低吞吐量。另一方面，由于FPGA內(nèi)部有有限數(shù)量的分支，為了確保多引擎實(shí)例在一個(gè)FPGA中可行，哈希表不應(yīng)該消耗太多的分支。

6.3.2 排序歸并連接

• 排序合并連接 (Sort Merge Join)是一種兩個(gè)表在做連接時(shí)用排序操作(Sort)和合并操作(Merge)來得到連接結(jié)果集的連接方法。
• 通常情況下，排序合并連接的執(zhí)行效率遠(yuǎn)不如哈希連接，但前者的使用范圍更廣，因?yàn)楣＿B接只能用于等值連接條件，而排序合并連接還能用于其他連接條件(如<,<=,>.>=)
• Sort Merge主要的開銷在于對(duì)兩表連接的排序，已經(jīng)在連接關(guān)聯(lián)列上已經(jīng)進(jìn)行了排序，則該連接操作就不需要再進(jìn)行 sort 操作，這樣可以大大提高這種連接操作的連接速度，特別是對(duì)于較大的表。
• 研究進(jìn)展：Ren等人[20]提出了一個(gè)異構(gòu)CPU-FPGA平臺(tái)中的排序連接方法。在FPGA中執(zhí)行前幾個(gè)排序，并將部分結(jié)果流到cpu，進(jìn)行合并連接。其他人則研究哈希連接和排序-合并連接之間的比較，在CPU中的對(duì)比研究較多，F(xiàn)PGA中的對(duì)比研究較少。

7 未來研究方向

7.1 數(shù)據(jù)庫結(jié)構(gòu)

內(nèi)存中的數(shù)據(jù)庫應(yīng)該被設(shè)計(jì)為支持多種類型的計(jì)算元素（CPU、GPU、FPGA）的結(jié)構(gòu)。

7.2 加速器設(shè)計(jì)

• 對(duì)于幾個(gè)關(guān)鍵操作符，基于FPGA的加速做的很多。但同時(shí)利用CPU和FPGA，以及CPU、FPGA和GPU的組合的設(shè)計(jì)上所做的工作較少。
• 給FPGA帶來的另一個(gè)機(jī)會(huì)是數(shù)據(jù)庫開始支持新興的機(jī)器學(xué)習(xí)。一些數(shù)據(jù)庫集成了對(duì)查詢優(yōu)化的機(jī)器學(xué)習(xí)方法。這所需的大量計(jì)算都給數(shù)據(jù)庫系統(tǒng)帶來了計(jì)算挑戰(zhàn)，而FPGA可能會(huì)有所幫助。因此，針對(duì)這些新興的方法新加速器值得研究。
• 從系統(tǒng)的角度來看，單個(gè)FPGA只能提供有限的性能，而多FPGA架構(gòu)應(yīng)該會(huì)帶來顯著的加速。一方面，可以在不同的FPGA中實(shí)現(xiàn)不同的功能，來實(shí)現(xiàn)更多的功能和更復(fù)雜的工作。另一方面，多個(gè)FPGA可以一起工作，以提高性能。
• 使用FPGAs作為云資源可以進(jìn)一步提高云和分布式數(shù)據(jù)庫系統(tǒng)中的FPGA利用率。與此相關(guān)的重要挑戰(zhàn)包括如何將FPGA與cpu連接起來，以及如何分配工作負(fù)載。

7.3 與GPU的比較

• GPU現(xiàn)在已經(jīng)成為數(shù)據(jù)庫系統(tǒng)的一個(gè)重要加速器，因?yàn)镚PU有數(shù)千到數(shù)萬個(gè)線程，能夠提供高吞吐量。除了高并行性，集成HBM使其擁有大容量?jī)?nèi)存和快速訪問。雖然FPGA現(xiàn)在也集成了HBM，但FPGA通常不能提供和GPU相同數(shù)量級(jí)的線程。
• 什么類型的數(shù)據(jù)庫應(yīng)用程序在FPGA上比GPU工作得更好：
  • 第一個(gè)可能是對(duì)延遲敏感的流媒體處理應(yīng)用程序，如網(wǎng)絡(luò)處理。流處理中高吞吐量和低延遲的要求給GPU帶來了挑戰(zhàn)。由于GPU需要格式化良好的數(shù)據(jù)，并以批處理方法來處理數(shù)據(jù)以獲得吞吐量，格式化可能會(huì)引入額外的延遲。然而FPGA的數(shù)據(jù)流設(shè)計(jì)的特性可以完美的滿足要求。
  • FPGA可能在需要特殊功能的特定領(lǐng)域，在吞吐量方面擊敗GPU。例如，如果希望構(gòu)建在加密層下運(yùn)行的數(shù)據(jù)庫，需要將加密與其他操作符相結(jié)合。FPGAs可以在硬件中有效地實(shí)現(xiàn)這些特殊功能，而通過在管道中組合兩個(gè)功能組件，其對(duì)吞吐量的影響通?？梢院雎圆挥?jì)。

• 我們還可以考慮探索使用CPU-GPU-FPGA組合來構(gòu)建更多異構(gòu)性的數(shù)據(jù)庫系統(tǒng)。不同的處理器有不同的特性和不同的優(yōu)點(diǎn)。cpu擅長(zhǎng)于復(fù)雜的控制和任務(wù)調(diào)度，GPU擅長(zhǎng)在大量數(shù)據(jù)量的并行性批處理模式下工作，而FPGAs可以通過數(shù)據(jù)流和管道設(shè)計(jì)提供高吞吐量和低延遲。將這些處理器集成在一個(gè)系統(tǒng)中，并將工作負(fù)載分配給最適合的處理器，很可能會(huì)帶來優(yōu)勢(shì)。然而，構(gòu)建這個(gè)系統(tǒng)需要解決一些挑戰(zhàn)，包括如何將任務(wù)劃分為軟件和硬件，如何管理系統(tǒng)中的計(jì)算資源，以及如何支持不同類型的處理器之間的數(shù)據(jù)一致性。

參考文獻(xiàn)

In-memory database acceleration on FPGAs: a survey
FPGA: What’s in it for a Database?文章來源地址http://www.zghlxwxcb.cn/news/detail-725100.html

到了這里，關(guān)于FPGA在內(nèi)存數(shù)據(jù)庫加速中的應(yīng)用：綜述的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！