Title :
Scalable and dynamically updatable lookup engine for decision-trees on FPGA
Author :
Qu, Yun R. ; Prasanna, Viktor K.
Author_Institution :
Ming Hsieh Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA, USA
Abstract :
Architectures for tree structures on FPGAs as well as ASICs have been proposed over the years. The exponential growth in the memory size with respect to the number of tree levels restricts the scalability of these architectures. In this paper, we propose a scalable lookup engine on FPGA for large decision-trees; this engine sustains high throughput even if the tree is scaled up with respect to (1) the number of fields and (2) the number of leaf nodes. The proposed engine is a 2-dimensional pipelined architecture; this architecture also supports dynamic updates of the decision-tree. Each leaf node of the tree is mapped onto a horizontal pipeline; each field of the tree corresponds to a vertical pipeline. We use dual-port distributed RAM (distRAM) in each individual Processing Element (PE); the resulting architecture for a generic decision-tree accepts two search requests per clock cycle. Post place-and-route results show that, for a typical decision-tree consisting of 512 leaf nodes, with each node storing 320-bit data, our lookup engine can perform 536 Million Lookups Per Second (MLPS). Compared to the state-of-the-art implementation of a binary decision-tree on FPGA, we achieve 2× speed-up; the throughput is sustained even if frequent dynamic updates are performed.
Keywords :
application specific integrated circuits; decision trees; distributed memory systems; field programmable gate arrays; pipeline processing; random-access storage; 2dimensional pipelined architecture; ASIC; FPGA; binary decision-tree; decision-trees; distRAM; dual-port distributed RAM; horizontal pipeline; memory size; processing element; scalable lookup engine; tree structure; vertical pipeline; Clocks; Computer architecture; Engines; Field programmable gate arrays; Heuristic algorithms; Pipelines; Throughput;
Conference_Titel :
High Performance Extreme Computing Conference (HPEC), 2014 IEEE
Conference_Location :
Waltham, MA
Print_ISBN :
978-1-4799-6232-7
DOI :
10.1109/HPEC.2014.7040952