Abstract:
A method and system for allocating and storing data to a cache memory in each processor in a multiprocessor computer system. Data structures in main memory are partitioned into substructures that are classified as either exclusive substructures or sharing substructures. The exclusive substructures are cached exclusively by a specified processor, and the sharing substructures are cached by specified groups of processors in the multiprocessor computer. This classified partitioning results in an improved cache hit ratio compared to standard caching schemes, which improvement increases with the number of processors in the multiprocessor computer.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Technical Field  
           [0002]    The present invention relates in general to the field of computers, and, in particular, to computer memories. Still more particularly, the present invention relates to an improved method and system for improving the performance of cache memories in a multiprocessor computer system.  
           [0003]    2. Description of the Related Art  
           [0004]    Under a typical prior art method of utilizing cache memories in a multiprocessor computer system, common data used by multiple processors is mapped (cached) from a main memory to a cache memory of one or more of the multiple processors in the multiprocessor computer system. Under this traditional method of caching, initially each cache memory of each processor of the multiprocessor computer system may contain a valid copy of the common data. However, after a first processor writes an update to the common data into its cache, only that first processor&#39;s cache contains a valid copy of the common data. Whenever another processor needs to read or write to (change) the common data, it will “miss” the cached common data since the valid data is only in the first processor&#39;s cache. For example, in a multiprocessor computer having four processors, and assuming that the data is written to frequently, there is a 25% chance that the requesting processor will have the most current common data in its local cache, and thus a cache “hit” occurs when that common data is accessed. The same probability states that there is a 75% chance that the most current common data being requested will be in the cache of one of the other three processors, and thus the requesting processor will incur a cache “miss.” A cache “miss” requires the requesting processor to then “snoop” the caches of the other processors for the requested common data, or to go to main memory if none of those caches have the requested data. The description and percentages above assume that each processor has previously cached and is able to change the requested data.  
         SUMMARY OF THE INVENTION  
         [0005]    The present invention recognizes the need to improve the hit ratio of a cache memory in a multiprocessor computer. The present invention therefore is a method and system for allocating and storing data to the cache memory in each processor in a multiprocessor computer system. Data structures in a main memory are partitioned into substructures that are classified as either exclusive substructures or sharing substructures. The exclusive substructures are cached exclusively by a specified processor, and the sharing substructures are cached by specified groups of processors in the multiprocessor computer. The classified partitioning results in an improved cache hit ratio compared to cache hit ratios found in standard caching schemes. This improvement over standard caching schemes becomes greater as the number of processors in the multiprocessor computer increases.  
           [0006]    The above, as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]    The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:  
         [0008]    [0008]FIG. 1 illustrates a partitioning of a data structure in a main memory of a multiprocessor computer into data exclusive substructures and sharing substructures;  
         [0009]    [0009]FIG. 2 is a block diagram of a multiprocessor computer system utilizing the present invention&#39;s method of partitioning a data structure in a main memory;  
         [0010]    [0010]FIG. 3 depicts the sharing relationship between processors of sharing substructures stored in cache lines of cache memories associated with different processors; and  
         [0011]    [0011]FIG. 4 is a chart illustrating cache “hit” improvements using the present invention with various multiprocessor computer systems having different numbers of processors.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0012]    With reference now to the drawings and in particular to FIG. 1, there is depicted a preferred method of partitioning a data structure  32  found in memory  16 , described and depicted below in FIG. 2. In a preferred embodiment, data structure  32  is understood to be any group of data located in memory  16 . As illustrated in FIG. 1, data structure  32  is partitioned into two classes of data: exclusive substructures  34  and sharing substructures  36 .  
         [0013]    Exclusive substructures  34  are data that are designated to be copied to and stored in cache memory (“cached”) of only one specified processor  13 . For example, exclusive substructure  34  labeled “Data: P13a-P13a” is cached only by processor  13   a  (depicted in FIG. 2). In this example, no processor other than processor  13   a  is allowed to ordinarily cache or even access “Data: P13a-P13a,” unless authorized by software as described below. Each processor  13  is thus assigned its respective exclusive substructure  34 .  
         [0014]    Sharing substructures  36  are those data that are designated to be cached to more than one of processors  13 . That is, each of the sharing substructures  36  is cachable to the cache memory of two or more specified processors  13 . For example, sharing substructure  36  labeled “Data: P13a-P13b” is cached to a cache memory  30   a  and a cache memory  30   b  (illustrated in FIG. 2) associated with processors  13   a  and  13   b  (shown in FIG. 2). While sharing substructures  36  are described and named in FIG. 1 to illustrate each sharing substructure  36  being shared between two processors  13 , it is understood that according to the present invention each sharing substructure  36  may be cached by more than two processors  13  in the present invention.  
         [0015]    Referring now to FIG. 2, there is illustrated a multiprocessor computer system  10  as used by the present invention. Computer system  10  has multiple processors  13 , four of which, processor  13   a  through processor  13   d,  are depicted. Each processor  13  is connected to various devices (not shown), including input/output (I/O) devices (such as a display monitor, keyboard, graphical pointer (mouse), and a permanent storage device (hard disk)), a main memory Input/Output controller for accessing memory device  16  (such as random access memory or RAM) that is used by the processors to carry out program instructions, and firmware (not shown) whose primary purpose is to seek out and load an operating system from one of the peripherals (usually the permanent memory device) whenever the computer is first turned on. Processors  13  communicate with the peripheral devices by various means, including a generalized interconnect or bus  20 , or direct memory-access channels (not shown). Computer system  10  may have many additional components which are also not shown, such as serial and parallel ports for connection to, e.g., modems or printers. Those skilled in the art will further appreciate that there are other components that might be used in conjunction with those shown in the block diagram of FIG. 2; for example, a display adapter might be used to control a video display monitor, a memory controller can be used to access memory  16 , etc.  
         [0016]    Still referencing FIG. 2, there are illustrated caches  30 , associated with each processor  13 , that store the substructures of the partitioned data structure  32  depicted in FIG. 1. For example, processor  13   a  is shown being associated with a cache  30   a  having four cache lines  40   a.  A first cache line  40   a  contains data from exclusive substructures  34  having data labeled “Data: P13a-P13a,” indicating data that is cached only by processor  13   a.  In a preferred embodiment, processor  13   a  contains instructions directing it to cache the exclusive substructure  34  containing data labeled “Data: P13a-P13a” only is the first or otherwise specified cache line  40   a.  The next cache line  40   a  contains data labeled “Data: P13a-P13b,” indicating a sharing substructure  36  that may be cached by both processor  13   a  and processor  13   b.  The third cache line  40   a  contains data labeled “Data: P13a-P13d,” indicating a sharing substructure  36  that is cached by both processor  13   a  and processor  13   d.  The fourth cache line  40   a  contains data labeled “Data: P13a-P13c,” indicating a sharing substructure  36  that is cached by both processor  13   a  and processor  13   c.  In a preferred embodiment, processor  13   a  contains instructions directing it to cache the above specified sharing substructures  36  in specified caches lines  40   a  reserved for caching sharing substructures  36 . Caches  30   b,    30   c,  and  30   d  contain data from analogous exclusive substructures  34  and sharing substructures  36  as illustrated for cache  30   a.    
         [0017]    Referring now to FIG. 3, there is depicted pictorially the communication relationship between different cache lines  40  according to their specification. For example, data such as “Data: P13A-P13a” defined and depicted in FIG. 2 as exclusive substructures  34  are those frequently used, manipulated and therefore cached by a specified processor  13 . An example of such data would be a pointer to a job list or a counter. Preferably, data that is used at all times only by a specific processor  13  remains exclusive to that processor for the purposes of accessing and manipulating. Occasionally some exclusive substructures  34  contain data, such as counters, that may need to be occasionally “collected” or summed. For example, a counter in a cache line  40   a  such as “Data: P13a-P13a” from exclusive substructure  34  may need to be added to corresponding counters located in exclusive substructures  34  in cache lines  40   b  (Data: P13b-P13b),  40   c  (Data: P13c-P13c) and  40   d  (Data: P13d-P13d) to arrive at the total count for a process. Software would thus allow the data from the exclusive substructures  34  to be accessed by one of the processors  13  or another processing unit (not shown) to “collect” the data from these cache lines  40 . However, it should be understood and appreciated by those skilled in the art of software architecture that such data collection (coalescence, summing) are typically infrequent in software operations, and thus will have minimal impact on the overall efficiency of the present invention.  
         [0018]    Still referring to FIGS. 2 and 3, sharing substructures  36  are those substructures of data structure  32  that are cached in more than one cache  30 , thus allowing two or more processors  13  to communicate through their respective cache lines  40  containing data from the same sharing substructure  36 . For example, sharing substructure  36  containing data described as “Data: P13a-P13b” is cachable by both processor  13   a  and  13   b,  but no other processors  13 . Thus, if processor  13   a  has a cache “miss,” instructions in processor  13   a  direct processor  13   a  to snoop processor  13   b &#39;s cache  30   b  and no other cache  30 .  
         [0019]    While FIG. 2 and FIG. 3 depict data being cached to four processors  13 , it is understood that the present invention may be used with any number of multiprocessors or nodes. That is, the number of processors to which data is cached may be any integer greater than one. Further, the data may be cached to a group of processors (node, not illustrated). In a preferred embodiment, the multiprocessor system has multiple nodes each containing multiple processors. For example, the multiprocessor system may have  32  processors arranged in four nodes of eight processors each. Data structure  32  is partitioned and shared between nodes just as between processors  13  described above. In this example, each of the four nodes has four cache lines  40  that are shared by all of the processors within the node. One of the four cache lines  40  in the node is used for storage of an exclusive substructure  34 , and the remaining three cache lines  40  store sharing substructures  36 , analogous to the system and process described above for single processors  13 , rather than nodes of processors, making up the multiprocessor system. Thus, the present invention describes data caching in a multiprocessor system having multiple processing units. Each processing unit may be either a single processor  13  or a node of processors.  
         [0020]    Also, while in a preferred embodiment each exclusive substructure  34  and each sharing substructure  36  corresponds to a single cache line in cache lines  40 , in an alternate embodiment multiple sharing substructures  36  may be assigned to and cached in a single cache line  40  of a particular processor  13  or set of processors  13 .  
         [0021]    Whether data is cached as described above to processors  13  or nodes or any other processing unit, the present invention improves the cache “hit” ratio. The expected cache hit ratio for data cached from data structure  32  using the present invention can be expressed as:  
         1   n     +       (     1   -     1   n       )     2                           
 
         [0022]    where n is the number of processors that are sharing the data. The term  
       1   n                         
 
         [0023]    reflects the probability the needed data is an exclusive substructure  34  assigned to a cache line in cache  40  of the requesting processor  13 . The probability that the needed data is from a sharing substructure  36  is  
         1   -     1   n       ,                         
 
         [0024]    but since each processor  13  shares a sharing substructure  36  with one other processor  13  in the example shown, the probability of the most current cache data being in the requesting processor  13  is  
           (     1   -     1   n       )     2     .                         
 
         [0025]    The improvement in cache “hit” performance is shown in FIG. 4. The formula for the improvement can be expressed as:  
             1   n     +       (     1   -     1   n       )     2         1   n       ⇒         1     2      n       +     1   2         1   n       ⇒       (       1     2      n       +     1   2       )          (     n   1     )       ⇒       1   2     +     n   2                             
 
         [0026]    Thus, FIG. 4 shows in table format the different hit rates and improvement levels over the prior art using the present invention. For example, with four processors, the standard hit percentage using the prior art method of caching described above is 25%, since the chance of a cache hit using the standard prior art caching system described above is one out of four. The hit percentage using the present invention is 62.5%, for an improvement of 250% (2.5 fold). As seen in FIG. 4, the improvement level over the prior art method of caching increases greatly as the number of processors used in the multiprocessor system increases.  
         [0027]    While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention.