Method and apparatus for wide word deletion in content addressable memories
View Patent ↗A system and method for searching and deleting segmented wide word entries in a CAM array is disclosed. A normal CAM search operation is executed to find the first word segment of a wide word. Once found, a search and delete operation is executed to find all successive word segments of the wide word, with the last word segment being marked as a deleted word segment, along a first CAM array direction. Once the last word segment is deleted, the wide word is considered to have been deleted because subsequent searches for the wide word will not find its last word segment. A purge operation is then executed along the opposite CAM array direction to delete all the word segments of the deleted wide word. Match processing circuits in each row of the CAM array can pass search results to an adjacent row above or below it to ensure that only word segments belonging to the wide word are found in the search and delete operation and deleted in the purge operation.
1. A content addressable memory comprising:
an array of content addressable memory cells, the array comprising a matchline row comprising data bit cells and control cells, wherein the matchline row is coupled to a matchline, and wherein the matchline is configured to provide a search result corresponding to a match state of the matchline;
a match processing circuit associated with the matchline row, wherein the match processing circuit is configured to perform a deletion operation, the deletion operation comprising marking the contents of the matchline row for deletion if (i) the contents of the matchline row correspond to a last word segment of a first wide word or (ii) the contents of the matchline row do not correspond to a last word segment of a second wide word and the match processing circuit receives a match flag from an adjacent match processing circuit indicating that the contents of a lower adjacent matchline row have been marked for deletion;
an address decoder for addressing the data bit cells and the control cells;
write data circuitry for writing data to the data bit cells and the control cells; and,
search data circuitry for writing search data onto searchlines.
2. The content addressable memory of claim 1 , wherein at least one control cell is associated with a set circuit coupled to a content addressable memory cell, the set circuit configured to receive set signals and the output of the match processing circuit for setting the logic state of the content addressable memory cell when the set signals are at predetermined logic states.
3. The content addressable memory of claim 1 , wherein the match processing circuit comprises a flip-flop circuit for receiving the search result at its D-input, for providing the latched search result from its Q-output in response to a clock pulse.
4. The content addressable memory of claim 3 , wherein the match processing circuit comprises a first logic pass gate for passing the search result to the flip-flop circuit when the adjacently latched search result corresponds to the match state.
5. The content addressable memory of claim 4 , wherein the match processing circuit comprises a second logic pass gate for passing the latched search result to the adjacent match processing circuit in response to a first pass enable signal.
6. The content addressable memory of claim 5 , wherein the match processing circuit comprises a third logic pass gate for passing the latched search result to another adjacent match processing circuit in response to a second pass enable signal.
7. The content addressable memory of claim 5 , wherein the match processing circuit comprises a third logic pass gate for selectively passing one of the latched search result and the adjacently latched search result from the adjacent row to the control cells in response to a second pass enable signal.
8. A content addressable memory comprising:
a matchline row comprising data bit cells and control cells, wherein the matchline row is coupled to a matchline, and wherein the matchline is configured to provide a search result corresponding to a match state of the matchline; and,
a match processing circuit associated with the matchline row, wherein the match processing circuit is configured to perform a deletion operation comprising marking the contents of its corresponding matchline row for deletion if (i) the contents of the matchline row correspond to a last word segment of a first wide word or (ii) the contents of the matchline row do not correspond to a last word segment of a second wide word and the match processing circuit receives a match flag from an adjacent match processing circuit indicating that the contents of a lower adjacent matchline row have been marked for deletion.
9. The content addressable memory of claim 8 , wherein at least one control cell is associated with a set circuit coupled to a content addressable memory cell, the set circuit configured to receive set signals and the output of the match processing circuit for setting the logic state of the content addressable memory cell when the set signals are at predetermined logic states.
10. The content addressable memory of claim 8 , wherein the match processing circuit comprises a flip-flop circuit for receiving the search result at its D-input, for providing the latched search result from its Q-output in response to a clock pulse.
11. The content addressable memory of claim 10 , wherein the match processing circuit comprises a first logic pass gate for passing the search result to the flip-flop circuit when the adjacently latched search result corresponds to the match state.
12. The content addressable memory of claim 11 , wherein the match processing circuit comprises a second logic pass gate for passing the latched search result to the adjacent match processing circuit in response to a first pass enable signal.
13. The content addressable memory of claim 12 , wherein the match processing circuit comprises a third logic pass gate for passing the latched search result to another adjacent match processing circuit in response to a second pass enable signal.
14. The content addressable memory of claim 12 , wherein the match processing circuit comprises a third logic pass gate for selectively passing one of the latched search result and the adjacently latched search result from the adjacent row to the control cells in response to a second pass enable signal.