PATENT ABSTRACT
A multiprocessor system includes a plurality of processors that share a multiple-way set-associative cache memory that includes a directory and a data array, the multiprocessor system being partitioned such that the plurality of processor operate as independent systems. The multiprocessor system also includes a hit judgement circuit that determines hits of, of the ways in the sets that are designated at the time a processor of a particular partition accesses the shared cache memory, only those ways that have been allocated in advance in accordance with active signals that are supplied as output at the time of the access.

PATENT DESCRIPTION
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a shared cache memory, and more particularly to a multiprocessor system and to a method of controlling hit determination of a shared cache memory in a multiprocessor system that includes a plurality of processors that share a multiple-way (n-way) set-associative cache memory that includes a directory and a data array, the multiprocessor system being partitioned such that the plurality of processors each operate as independent systems.  
           [0003]    2. Description of the Related Art  
           [0004]    In a multiprocessor system in which a plurality of processors share a cache, and moreover, in a multiprocessor system that has been partitioned to allow the plurality of systems to operate independently, each partition operates as an independent system (OS), and processors may therefore in some cases use the same address to refer to different memory sites.  
           [0005]    Thus, when a different partition has registered a different memory block in the cache by the same address, a partition that refers to the cache at the same address may cause a conflicting cache hit.  
           [0006]    An example of such a conflicting cache hit will be explained hereinbelow with reference to FIG. 1. It is first assumed that the system is partitioned such that partition K 1  is processor  0  and partition K 2  is processor  1 . Processor  1  (partition K 2 ) sequentially supplies as output addresses X, Y, P, and Q in memory blocks A, B, C, and D, following which processor  0  (partition K 1 ) sequentially supplies as output addresses R, Y, P in memory blocks E, F, and G. It is further assumed that each of the above-described blocks A-G are blocks in the same set i and that the cache memory is in the initial state.  
           [0007]    When processor  1  (partition K 2 ) supplies addresses X, Y, P, and Q in blocks A, B, C, and D, copies of blocks A, B, C, and D are stored in ways  0 ,  1 ,  2 , and  3  of set i of data array  214  as shown in FIG. 1A.  
           [0008]    The subsequent output of address R in block E by processor  0  (partition K 1 ) results in a miss, and the copy of block A that was stored in way  0  is replaced by the copy of block E.  
           [0009]    The subsequent sequential output from processor  0  of addresses Y and P in blocks F and G (the same addresses as blocks B and C) results in a cache hit at ways  1  and  2  that were registered by partition K 2 , as shown in FIGS. 1C and 1D, resulting in a conflicting cache hit.  
           [0010]    As one example for preventing such a conflicting cache hit, Japanese Patent laid-open No. 2001-282617 discloses a case in which bits for storing partition numbers are extended on all cache tags, and a comparison circuit, when carrying out hit determination, determines partitions that are registered in the cache. As a result, cache hits are guaranteed not to occur in cache blocks that are registered in other partitions, and conflicting cache hits are therefore prevented.  
           [0011]    However, a method in which bits are added to a cache tag and shared cache areas are allocated to each partition such as the aforementioned Japanese Patent No. 2001-282617 also entails an increase in the hardware construction. The above-described method is therefore problematic because it does not allow miniaturization of the shared cache, miniaturization of an on-chip multiprocessor system having a limited chip area, or a reduction in costs.  
         SUMMARY OF THE INVENTION  
         [0012]    It is an object of the present invention to provide a multiprocessor system and a method of controlling hit determination for a shared cache memory of the type initially defined, this system having the same amount of hardware as a system of the prior art and being capable of preventing conflicting cache hits of each partition, and further, being capable of both reducing costs and allowing miniaturization of a shared cache or miniaturization of an on-chip multiprocessor system having a limited chip surface area.  
           [0013]    According to a first aspect of the present invention hits of, of the ways in a set that have been designated at the time a processor of a particular partition accesses a shared cache memory, only those ways that have been allocated in advance in accordance with active signals that are supplied as output at the time of the access are determined.  
           [0014]    According to a second aspect of the present invention, the multiprocessor system comprises a circuit for determining hits of, of the ways in a set that have been designated at the time of a processor of a particular partition accesses the shared cache memory, only those ways that have been allotted in advance in accordance with active signals that are supplied as output at the time of the access.  
           [0015]    In a multiprocessor system that shares a cache among a plurality of processors and in which the multiprocessor system has been partitioned, allocating ways that correspond to each partition and removing from hit determination ways that are allocated to other partitions can prevent conflicting cache hits of each partition while using an amount of hardware that is equivalent to the prior art. This approach not only allows miniaturization of a shared cache or miniaturization of an on-chip multiprocessor system having a limited chip area, but also allows a reduction in cost.  
           [0016]    The above and other objects, features, and advantages of the present invention will become apparent from the following description with reference to the accompanying drawings, which illustrate examples of the present invention. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0017]    [0017]FIG. 1 is a view for explaining the operations of the prior art;  
         [0018]    [0018]FIG. 2 is a block diagram showing the construction of an information processing system according to an embodiment of the present invention;  
         [0019]    [0019]FIG. 3 is a block diagram showing an example of the construction of a cache controller and an on-chip cache memory;  
         [0020]    [0020]FIG. 4 is a block diagram showing an example of the construction of the replacement control circuit shown in FIG. 3;  
         [0021]    [0021]FIG. 5 is a block diagram for explaining input/output signals of the comparison circuit that is shown in FIG. 3; and  
         [0022]    [0022]FIG. 6 is a view for explaining an example of the operation of the embodiment of FIG. 2. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0023]    Referring now to FIG. 2, an information processing system according to an embodiment of the present invention includes on-chip multiprocessor system  110 , on-chip multiprocessor system  120 , off-chip cache memory  130 , main memory  140 , memory bus  150 , and memory bus  160 .  
         [0024]    In the present embodiment, on-chip multiprocessor system  110  is divided into two systems, is in a state in which three systems operate including multiprocessor system  120 , partition numbers being allocated such that partition K 1  is allocated to processor core  111 , partition K 2  is allocated to processor core  112 , and partition K 3  is allocated to on-chip multi processor system  120 .  
         [0025]    On-chip multiprocessor system  110  comprises processor cores  111  and  112 , cache controller  113 , and on-chip cache memory  114 . On-chip multiprocessor system  120  comprises processor cores  121  and  122 , cache controller  123 , and on-chip cache memory  124 . On-chip cache memory  114  and on-chip cache memory  124  are four-way set-associative cache memories.  
         [0026]    [0026]FIG. 3 is a block diagram showing an example of the construction of cache controller  113  and on-chip cache memory  114  that are shown in FIG. 2. Cache controller  123  and on-chip cache memory  124  are of the same construction.  
         [0027]    Address register  201  is a register for holding physical addresses (assumed to be 32-bit addresses) when processor cores  111  and  112  access main memory  140 . These physical addresses are each composed of block address  202  (here assumed to be 18 bits), set address  203  (here assumed to be 8 bits), and in-block byte address  204  (here assumed to be 6 bits). The number of sets in directory  207  and data array  214  is therefore  256 .  
         [0028]    A copy of an appropriate block of main memory  140  is stored in each of the areas (4 ways×256 sets) of data array  214 . Tags are stored in each of the areas (4 ways×256 sets) of directory  207 , these tags being composed of: the block addresses of blocks for which copies are stored in corresponding areas of data array  214 ; and effective bits that indicate whether these copies are effective or not.  
         [0029]    Register  209  is a register for holding set addresses  203 . Decoder  210  decodes a set address that is held in register  209  and supplies as output a selection signal to select one of the 0th to the 255th sets of directory  207 .  
         [0030]    Register  215  is a register for holding set addresses  203 . Decoder  216  decodes the set address that is held in register  215  and supplies as output a selection signal to select one of the 0th to the 255th sets of data array  214 .  
         [0031]    As shown in FIG. 5, comparison circuit  208  receives as input: the content (tags) of the 0th to third ways in the sets that have been selected by decoder  210  from the 256 sets of directory  207 , block addresses  202  that are held in address register  201 , and active signals  401 . Active signals  401  are two-bit signals and are supplied from memory elements such as registers when partition K 1  or partition K 2  accesses the memory. In this embodiment, the content of active signals  401  is the number of the partition that requested memory access, this number being “01” for partition K 1  and “10” for partition K 2 .  
         [0032]    Next, regarding the operation of comparison circuit  208  will be explained.  
         [0033]    Operation when active signal  401  indicates partition K 1 :  
         [0034]    Comparison circuit  208  compares block address  202  with the block addresses in the tag for which the effective bits of way  0  and way  1 , which have been allocated to partition K 1 , indicates that they are effective; and supplies as output a miss signal if matching does not occur and a hit signal if matching does occur.  
         [0035]    Operation when active signal  401  indicates partition K 2 :  
         [0036]    Comparison circuit  208  compares block address  202  with block addresses in the tag for which the effective bits of way  2  and way  3 , which have been allocated to partition K 2 , indicates that they are effective; and supplies as output a miss signal if matching does not occur and a hit signal if matching does occur.  
         [0037]    Operation when active signal  401  indicates a non-partitioned state:  
         [0038]    Comparison circuit  208  compares block address  202  with the block addresses in the tag for which the effective bits of way  0 , way  1 , way  2  and way  3  indicate that they are effective; supplies as output a miss signal if matching does not occur and a hit signal if matching does occur. In addition, the hit signal contains selection information indicating the way in which the matching block addresses are stored.  
         [0039]    Register  211  is a register for holding hit signals and miss signals that are supplied as output from comparison circuit  208 .  
         [0040]    If a hit signal is supplied as output from comparison circuit  208 , selection circuit  217  supplies the data that are stored in the area of data array  214  that is specified by the output of decoder  216  and the selection information that is contained within this hit signal.  
         [0041]    When a miss occurs, cache tag register  205  holds the tag that is written to directory  207 . Data register  212 , on the other hand, holds a copy of the block that is written to data array  214  when a miss occurs.  
         [0042]    When a miss signal is supplied as output from comparison circuit  208 , replacement control circuit  218  supplies a replacement way signal that indicates the way that is the object of replacement. The details of the construction and operation of replacement control circuit  218  will be explained hereinbelow.  
         [0043]    In accordance with a replacement way signal from replacement control circuit  218 , selection circuit  206  supplies the tag that is being held in cache tag register  205  to, of the four ways of directory  207 , the way that is indicated by the replacement way signal. Directory  207  writes the tag that has been supplied from selection circuit  206  to the area that is specified by the way that is the output destination and by the set that is selected by decoder  210  (the set in which the miss occurred).  
         [0044]    Selection circuit  213 , on the other hand, in accordance with the replacement way signal from replacement control circuit  218 , supplies the copy of the block that is being held in data register  212  to, of the four ways of data array  214 , the way that is indicated by the replacement way signal. Data array  214  writes the copy of the block that has been supplied from selection circuit  213  to the area that is specified by the way that is the output destination and the set that was selected by decoder  216  (the set in which the miss occurred).  
         [0045]    [0045]FIG. 4 is a block diagram that shows an example of the construction of replacement control circuit  218  that is shown in FIG. 3. This replacement control circuit  218  comprises LRU bit updating circuit  301 , LRU bit holding unit  302 , and replacement object selection circuit  303 .  
         [0046]    LRU bit holding unit  302  consists of the  256  sets from the 0th to the 255th set, and in each set, LRU bits are stored that indicate the order of reference of the four ways within that set. In the present embodiment, LRU bits are composed of 8 bits with two bits being allocated to each of way  0 , way  1 , way  2  and way  3  in that order starting from the leading bit. The bits that correspond to each way are set to “00”, “01”, “10”, and “11” in the order starting from the earliest reference.  
         [0047]    When a hit signal is supplied as output from comparison circuit  208 , LRU bit updating circuit  301  updates, of the LRU bits that are being held in LRU bit holding unit  302 , the LRU bits in the set that is specified by set address  203 .  
         [0048]    The miss signal from comparison circuit  208 , the output of LRU bit holding unit  302  (the content of the set that is selected by the set address), and the active signal are applied as input to replacement object selection circuit  303 . Replacement object selection circuits  303  manage the four ways of directory  207  and data array  214  by dividing the ways into groups: the ways for partition K 1  (way  0  and way  1 ) and the ways for partition K 2  (way  2  and way  3 ).  
         [0049]    When a miss signal is supplied as output from comparison circuit  208 , replacement object selection circuit  303  carries out the following operations based on the processor core that is indicated by the active signal (the processor core that performed the memory access that caused the miss).  
         [0050]    Operations when the active signal indicates partition K 1 :  
         [0051]    Of the LRU bits of 8-bit structure that are supplied from LRU bit holding unit  302 , the bits that correspond to ways  0  and  1  that are group-allocated to partition K 1  are compared (in the present embodiment, the 0th and first bits are compared with the second and third bits) to check which of the ways was consulted earliest. A replacement way signal that indicates the way that was consulted earliest is then generated and supplied as output. For example, if the bits that correspond to ways  0  and  1  are “00” and “10” respectively, a replacement way signal indicating way  0  is supplied. This replacement way signal is supplied to selection circuits  206  and  213  in FIG. 3.  
         [0052]    Operations when the active signal indicates partition K 2 :  
         [0053]    Of the LRU bits of 8-bit structure that are supplied from LRU bit holding unit  302 , the bits that correspond to ways  2  and  3  that are group-allocated to partition K 2  are compared (in the present embodiment, the fourth and fifth bits are compared with the sixth and seventh bits) to check which of the ways was consulted earliest. A replacement way signal that indicates the way that was consulted earliest is then generated and supplied as output.  
         [0054]    Operations when the active signal indicates a non-partitioned state:  
         [0055]    The LRU bits of 8-bit structure that are supplied as output from LRU bit holding unit  302  are compared to check which of the ways of way  0 , way  1 , way  2 , and way  3  was consulted earliest. A replacement way signal that indicates the way that was consulted earliest is then generated and supplied as output.  
         [0056]    The operation of the present embodiment will be described hereinbelow with reference to FIG. 6.  
         [0057]    As an example, processor core  111  now successively supplies addresses X and Y in blocks A and B; followed by processor core  112  which successively supplies addresses P, Q, and X in blocks C, D, and E; following which processor core  111  again successively supplies addresses X and Y in blocks A and B. It is here assumed that all of the above-described blocks A-E are blocks within the same set i, and that the cache memory is in the initial state.  
         [0058]    Processor core  111  supplies addresses X and Y in blocks A and B, following which processor core  112  supplies addresses P and Q in blocks C and D, whereupon copies of blocks A, B, C, and D are stored in ways  0 ,  1 ,  2 , and  3  of set i of data array  214  as shown in FIG. 6A.  
         [0059]    Processor core  112  then supplies address X (the same address as block A) in block E, whereupon a miss occurs because the ways for processor core  112  are limited to ways  2  and  3 , and the copy of block C that was stored in way  2  is replaced by the copy of block E, as shown in FIG. 6B.  
         [0060]    Despite the subsequent output from processor core  111  of addresses X and Y in blocks A and B, cache hits occur in ways  0  and  1  as shown in FIGS. 6C and 6D.  
         [0061]    Although the number of processors sharing a cache is just two in the above-described embodiment, this number may be three or more. In addition, although the number of partitions of the parts that share the cache was just two in the above-described embodiment, this number may be three or more.  
         [0062]    Finally, although the number of ways was four in the above-described embodiment, this number may be one, two, three, five, or more.  
         [0063]    Although the cache described in the above-described embodiment was a primary cache, the cache may also be a lower-order cache. For example, this embodiment was applied to off-chip cache memory  130  shown in FIG. 2 (in which case, the number of partitions is three). In this embodiment, the active signal was information on the partitions, but the active signal may also be other information (for example, the processor number), and the logic of the corresponding hit determination circuit and replacement object selection circuit can also be applied to such a case.  
         [0064]    While preferred embodiments of the present invention have been described using specific terms, such description is for illustrative purposes only, and it is to be understood that changes and variations may be made without departing from the spirit or scope of the following claims.