Abstract:
Techniques and methods are used to reduce allocations to a higher level cache of cache lines displaced from a lower level cache. The allocations of the displaced cache lines are prevented for displaced cache lines that are determined to be redundant in the next level cache, whereby castouts are reduced. To such ends, a line is selected to be displaced in a lower level cache. Information associated with the selected line is identified which indicates that the selected line is present in a higher level cache or the selected line is a write-through line. An allocation of the selected line in the higher level cache is prevented based on the identified information. Preventing an allocation of the selected line saves power that would be associated with the allocation.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
       [0001]    The patent application entitled “Apparatus and Methods to Reduce Castouts in a Multi-Level Cache Hierarchy U.S. application Ser. No. 11/669,245 filed on Jan. 31, 2007 has the same assignee as the present application and is hereby incorporated by reference in its entirety. 
     
    
     FIELD OF THE DISCLOSURE 
       [0002]    The present disclosure relates generally to the field of cache memory and, more specifically, to memory systems with instruction, data, and victim caches. 
       BACKGROUND 
       [0003]    Many portable products, such as cell phones, laptop computers, personal data assistants (PDAs) or the like, utilize a processor executing programs, such as, communication and multimedia programs. The processing system for such products includes a processor and memory complex for storing instructions and data. Large capacity main memory commonly has slow access times as compared to the processor cycle time. As a consequence, the memory complex is conventionally organized in a hierarchy based on capacity and performance of cache memories, with the highest performance and lowest capacity cache located closest to the processor. For example, a level 1 instruction cache and a level 1 data cache would generally be directly attached to the processor. While a level 2 unified cache is connected to the level 1 (L1) instruction and data caches. Further, a system memory is connected to the level 2 (L2) unified cache. The level 1 instruction cache commonly operates at the processor speed and the level 2 unified cache operates slower than the level 1 cache, but has a faster access time than that of the system memory. Alternative memory organizations abound, for example, memory hierarchies having a level 3 cache in addition to an L1 and an L2 cache. Another memory organization may use only a level 1 cache and a system memory. 
         [0004]    A memory organization may be made up of a hierarchy of caches operating as inclusive caches, strictly inclusive caches, exclusive caches, or a combination of these cache types. By definition herein, any two levels of cache that are exclusive to each other can not contain the same cache line. Any two levels of cache that are inclusive of each other may contain the same cache line. Any two levels of cache that are strictly inclusive of each other means that the larger cache, usually a higher level cache, must contain all lines that are in the smaller cache, usually a lower level cache. In a three or more multi-level cache memory organization, any two or more cache levels may operate as one type of cache, such as exclusive, and the remaining cache levels may operate as one of the alternative types of cache, such as inclusive. 
         [0005]    An instruction cache is generally constructed to support a plurality of instructions located at a single address in the instruction cache. A data cache is generally constructed to support a plurality of data units located at a single address in the data cache, where a data unit may be a variable number of bytes depending on the processor. This plurality of instructions or data units is generally called a cache line or simply a line. For example, a processor fetches an instruction or a data unit from an L1 cache and if the instruction or data unit is present in the cache a “hit” occurs and the instruction or data unit is provided to the processor. If the instruction or data unit is not present in the L1 cache a “miss” occurs. A miss may occur on an instruction or data unit access anywhere in a cache line. When a miss occurs, a line in the cache is replaced with a new line containing the missed instruction. A replacement policy is used to determine which cache line to replace. For example, selecting or victimizing a cache line that has been used the least represents a least recently used (LRU) policy. The cache line selected to be replaced is the victim cache line. 
         [0006]    A cache line may also have associated with it a number of status bits, such as a valid bit and a dirty bit. The valid bit indicates that instructions or data reside in the cache line. The dirty bit indicates whether a modification to the cache line has occurred. In a write-back cache, the dirty bit indicates that when a cache line is to be replaced the modifications need to be written back to the next higher memory level in the memory system hierarchy. 
         [0007]    A victim cache may be a separate buffer connected to a cache, such as a level 1 cache, or integrated in an adjacent higher level cache. Victim cache lines may be allocated in the victim cache under the assumptions that a victim line may be needed relatively shortly after being evicted and that accessing the victim line when needed from a victim cache is faster than accessing the victim line from a higher level of the memory hierarchy. With a victim cache integrated in an adjacent higher level cache, a castout occurs when a line is displaced from the lower level cache and is allocated in the higher level cache, thus caching the lower level cache&#39;s victims. The lower level cache sends all displaced lines, both dirty and non-dirty, to the higher level cache. In some cases, the victim line may already exist in the victim cache and rewriting already existing lines wastes power and reduces bandwidth to the victim cache. 
       SUMMARY 
       [0008]    The present disclosure recognizes that reducing power requirements in a memory system is important to portable applications and in general for reducing power needs in processing systems. To such ends, an embodiment of the invention addresses a tracking method to reduce allocation of displaced cache lines. A requested address is determined to miss in a lower level cache and in a next higher level cache. The requested address is determined to be a write-through address in access to the lower level cache. An allocation indication is saved with a tag of a cache line allocated in the lower level cache due to the miss in the lower level cache, wherein the allocation indication indicates the cache line was identified as a write-through line in the lower level cache. 
         [0009]    Another embodiment of the invention addresses a method to reduce castouts. In a level X cache, in response to a miss in the level X cache and in a level X+1 cache, an allocation bit is saved in a tag of a cache line associated with the miss in the level X cache. The allocation bit indicates the cache line is identified as a write-through line in the level X cache. A line is selected to be displaced in the level X cache. A castout of the selected line from the level X cache to the level X+1 cache is prevented in response to an allocation bit of the selected line indicating the selected line is a write-through cache line. 
         [0010]    Another embodiment of the invention addresses a memory system having a plurality of cache levels. A lower level cache is configured to store a plurality of first cache lines each with an allocation bit. Each allocation bit indicates whether an associated first cache line is a write-through cache line. A castout logic circuit is configured to determine whether a first cache line selected for displacement from the plurality of first cache lines is redundant with a cache line in the higher level cache based on an allocation bit associated with the selected first cache line that identifies the selected first cache line as a write-through line. A castout of the selected first cache line to the higher level cache is avoided in response to the allocation bit of the selected first cache line. 
         [0011]    It is understood that other embodiments of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein various embodiments of the invention are shown and described by way of illustration. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modification in various other respects, all without departing from the present invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]      FIG. 1  illustrates a wireless communication system; 
           [0013]      FIG. 2  is a functional block diagram of an exemplary processor and memory complex in which duplicate line fills in a victim cache are reduced; and 
           [0014]      FIG. 3  is a flow diagram illustrating a process for reducing duplicate line fills in a victim cache. 
       
    
    
     DETAILED DESCRIPTION 
       [0015]    The detailed description set forth below in connection with the appended drawings is intended as a description of various exemplary embodiments of the present invention and is not intended to represent the only embodiments in which the present invention may be practiced. The detailed description includes specific details for the purpose of providing a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced without these specific details. In some instances, well known structures and components are shown in block diagram form in order to avoid obscuring the concepts of the present invention. 
         [0016]      FIG. 1  illustrates an exemplary wireless communication system  100  in which an embodiment of the invention may be advantageously employed. For purposes of illustration,  FIG. 1  shows three remote units  120 ,  130 , and  150  and two base stations  140 . It will be recognized that common wireless communication systems may have many more remote units and base stations. Remote units  120 ,  130 , and  150  include hardware components, software components, or both as represented by components  125 A,  125 C, and  125 B, respectively, which have been adapted to embody the invention as discussed further below.  FIG. 1  shows forward link signals  180  from the base stations  140  to the remote units  120 ,  130 , and  150  and reverse link signals  190  from the remote units  120 ,  130 , and  150  to the base stations  140 . 
         [0017]    In  FIG. 1 , remote unit  120  is shown as a mobile telephone, remote unit  130  is shown as a portable computer, and remote unit  150  is shown as a fixed location remote unit in a wireless local loop system. By way of example, the remote units may alternatively be cell phones, pagers, walkie talkies, handheld personal communication systems (PCS) units, portable data units such as personal data assistants, or fixed location data units such as meter reading equipment. Although  FIG. 1  illustrates remote units according to the teachings of the disclosure, the disclosure is not limited to these exemplary illustrated units. Embodiments of the invention may be suitably employed in any device having a processor with at least two levels of a memory hierarchy, such as a level 1 cache and a level 2 cache. 
         [0018]      FIG. 2  is a functional block diagram of an exemplary processor and memory complex  200  in which duplicate line fills in a victim cache are reduced. The exemplary processor and memory complex  200  includes a processor  202 , a level 1 cache (L1 cache)  203  comprising an L1 cache line array  204  and an L1 cache control unit  206 , a memory management unit (MMU)  207 , an inclusive level 2 cache (L2 cache)  208 , and a system memory  210 . The L2 cache  208  may operate with an integrated victim cache, which allows victim lines selected from the L1 cache  203  to be cached in the L2 cache  208  as described in more detail below. The L1 cache control unit  206  includes castout logic circuit  212  and a level 1 content addressable memory (L1 CAM)  214  for tag matching, as may be used in various types of caches, such as, a set associative cache or a fully associative cache. The Memory Management Unit (MMU)  207  contains write-through bits, such as write through bit  209 , associated with line addresses to the L1 cache  203 , such as line addresses  231 - 233 . The write-through bit  209  indicates whether store operations to the L1 cache are required to both write the data to the L1 cache and write the data through to the L2 cache. Memory address ranges may be program settable to indicate write-through mode operation. Peripheral devices, which may connect to the processor complex, are not shown for clarity of discussion. The exemplary processor and memory complex  200  may be suitably employed in various embodiments of the invention in components  125 A-C for executing program code that is stored in the caches  203  and  208  and the system memory  210 . 
         [0019]    The L1 cache line array  204  may include a plurality of lines, such as cache lines  215 - 217 . In one embodiment, the L1 cache  203  is a data cache with each line made up of a plurality of data units. In another embodiment, the L1 cache  203  is an instruction cache with each line made up of a plurality of instructions. In a further embodiment, the L1 cache  203  is a unified cache with each line made up of a plurality of instructions or data units. For example, each line is made up of a plurality of elements (U 0 , U 1 , . . . , U 7 )  218 - 225 , respectively, appropriate for the instantiated cache embodiment. Associated with each line is a tag  226 , a dirty bit (D)  228 , and a force replacement castout bit (FRC)  230 , as will be discussed in greater detail below. The cache lines  215 - 217  reside in the L1 cache line array  204  at line addresses  231 - 233 , respectively. The L1 cache control unit  206  contains address control logic responsive to an instruction address or data address (I/DA)  234  received over I/DA interface  235  to access cache lines. The I/DA  234  may be made up of a tag  236 , a line address field  238 , an instruction/data “U” field  240 , and a byte “B” field  242 . 
         [0020]    In order to fetch an instruction or a data unit in the exemplary processor and memory complex  200 , the processor  202  generates an instruction/data address (I/DA)  234  of the desired instruction/data to be fetched and sends the fetch address to the L1 cache control unit  206  and the MMU  207 . Based on the received I/DA  234 , the L1 cache control unit  206  checks to see if the instruction or data is present in the L1 cache line array  204 . This check is accomplished, for example, through the use of comparison logic that checks for a matching tag  244  associated with line  215  which was selected by the I/DA  234 . If the instruction or data is present, a match or a hit occurs and the L1 cache control unit  206  indicates that the instruction or data is present in the L1 cache  203 . If the instruction or data is not present, no match or a miss will be found and the L1 cache control unit  206  provides a miss indication that the instruction or data is not present in the L1 cache  203 . 
         [0021]    If the instruction or data is present, the instruction or data at the instruction/data fetch address is selected from the L1 cache line array  204 . The instruction or data is then sent on instruction/data out bus  246  to the processor  202 . 
         [0022]    If the instruction/data is not present in the cache, miss information is provided to the L2 cache  208  by a miss signal  248  indicating a miss has occurred. The write-through bit  209  from MMU  207  is provided by a write-through signal  211  in addition to the miss signal  248  to the L2 cache  208 . Upon detecting a miss in the L1 cache  203 , an attempt is made to fetch the desired instruction/data from the L2 cache  208 . If the desired instruction/data is present in the L2 cache  208 , it is provided on a memory bus interface  250 . If the desired instruction/data is not present in the L2 cache  208 , it is fetched from system memory  210 . 
         [0023]    A force replacement castout (FRC) signal  254  from the L2 cache  208  is sent to the lower L1 cache  203  along with the desired instruction/data sent on the memory bus interface  250 . The FRC signal  254  indicates whether or not the supplied instruction/data was obtained due to a hit in the upper level L2 cache  208 . For example, the FRC signal  254  in a “0” state indicates the desired instruction/data was supplied from the L2 cache  208 . The FRC signal  254  in a “1” state indicates the desired instruction/data was supplied from another level memory above the L2 cache  208 , such as from the system memory  210 . The FRC signal  254  is stored in the L1 cache  203 , for example, as FRC bits  256 - 258  along with a tag associated with the appropriate cache line, such as lines  215 - 217 . When the requested line is a miss in the L2 cache  208  and the L1 cache  203 , the L1 cache  203  is supplied by the next level of memory above the L2 cache  208 , whereas the L2 cache  208  does not allocate the line at the time of the miss. 
         [0024]    If the instruction/data address (I/DA)  234  that is applied to the lower level cache is identified as being write-through in the lower level cache as determined, for example by the write-through bit  209  being a 1 for the requested address, then a line is allocated in the upper level cache, such as the L2 cache  208 , and the FRC signal is driven to zero. The MMU  207  identifies the write-through status for the address over write-through signal  211  to the L2 cache. The castout logic circuit  212  in the L1 cache evaluates the FRC signal  254  that was supplied by the L2. Setting a write-through bit on an initial allocation into the upper level cache at the time of the fetch of the requested address prevents a duplicate allocation in the upper level cache when an actual write, associated with a write-through operation, for example, is performed. An allocation indication, such as the FRC signal  254  having a zero value in response to the write-through signal  211  having a one value, for example, is saved in a tag of a cache line allocated in the lower level cache due to a miss in the lower level cache. A zero value of the FRC bit, stored in a tag of a cache line, prevents a redundant or duplicate line fill when the line is displaced from the lower level cache, such as the L1 cache  203 . 
         [0025]    When a lower level cache must displace a line, the line may be allocated in the next level cache in response to information stored with the line in the lower level cache. For example, when a lower level cache, such as the L1 cache  203 , selects a line to be displaced, such as cache line  215 , with an FRC bit  257  and a dirty indication, as indicated by the dirty bit  259  in a “1” state, the castout logic circuit  212  makes a determination that the cache line  215  is to be allocated to the next level of the memory hierarchy. If a cache line is selected to be displaced that is not dirty, such as cache line  216  with the dirty bit  260  in a “0” state, and has its associated FRC bit  256  set active, for example, to a “1” state, the cache line  216  is also allocated to the next level of the memory hierarchy. The FRC bit  256  is conditionally set active in response to an FRC signal  254  indication provided by the next level of the memory hierarchy that the line was not found in its directory and conditional on an associated write-through bit. For example, if a write-through bit is set active, such as the write-through bit  209 , the FRC signal  254  is driven to a zero value. If the write-through bit is not set active, the FRC signal  254  may be set active. If a cache line which is selected to be replaced is not dirty, such as cache line  217  with its dirty bit  261  in a “0” state, and has an associated FRC bit  258  set inactive, for example, to a “0” state, the castout logic circuit  212  makes a determination that the cache line  217  is not to be allocated to the next level of the memory hierarchy. A castout is not required due to the line being not dirty and the FRC bit  258  indicating by its inactive state that this cache line  217  is present in or redundant with a line in the next level of the memory hierarchy. In short, the higher level cache allocates a cache line when the dirty bit is set or the FRC bit is set. Through such use of the FRC bit, redundant castouts are suppressed thereby saving power and access cycles by avoiding unnecessary accesses to upper levels of the memory hierarchy. 
         [0026]      FIG. 3  is a flow diagram illustrating a process  300  for reducing duplicate line fills in a victim cache. In the process  300 , a memory level is indicated by indexes (X), (X+1), or (X+2), where, for example, with X=1, an L1, an L2, and an L3 memory level may be indicated. Also, descriptions of the blocks of process  300  include reference numbers to functional elements in  FIG. 2 . 
         [0027]    The process  300  begins with a processor, such as processor  202 , that fetches an instruction or a data unit at block  302 . At decision block  304 , it is determined whether the instruction/data requested can be located in an L(X) cache, such as the L1 cache  203 . If the instruction/data can be located, the requested instruction/data is fetched from the L(X) cache at block  306  and the instruction/data is returned to the processor at block  308 . 
         [0028]    If the instruction/data cannot be located in the L(X) cache, a miss indication is generated and at decision block  310  it is determined whether the instruction/data requested can be located in an L(X+1) cache, such as the L2 cache  208 . If the instruction/data can be located, the requested instruction/data is fetched from the L(X+1) cache at block  316 . At block  318 , the force replacement castout (FRC) bit, such as FRC bit  258 , is set to a “0” state in a tag line, such as associated with cache line  217 , of the L1 cache  203  in order for the L1 cache  203  to preclude sending this instruction/data to the L2 cache  208 . The process  300  then proceeds to decision block  320 . 
         [0029]    Returning to decision block  310 , if the instruction/data cannot be located in the L(X+1) cache, a miss indication is generated. At block  312 , the requested instruction/data is fetched from a level of the memory hierarchy that is greater than or equal to the L(X+2) level, such as, an L3 cache or the system memory  210  of the processor and memory complex  200 . The process  300  then proceeds to decision block  313 . 
         [0030]    At decision block  313 , a determination is made whether the address of the instruction/data is a write-through address in access to the L(X) cache. If the address is a write-through address, the process  300  proceeds to block  318  which sets the force replacement castout (FRC) bit, such as FRC bit  258 , to a “0” state in a tag line. The determination whether the address is a write-through address is made in response to a write-through bit accessed at the address from a memory management unit, such as MMU  207 . If the address is not a write-through address, the process  300  proceeds to block  314 . At block  314 , the FRC bit, for example, the FRC bit  256  is set to a “1” state, and is stored with the tag associated with the selected line, such as cache line  216 . 
         [0031]    At decision block  320 , it is determined whether a line should be replaced in the L(X) cache, such as the L1 cache  203 . If it is determined that a line should be replaced in the L(X) cache, it is further determined at decision block  322  whether the selected line, a victim line, is dirty, such as indicated by dirty bit  259  in a “1” state. If the selected victim line is dirty, the victim line is allocated at block  324  in the L(X+1) cache, such as the L2 cache  208 . If the selected victim line is not dirty, such as indicated by dirty bits  260  and  261 , the FRC bit is checked to determined whether it is set active in decision block  326 . If at decision block  326  it is determined that the FRC bit is active, such as is the case for FRC bit  256 , the victim line is allocated at block  324  in the L(X+1) cache, such as the L2 cache  208 . 
         [0032]    If it is determined at decision block  320  that a line should not be replaced or if at decision block  326  it is determined that the FRC bit is inactive, such as in a “0” state, as is the case for FRC bit  258 , the requested instruction/data is allocated at block  328  in the L(X) cache, such as the L1 cache  203 . The requested instruction/data is also returned at block  330  to the requesting processor, such as processor  202 . In such manner, a redundant castout to the L(X+1) cache is avoided, thereby saving power and improving cache access bandwidth in the memory hierarchy. 
         [0033]    The various illustrative logical blocks, modules, circuits, elements, and/or components described in connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic components, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general-purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing components, for example, a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration appropriate for a desired application. 
         [0034]    The methods described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. A storage medium may be coupled to the processor such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. 
         [0035]    While the invention is disclosed in the context of illustrative embodiments for instruction caches, data caches, and other types of caches, it will be recognized that a wide variety of implementations may be employed by persons of ordinary skill in the art consistent with the above discussion and the claims which follow below.