High Throughput and Large Capacity Pipelined Dynamic Search Tree on FPGA

Free registration required

Executive Summary

The authors 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, their 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 (logN) 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.

  • Format: PDF
  • Size: 312.14 KB