Search engine for large database search using CAM and hash
View Patent ↗A search engine having a controller, a memory, and at least one hash-CAM (H-CAM). The memory includes a database of search values and associate content or just associate content. The controller uses search values to access the memory to obtain the search results. The H-CAM includes at least one set of paired hash units and CAM units and at least one logic unit. The CAM units hold values known to cause hash collisions in the paired hash units, and the logic unit prioritizes the hash and CAM unit outputs to address values usable to access the memory and obtain a search result at the controller that is not the result of a hash collision. The H-CAM may optionally include a search data storage to store the search values, so that they need not be stored in the memory, and a comparator to determine and handle new search data based hash collisions. The H-CAM may optionally also be cascaded.
1. A search engine, comprising:
a controller to provide a search value representing a search result;
a memory to store a search database of said search results and to provide instances of said search results to said controller;
a hash-CAM sub-circuit (H-CAM) including:
a hash unit to receive said search value from said controller and generate a hash output based there on;
a CAM unit to store a CAM database of instances of said search values known to cause hash collisions in said hash unit, to receive said search value from said controller, and to match said search value against said CAM database such that a CAM output is provided if a match exists; and
a logic unit to receive said hash output and said CAM output, to create an address value based on said CAM output if a said match exists and otherwise to create said address value based on said hash output, and to provide said address value to said memory, wherein said address value represents an address in said memory, thereby permitting detection and resolution of hash collisions when searching said search database of said search results in said memory.
2. The search engine of claim 1 , wherein said hash unit is programmable to employ different hash algorithms.
3. The search engine of claim 1 , wherein said controller is further to program said CAM unit with new entries in said CAM database, thereby permitting programming to detect and resolve new hash collisions.
4. The search engine of claim 1 , wherein said logic unit is further to create a hash address based on a hash value and an offset value, and to instead create said address value based on a pointer value and a hash hit signal, and said H-CAM further includes:
a search data storage to store a plurality of hash pointer values and a plurality of search data values, wherein said hash pointer values represent instances of said hash outputs and said search data values represent instances of said search values;
said search data storage further to receive said hash address from said logic unit, to retrieve a said hash pointer value based on said hash address, to provide said hash pointer value to said logic unit as said pointer value, and to retrieve a said search data value based on said hash pointer value; and
a comparator to receive and compare said search value and said search data value to determine whether a match exists, and, if a said match exists, to provide said hash hit signal to said logic unit, thereby permitting said memory to not store any instances of said search values in said search database yet still permit the search engine to detect and resolve hash collisions.
5. The search engine of claim 4 , wherein said logic unit is further to generate a search hit signal based on said hash hit signal and whether a said match exists in said CAM unit, and to provide said search hit signal to said controller.
6. A search engine, comprising:
a controller to provide a search value representing a search result;
a memory to store a search database of said search results and to provide instances of said search results to said controller;
a hash-CAM (H-CAM) sub-circuit including:
a plurality of hash units each to receive an input value and generate a hash value based there on, wherein the first said input value is said search value and the last said hash value is a hash output;
a plurality of CAM units equaling said hash units, whereby each respective said CAM unit is definable as having a paired said hash unit; and
said CAM units to each store a CAM database of instances of said input values known to cause hash collisions in its paired said hash unit, to receive a said input value common with its paired said hash unit, to match said input value against its said CAM database, and to provide a CAM output if a match exists; and
a logic unit to receive said hash output and said CAM outputs and create an address value based there on, and to provide said address value to said memory, wherein said address value represents an address in said memory, thereby permitting detection and resolution of hash collisions when searching said search database of said search results in said memory.
7. The search engine of claim 6 , wherein said hash unit is programmable to employ different hash algorithms.
8. The search engine of claim 6 , wherein said controller is further to program said CAM unit with new entries in said CAM database, thereby permitting programming to detect and resolve new hash collisions.
9. The search engine of claim 6 , further comprising:
a plurality of hash input logics, one per said hash unit, selectively to route said input values to their respective hash units and said CAM units;
a CAM input logic to selectively route said input values to said plurality of CAM units; and
a CAM output logic to selectively combine said CAM outputs, thereby permitting configurable application of said pluralities of said hash units and said CAM units.
10. The search engine of claim 6 , wherein said logic unit is further to create a hash address based on said hash value and an offset value, and to instead create said address value based on a pointer value and a hash hit signal, and said H-CAM further includes:
a search data storage to store a plurality of hash pointer values and a plurality of search data values, wherein said hash pointer values represent instances of said hash outputs and said search data values represent instances of said search values;
said search data storage further to receive said hash address from said logic unit, to retrieve a said hash pointer value based on said hash address, to provide said hash pointer value to said logic unit as said pointer value, and to retrieve a said search data value based on said hash pointer value; and
a comparator to receive and compare said search value and said search data value to determine whether a match exists, and, if a said match exists, to provide said hash hit signal to said logic unit, thereby permitting said memory to not store any instances of said search values in said search database yet still permit the search engine to detect and resolve hash collisions.
11. The search engine of claim 10 , wherein said logic unit is further to generate a search hit signal based on said hash hit signal and whether a said match exists in said CAM unit, and to provide said search hit signal to said controller.
12. The search engine of claim 10 , further comprising:
a plurality of hash input logics, one per said hash unit, selectively to route said input values to their respective hash units and said CAM units;
a CAM input logic to selectively route said input values to said plurality of CAM units; and
a CAM output logic to selectively combine said CAM outputs, thereby permitting configurable application of said pluralities of said hash units and said CAM units.
13. The search engine of claim 12 , further comprising a plurality of said H-CAMs, thereby pemiitting cascading configurable application of said plurality of said H-CAMs and said pluralities of said hash units and said CAM units there in.
14. A search engine, comprising:
controller means for controlling the search engine and for providing a search value representing a search result;
memory means for storing a search database of said search results and for providing instances of said search results to said controller means;
a hash-CAM (H-CAM) including:
hash means for receiving said search value from said controller means and for generating a hash output based there on;
CAM means for storing a CAM database of instances of said search values known to cause hash collisions in said hash means, for receiving said search value from said controller means, and for matching said search value against said CAM database such that a CAM output is provided if a match exists; and
logic means for receiving said hash output and said CAM output, for creating art address value based on said CAM output if a said match exists and otherwise for creating said address value based on said hash output, and for providing said address value to said memory means, wherein said address value represents an address in said memory means, thereby permitting detection and resolution of hash collisions when searching said search database of said search results in said memory means.
15. The search engine of claim 14 , wherein said hash means is programmable to employ different hash algorithms.
16. The search engine of claim 14 , wherein said controller means is further for programming said CAM means with new entries in said CAM database, thereby permitting programming to detect and resolve new hash collisions.
17. The search engine of claim 14 , wherein said logic means is further for creating a hash address based on said hash value and an offset value, and for instead creating said address value based on a pointer value and a hash hit signal, and said H-CAM further includes:
search data storage means for storing a plurality of hash pointer values and a plurality of search data values, wherein said hash pointer values represent instances of said hash outputs and said search data values represent instances of said search values;
said search data storage further for receiving said hash address from said logic unit, for retrieving a said hash pointer value based on said hash address, for providing said hash pointer value to said logic means as said pointer value, and for retrieving a said search data value based on said hash pointer value; and
comparator means for receiving and comparing said search value and said search data value to determine whether a match exists, and, if a said match exists, for providing said hash hit signal to said logic means, thereby permitting said memory means to not store any instances of said search values in said search database yet still permit the search engine to detect and resolve hash collisions.
18. The search engine of claim 17 , wherein said logic means is further for generating a search hit signal based on said hash hit signal and whether a said match exists in said CAM means, and for providing said search hit signal to said controller means.
19. A search engine, comprising:
controller means for providing a search value representing a search result;
memory means for storing a search database of said search results and for providing instances of said search results to said controller means;
a hash-CAM (H-CAM) including:
a plurality of hash means for receiving an input value and for generating a hash value based there on, wherein the first said input value is said search value and the last said hash value is a hash output;
a plurality of CAM means equaling said hash means, whereby each respective said CAM means is definable as having a paired said hash means; and
said CAM means for each storing a CAM database of instances of said input values known to cause hash collisions in its paired said hash means, for receiving a said input value common with its paired said hash means, for matching said input value against its said CAM database, and for providing a CAM output if a match exists; and
logic means for receiving said hash output and said CAM outputs and creating an address value based there on, and for providing said address value to said memory means, wherein said address value represents an address in said memory means thereby permitting detection and resolution of hash collisions when searching said search database of said search results in said memory means.
20. The search engine of claim 19 , wherein said hash means is programmable to employ different hash algorithms.
21. The search engine of claim 19 , wherein said controller means is further for programming said CAM means with new entries in said CAM database, thereby permitting programming to detect and resolve new hash collisions.
22. The search engine of claim 19 , further comprising:
a plurality of hash input logic means, one each per said hash means, for selectively routing said input values to their respective hash means and to said CAM means;
CAM input logic means for selectively routing said input values to said plurality of CAM means; and
CAM output logic means for selectively combining said CAM outputs, thereby permitting configurable application of said pluralities of said hash means and said CAM means.
23. The search engine of claim 19 , wherein said logic means is further for creating a hash address based on said hash value and an offset value, and for instead creating said address value based on a pointer value and a hash hit signal, and said H-CAM further includes:
search data storage means for storing a plurality of hash pointer values and a plurality of search data values, wherein said hash pointer values represent instances of said hash outputs and said search data values represent instances of said search values;
said search data storage means further for receiving said hash address from said logic means, for retrieving a said hash pointer value based on said hash address, for providing said hash pointer value to said logic means as said pointer value, and for retrieving a said search data value based on said hash pointer value; and
comparator means for receiving and comparing said search value and said search data value to determine whether a match exists, and, if a said match exists, for providing said hash hit signal to said logic means, thereby permitting said memory means to not store any instances of said search values in said search database yet still permit the search engine to detect and resolve hash collisions.
24. The search engine of claim 23 , wherein said logic means is further for generating a search hit signal based on said hash bit signal and whether a said match exists in said CAM means, and for providing said search hit signal to said controller means.
25. The search engine of claim 23 , further comprising:
a plurality of hash input logic means, one per said hash unit, for selectively routing said input values to their respective hash means and to said CAM means;
CAM input logic means for selectively routing said input values to said plurality of CAM means; and
CAM output logic means for selectively combining said CAM outputs, thereby permitting configurable application of said pluralities of said hash means and said CAM means.
26. The search engine of claim 25 , further comprising a plurality of said H-CAMs, thereby pennitting cascading configurable application of said plurality of said H-CAMs and said pluralities of said hash means and said CAM means there in.