Paper Info
Title
High throughput and large capacity pipelined dynamic search tree on FPGA
Abstract
We propose a pipelined Dynamic Search Tree (pDST) on FPGA which offers high throughput for lookup, insert and delete operations as well as the capability to perform in-place incremental updates. Based on the pipelined 2-3 tree data structure, our pDST supports one lookup per clock cycle and maintains tree balance under continual insert and delete operations. A novel buffered update scheme together with a bi-directional linear pipeline allows the pDST to perform one insert or delete operation per O(log N) cycles (N being the tree capacity) without stalling the lookup operations. Nodes at each pipeline stage are allocated and freed by a free-node chaining mechanism which greatly simplifies the memory management circuit. Our prototype implementation of a 15-level, 32-bit key dual-port pDST requires 192 blocks of 36 Kb BRAMs (64%) and 12.8k LUTs (6.3%) on a Virtex 5 LX330 FPGA. The circuit has a maximum capacity of 96k 32-bit keys and clock rate of 135 MHz, supporting 242 million lookups and concurrently 3.97 million inserts or deletes per second.
Year
DOI
Venue
2010
10.1145/1723112.1723128
FPGA
Keywords
Field
DocType
high throughput,tree balance,32-bit key dual-port pdst,million insert,tree data structure,lookup operation,lx330 fpga,dynamic search tree,continual insert,32-bit key,large capacity,bi-directional linear pipeline,tree capacity,openflow,memory management,data structure,2 3 tree,b tree,ip forwarding
2–3 tree,Computer science,Tree (data structure),Parallel computing,Field-programmable gate array,B-tree,Real-time computing,Virtex,Cycles per instruction,Clock rate,Search tree
Conference
Citations 
PageRank 
References 
15
0.98
9
Authors
2
Name
Order
Citations
PageRank
Yi-Hua Yang1272.05
Viktor K. Prasanna27211762.74