Block-writable content addressable memory device
View Patent ↗A content addressable memory device including a memory to store a searchable database, a search circuit, and a first-in-first-out storage circuit. The search circuit generates a plurality of address values that correspond to unoccupied storage locations within the memory, and the plurality of address values are queued within the first-in-first-out storage circuit to enable the address values to be read in succession by an external device.
1. A method of operation within a content addressable memory (CAM) device, the method comprising:
generating a plurality of address values that correspond to respective unused storage locations within the CAM device; and
storing the plurality of address values within an ordered-entry storage circuit within the CAM device.
2. The method of claim 1 wherein storing the plurality of address values within an ordered-ent ry storage circuit comprises storing the plurality of address values within a first-in-first-out storage circuit.
3. The method of claim 1 wherein storing the plurality of address values within an ordered-entry storage circuit comprises storing the plurality of address values within a last-in-first-out storage circuit.
4. The method of claim 1 further comprising:
receiving a command to read an address value from the ordered-entry storage circuit; and
outputting a first address value of the plurality of address values on to a signal path coupled between the CAM device and an external device in response to the command.
5. The method of claim 4 wherein outputting the first address value onto the signal path comprises selecting a head storage location of the ordered-entry storage circuit to source the first address value to an output driver circuit coupled to the signal path.
6. The method of claim 5 wherein selecting a head storage location to source the first address value to the output driver circuit comprises activating a plurality of transistor switches coupled between the head storage location and the output driver circuit.
7. The method of claim 1 wherein generating a plurality of address values comprises:
receiving a plurality of candidate values to be stored within the CAM device; and
searching the CAM device to determine, for each of the candidate values, whether a storage location is available for storage of the candidate value.
8. The method of claim 7 wherein searching the CAM device to determine whether a storage location is available for the candidate value comprises:
generating an index based on the candidate value; and
determining whether a storage location that corresponds to the index is occupied.
9. The method of claim 8 wherein generating an index based on the candidate value comprises generating a hash index.
10. The method of claim 4 further comprising outputting the first address value onto an address bus coupled between the CAM device and an associated memory device.
11. The method of claim 4 further comprising receiving a memory write command within the CAM device and, in response to the memory write command, outputting the first address value and a plurality of control signals to the associated memory device to enable storage of a data value within the associated memory device at a location indicated by the first address value.
12. The method of claim 11 wherein outputting a plurality of control signals to the associated memory device comprises outputting a write enable signal to the associated memory device.
13. The method of claim 4 further comprising storing a plurality of candidate values within the CAM device at the plurality of address values stored within the ordered-entry storage circuit.
14. The method of claim 13 wherein storing the plurality of candidate values within the CAM device at addresses indicated by the ordered-entry storage circuit comprises storing a first candidate value of the plurality of candidate values in one of a plurality of CAM blocks indicated by a first one of the plurality of address values within the ordered-entry storage circuit.
15. The method of claim 1 further comprising:
successively storing each of the plurality of address values in a result register; and
storing a plurality of candidate values in storage locations within the CAM device indicated by each one of the successively stored address values within the result register.
16. The method of claim 15 wherein successively storing each of the plurality of address values in the result register comprises storing each one of the plurality of address values in the result register concurrently with storing the one of the plurality of address values in the ordered-entry storage circuit.
17. The method of claim 16 wherein successively storing each of the plurality of address values in the result register comprises successively overwriting each of the plurality of address values within the result register, except a final one of the address values.
18. A content addressable memory (CAM) device comprising:
a memory to store a searchable database;
a first circuit coupled to the memory and adapted to generate a plurality of address values that correspond to unoccupied storage locations within the memory; and
an ordered-entry storage circuit to store the plurality of address values.
19. The CAM device of claim 18 wherein the ordered-entry storage circuit comprises a first-in-first-out storage circuit.
20. The CAM device of claim 18 wherein the ordered-entry storage circuit comprises a first-in-first-out storage circuit.
21. The CAM device of claim 18 wherein the first circuit comprises a compare circuit to evaluate a predetermined bit of a selected storage location within the memory to determine whether the storage location is unoccupied.
22. The CAM device of claim 21 wherein the first circuit further comprises an address generation circuit to generate an address based on a candidate value sought to be stored within the CAM device, the address corresponding to the selected storage location.
23. The CAM device of claim 22 wherein the address generation circuit comprises a hash index generator, and wherein the address based on the candidate value comprises a hash index.
24. The CAM device of claim 18 further comprising a plurality of CAM blocks each including a respective portion of the memory and a respective sub-circuit of the first circuit, each sub-circuit being adapted to output a respective block index in response to a request to search for an unoccupied storage location within the respective portion of the memory.
25. The CAM device of claim 24 wherein the first circuit comprises a priority logic circuit coupled to receive the block indices from the sub-circuits, the priority logic circuit being adapted to select one of the block indices indicated to correspond to an unoccupied storage location within the memory, the one of the block indices forming a component of one of the plurality of address values that correspond to unoccupied storage locations within the memory.
26. The CAM device of claim 18 further comprising a bus interface coupled to the ordered-entry storage circuit, the ordered-entry storage circuit being adapted to output a least recently stored one of the plurality of address values via the bus interface.
27. The CAM device of claim 26 wherein the ordered-entry storage circuit is adapted to output the least recently stored one of the plurality of address values in response to a first control signal.
28. The CAM device of claim 18 wherein the ordered-entry storage circuit comprises:
a plurality of storage elements; and
a queue control circuit to control storage of the plurality of address values within the plurality of storage elements.
29. The CAM device of claim 28 wherein the queue control circuit comprises a counter to indicate the number of address values stored within the plurality of storage elements.
30. The CAM device of claim 18 further comprising a control logic circuit coupled to the ordered-entry storage circuit and adapted to output a succession of load signals to the ordered-entry storage, each of the load signals enabling the ordered-entry storage to store a respective one of the plurality of address values.
31. A content addressable memory device (CAM) comprising:
a storage array;
means for generating a plurality of address values that correspond to respective unused storage locations within the storage array; and
means for queuing the plurality of address values within the CAM device.
32. The CAM device of claim 31 wherein the means for queuing the plurality of address values within the CAM device comprises means for storing the plurality of address values in an order from a least recently generated one of the plurality of address values to a most recently generated one of the plurality of address values.
33. The CAM device of claim 32 wherein the means for queuing the plurality of address values within the CAM device further comprises means for outputting the least recently generated one of the address values in response to a read signal.
34. The CAM device of claim 31 wherein the means for queuing the plurality of address values comprises counter means for generating a count value that indicates the number of address values queued within the means for queuing.
35. The CAM device of claim 31 wherein the means for generating a plurality of address values that correspond to respective unused storage locations within the storage array comprises means for searching the storage array to determine, for each of a plurality of candidate values, whether a storage location of the storage array is available for storage of the candidate value.