US20020163823A1

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

Info

Publication number: US20020163823A1
Application number: US09/850,882
Authority: US
Inventors: Anders Edman; Henrik Johansson
Original assignee: Individual
Current assignee: Synopsys Inc
Priority date: 2001-05-07
Filing date: 2001-05-07
Publication date: 2002-11-07
Anticipated expiration: 2021-05-07
Also published as: US6477071B1

Abstract

The present invention provides a content addressable memory (CAM) circuit that includes at least one row of memory cells storing data to be subjected to search data for a compare operation, with the cells in each row being inter-connected by a match line. Each cell can, if the search data does not match the stored data, discharge the match line in an evaluation operation. According to the present invention, a match line is partitioned into a least two segments, each segment having a first unit for precharging and evaluating the match line segment and a second unit for determining the result of the evaluation operation. The compare operation of the second and any subsequent segments is performed and the corresponding matchline segment involved only if the result of the compare operation of the respective preceding segment indicates a data match.

Description

FIELD OF THE INVENTION

The present invention relates to content addressable memory (CAM) circuitry with a partitioned match line.

BACKGROUND OF THE INVENTION

When one needs to do a fast search among large amounts of data one usually uses associative memories or content addressable memories (CAM). By using a fully parallel CAM, i.e. all cells in all rows of the CAM are searched simultaneously, one can search through the whole memory with only one instruction and this is very fast.

A drawback with a common parallel CAM is the large power consumption. The most common way to implement the match operation in a fully parallel CAM is to use a wired-OR gate for the match operation. This wired-OR gate is implemented with a wire, a match line, which is common to all CAM cells in a row. All cells can discharge the normally precharged line if there is a mismatch, or leave it alone if there is a match, for the searched and the stored bit of each CAM cell. The match line has a high capacitance due to the many CAM cells. The precharge and the very common discharges make the activity of the line almost equal to one under normal usage of the CAM. Hence, the power consumption of the match line is high.

Another known way to implement a CAM is to do it serially. In a serial implementation, a CAM row is searched bit by bit. However, the serial implementations have high latency.

It is also previously known to divide a CAM into parts. U.S. Pat. No. 5,517,441 to Dietz et al. discloses CAM circuitry in which logic states of a first and second part of a match line are selectively modified in response to comparisons between information, and the logic state of a second match line is selectively modified in response to the logic state of the first match line. This design results in faster comparisons when the search data input is partitioned.

U.S. Pat. No. 5,592,407 to Konishi et al. discloses an associative memory divided into blocks. The power consumption is reduced by making active only the necessary areas. The prior art does not effectively address the issue of high power consumption in a CAM circuit.

SUMMARY OF THE INVENTION

The present invention provides a content addressable memory circuit comprising at least one row of memory cells, the memory cells storing data to be subjected to search data for a compare operation. Each cell has the capability when subjected to the search data, if the search data does not match the stored data, to set the comparison operation result to a state indicating a mismatch.

According to the invention, a row is partitioned into at least two segments, each segment having a unit capable of controlling its compare operation and does this based on the result of the comparisons of previous segments, if any. The first segment does always perform its comparison. The following segments perform their comparisons only if it is still unclear if it is a match or not.

In a preferred embodiment, the first segment of the match line is arranged to be precharged and evaluated in all compare operations, while subsequent segments of the match line are arranged to be precharged only if the result of the compare operation of the respective preceding segment is a match and to force the match wire to indicate a mismatch if the preceding segment result is a mismatch.

In a second embodiment, all segments of the match line are arranged to be precharged for a compare operation, but only the first segment of the match line is arranged to be evaluated in all compare operations, while subsequent segments of the match line are arranged to be evaluated only if the result of the compare operation of the respective preceding segment is a match. A forward line is provided to transmit a mismatch message from one unit to the next overriding the state of the match line.

In a third embodiment, the memory circuit is designed with a combined conditional precharge and evaluation of match-line segments. The first segment ML ₀is always precharged and evaluated, while subsequent segments of the match line are arranged to be precharged and evaluated only if the result of the compare operation of the respective preceding segment is a match, and there is a discharge of the segment only if there is a mismatch in the evaluation. A forward line is provided to transmit a mismatch message from one unit to the next overriding the state of the match line.

