High Throughput and Large Capacity Pipelined Dynamic Search Tree on FPGA

Yi-Hua Edward Yang and Viktor K. Prasanna
USC/EE


Abstract

The search tree structure is a deterministic and efficient data structure for maintaining large amount of data. We propose a \emph{pipelined Dynamic Search Tree} (pDST) architecture on FPGA which offers high throughputs for \noun{lookup}, \noun{insert} and \noun{delete} operations as well as incremental and in-place data structure updates. Taking advantage of the highly parallel circuit resource on FPGA, our pDST is fully pipelined and supports one \noun{lookup} per clock cycle. Based on the 2-3 tree data structure, the pDST maintains perfect tree balance under continual \noun{insert}s and \noun{delete}s. We design a \emph{bi-directional linear pipeline}, one direction for key search and the other for key update, for streamlined operations. A novel \emph{delayed update} scheme is used to allows non-blocking \noun{insert} and \noun{delete} operations: a pDST with $N$ keys can perform one \noun{insert} or \noun{delete} every $O\left(\log N\right)$ cycles without halting the pipeline for the \noun{lookup} operations. Furthermore, node memory at each pipeline stage is allocated by an implicit \emph{chain of free nodes} which greatly simplifies the memory management circuit. Our prototype implementation of a 15-stage, 32-bit key dual-port pDST requires 192 blocks of 36~Kb BRAMs (64\%) and 24.8k LUTs (12.2\%) on a Virtex 5 LX330 FPGA. The circuit has a maximumn capacity of 128k 32-bit keys and achieves a clock rate of 185~MHz, supporting over 300 million \noun{lookup}s \emph{and} over 10 milion \noun{insert}s or \noun{delete}s per second.