A Novel FPGA-Based High Throughput Accelerator For Binary Search Trees
A Novel FPGA-Based High Throughput Accelerator For Binary Search Trees
复制标题
一种新型的基于 FPGA 的二叉搜索树高吞吐量加速器
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Cristal
中科院分区：
文献类型：
--
作者：
Oyku Melikoglu;Oğuz Ergin;Behzad Salami;Julián Pavón;O. Unsal;A. Cristal
本文提出了一种用于现场可编程门阵列（FPGA）的深度流水线和大规模并行二叉搜索树（BST）加速器。我们的设计依赖于极其并行的片上存储器，或FPGA的块RAM（BRAM）架构。为了实现显着的吞吐量BST上的搜索操作，我们提出了几种新的机制，包括树复制以及水平，重复，和混合（水平-垂直）树分区。此外，我们提出了有效的技术，以减少失速率，可以发生在并行树搜索。通过将这些技术与Xilinx Virtex-7 VC 709平台上的实现相结合，我们实现了与基线实现相比高达8倍的吞吐量改进增益，即，基于FPGA的全流水线加速器。
This paper presents a deeply pipelined and massively parallel Binary Search Tree (BST) accelerator for Field Programmable Gate Arrays (FPGAs). Our design relies on the extremely parallel on-chip memory, or Block RAMs (BRAMs) architecture of FPGAs. To achieve significant throughput for the search operation on BST, we present several novel mechanisms including tree duplication as well as horizontal, duplicated, and hybrid (horizontal-vertical) tree partitioning. Also, we present efficient techniques to decrease the stalling rates that can occur during the parallel tree search. By combining these techniques and implementations on Xilinx Virtex-7 VC709 platform, we achieve up to 8X throughput improvement gain in comparison to the baseline implementation, i.e., a fully-pipelined FPGA-based accelerator.
用于数据库加速的高级综合语言和工具的实证评估
DOI：
10.1109/fpl.2014.6927484
发表时间：
2014
期刊：
--
影响因子：
--
作者：
Arcas-Abella O
通讯作者：
Arcas-Abella O