In a fourth embodiment, the memory circuit is designed with a combined conditional precharge and/or evaluation of match-line segments. Rows are combined into a group or several groups of rows. A group of rows comprises at least one forward line for moving a mismatch message from one group of segments to the next group of segments, and the forward line is shared by a group of rows to indicate that there is no row with a match in the group.

The object of the present invention is to provide a novel implementation of a content addressable memory circuit having reduced power consumption. This is achieved by partitioning the match wire and designing the CAM such that the precharge and/or evaluation of the segments of the match line are made conditional. A key advantage of the present invention is that the power consumption of the device from precharging and discharging the match line is reduced since only a part of the comparison circuitry will be activated during most searches. Another advantage is that the present invention provides for a faster operating memory device.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will be described further in detail below with reference to the accompanying drawings, in which: [0014]
FIG. 1 is a schematic diagram of a typical CAM cell, [0015]
FIG. 2 is a schematic illustration of one row of a CAM circuit according to the preferred embodiment of the present invention, and [0016]
FIG. 3 is a schematic illustration of a group of rows of a CAM circuit according to another embodiment of the present invention.[0017]

DETAILED DESCRIPTION OF THE INVENTION

A typical CAM cell that may be incorporated in the present invention is illustrated in FIG. 1. It should be noted that the design of the CAM cell does not form a part of the present invention and other suitable CAM cells are well known in the art. The [0018] basic cell 1 stores data B, B′, that may be read and written as a random access memory (RAM) cell by means of a word line 5 for selecting the cell and a complimentary pair of bit lines 3 for storing or retrieving data. The RAM functionality is well known in the prior art. For the compare operation in the CAM functionality, the cell is connected via comparators 2 to a complementary pair of search or match data lines 4. The comparison operation is normally implemented with a wired-OR gate that usually utilizes two phases for each operation, a precharge phase and an evaluation phase. The wired-OR gate has a wire that is shared by all memory cells. It is usually called the match wire or line. In a compare or match operation, the match line 6 is precharged and then a complementary pair of search data SD, SD′ 0 is applied on the search data lines 4. The evaluation phase of the search operation is when the comparators of the cells have the possibility to discharge the match line. If the search data matches the stored data, the match line 6 state will be unchanged by the cells 1. If there is a mismatch, any cell, with a mismatch, will discharge the match line 6. The result of the evaluation is determined by checking the status of the match line. Both the precharge and discharge of the match line contribute to the power consumption of the memory.
According to the invention, a compare operation will, in most cases, not be executed if either of the precharge or the evaluation is not performed. [0019]
When the prior segment, to an intermediate segment, indicates a mismatch, this information must be provided to segments following the intermediate segment, for example, by forcing the intermediate segment match wire to indicate a mismatch or by the use of a separate wire, a forward wire, that indicates a mismatch and therefore overrides the match wire state. [0020]
In FIG. 2, one row of a CAM circuit according to the invention is illustrated. Generally, the CAM memory comprises several rows having common bit lines and search data lines. However, all rows are identical and only one is illustrated in FIG. 2. Each row comprises typically 64 [0021] identical CAM cells 1, of which only a number is shown. The match line 6 interconnects the CAM cells, but according to the present invention the match line is partitioned into a number of the segments. In FIG. 2 two segments ML₀and ML₁are shown.
A row compare operation refers to the comparison operation of the whole row, while a segment operation refers to the comparison operation of one segment only. An entry may be stored in several rows. Therefore, an entry-comparison operation may require several row-comparison operations. [0022]
The first segment ML[0023] ₀is precharged by a comparison-control unit 7 serving to precharge the match line, to control the application of search data and therefore the evaluation of the search operation. The second segment ML₁is precharged by a match-determination and comparison-control unit 8 serving to precharge the match line, to control the application of search data and therefore the evaluation of the search operation of the second segment, and also to read the result of the comparison operation of the preceding first segment, that is to determine if there is a match. The match determination of the preceding segment may control if the comparison of the subsequent segment is to be performed or not. After the last segment a match-determination unit 9 takes care of reading the result of the comparison operation of the last segment of the match line, here ML₁. The match-determination unit 9 provides the result output. Also the search data is partitioned into two parts, SD₀and SD₁, as illustrated by the two block arrows.
In a compare operation, all [0024] cells 1 in a segment are subjected to a relevant part of the search data. All cells with a mismatch contribute to the discharging of the match-line segment. One cell is sufficient to discharge the match-line segment, but the more cells that are contributing to the discharge, the faster the match-line segment will be discharged. As will be explained below, the timing is adjusted to the maximum expected discharge time. If all cells match, the match line will remain high. The match line is received as an input to the match-determination and comparison-control unit 8 of the next segment or the final match-determination unit 9, as the case may be. If the last match-line segment remains high, this indicates a complete match and this result is output by the result or match-determination unit 9.
Thus, the condition that the combined result of all the preceding segments is match, in other words no preceding segment has a mismatch, is used either to indicate a complete match or as an input enabling further compare operations. [0025]
Data associated to the row may be stored in [0026] extra RAM cells 13, which are read by means of the word line and bit lines shown in FIG. 1. Also some of the CAM cells may be configured to store associated data by the use of masks, if they are not involved in the compare operation. In some associative memories each row is associated with a fixed address pointing to a result stored in another memory table. Usually the CAM memory contains several rows. In case of matches in several rows, a priority function (not shown) located after the match-determination units ensures that only one row is selected as the match with the highest priority.
Also masks may be applied to the search data between rows (not shown) and/or the stored data in order to achieve certain functionality. However, this does not form part of the present invention. [0027]
As mentioned in the introduction, the power consumption is reduced if the rows are partitioned. That is because, if there is a mismatch in the first segment, the comparison operations in subsequent segments need not be performed. Generally, only the first segment is toggling between charged and discharged states under normal usage. The possibly hierarchical structure of data stored in the memory rows may contribute to this behaviour even more than if the data were randomly distributed. [0028]
In a first and preferred embodiment of the invention, the memory circuit is designed with a conditional precharge of match-line segments. In FIG. 2, two segments are shown but further divisions are possible. [0029]
For each segment, the events have to occur in a fixed order. If the segment is to be subjected to a compare operation, the segment is first precharged, then the search data is applied through the search data lines, then a time has to pass allowing the match line to be discharged, thereafter the state of the match line can be used by succeeding blocks. In the first embodiment, the first segment ML[0030] ₀is always precharged. Then the search data SD₀is applied. After a predefined time duration, the state of the match-line segment ML₀can be used by succeeding blocks. If the match-line segment ML₀has been discharged, i.e. at least one bit mismatch has occurred, the subsequent match-line segment ML₁is not precharged by the match-determination and comparison-control unit 8 but is set to low. The same applies to any subsequent match-line segment.
If there is no mismatch in the first segment ML[0031] ₀, the match line will remain high. A logic circuit in the match-determination and comparison-control unit 8 combines the state of the match-line segment ML₀with the clock input so that the unit 8 precharges the match-line segment ML₁only if the preceding match-line segment is high, i.e. a positive match determination. If all cells match the search data, all the match-line segments will remain high and the result unit 9 will output the result of the match operation as before.
The advantage of the first embodiment is that there will be a precharge only if there is a match in the preceding segment and the activity of the match wire will decrease. [0032]
In a second embodiment of the present invention the memory circuit is designed with a conditional evaluation of match-line segments. This embodiment uses an additional signal transmitted on a [0033] forward line 14 shown in broken lines. Initially, all match-line segments are precharged. The first part of the search data SD₀is applied to the first row segment. If all cells 1 match, the next part of the search data SD₁is applied to the next segment. However, if there is at least one bit mismatch in the first segment, this will be detected by the match-determination and comparison-control unit 8, therefore the second segment will not be evaluated and a mismatch message will be transmitted through the separate forward line 14 to the next match-determination and compareison-control unit or, in case of the last match-line segment, to the match-determination unit 9. The mismatch message will override the state of the ordinary match line to ensure that the result of the match determination is a miss. Subsequent segments of the row will not be evaluated. The evaluation may be stopped in various ways, either by stopping the search data or by means of a control signal. The forward line has lower capacitance and activity than the match wire of a fully parallel CAM making the added power from the forward line significantly less than the power saved by the lower activity on the match wires.
The advantage of the second embodiment is that there will be no discharge of subsequent segments if there is a mismatch in the preceding segment, and the precharge in the next compare operation is reduced to segments discharged previously. [0034]
In a third embodiment of the present invention the memory circuit is designed with a combined conditional precharge and evaluation of match-line segments. The first segment ML[0035] ₀is always precharged and evaluated as in the first embodiment. If the match-line segment ML₀has been discharged, i.e. at least one bit mismatch has occurred, the subsequent match-line segment ML₁is not precharged by the match-determination and comparison-control unit 8. However, a mismatch message will be transmitted through a separate forward line 14 to the next match-determination and comparison-control unit or, in case of the last match-line segment, to the match-determination unit 9 as in the second embodiment. Subsequent segments of the match line ML₁will not be precharged nor evaluated but remain in its previous state, whether high or low. If there is no mismatch in the first segment ML₀, the match line will remain high. A logic circuit in the match-determination and comparison-control unit 8 combines the state of the match-line segment ML₀with the clock input so that the unit 8 precharges the match-line segment ML₁only if the preceding match-line segment is high. If all cells match the search data all the match-line segments will remain high and the result unit 9 will output the result as before.
The advantage of the third embodiment is that there will be a precharge and evaluation only if there is a match in the preceding segment, and there is a discharge of the segment only if there is a mismatch in the evaluation. [0036]
One approach to reduce or eliminate the power consumed in connection with applying the search data is not to perform the evaluation by, e.g., not applying the search data. For example, a forward line that is shared by a number of rows, e.g. 16 rows, is used to both control the application of search data and to provide the following segment with the information that there is no match in the 16 rows. This is an implementation of a fourth embodiment of the invention and is shown in FIG. 3. The match lines, ML[0037] ₁₃in0 to ML₁₃in<n>, are fed to a common group match-determination and comparison-control unit 15 that determines if there is any match in the group and outputs the result on the shared forward line to a common group match-determination unit 16 (or a further interposed group match-determination and comparison-control unit 15). The group match-determination units 9 outputs are gated by the common group match-determination unit 16. Their outputs are forced to indicate a mismatch when the state of the incoming match lines to the match-determination units 9 is not valid. If there is no match in the first segment in any one of the 16 rows, a group mismatch message will be transmitted through the common group forward line and eventually to the final group match-determination unit 16.
The fourth embodiment may be designed with conditional precharge and/or conditional evaluation. In other words, the first segments are always precharged and there is a conditional precharge and/or evaluation of subsequent segments in a manner similar to the first and third embodiments; or all segments are always precharged and there is a conditional evaluation of subsequent segments in a manner similar to the second embodiment. The case with row-based conditional precharge and group-based conditional evaluation is a combination of the first embodiment on the row level and the second embodiment on the level of a group of 16 rows resulting in a variation on the third embodiment. [0038]
As mention above, one entry may be stored in several rows. Then, an entry-comparison operation requires several row-comparison operations. The first row-comparison operation is always executed, while the execution of subsequent row-comparison operations for an entry are dependent on the result of the entry's preceding row-comparison operations. [0039]
Due to the partitioning there is a need for more timing control signals (clock signals). One way is to use self-timing to provide the needed control signals. Since more operations may be performed in the same clock cycle, the self-timing do not increase the latency of the chip. Another way to provide the clock signals is to pipeline the match operation. However, this increases the latency of the chip since one compare operation is performed over several clock cycles. High throughput and low power are in many cases more important than low latency. [0040]
If self-timing is used, one clock cycle is divided by introducing delays in the [0041] clock signal line 12. As may be seen from FIG. 2, the first comparison-control unit 7 is triggered by the clock without any delay.
Precharge is done as a preparation before the clock edge starts the evaluation of the first segment. The [0042] delay 10 is set such that there is sufficient time to discharge the match-line segment even if only one mismatching cell performs the discharge. A delay inside the match-determination and comparison-control unit 8, that is not shown in FIG. 2, gives the unit 8 sufficient time to precharge its match-line segment. More delays 10 are introduced in the clock signal line 12 between the match-determination and comparison-control unit 8 and subsequent units and the final match determination unit 9.
If pipelining is used, the same clock controls all the [0043] units 7, 8 and 9, i.e. without the delays 10 shown in phantom lines. Thus, when the clock is in its precharge phase the match line MLO is precharged and the following match lines are conditionally precharged, and when the clock is in the evaluation phase, the evaluation starts of the comparison operation of the segments, that may be conditional for all segments except the first. Flip-flops are inserted between the row segments to store the segments comparison operation result. The search data word must be clocked through flip-flops to match the scheduling of the comparison operations of each segment. In FIG. 2 the introduced layers of flip-flops are represented with thick dashed lines 11 to emphasize the partitioning of the circuit into slices when introducing pipelining. Time-discrete signals passing the slice interfaces will go through a flip-flop (if we assume no signals going in the backwards direction). Time-analog signals, e.g. a clock, passing the layer are not fed through flip-flops. Due to the pipelining, the applied search data SD₀for the first segment belongs to one word while the simultaneously applied search data SD₁for the next segment belongs to the preceding search data word.
Combinations of self-timing and pipelining can also be used to provide the needed timing control to perform the partitioned compare operations. [0044]
Preferred embodiments of the invention have been described in detail above. However, as will be appreciated by a person skilled in the art, various changes, substitutions and modifications can be made in the exemplary embodiments without departing from the scope of the present invention. The scope of the invention is not limited by the disclosed embodiments but is defined by the following claims. [0045]

Claims

What is claimed is:

1. A content addressable memory circuit comprising at least one row of memory cells, the memory cells storing data to be subjected to search data for a compare operation, means for a compare operation, and a result output to indicate a result of a row-compare operation, wherein:

the row is partitioned into at least two segments, each segment having a comparison-control unit capable of controlling the segments' compare operation and all units, except a first, are capable of determining the result of a previous segments' compare operations, the execution of the compare operation of the second and any subsequent segments being dependent of the result of the compare operation of one or more preceding segments.

2. A memory circuit according to claim 1, wherein: the first segment of the row is arranged to be precharged and evaluated in all row-compare operations, and subsequent segments are arranged to be precharged only if a combined result of the segment-compare operations of the respective preceding segments is a match.

3. A memory circuit according to claim 1, wherein all segments of the row are arranged to be precharged, but only the first segment is evaluated in all row compare operations subsequent segments are evaluated only if a result of the combined segment-compare operations of the respective preceding segment is a match.

4. A memory circuit according to claim 1, further comprising a forward line in a segment for transmitting a mismatch message from the previous segment to a following segment or the comparison result output.

5. A memory circuit according to claim 4, wherein the first segment compare operation of the row is executed in all row-compare operations, while subsequent segment compare operations are arranged to be executed only if the combined result of the segment-compare operations of the preceding segments is a match.

