Method and apparatus for content addressable memory with a partitioned match line

In a content addressable memory comprising at least one row of memory cells, each memory cell in said row for storing data and including a comparator for comparing the data in said memory cell with search data selectively coupled to the memory cell and a match line connected to the memory cell to indicate whether the search data matched the data stored in the memory cell, a row compare circuit for generating a result output that indicates when the data in each memory cell in said row matches the search data coupled thereto, comprising:

• a plurality of comparison control units for partitioning the memory cells in said row into at least two segments of memory cells, each said comparison control unit for controlling the comparing of the data in the memory cells grouped in its associated segment of memory cells with search data coupled to the memory cells in said segment, each said memory cell in a given segment connected in common to a match line, said match line being caused to indicate whether the search data does not match the data stored in any of the memory cells in that segment, each said comparison control unit except the first comparison control unit operative to determine the result of a previous segment's compare operation, each said comparison control unit being prevented from executing a compare operation with respect to its segment of memory cells when a mismatch has been detected by a previous segment's compare operation in said row, and wherein the first comparison control unit in said row presets the match line connected to the memory cells in the first segment of memory cells to cause the memory cells in said first segment to be compared with search data coupled to the memory cells in said segment whenever a row comparison operation is initiated, said first segment match line being caused to indicate whether the search data does not match the data stored in any of the memory cells in said first segment;
• a match determination unit coupled to the match line of the last segment of memory cells in said row for generating said result output;
• and
• a forward line coupled to each said comparison control unit for transmitting a mismatch signal from one segment to a next segment for preventing the comparison control unit in said next segment from executing a compare operation with respect to its segment of memory cells, said forward line further coupled to said match determination unit for transmitting said mismatch signal to said match determination unit.

In a content addressable memory comprising at least one group of rows of memory cells, each memory cell in each said row for storing data and including a comparator for comparing the data in said memory cell with search data selectively coupled to the memory cell and a match line connected to the memory cell to indicate whether the search data matched the data stored in the memory cell, a row compare circuit for generating a result output that indicates when the data in each memory cell in each said row matches the search data coupled thereto, comprising:

• a plurality of comparison control units for partitioning the memory cells in each said row into at least two segments of memory cells, said group being partitioned into at least two columns of segments each said comparison control unit for controlling the comparing of the data in the memory cells grouped in its associated segment of memory cells with search data coupled to the memory cells in said segment, each said memory cell in a given segment connected in common to a match line, said match line being caused to indicate whether the search data does not match the data stored in any of the memory cells in that segment, each said comparison control unit except the first comparison control unit operative to determine the result of a previous segment's compare operation, each said comparison control unit being prevented from executing a compare operation with respect to its segment of memory cells when a mismatch has been detected by a previous segment's compare operation in said row, and wherein the first comparison control unit in said row presets the match line connected to the memory cells in the first segment of memory cells to cause the memory cells in said first segment to be compared with search data coupled to the memory cells in said segment whenever a row comparison operation is initiated, said first segment match line being caused to indicate whether the search data does not match the data stored in any of the memory cells in said first segment;
• a match determination unit coupled to the match line of the last segment of memory cells in each said row for generating said result output;
• a plurality of group comparison control units, each said group comparison control unit coupled to each segment match line in a column of segments in said group of rows for detecting a mismatch result from any segment match line in said column;
• a group match determination unit for gating each said match determination unit in said group of rows;
• and
• a forward line coupled to each said group comparison control unit for transmitting a mismatch signal from one column of segments to a next column of segments for preventing all comparison control units in said next column of segments from executing a compare operation with respect to its segment of memory cells, said forward line further coupled to said group match determination unit for transmitting said mismatch signal to said group match determination unit.

In a content addressable memory comprising a plurality of rows of memory cells, each memory cell in each said row for storing data and including a comparator for comparing the data in said memory cell with search data selectively coupled to the memory cell and a match line connected to the memory cell to indicate whether the search data matched the data stored in the memory cell, a row compare circuit for generating a result output that indicates when the data in each memory cell in each said row matches the search data coupled thereto, comprising:

• a plurality of comparison control units for partitioning the memory cells in each said row into at least two segments of memory cells, each said comparison control unit for controlling the comparing of the data in the memory cells grouped in its associated segment of memory cells with search data coupled to the memory cells in said segment, each said memory cell in a given segment connected in common to a match line, said match line being caused to indicate whether the search data does not match the data stored in any of the memory cells in that segment, each said comparison control unit except the first comparison control unit operative to determine the result of a previous segment's compare operation, each said comparison control unit being prevented from executing a compare operation with respect to its segment of memory cells when a mismatch has been detected by a previous segment's compare operation in said row, and wherein the first comparison control unit in each said row presets the match line connected to the memory cells in the first segment of memory cells to cause the memory cells in said first segment to be compared with search data coupled to the memory cells in said segment whenever a row comparison operation is initiated, said first segment match line being caused to indicate whether the search data does not match the data stored in any of the memory cells in said first segment, said subsequent match lines in said row being preset only if the combined result of the segment compare operations of the respective preceding segments is a match;
• and
• a match determination unit coupled to the match line of the last segment of memory cells in each said row for generating said result output, wherein if a series of search data to be compared is stored in a plurality of rows such that a row-compare operation for at least two rows is required, the row compare operation of a first row is always executed, and the row compare operation of each subsequent row is executed only if the match determination for the preceding row indicates a match.