Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
1999-07-12
2001-01-16
Nguyen, Tan T. (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C711S108000
Reexamination Certificate
active
06175513
ABSTRACT:
BACKGROUND
1. Field of Invention
This invention relates generally to content addressable memories and specifically to multiple match conditions in a content addressable memory.
2. Description of Related Art
A content addressable memory (CAM) includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory cells in the CAM array constitute a CAM word. During compare operations, a comparand word is received at appropriate input terminals of the CAM and then compared to all the CAM words. If the comparand word matches one of the CAM words, a match line corresponding to the matching CAM word is asserted to indicate a match condition. If the comparand word matches more than one of the CAM words, the match line corresponding to each of the matching CAM words is asserted, and a “multiple match” flag is also asserted to indicate the multiple match condition.
The multiple match flag is generated in response to a logical combination of the match line signals. The complexity of multiple match circuits that implement this logical combination increases approximately exponentially with increases in the number of CAM words. For example, where a CAM array has only two words, the multiple match flag is generated by simply ANDing the two corresponding match signals. Thus, for an array having 2 CAM words, the multiple match flag=m
0
*m
1
, where m
0
and m
1
are the first and second corresponding match line signals, respectively, and * indicates the logical AND function. Here, the multiple match circuit is typically implemented using a single 2-input AND gate. For 4 CAM words, the multiple match flag MMF=m
0
*m
1
+m
0
*m
2
+m
0
*m
3
+m
1
*m
2
+m
1
*m
3
+m
2
*m
3
, where + indicates the logical OR function. The corresponding multiple match circuit is typically implemented using six 2-input AND gates and one 6-input OR gate to provide the multiple match flag MMF. In a similar manner, for an array having 8 CAM words, the multiple match circuit is typically implemented using twenty-eight 2-input AND gates and a 28-input OR gate. Therefore, as shown in the above example, the size and complexity of the multiple match logic circuit is approximately exponentially related to the number of CAM words, as there is an AND gate for each possible combination of match line signals.
The rapid growth of the Internet has resulted in an explosion in the number of Internet Protocol (IP) addresses which, in turn, has necessitated the use of increasingly larger CAM arrays for IP address routing. Since the size and complexity of conventional multiple match circuits are approximately exponentially related to the number of CAM words, as described above, incremental increases in CAM array size typically result in approximately exponential increases in the size and complexity of the associated multiple match circuit. This exponential relationship between number of CAM words and size of the multiple match circuit can undesirably limit the cost-effectiveness of larger CAM array sizes desired for IP addressing.
SUMMARY
A multiple match circuit and structure are disclosed whose size and complexity are approximately logarithmically related to the number of CAM words. In accordance with one embodiment of the present invention, a multiple match flag circuit is configured to determine whether a multiple match condition exists during a compare operation within an n-word CAM array, and is also configured to generate a multiple match flag by logically ORing k=log
2
n intermediate multiple match flags. Each of the intermediate multiple match flags is generated in response to a unique logical combination of a plurality of match line signals corresponding to the n CAM words.
For one embodiment, the first n/2 match line signals are logically ORed and the second n/2 match line signals are logically ORed. The resultant OR output signals are logically ANDed to generate a first intermediate multiple match flag. Then, the first n/4 match line signals and the second n/4 match line signals are each logically ORed together, and the resulting OR output signals are logically ANDed together to generate a first signal. The third n/4 match line signals and the fourth n/4 match line signals are combined in a similar manner to generate a second signal. These first and second signals are logically ORed to generate a second intermediate multiple match flag. Next, eight groups of n/8 match line signals are each logically ORed together to generate eight OR output signals. Sequential pairs of these eight OR output signals are logically ANDed together, and the resultant AND output signals are then logically ORed to generate a third intermediate multiple match flag. This process continues for k=log
2
n iterations, where each iteration includes an associated match logic circuit. In the last or k=log
2
n
th
iteration, pairs of the match line signals are logically ANDed to generate n/2 signals which, in turn, are logically ORed to generate the last intermediate multiple match flag.
In other embodiments, a plurality of the multiple match circuits disclosed herein can be cascaded together to generate a multiple match flag for larger CAM arrays. The approximately logarithmical relationship between the size and complexity of present multiple match circuits and the number of CAM words may allow for savings in silicon area which becomes increasingly significant with increasing CAM size. Further, the reduced circuit complexity may result in less parasitic capacitances and gate delays which, in turn, generally improves circuit performance.
REFERENCES:
patent: 5426602 (1995-06-01), Luuoff
patent: 5446686 (1995-08-01), Bosngav et al.
patent: 5454094 (1995-09-01), Montoye
patent: 5640534 (1997-06-01), Liv et al.
patent: 5852569 (1998-12-01), Srinivasan et al.
patent: 5893931 (1999-04-01), Peng et al.
Preliminary Data Sheet, GEC Plessey Semiconductors, Feb. 1997, pp. 1-15.
NetLogic Microsystems
Nguyen Tan T.
Paradice III William L.
LandOfFree
Method and apparatus for detecting multiple matches in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for detecting multiple matches in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detecting multiple matches in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2477485