Abstract:
One embodiment of the present invention provides a multiprocessor system that includes a number of processors with higher-level caches that perform memory accesses through a lower-level cache. This multiprocessor system also includes a reverse directory coupled to the lower-level cache, which includes entries corresponding to lines in the higher-level caches, wherein each entry identifies an associated entry in the lower-level cache. In one embodiment of the present invention, the higher-level cache is a set-associative cache, and storing the information within the reverse directory specifies a way location in the higher-level cache in which the line is to be stored. The system is configured to use this way information during a subsequent invalidation operation to invalidate the line in the higher-level cache without having to perform a lookup in the higher-level cache to determine the way location of the line in the higher-level cache.

Description:
RELATED APPLICATION  
       [0001]    This application hereby claims priority under 35 U.S.C. §119 to U.S. Provisional Patent Application No. 60/283,254, filed on Apr. 11, 2001, entitled “Reverse Directory for Facilitating Accesses Involving a Lower-Level Cache,” by inventors Shailender Chaudlrry and Marc Tremblay. 
     
    
     
       BACKGROUND  
         [0002]    1. Field of the Invention  
           [0003]    The present invention relates the design of multiprocessor systems, More specifically, the present invention relates to a method and an apparatus for using a reverse directory located at a lower-level cache to facilitate operations involving higher-level caches that perform accesses through the lower-level cache.  
           [0004]    2. Related Art  
           [0005]    In order to achieve high rates of computational performance, computer system designers are beginning to employ multiple processors that operate in parallel to perform a single computational task. One common multiprocessor design includes a number of processors  151 - 154  coupled to level one (L 1 ) caches  161 - 164  that share a single level two (L 2 ) cache  180  and a memory  183  (see FIG. 1). During operation, if a processor  151  accesses a data item that is not present in local L 1  cache  161 , the system attempts to retrieve the data item from L 2  cache  180 . If the data item is not present in L 2  cache  180 , the system first retrieves the data item from memory  183  into L 2  cache  180 , and then from L 2  cache  180  into L 1  cache  161 .  
           [0006]    Note that coherence problems can arise if a copy of the same data item exists in more than one L 1  cache. In this case, modifications to a first version of a data item in L 1  cache  161  may cause the first version to be different than a second version of the data item in L 1  cache  162 .  
           [0007]    In order to prevent coherency problems, computer systems often provide a coherency protocol that operates across bus  170 . A coherency protocol typically ensures that if one copy of a data item is modified in L 1  cache  161 , other copies of the same data item in L 1  caches  162 - 164 , in L 2  cache  180  and in memory  183  are updated or invalidated to reflect the modification.  
           [0008]    Coherence protocols typically perform invalidations by broadcasting invalidation messages across bus  170 . If such invalidations occur frequently, these invalidation messages can potentially tie up bus  170 , and can thereby degrade overall system performance.  
           [0009]    In order to remedy this problem, some designers have begun to explore the possibility of maintaining directory information within L 2  cache  180 . This directory information specifies which L 1  caches contain copies of specific data items. This allows the system to send invalidation information to only the L 1  caches that contain the data item instead of sending a broadcast message to all L 1  caches. (This type of system presumes that there exist separate communication pathways for invalidation messages to each of the L 1  caches  161 - 164 , unlike the example illustrated in FIG. 1, which uses a single shared bus  170  to communicate with L 1  caches  161 - 164 .)  
           [0010]    However, note that storing directory information for each entry in L 2  cache  180  is wasteful because L 2  cache  180  typically has many more entries than L 1  caches  161 - 164 . This means that most of the entries for directory information in L 2  cache  180  will be empty.  
           [0011]    Furthermore, note that L 1  caches  161 - 164  are typically set-associative. Hence, when an invalidation message is received by L 1  cache  161 , a lookup and comparison must be performed in L 1  cache  161  to determine the way location of the data item. For example, in a four-way set-associative L 1  cache, a data item that belongs to a specific set (that is specified by a portion of the address) can be stored in one of four possible “ways”. Consequently, tags from each of the four possible ways must be retrieved and compared to determine the way location of the data item. This lookup is time-consuming and can degrade system performance.  
           [0012]    What is needed is a method and an apparatus for maintaining directory information for L 1  caches without wasting memory.  
           [0013]    Furthermore, what is needed is a method and an apparatus for invalidating an entry in an L 1  cache without performing a lookup to determine the way location of the entry.  
         SUMMARY  
         [0014]    One embodiment of the present invention provides a multiprocessor system that includes a number of processors with higher-level caches that perform memory accesses through a lower-level cache. This multiprocessor system also includes a reverse directory coupled to the lower-level cache, which includes entries corresponding to lines in the higher-level caches, wherein each entry identifies an associated entry in the lower-level cache.  
           [0015]    In one embodiment of the present invention, the lower-level cache is configured to receive a request from a higher-level cache to retrieve a line from the lower-level cache. If the line is present within the lower-level cache, the system sends the line to the higher-level cache so that the line can be stored in the higher-level cache. The system also stores information in the reverse directory to indicate that the line is stored in the higher-level cache.  
           [0016]    In a variation on this embodiment, the higher-level cache is an N-way set-associative cache, and storing the information in the reverse directory involves storing way information identifying a way location in the higher-level cache in which the line is to be stored. The multiprocessor system is additionally configured to use this way information during a subsequent invalidation operation to invalidate the line in the higher-level cache without having to perform a lookup in the higher-level cache to determine the way location of the line in the higher-level cache.  
           [0017]    In one embodiment of the present invention, the lower-level cache is additionally configured to generate a miss to pull the line into the lower-level cache, if the line is not present within the lower-level cache.  
           [0018]    In one embodiment of the present invention, upon receiving an update request that causes a target entry in the lower-level cache to be updated, the system performs a lookup in the reverse directory to determine if the target entry is contained in one or more higher-level caches. For each higher-level cache that contains the target entry, the system sends an invalidation request to the higher-level cache to invalidate the target entry, and updates a corresponding entry in the reverse directory to indicate that the target entry has been invalidated in the higher-level cache.  
           [0019]    Note that this update request can include, a load miss, a store miss, and a store hit on the target entry. If the update request is a store hit, the lookup in the reverse directory involves looking up the target entry in all higher-level caches, except for a higher-level cache that caused the store hit.  
           [0020]    In one embodiment of the present invention, the reverse directory includes a fixed entry corresponding to each entry in each of the higher-level caches.  
           [0021]    In one embodiment of the present invention, each entry in the reverse directory includes information specifying a location of a corresponding entry in the lower-level cache.  
           [0022]    In one embodiment of the present invention, the lower-level cache is organized as an M-way set associative cache. In this embodiment, each entry in the reverse directory includes: a way identifier that identifies a way location of a corresponding entry within the lower-level cache; a set identifier that identifies a set location of the corresponding entry within the lower-level cache, wherein the set identifier does not include set information that can be inferred from a location of the entry within the reverse directory; and a valid flag indicating whether the entry in the reverse directory is valid.  
           [0023]    In one embodiment of the present invention, the multiprocessor system is located on a single semiconductor chip.  
           [0024]    In one embodiment of the present invention, the lower-level cache is an L 2  cache, and each of the higher-level caches is an L 1  cache.  
           [0025]    In one embodiment of the present invention, the higher-level caches are organized as write-through caches, so that updates to the higher-level caches are immediately written through to the lower-level cache.  
           [0026]    In one embodiment of the present invention, the lower-level cache includes multiple banks that can be accessed in parallel. 
       
    
    
     BRIEF DESCRIPTION OF THE FIGURES  
       [0027]    [0027]FIG. 1A illustrates a multiprocessor system.  
         [0028]    [0028]FIG. 1B illustrates a multiprocessor system with a reverse directory in accordance with an embodiment of the present invention.  
         [0029]    [0029]FIG. 2 illustrates an L 2  cache with multiple banks within a multiprocessor system in accordance with an embodiment of the present invention.  
         [0030]    [0030]FIG. 3 illustrates a reverse directory in accordance with an embodiment of the present invention.  
         [0031]    [0031]FIG. 4 illustrates a reverse directory entry in accordance with an embodiment of the present invention.  
         [0032]    [0032]FIG. 5 is a flow chart illustrating the process of creating or updating a reverse directory entry in accordance with an embodiment of the present invention.  
         [0033]    [0033]FIG. 6 is a flow chart illustrating the process of using reverse directory entries to perform invalidations in accordance with an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0034]    The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.  
         [0035]    Multiprocessor System  
         [0036]    [0036]FIG. 1B illustrates a multiprocessor system  100  with a reverse directory in accordance with an embodiment of the present invention. Note much of multiprocessor system  100  is located within a single semiconductor chip  101 . More specifically, semiconductor chip  101  includes a number of processors  110 ,  120 ,  130  and  140 , which contain level one (L 1 ) caches  112 ,  122 ,  132  and  142 , respectively. Note that the L 1  caches  112 ,  122 ,  132  and  142  may be separate instruction and data caches, or alternatively, unified instruction/data caches. L 1  caches  112 ,  122 ,  132  and  142  are coupled to level two (L 2 ) cache  106 , which includes a reverse directory  302 , which is described in more detail with reference to FIGS.  3 - 6  below. L 2  cache  106  is coupled to off-chip memory  102  through memory controller  104 .  
         [0037]    In one embodiment of the present invention, L 1  caches  112 ,  122 ,  132  and  142  are write-through caches, which means that all updates to L 1  caches  112 ,  122 ,  132  and  142  are automatically propagated to L 2  cache  106 . This simplifies the coherence protocol, because if processor  110  requires a data item that is present in L 1  cache  112 , processor  110  can receive the data from L 2  cache  106  without having to wait for L 1  cache  112  to source the data. Moreover, no forwarding network is needed to allow L 1  cache  112  to source the data. Note that in one embodiment of the present invention, L 2  cache  106  is an “inclusive cache”, which means that all items in L 1  caches  112 ,  122 ,  132  and  142  are included in L 2  cache  106 .  
         [0038]    L 2  Cache with Multiple Banks  
         [0039]    [0039]FIG. 2 illustrates an L 2  cache  106  with multiple banks in accordance with an embodiment of the present invention. In this embodiment, L 2  cache  106  is implemented with four banks  202 - 205 , which can be accessed in parallel by processors  110 ,  120 ,  130  and  140  through switch  220 . Note that only two bits of the address are required to determine which of the four banks  202 - 205  a memory request is directed to. Switch  120  additionally includes an I/O port  150  for communicating with I/O devices. Also note that each of these banks  202 - 205  includes a reverse directory. Furthermore, each of the banks  202 - 205  has its own memory controller  212 - 215 , which is coupled to an associated bank of off-chip memory  232 - 235 .  
         [0040]    Note that with this architecture, it is possible to concurrently connect each L 1  cache to its own bank of L 2  cache, which increases the bandwidth to the L 2  cache  106 .  
         [0041]    Reverse Directory  
         [0042]    [0042]FIG. 3 illustrates L 2  bank  202  along with an associated reverse directory  302  in accordance with an embodiment of the present invention. L 2  bank  202  contains an eight-way set associative cache  304  for storing instructions and data. A portion of the address is used to determine a set within cache  304 , which is represented by a row of cache  304 . Within a given set, eight different entries can be stored in each of eight different “way locations,” which are represented by the eight columns in cache  304 .  
         [0043]    Reverse directory  302  includes a separate block for each L 1  cache. More specifically, block  312  is associated with L 1  cache  112 , block  322  is associated with L 1  cache  122 , block  332  is associated with L 1  cache  132 , and block  342  is associated with L 1  cache  142 .  
         [0044]    Note that each of these blocks  312 ,  322 ,  332  and  342  includes an entry for each line in the associated L 1  caches  112 ,  122 ,  132  and  142 . Moreover, since L 1  cache  112  is organized as a four-way set associative cache, the associated block  312  within reverse directory  302  is also organized in the same fashion. However, note that entries within L 1  cache  112  contain data and instructions, whereas entries within the associated block  312  contain indexing information specifying a location of the line within cache  304 .  
         [0045]    Reverse Directory Entry  
         [0046]    [0046]FIG. 4 illustrates how a reverse directory entry  430  is created in accordance with an embodiment of the present invention.  
         [0047]    The top portion of FIG. 4 illustrates an address  400  of a data item (or instruction) within memory  102 . L 1  cache  112  divides this address into L 1  tag  412 , L 1  set number  414 , and L 1  line offset  418 . L 1  set number  414  is used to look up a specific set of the four-way set-associative L 1  cache  112 . L 1  tag  412  is stored in L 1  cache  112 , and is used to perform comparisons for purposes of implementing the four-way set-associative memory for each set. L 1  line offset  418  determines a location of a specific data item within the line in L 1  cache  112 .  
         [0048]    L 2  cache  106  divides address  400  into L 2  tag  402 , L 2  set number  404 , L 2  bank number  406  and L 2  line offset  408 . L 2  bank number  406  determines a specific bank from the four banks  202 - 205  of L 2  cache  106 . L 2  set number  404  is used to look up a specific set of the eight-way set-associative bank of L 2  cache  106 . L 2  tag  402  is stored in a specific bank of L 2  cache  106 , and is used to perform comparisons for purposes of implementing the eight-way set-associative memory for each set. L 2  line offset  408  determines a location of a specific data item within the line in L 2  cache  106 .  
         [0049]    The associated entry  430  for address  400  within reverse directory  302  contains truncated L 2  set number  424 , L 2  way number  429  and valid bit  427 . Truncated L 2  set number  424  includes the portion of L 2  set number  404  which cannot be determined from the location of the entry within L 1  cache  112 . In other words, it contains the portion of L 2  set number  404 , which does not overlap with L 1  set number  414 . L 2  way number  429  contains a three-bit index which specifies a column location of the line, out of the eight possible way locations for the line, in cache  304 . Finally, valid bit  427  indicates whether entry  430  is valid.  
         [0050]    Note that instead of storing an L 1  cache location for each line within L 2  cache  106 , the illustrated embodiment stores an entry for each L 1  cache location, and each of these entries specifies an L 2  cache location that is associated with the L 1  location.  
         [0051]    Hence, one can think of directory  302  as a “reverse directory” because instead of keeping a pointer to an L 1  entry from each L 2  entry, it keeps a pointer in the reverse direction from each L 1  entry to a corresponding L 2  entry. This saves memory because there are typically many fewer L 1  entries than L 2  entries.  
         [0052]    Process of Creating a Reverse Directory Entrv  
         [0053]    [0053]FIG. 5 is a flow chart illustrating the process of creating or updating a reverse directory entry in accordance with an embodiment of the present invention. The process starts when a request to retrieve a line is received at L 2  cache  106  from L 1  cache  112  (step  502 ). This request includes address  400 , an L 1  cache number that identifies L 1  cache  112 , and a way location in L 1  cache  112  into which the line will be stored after it is retrieved.  
         [0054]    Next, if the request generates a miss in L 2  cache  106 , the system retrieves the line into L 2  cache  106  from memory  102  (step  504 ). If this retrieval causes and existing entry in L 2  cache  106  to be invalidated, then the corresponding entries in reverse directory  302  may have to be invalidated.  
         [0055]    The system then retrieves the line from L 2  cache  106  and sends to line to L 1  cache  112  (step  506 ).  
         [0056]    The system also constructs an entry  430  for reverse directory  302  (step  508 ). This entry includes truncated L 2  set number  424 , L 2  way number  429  and valid bit  427  as is descried above with reference to FIG. 4.  
         [0057]    The system then stores the entry into a location in reverse directory  302  (step  510 ). The location is determined by a number of items. From L 2  bank number  406 , the system knows to look into L 2  bank  202 . From the L 1  cache number, the system knows to look a block  312 , which is associated with L 1  cache  112 . From address  400 , the system determines a row that is associated with a specific L 1  set. From the L 1  way location received with the request, the system determines a column within the row.  
         [0058]    Process of Using a Reverse Directory Entry  
         [0059]    [0059]FIG. 6 is a flow chart illustrating the process of using reverse directory entries to perform invalidations in accordance with an embodiment of the present invention. The system starts by receiving a request that causes an update of L 2  cache  106  (step  602 ). This request can include: a store hit on the target entry by another processor, a load miss, or a store miss.  
         [0060]    Next, the system reconstructs the entry for the request in reverse directory  302 . This is accomplished by performing a lookup in L 2  cache  106  to determine the L 2  way number  429  in which the target entry is located (step  604 ), and retrieving the L 2  set number  404  from address  400  as is illustrated in FIG. 4 (step  606 ). These values are combined to construct the reverse directory entry  130 .  
         [0061]    Next, the system uses this entry to search reverse directory  302  in order to determine which L 1  caches contain the entry (step  608 ). Note that the system only has to search the reverse directory that is associated a bank of L 2  cache  206  that is specified by L 2  bank number  406 . Furthermore, the set number within the reverse directory can be determined from the address, which means that the search only has to consider entries in the four possible “ways” for each set. Also note that if the request is a store hit by another processor, the system does not have to search the bank for the processor that caused the store hit.  
         [0062]    For each L 1  cache that contains the entry, the system sends an invalidation message to the L 1  cache. This invalidation message includes the L 1  way number, so that an associative lookup in the L 1  cache can be avoided. The system also updates the corresponding reverse directory entry to indicate that it has been invalidated (step  610 ).  
         [0063]    The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.