Abstract:
A technique for scheduling cache cleaning operations maintains a clean distance between a set of least-recently-used (LRU) clean lines and the LRU dirty (modified) line for each congruence class in the cache. The technique is generally employed at a victim cache at the highest-order level of the cache memory hierarchy, so that write-backs to system memory are scheduled to avoid having to generate a write-back in response to a cache miss in the next lower-order level of the cache memory hierarchy. The clean distance can be determined by counting all of the LRU clean lines in each congruence class that have a reference count that is less than or equal to the reference count of the LRU dirty line.

Description:
[0001]    The present Application is a Continuation of U.S. patent application Ser. No. 13/920,756, filed on Jun. 18, 2013 and claims priority thereto under 35 U.S.C. 120. The disclosure of the above-referenced parent U.S. Patent Application is incorporated herein by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention is related to processing systems and processors, and more specifically to techniques for scheduling cache cleaning operations based on the distance between the least-recently-used (LRU) line and the first dirty line. 
         [0004]    2. Description of Related Art 
         [0005]    Cache performance can be improved when periodic flushing of dirty cache lines (i.e., “cache cleaning”) is performed. U.S. Patent Application Publication 2011/0276762 discloses a cache cleaner that schedules write bursts by collecting entries in a write queue. The entries are collected by determining if the number of dirty lines present in a congruence class exceeds a threshold and then scheduling write-back of one or more dirty lines if the threshold is exceeded. 
         [0006]    While such a scheme will tend to minimize the number of dirty lines present in the cache, depending on actual accesses to lines within each congruence class, and depending on the number of new lines loaded in each congruence class, the cache-cleaning algorithm may still lead to excessive cast-out write-back penalties (waiting on space to be made in a congruence class for one or more new lines that are loaded). 
         [0007]    Therefore, it would be desirable to provide a cache controller methodology that can more effectively control cache cleaning operations to provide improved cache performance and reduce the number of write operations issued to system memory. 
       BRIEF SUMMARY OF THE INVENTION 
       [0008]    The invention is embodied in a method of operation of a memory subsystem and cache memory that schedules cache cleaning operations according to a clean line distance. 
         [0009]    In the method, the cache control logic determines an indication of a number of line allocations that can be supported by the current state of each congruence class without causing a write-back of a dirty line. The control logic compares the indication to a specified clean distance value to determine when to schedule write-backs of dirty lines of the cache memory circuit, and then if write-backs should be scheduled, the control logic schedules the write-backs of one or more of the dirty lines. The clean distance can be determined by counting all of the LRU clean lines in each congruence class that have a reference count that is less than or equal to the reference count of the LRU dirty line. 
         [0010]    The foregoing and other objectives, features, and advantages of the invention will be apparent from the following, more particular, description of the preferred embodiment of the invention, as illustrated in the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
         [0011]    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 objectives, and advantages thereof, will best be understood by reference to the following detailed description of the invention when read in conjunction with the accompanying Figures, wherein like reference numerals indicate like components, and: 
           [0012]      FIG. 1  is a block diagram illustrating a processing system in which techniques according to an embodiment of the present invention are practiced. 
           [0013]      FIG. 2  is a block diagram illustrating details of a memory hierarchy in accordance with an embodiment of the present invention. 
           [0014]      FIG. 3  is a block diagram of a cache memory in accordance with an embodiment of the present invention. 
           [0015]      FIG. 4  is a flow chart depicting a method of scheduling cache write-back operations in accordance with an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0016]    The present invention relates to cache memory and memory subsystem including a cache memory, in which background write-back operations are scheduled according to a “clean distance” value that specifies a minimum number of prospective cache victims (cast-out candidates) that are non-dirty (have not been modified). The cache attempts to maintain the clean distance by keeping track of the reference count of the first dirty line and counting the number of clean lines having lower reference counts, and thus will be victimized according to a least-recently used (LRU) replacement algorithm before the dirty line. Since dirty lines must be read (for the write-back operation) and then written over, the performance penalty to victimize a dirty line is higher than that for a clean line, and thus the present invention improves cache performance If the clean distance is violated for a particular congruence class, background write operations are scheduled for that congruence class to restore the clean distance. 
         [0017]    Referring now to  FIG. 1 , a processing system in accordance with an embodiment of the present invention is shown. The depicted processing system includes a number of processors  10 A- 10 D, each coupled to a memory controller/bridge  15 A,  15 B in conformity with an embodiment of the present invention. The depicted multi-processing system is illustrative, and processing systems in accordance with other embodiments of the present invention include uni-processor systems having symmetric multi-threading (SMT) cores. Processors  10 A- 10 D are identical in structure and include cores  20 A- 20 B and a cache/local storage  12 , which may be a cache level, or a level of internal system memory. Processors  10 A- 10 B are coupled to a main system memory  14  by memory controller/bridge  15 A, a storage subsystem  16 , which includes non-removable drives and optical drives, for reading media such as a CD-ROM  17  forming a computer program product and containing program instructions implementing operating systems and other software for execution by processors  10 A- 10 D, The illustrated processing system also includes input/output (I/O) interfaces and devices  18  such as mice and keyboards for receiving user input and graphical displays for displaying information. Processors  10 C- 10 D are similarly coupled to main system memory  14 B, storage subsystem  16 , which includes non-removable drives and optical drives, for reading media such as CD-ROM  17 , by memory controller/bridge  15 B. While the system of  FIG. 1  is used to provide an illustration of a system in which the processor architecture of the present invention is implemented, it is understood that the depicted architecture is not limiting and is intended to provide an example of a suitable computer system in which the techniques of the present invention are applied. 
         [0018]    Referring now to  FIG. 2 , a memory hierarchy in accordance with an embodiment of the invention is shown. A lower-order cache  12  is coupled to an even lower-order cache (or a processor core in the case of an L1 cache). Lower-order cache  12  is also coupled to a higher-order cache  16  to which victims (cast-out members) from lower-order cache  12  are written when removed from lower-order cache  12 . Higher-order cache  16  includes a control logic  18  that manages accesses to data values stored in a value storage  22  of higher-order cache  16 . The locations of the data values are tracked in a directory  20  of higher-order cache  16 , which also contains status flags for the various values, which are generally cache lines and reference counts indicating the number of times the data values have been accessed since being loaded into value storage  22 . Higher-order cache  16  is coupled to a memory controller, such as a memory controller and bridge  15  that can be used to implement memory controller and bridge units  15 A,  15 B in the system of  FIG. 1 . Memory controller and bridge  15  manages accesses to system memory  14  which provides values to and receives values from the lower-order levels of the memory hierarchy as needed. 
         [0019]    In general, the exemplary embodiment shown in  FIG. 2  is an inclusive hierarchy, with higher-order cache  16  being an inclusive or pseudo-inclusive cache that also serves as a victim cache for lower-order cache  12 . However, techniques of the present invention apply to other types of caches and cache hierarchies and the illustrated cache hierarchy is only one example of a cache memory subsystem to which the techniques disclosed herein may apply. Further, any of the caches shown in  FIG. 2  may be included in an integrated circuit that contains one or more processor cores to which lower-order cache  12  is coupled, or may be external to the processor core integrated circuit. System memory  14 , at least the portion that maps to lines in the remainder of the cache hierarchy, may also be included within an integrated circuit that includes the processor cores, for example in embedded systems, so that the entire mechanism illustrated herein might be implemented within a single integrated circuit, or across multiple integrated circuits. In other terms, the boundary between the processor core can be at the cache level, or the system memory level, and memory controller and bridge  15  that handles the write-backs to system memory  14  from higher-order cache may be located in a processor integrated circuit, or a separate integrated circuit. 
         [0020]    Referring now to  FIG. 3 , details of higher-order cache  16  are shown, in accordance with an embodiment of the invention. Value storage  22  contains values that are separated into congruence classes, corresponding to the columns of value storage  22 , which are selected according to the least significant bits of the address of the values stored in value storage  22 . Directory  20  contains entries describing entries in value storage  22 , and include a tag field, which is formed from the most-significant bits of the value address, a reference count ref, and flag bits including a modified bit M that indicates whether the particular line is dirty. In the example, only a portion of director  20  is shown that corresponds to a small portion of the actual entries that would be present in a single congruence class of higher-order cache  16 . In the example, the dirty lines are those having the modified bit M set equal to a logical “1” state, and the dirty line with the lowest reference count, which is taken as the LRU member, has a reference count of 4. The clean lines, which are those having modified bit M set to zero, can be observed to determine which lines will be victimized before any dirty line, which in the example are the lines with reference counts of 1, 2 and 4. The method of the present invention, as described below, will total those lines, in the example totaling 4, and will compare that total to a clean distance, e.g., five, which, in the example, will cause an indication that at least one of the lines should be written-back to system memory  14 , in order to preserve the clean distance in higher-order cache  16 . 
         [0021]    Referring now to  FIG. 4 , a method according to an embodiment of the present invention is depicted a flow chart. When the cache directory is accessed, which occurs when a data value access request is received (step  40 ), a check is performed, for the congruence class (step  41 ), to determine whether the clean distance is currently maintained. The exemplary check determines the reference count of the least-recently-used (LRU) dirty member of the class (step  42 ). The total number of clean members having a reference count less than or equal to the reference count of the LRU dirty member is computed for the congruence class (step  43 ) and that total is subtracted from the specified clean distance to determine a cleanup count (step  44 ), if any, that is required to restore the clean distance. The method then sets a work vector to include a cleanup count number of entries, which may be a mechanism that specifies just a number of LRU entries to clean, specifies indices for the specific entries to clean, or provides some other form of vector that can specify a number of entries to clean for each congruence class (step  45 ). Until the last congruence class has been processed (decision  46 ), steps  41 - 45  are repeated for each congruence class. U.S. Patent Application No. US20110276762 “COORDINATED WRITE-BACK OF DIRTY CACHELINES” discloses a write-back scheduling technique that can be used in conjunction with the present invention, and is incorporated herein by reference. 
         [0022]    While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form, and details may be made therein without departing from the spirit and scope of the invention.