6. A memory circuit according to claim 4, wherein: the forward line is shared by a group of rows in a segment, such that if there is no match in the first segment in any of the rows in the group, the mismatch message will be transmitted through the forward line.

7. A memory circuit according to claim 6, wherein the first segments of the group of rows are arranged to execute a segment-compare operation in all row compare operations, and subsequent segments of the group of rows are arranged to perform segment-cmpare operations only if the result of the segment-compare operations of the preceding segments of all of the rows in a group has at least one row with a combined result of the preceding segments that is a match.

8. A memory circuit according to claim 7, wherein all segments of the group of rows are arranged to be precharged, but only the first segments of the group of rows are arranged to be evaluated in all row-compare operations and subsequent segments of the group of rows are arranged to be evaluatred only if the segment-compare operations of the preceding segments, of all of the rows of the group has at least one row with a combined result that is a match.

9. A memory circuit according to claim 7, wherein the first segment of the group of rows are arranged to be precharged and evaluated in all row-compare operations, and subsequent segments of the group of rows are arranged to be precharged only if there are matches in the rows' preceding segments and evaluated only if the combined result of the segment-compare operations of the preceding segments of all rows has at least one matching row in a group.

10. A memory circuit according to claim 1, wherein each of the comparison-control units has clock inputs for timing the comparison operation, and a clock signal line is connected to said clock inputs for transmitting a clock signal from a single clock, and a delay is introduced in the clock signal line between clock inputs to delay each said clock edge associated with an execution of the comparison operation.

11. A memory cirucit according to claim 1, wherein each comparison-control unit has clock inputs for timing the comparison operation, and a clock signal line is connected to said clock inputs for transmitting a clock signal from a single clock, and a memory element is introduced between two row segments and one or more memory elements are introduced in a path of the search data to a later segment to align the comparison result information from the segment with the applied search data in the later segment.

12. A memory circuit according to clam 1, wherein an entry is stored in several rows, an entry-comparison operation requires several row-comparison operations, and a first row-comparison operation is always executed, and execution of one or more subsequent row-comparison operations for an entry are dependent on the result of the entry's preceding row-comparison operations.