Abstract:
A content addressable memory which detects whether p (where p is an integer of 2 or more) bit sequences coincide respectively with reference bit sequences, said content addressable memory comprising: q comparison units which compares bit groups obtained by dividing the p bit sequences into q (where q is an integer of 2 or more) parts with corresponding bit groups in the reference bit sequences in p times; a precharge unit which precharges output lines of said q comparison units; and a comparison control unit responsive to a decision of noncoincidence in at least one of said q comparison units while said q comparison units are conducting an r th  (where r is an integer variable that is 1 or more and that is at most p−1, and p is an integer of 2 or more) comparison operation, which stops precharging to be performed by said precharge unit at time of an (r+1) th  comparison operation and subsequent comparison operations.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
         [0001]    This application claims benefit of priority under 35USC §119 to Japanese Patent Application No. 2003-88379, filed on Mar. 27, 2003, the entire contents of which are incorporated by reference herein.  
         BACKGROUND OF THE INVENTION  
         [0002]    1. Field of the Invention  
           [0003]    The present invention relates to a content addressable memory (CAM) to be used to convert a virtual address to a physical address in a microprocessor.  
           [0004]    2. Related Art  
           [0005]    In microprocessors, a content addressable memory is typically used to convert a virtual address to a physical address (see Japanese Patent Application Laid-Open Publication Nos. 2000-235787 and 2002-163891).  
           [0006]    [0006]FIG. 8 is a circuit diagram showing an internal configuration of a conventional content addressable memory (CAM). The content addressable memory includes as many comparison circuits  31  as the number of bits provided for each of a plurality of entries, and precharge circuits  32  each connected to an output line L 1  for comparison circuits  31  of the same entry. Each comparison circuit  31  includes an SRAM cell  33  which stores a reference bit sequence, transistors Q 21  and Q 22  which controls reading/writing data from/into the SRAM cell  33 , a comparator  34  which compares data stored in the SRAM cell  33  with comparison data inputted from the outside, and a transistor Q 23 , which is turned on and off according to an output of the comparator  34 .  
           [0007]    The precharge circuit  32  is a so-called wired-NOR including a transistor Q 24  which precharges the output line L 1  to a high level, a transistor Q 25  and an inverter IV  11  which holds a logic of the output line L 1 .  
           [0008]    The output line L 1  is precharged to the high level by the precharge circuit  32 . If noncoincidence is detected in any one of the comparison circuits  31 , then the output line L 1  becomes a low level.  
           [0009]    The content addressable memory shown in FIG. 8 includes as many such wired-NORs as the number of entries. When comparison circuits  31  conduct comparison operation, all wired-NORs operate because of the characteristics, and noncoincidence occurs in almost all wired-NORs, resulting in a problem of very large current consumption.  
           [0010]    In a multi-comparison content addressable memory shown in FIG. 9 obtained by expanding the content addressable memory shown in FIG. 8, the number of wired-NORs increases and the problem of the current consumption is further aggravated. Even in a time-divisional multi-comparison CAM which performs multi-comparison in time division in order to restrain increase of layout, there is the problem in which current consumption increases.  
         SUMMARY OF THE INVENTION  
         [0011]    A content addressable memory according to an embodiment of the present invention which detects whether p (where p is an integer of 2 or more) bit sequences coincide respectively with reference bit sequences, said content addressable memory comprising:  
           [0012]    q comparison units which compares bit groups obtained by dividing the p bit sequences into q (where q is an integer of 2 or more) parts with corresponding bit groups in the reference bit sequences in p times;  
           [0013]    a precharge unit which precharges output lines of said q comparison units; and  
           [0014]    a comparison control unit responsive to a decision of noncoincidence in at least one of said q comparison units while said q comparison units are conducting an r th  (where r is an integer variable that is 1 or more and that is at most p−1, and p is an integer of 2 or more) comparison operation, which stops precharging to be performed by said precharge unit at time of an (r+1) th  comparison operation and subsequent comparison operations.  
           [0015]    Furthermore, a content addressable memory which detects whether p (where p is an integer of 2 or more) bit sequences coincide respectively with reference bit sequences, said content addressable memory comprising:  
           [0016]    q comparison units which compares bit groups obtained by dividing the p bit sequences into q (where q is an integer of 2 or more) parts with corresponding bit groups in the reference bit sequences in p times; and  
           [0017]    a comparison control unit responsive to a decision of noncoincidence in at least one of said q comparison units while said q comparison units are conducting an r th  (where r is an integer variable that is 1 or more and that is at most p−1, and p is an integer of 2 or more) comparison operation, which suspends an (r+1) th  comparison operation and subsequent comparison operations to be conducted by said q comparison units. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]    [0018]FIG. 1 is a circuit diagram showing an internal configuration of a first embodiment of a content addressable memory according to the present invention;  
         [0019]    [0019]FIG. 2 is a block diagram showing a schematic configuration of a memory system including a content addressable memory  1  shown in FIG. 1;  
         [0020]    [0020]FIG. 3 is a timing diagram showing operation timing of a content addressable memory  1  shown in FIG. 1;  
         [0021]    [0021]FIG. 4 is a circuit diagram showing an internal configuration of a second embodiment of a content addressable memory  1  according to the present invention;  
         [0022]    [0022]FIG. 5 is a block showing an example of a content addressable memory in which data is divided into three or more bit sequences and time division comparison is performed;  
         [0023]    [0023]FIG. 6 is a diagram showing an example of bit sequences which are inputted to a content addressable memory shown in FIG. 5;  
         [0024]    [0024]FIG. 7 is a diagram showing comparison operations performed in comparison circuits shown in FIG. 5;  
         [0025]    [0025]FIG. 8 is a circuit diagram showing an internal configuration of a conventional content addressable memory; and  
         [0026]    [0026]FIG. 9 is a circuit diagram of a conventional multi-comparison content addressable memory. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0027]    Hereafter, a content addressable memory and a memory system according to the present invention will be described more specifically with reference to the drawings.  
       First Embodiment  
       [0028]    [0028]FIG. 1 is a circuit diagram showing an internal configuration of a first embodiment of a content addressable memory according to the present invention. FIG. 2 is a block diagram showing the schematic configuration of a memory system including a content addressable memory  1  shown in FIG. 1.  
         [0029]    The content addressable memory  1  of the present embodiment is a multi-comparison CAM which compares each of two bit sequences A&lt;0:n&gt; and B&lt;0:n&gt; with a reference bit sequence. More specifically, each of the bit sequences A&lt;0:n&gt; and B&lt;0:n&gt; is divided into a plurality of bit groups, and time is shifted for each group in order to perform comparison in twice. The content addressable memory  1  that performs such a comparison is called time division two-comparison CAM as well.  
         [0030]    The content addressable memory  1  shown in FIG. 1 is supplied with bit groups from a bit sequence distribution circuit  2  shown in FIG. 2. The bit sequence distribution circuit  2  divides each of the bit sequences A&lt;0:n&gt; and B&lt;0:n&gt; into two bit groups, and supplies them to the content addressable memory  1 . The number of bits need not necessarily be the same in respective bit groups.  
         [0031]    The content addressable memory  1  shown in FIG. 1 performs comparison operation according to bit groups supplied from the bit sequence distribution circuit  2  shown in FIG. 2, and switches logics of coincidence lines according to results of comparison. A RAM  3  shown in FIG. 2 switches whether data should be outputted according to the logics of the coincidence lines.  
         [0032]    Only the circuit configuration corresponding to one entry is shown in FIG. 1. However, the circuit shown in FIG. 1 may be provided for each of a plurality of entries. For each entry, the content addressable memory  1  shown in FIG. 1 includes two comparison circuits  11  and  12  and a comparison control circuit  13 . The comparison circuits  11  and  12  compare the bit sequence supplied from the bit sequence distribution circuit  2  with a bit sequence stored in an SRAM cell  15  in twice.  
         [0033]    The comparison circuit  11  includes bit comparison sections  14  corresponding to (n−m) bits. The comparison circuit  12  includes bit comparison sections  14  corresponding to (m+1) bits. In the same way as FIG. 8, each bit comparison section  14  includes an SRAM cell  15 , transistors Q 1  and Q 2  which control reading/writing data from/into the SRAM cell  15 , a comparator  16  which performs bit comparison, and a transistor Q 3  controlled to turn on/off by an output of the comparator  16 .  
         [0034]    In respective bit comparison sections  14 , drain terminals of the transistors Q 3  are connected to a common output line L 1 .  
         [0035]    The comparison control circuit  13  includes a precharge circuit  17  for the comparison circuit  11 , a latch circuit  19  which controls precharge operation of the precharge circuit  17 , a precharge circuit  18  for the comparison circuit  12 , a latch circuit  20  which controls precharge operation of the precharge circuit  18 , and NAND gates G 3  and G 4  which combine latch outputs of the latch circuits  19  and  20  and thereby generating the locics of the coincidence lines. The precharge circuit  17  includes transistors Q 4  to Q 6 , a NAND gate G 1 , and inverters IV 1  to IV 3 . The precharge circuit  18  includes transistors Q 7  to Q 9 , a NAND gate G 2 , and inverters IV 4  to IV 6 .  
         [0036]    [0036]FIG. 3 is a timing diagram showing operation timing of the content addressable memory  1  shown in FIG. 1. As shown in FIG. 3, the content addressable memory  1  shown in FIG. 1 performs comparison operation in twice in a predetermined interval (for example, in one cycle of a processor ranging from t 1  to t 2 ). In a first comparison operation, the comparison circuit  11  performs comparison of A&lt;n&gt;A&lt;n−1&gt; . . . A&lt;m+1&gt;, and the comparison circuit  12  performs comparison of B&lt;m&gt;B&lt;m−1&gt; . . . B&lt;0&gt;. In a second comparison operation, the comparison circuit  11  performs comparison of B&lt;n&gt;B&lt;n−1&gt; . . . B&lt;m+1&gt;, and the comparison circuit  12  performs comparison of A&lt;m&gt;A&lt;m−1&gt; . . . A&lt;0&gt;.  
         [0037]    Hereafter, it is supposed that the reference bit sequence is stored in the SRAM cells  15  in the bit comparison sections  14  beforehand. The reference bit sequence is written into the SRAM cells  15  by using bit lines BL and /BL.  
         [0038]    First of all, both CP&lt;n:0&gt; and /CP&lt;n:0&gt; are set to their high level, and outputs of all comparators  16  in the two comparison circuits  11  and  12  are set to their low level. All Q 3 s are turned off.  
         [0039]    Subsequently, a pulse of high level is supplied to a signal pre 1  to precharge the output lines L 1  of the two comparison circuits  11  and  12  to their high level.  
         [0040]    Subsequently, a complementary signal for A&lt;n:m+1&gt; is inputted to CP&lt;n:m+1&gt; and /CP&lt;n:m+1&gt; for the comparison circuit  11 . A complementary signal for B&lt;m:0&gt; is inputted to CP&lt;m:  0 &gt; and /CP&lt;m:0&gt; for the comparison circuit  12 . As a result, comparison operation is performed in the bit comparison sections  14 , and a result of the comparison is outputted to the output line L 1 . If noncoincidence occurs in at least one bit comparison section  14 , then the output line L 1  becomes the low level.  
         [0041]    Current consumption required for operation heretofore described is the same as the operation current required for the conventional operation, i.e., the operation current required for the operation performed only once. The present embodiment has a feature that noncoincidence detected in any bit sequence in the first comparison operation prevents the second comparison operation from being performed for that bit sequence. As a result, the current consumption can be reduced.  
         [0042]    The logics of the output lines L 1  showing results of the first comparison operation are latched in the latch circuits  19  and  20 . Unless noncoincidence occurs in any bit comparison section  14  in the comparison circuit  11 , an output of the latch circuit  19  becomes its high level. If noncoincidence is detected in any one of the bit comparison sections  14 , then the output of the latch circuit  19  becomes its low level.  
         [0043]    If the output of the latch circuit  19  becomes its low level, then the transistor Q 8  for precharging are not turned on, and the precharging is not performed.  
         [0044]    The bit sequence distribution circuit  2  in the present embodiment supplies bit groups belonging to the same bit sequence to the comparison circuit  11  and the comparison circuit  12  respectively in the first comparison operation and the second comparison operation. For example, if noncoincidence is detected by the comparison circuit  11  in the first comparison operation, therefore, precharging for the comparison circuit  12  is not performed in the second comparison operation.  
         [0045]    Thus in the present embodiment, if noncoincidence is detected in the comparison circuit  11  in the first comparison operation, precharging for the comparison circuit  12  is not performed in the second comparison operation. By contraries, if noncoincidence is detected by the comparison circuit  12  in the first comparison operation, precharging for the comparison circuit  11  is not performed in the second comparison operation.  
         [0046]    Subsequently, the second comparison operation is started. First, CP&lt;n:0&gt; and /CP&lt;n:0&gt; are set to their high level. As a result, outputs of all comparators  16  become their low level, and all Q 3  transistors are turned off.  
         [0047]    Subsequently, a high level pulse is supplied to a signal pre 2  to selectively precharge only comparison circuits in which noncoincidence has not been detected in the first comparison operation.  
         [0048]    A complementary signal for B&lt;n:m+1&gt; is inputted to CP&lt;n:m+1&gt; and /CP&lt;n:m+1&gt; for the comparison circuit  11 . A complementary signal for A&lt;m:0&gt; is inputted to CP&lt;m:0&gt; and /CP&lt;m:0&gt; for the comparison circuit  12 .  
         [0049]    In this state, the bit comparison sections  14  in the comparison circuits  11  and  12  perform comparison operations, and results of the comparison operations are outputted to the output lines L 1 .  
         [0050]    The results of the first comparison operation are latched in the latch circuits  19  and  20 . Therefore, the logics of the output lines L 1 , which indicate results of the second comparison operation, are combined with the latch outputs of the latch circuits  19  and  20  by using NAND gates G 3  and G 4 . Coincidence signals are thus generated.  
         [0051]    For example, if noncoincidence has been detected by neither the comparison circuit  11  nor the comparison circuit  12  in neither the first comparison operation nor the second comparison operation, then the logics of the coincidence lines /match become the low level. If noncoincidene has been detected by at least one of the comparison circuits  11  and  12 , the logic of the coincidence line /match becomes the high level.  
         [0052]    The RAM  3  shown in FIG. 2 outputs corresponding data if the coincidence line /match is its low level, whereas the RAM  3  does not output data if the coincidence line /match is its high level.  
         [0053]    As a concrete implementation form of the present embodiment, a TLB (Translation Lookaside Buffer) which converts a virtual address to a physical address is conceivable. The virtual address inputted from the outside is subject to comparison in the content addressable memory  1 . If the comparison result indicates coincidence, then the RAM  3  outputs a physical address corresponding to the virtual address.  
         [0054]    The use object of the content addressable memory  1  of the present embodiment is not limited to the TLB.  
         [0055]    In this way, in the first embodiment, each of data of two kinds A&lt;n:0&gt; and B&lt;n:0&gt; is divided into two parts to form bit groups. For each bit group, comparison processing is conducted in twice by using the two comparison circuits  11  and  12 . If noncoincidence is detected in the first comparison operation, then the output line L 1  is not precharged in the second comparison operation. As compared with the case where precharging is performed every time, therefore, the current consumption can be reduced up to 50%.  
       Second Embodiment  
       [0056]    In the second embodiment, noncoincidence detected in the first comparison operation stops the second comparison operation in the bit comparison sections  14 .  
         [0057]    [0057]FIG. 4 is a circuit diagram showing an internal configuration of the second embodiment of the content addressable memory  1  according to the present invention. In FIG. 4, components common to FIG. 1 are denoted by the same characters as in FIG. 1. Hereafter, the second embodiment will be described centered on differences between the first embodiment and the second embodiment.  
         [0058]    Each of bit comparison sections  14  in the comparison circuits  11  and  12  includes transistors Q 10  and Q 11  which control whether source lines of transistors Q 3  are cut off. The transistor Q 10  is controlled to turn on or off by the latch output of the latch circuit  20 . The transistor Q 11  is controlled to turn on or off by the latch output of the latch circuit  19 .  
         [0059]    More specifically, if noncoincidence is detected by the comparison circuit  11 , then the transistor Q 11  is turned off and the transistor  3  in the comparison circuit  12  is also turned off. In the same way, if noncoincidence is detected by the comparison circuit  12 , then the transistor Q 10  is turned off, and the transistor Q 3  also is turned off. This prevents a current from flowing from the bit comparison section  14  to the ground line. As a result, the comparison operation in the bit comparison section  14  can be suspended.  
         [0060]    Hereafter, operation of the content addressable memory  1  shown in FIG. 4 will be described. First, both CP&lt;n:0&gt; and /CP&lt;n:0&gt; are set to their high level. As a result, all Q 3  transistors, which are outputs of all bit comparison sections  14  in the comparison circuits  11  and  12 , are turned off.  
         [0061]    Subsequently, a pulse of high level is supplied to a signal pre 1  to precharge the output lines L 1  of the two comparison circuits  11  and  12  to their high level.  
         [0062]    Subsequently, the latch circuits  19  and  20  which latch results of the first comparison operation performed by the comparison circuits  11  and  12  are set by the signal pre 1  to make all bit comparison sections  14  in the comparison circuits  11  and  12  operable.  
         [0063]    Subsequently, a complementary signal for A&lt;n:m+1&gt; is supplied to CP&lt;n:m+1&gt; and /CP&lt;n:m+1&gt; for the comparison circuit  11 . A complementary signal for B&lt;m:0&gt; is inputted to CP&lt;m:0&gt; and /CP&lt;m:0&gt; for the comparison circuit  12 .  
         [0064]    As a result, the respective comparison sections  14  in the comparison circuits  11  and  12  perform comparison operations, and output results of the comparison operations to the output lines L 1 . The latch circuits  19  and  20  latch the logics of the output lines L 1 . The operation described heretofore is the same as that of the first embodiment.  
         [0065]    If the output of the latch circuit  19  is the low level, then it is meant that noncoincidence has been detected in the comparison circuit  11 . In this case, the transistor Q 11  is turned off, and the transistor Q 3  in the comparison circuit  12  is prevented from operating. Therefore, the current is prevented from flowing from the comparator  16  to the ground line, and the comparison circuit  12  does not perform the comparison operation. In addition, the logic of the coincidence line /match becomes the high level, and the RAM  3  is notified of noncoincidence.  
         [0066]    On the other hand, if the outputs of the latch circuits  19  and  20  are high levels in the first comparison operation, then it is meant that noncoincidence has not been detected in the comparison circuits  11  and.  12 . In this case, the transistors Q 10  and Q 11  are turned on, and the transistor Q 3  can also operate. Therefore, second comparison operation is performed.  
         [0067]    The second comparison operation itself is performed in a procedure similar to that of the first embodiment. First, both CP&lt;n:0&gt; and /CP&lt;n:0&gt; of the comparison circuits  11  and  12  are set to their high level. As a result, transistors Q 3 , which are outputs of all bit comparison sections  14  in the comparison circuits  11  and  12 , are turned off.  
         [0068]    Subsequently, a high level pulse is supplied to a signal pre 2  to precharge the output lines L 1  of the two comparison circuits  11  and  12 . Subsequently, a complementary signal for B&lt;n:m+1&gt; is supplied to CP&lt;n:m+1&gt; and /CP&lt;n:m+1&gt; for the comparison circuit  11 . A complementary signal for A&lt;m:0&gt; is supplied to CP&lt;m:0&gt; and /CP&lt;m:0&gt; for the comparison circuit  12 .  
         [0069]    The results of the first comparison operation are latched in the latch circuits  19  and  20 . Therefore, the logics of the output lines L 1 , which indicate results of the second comparison operation, are combined with the latch outputs of the latch circuits  19  and  20  by using NAND gates G 3  and G 4 . Coincidence signals are thus generated. For example, if noncoincidence has been detected by neither the comparison circuit  11  nor the comparison circuit  12  in neither the first comparison operation nor the second comparison operation, then the logics of the coincidence lines /match become the low level. If noncoincidence has been detected by at least one of the comparison circuits  11  and  12 , the logic of the coincidence line /match becomes the high level.  
         [0070]    Thus, in the second embodiment, noncoincidence detected in at least one of the comparison circuits when performing the first comparison operation turns the transistor Q 10  or Q 11  off and prevents the second comparison operation from being performed. As compared with the first embodiment, therefore, the current consumption can be suppressed and the current efficiency can be improved.  
         [0071]    Since the two transistors Q 3  and Q 10  (or Q 11 ) are connected in cascade in the current path in each comparison section  14 , however, faster operation is possible in the first embodiment.  
         [0072]    In the first and second embodiments, the example in which time division comparison is performed on the bit sequences of two kinds of A&lt;n:0&gt; and B&lt;n:0&gt; has been described. However, the present invention can also be applied to time division comparison on of three or more kinds of bit sequences.  
         [0073]    Hereafter, an example in which comparison is performed as to whether each of p (where p is an integer of 2 or more) bit sequences coincides with a reference bit sequence will be described. In this case, the content addressable memory  1  includes q (where q is an integer of 2 or more) comparison circuits  21  and a comparison control circuit  13 , as shown in FIG. 5.  
         [0074]    Each of q comparison circuits  21  compares each bit group obtained by dividing each of p bit sequences into q parts with a reference bit sequence in p times.  
         [0075]    If noncoincidence is detected by at least one of comparison circuits  21  while q comparison circuits  21  are performing r th  (where r is an integer variable that is 1 or more and at most p−1) comparison operation, the comparison control circuit  13  suspends (r+1) th  and subsequent precharging, or suspends the comparison processing performed by the comparison circuits  21 .  
         [0076]    For example, it is now assumed that each of four bit sequences b 1 , b 2 , b 3  and b 4  is divided into three parts to form bit groups (b 1 - 1 , b 1 - 2 , b 1 - 3 ), (b 2 - 1 , b 2 - 2 , b 2 - 3 ), (b 3 - 1 , b 3 - 2 , b 3 - 3 ), and (b 4 - 1 , b 4 - 2 , b 4 - 3 ), as shown in FIG. 6 and comparison of these bit groups with reference bit sequences is performed in four times. In this case, comparison processing is performed in four times by using three comparison circuits  21 .  
         [0077]    First, as shown in FIG. 7, bit groups (b 1 - 1 , b 2 - 2 , b 3 - 3 ) are inputted respectively to these three comparison circuits  21 - 1 ,  21 - 2  and  21 - 3 , and a first comparison operation is performed. Subsequently, bit groups (b 2 - 1 , b 3 - 2 , b 4 - 3 ) are inputted respectively to these comparison circuits  21 - 1 ,  21 - 2  and  21 - 3 , and a second comparison operation is performed. Subsequently, bit groups (b 3 - 1 , b 4 - 2 , b 1 - 3 ) are inputted respectively to these comparison circuits  21 - 1 ,  21 - 2  and  21 - 3 , and a third comparison operation is performed. Subsequently, bit groups (b 4 - 1 , b 1 - 2 , b 2 - 3 ) are inputted respectively to these comparison circuits  21 - 1 ,  21 - 2  and  21 - 3 , and a fourth comparison operation is performed.  
         [0078]    The comparison order of the bit groups is not necessarily restricted to that shown in FIG. 7. In short, respective comparison circuits need only to perform comparison on bit groups of different bit sequences each time.  
         [0079]    Each of the reference bit sequence and p input bit sequences can be divided into q parts. However, the bit arrangement cannot be altered. Because the reference bit sequences to be compared therewith correspond thereto in one-to-one correspondence.  
         [0080]    For example, as shown in FIG. 7, each of the comparison circuits  21 - 1 ,  21 - 2  and  21 - 3  performs comparison on the same bit groups of the bit sequences b 1 , b 2 , b 3  and b 4 . For example, the comparison circuit  21 - 1  compares the bit groups b 1 - 1 , b 2 - 1 , b 3 - 1  and b 4 - 1  respectively with reference bit sequences. The comparison circuit  21 - 2  compares the bit groups b 2 - 2 , b 3 - 2 , b 4 - 2  and b 1 - 2  respectively with reference bit sequences. The comparison circuit  21 - 3  compares the bit groups b 3 - 3 , b 4 - 3 , b 1 - 3  and b 2 - 3  respectively with reference bit sequences.