  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.
