Content addressable memory device having state information processing circuitry
View Patent ↗Present embodiments allow a search engine to quickly save and restore state information to and from an external state memory when switching between multiple data flows by transferring the state information between the search engine and the external state memory in a parallel manner. More specifically, for CAM-based search engines configured according to present embodiments, the CAM array includes state information gating circuits that selectively allow state information stored in the CAM array's match latches to be transposed onto the array's bit lines and then read from the array using the array's sense amplifiers.
1. A search system comprising:
a content addressable memory (CAM) device configured to perform save state and restore (SSR) operations in which match information associated with a first flow is read from the CAM device during a flow switch operation;
SSR processing circuitry coupled to the CAM device and configured to encode the match information into a plurality of match addresses while the CAM device is generating match information associated with a second flow; and
a memory device coupled to the SSR processing circuitry and configured to store the plurality of match addresses, wherein each match address identifies a corresponding active match bit within the match information, and wherein only the match addresses corresponding to active match bits are stored in the external memory according to priority.
2. The search system of claim 1 , wherein each active match bit indicates a match condition during a compare operation between a search key and data stored in an array of CAM cells in the CAM device.
3. The search system of claim 1 , wherein the match addresses are stored in the external memory according to priority.
4. The search system of claim 1 , wherein the CAM device comprises:
an array of CAM cells arranged in a plurality of rows and columns of CAM cells, wherein each row of CAM cells is coupled to a match latch by a corresponding match line; and
gating circuitry configured to read a plurality of match bits stored in the match latches of a selected group of CAM rows from the CAM array in parallel using a plurality of bit lines associated with columns of the CAM array.
5. The search system of claim 1 , wherein the SSR processing circuitry includes save state circuitry comprising:
a read tank having a plurality of rows and a number of columns of memory cells, each row for storing the match information from a corresponding one of a plurality of groups of rows of CAM cells in the CAM device; and
priority encoding circuitry configured to generate the match addresses of all active match bits within the match information according to priority.
6. The search system of claim 5 , wherein the priority encoding circuitry further comprises:
a vertical priority encoder having a plurality of inputs each coupled to a corresponding row of the read tank and configured to select a highest priority row that has an active match bit; and
a horizontal priority encoder having a plurality of inputs each coupled to a corresponding column of the read tank and configured to generate a column address of a highest priority memory cell in the selected row that has an active match bit.
7. The search system of claim 6 , wherein:
the read tank further comprises a plurality of validity bits each indicating whether one or more of the match bits in a corresponding row of the read tank is active; and
the vertical priority encoder uses the valid bits to identify which rows of the read tank store at least one active match bit.
8. The search system of claim 7 , wherein the horizontal priority encoder generates column addresses only for the rows identified by the vertical priority encoder as having active match bits.
9. The search system of claim 8 , further comprising:
a write tank for writing the first set of state information back to the CAM device during a restore phase of the SSR operation; and
decoding circuitry coupled to receive the match addresses from the external memory, the decoding circuitry being configured to recreate the first set of state information to be stored in the write tank based on the received match addresses.
10. The search system of claim 9 , wherein the write tank comprises a plurality of write cells to store the first set of state information, and wherein the plurality of write cells are configured in rows and columns to form an array of write cells.
11. The search system of claim 10 , wherein each row of write cells corresponds with a group of match latches in the CAM device.
12. The search system of claim 10 , further comprising a write controller coupled to the write tank and the CAM device to selectively enable only rows containing at least one active write cell to be written to the CAM device.
13. The search system of claim 12 , wherein the write tank is configured to iteratively output each row containing at least one active write cell to the CAM device in order based, at least in part, on a priority associated with each row.
14. The search system of claim 1 , wherein the memory device is external to the CAM device.
15. A memory device coupled to a content addressable memory (CAM) device and configured to perform save state and restore (SSR) operations, the memory device comprising:
a read tank to store a first set of state information received from the CAM device during a save phase of an SSR operation, wherein the first set of state information comprises match results for a first flow processed in the CAM device;
priority encoding circuitry configured to generate match addresses for the first set of state information based on a prioritization scheme while the CAM device generates a second set of state information comprising match results for a second flow processed in the CAM device; and
a memory for storing the match addresses, wherein each match address identifies a corresponding active match bit within the match information, and wherein only the match addresses corresponding to active match bits are stored in the external memory according to priority.
16. The memory device of claim 15 , further comprising:
an address decoder coupled to the memory and configured to recreate the first set of state information from the match addresses stored in the memory; and
a write tank for writing the first set of state information back to the CAM device during a restore phase of the SSR operation.
17. The memory device of claim 15 , wherein the CAM device comprises:
an array of CAM cells arranged in a plurality of rows and columns of CAM cells, wherein each row of CAM cells is coupled to a match latch by a corresponding match line; and
gating circuitry configured to read a plurality of match bits stored in the match latches of a selected group of CAM rows from the CAM array in parallel using a plurality of bit lines associated with columns of the CAM array.
18. The memory device of claim 17 , wherein the read tank comprises:
a plurality of rows and a number of columns of memory cells, each row for storing the match information from a corresponding one of a plurality of groups of rows of CAM cells in the CAM device.
19. The memory device of claim 18 , wherein the priority encoding circuitry further comprises:
a vertical priority encoder having a plurality of inputs each coupled to a corresponding row of the read tank and configured to select a highest priority row that has an active match bit; and
a horizontal priority encoder having a plurality of inputs each coupled to a corresponding column of the read tank and configured to generate a column address of a highest priority memory cell in the selected row that has an active match bit.
20. The memory device of claim 19 , wherein:
the read tank further comprises a plurality of validity bits each indicating whether one or more of the match bits in a corresponding row of the read tank is active; and
the vertical priority encoder uses the valid bits to identify which rows of the read tank store at least one active match bit.
21. The memory device of claim 20 , wherein the horizontal priority encoder generates column addresses only for the rows identified by the vertical priority encoder as having active match bits.
22. The memory device of claim 16 , wherein the write tank comprises a plurality of write cells to store the first set of state information, and wherein the plurality of write cells are configured in rows and columns to form an array of write cells.
23. The memory device of claim 22 , wherein each row of write cells corresponds with a group of match latches in the CAM device.
24. The memory device of claim 22 , wherein the write tank is configured to iteratively output each row containing at least one active write cell to the CAM device in order based, at least in part, on a priority associated with each row.