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 an integrated circuit device, the method comprising:
receiving a plurality of values to be stored within the integrated circuit device;
determining, for each of the plurality of values, whether a storage location is available for storage of the value within the integrated circuit device; and
storing, for each of the plurality of values, an indication of whether a storage location is available for storage of the value.
2. The method of claim 1 wherein determining, for each of the plurality of values, whether a storage location is available for storage of the value comprises generating a storage address based on constituent bits of the value.
3. The method of claim 2 wherein generating a storage address based on constituent bits of the value comprises generating a hash index based on at least a subset of the constituent bits of the value.
4. The method of claim 2 wherein determining whether a storage location is available for storage of the value further comprises determining whether a storage location indicated by the storage address is occupied by a valid, previously stored value.
5. The method of claim 4 wherein determining whether the storage location indicated by the storage address is occupied by a valid, previously stored value comprises outputting a value from the storage location indicated by the storage address and determining whether a validity indicator within the value output from the storage location is in a first state.
6. The method of claim 1 wherein storing, for each of the plurality of values, an indication of whether a storage location is available for storage of the value comprises storing a plurality of flag values in a buffer, each flag value corresponding to a respective one of the plurality of values.
7. The method of claim 6 wherein each of the flag values has either a first state or a second state according to whether a storage location is available for storage of the corresponding one of the plurality of values.
8. The method of claim 6 wherein storing the plurality of flag values in a buffer comprises storing the plurality of flag values one after another in an ordered-entry storage circuit.
9. The method of claim 8 wherein storing the plurality of flag values one after another in an ordered-entry storage circuit comprises storing the plurality of flag values in a first-in-first-out storage buffer.
10. The method of claim 6 further comprising outputting the plurality of flag values from the integrated circuit device in response to one or more buffer read requests from an external device.
11. The method of claim 1 further comprising storing, for each of the plurality of values for which a storage location is available, an address of the storage location.
12. An integrated circuit device comprising:
a memory;
an external interface to receive a plurality of values to be stored within the memory;
control circuitry to determine, for each of the plurality of values, whether a storage location within the memory is available to store the value; and
a storage buffer to store, for each of the plurality of values, an indication of whether a storage location within the memory is available to store the value.
13. The integrated circuit device of claim 12 wherein the control circuitry comprises address generation circuitry to generate, for each of the plurality of values, a memory address based on constituent bits of the value.
14. The integrated circuit device of claim 13 wherein the address generation circuitry comprises a hash index generator to generate a hash index based on at least a subset of the constituent bits of the value.
15. The integrated circuit device of claim 13 wherein the control circuitry further comprises circuitry to read a value from the memory at the memory address generated by the address generating circuitry and to determine whether the memory address is occupied by a valid, previously stored value.
16. The integrated circuit device of claim 15 wherein the circuitry to determine whether the memory address is occupied by a valid, previously stored value comprises a circuit to determine whether a set of one or more validity bits within a value retrieved from the memory at the memory address is in a first state.
17. The integrated circuit device of claim 12 wherein the storage buffer comprises an ordered-entry storage circuit.
18. The integrated circuit device of claim 17 wherein the ordered-entry storage circuit is a first-in-first-out storage buffer.
19. The integrated circuit device of claim 12 wherein the storage buffer is coupled to the external interface to output, for each of the plurality of values, the indication of whether a storage location within the memory is available to store the value.
20. An integrated circuit device comprising:
storage means;
means for receiving a plurality of values to be stored within the storage means;
means for determining, for each of the plurality of values, whether a storage location within the storage means is available to store the value; and
means for storing, for each of the plurality of values, an indication of whether a storage location within the storage means is available to store the value.