|
The invention allows for a variety of tree-based search algorithms, common to several important router and network processor search applications, to be executed on a set of pipelined processor cores with minimal interconnect overhead, while maintaining extremely balanced allocation of memory to each processing element. This is possible even in the face of highly unbalanced databases (tree structures). A novel algorithm for allocating subtrees to processing elements enables this invention, and enables a double benefit: it eliminates the need for dynamic memory allocation per pipeline stage and it provides for better throughput.
The invention has been simulated experimentally with computer models, and the hardware for the pipelined processing elements has been synthesized using digital logic design tools to evaluate timing delays.
See also “A Tree Based Router Search Engine Architecture With Single Port Memories,” Florin Baboescu, Dean M. Tullsen, Grigore Rosu, Sumeet Singh, In Proceedings of the 32nd International Symposium on Computer Architecture, June, 2005.
Case No: SD2006-153
Keywords: search engines, network processors, IP lookup, VPN forwarding, packet classification
Inquiries To: invent@ucsd.edu
|
