Patent Publication Number: US-6336167-B1

Title: Cache storage management using dual stacks

Description:
FIELD OF THE INVENTION 
     The present invention relates to data processing and more particularly to management of a data storage cache where cache control employs dual stacks. 
     BACKGROUND OF THE INVENTION 
     Memory systems in computers generally have two layers: a slow, inexpensive layer for mass storage (main memory) and a fast, more expensive layer (cache) for current use. Main memory is typically implemented in the form of disk storage while cache memory is typically implemented in semiconductor technology. 
     Cache management is an important aspect of every computer system. The goal is always to cache or store in the fast, more expensive layer of memory those items which will be frequently used in the future but only those items. Choosing which items to store in cache memory is done on the basis of item use history. A primary characteristic of cache performance is hit ratio, the frequency with which memory requests are satisfied using items already stored in the cache. It is well-known that some stored data is accessed more frequently than other stored data. If frequently used main memory, typically disk sectors, can be quickly and accurately identified, the data in such sectors can be moved to cache storage to improve the hit ratio and accelerate data retrieval, thereby boosting overall system performance. 
     While much of the following discussion is in the context of movement of stored data from main memory to cache memory in computer memory systems, it should be understood that caching techniques can also be useful where tables of calculated values must be constructed and maintained to support other computer processes. An example is a routing table used for making routing decisions in TCP/IP networks. By using caching techniques to build a small routing table containing only frequently used information, it may be possible to boost the overall performance of a router system. 
     Depending upon the application, cache control can be implemented using either of at least two techniques. According to the first technique, each location in a cache memory is used to store both a data unit to be made available to a computer system and a small, unambiguous label that functions as a pointer to that data unit. According to the second technique, only the labels are stored in the cache control element with the labels serving as pointers or addresses to data units stored in a separate cache memory unit. The first technique may be favored for applications in which the size of the data units is limited since the first technique avoids the need to address a separate cache memory. The second technique may be favored where large data units need to be accommodated. While the following description may refer only to the existence of labels or entries in cache stacks, it should be understood that the description is intended to cover cache systems implemented using either of the two techniques described. 
     Presently cache maintenance problems are commonly solved with a cache replacement algorithm known as Least Recently Used (LRU). In a computer memory system using LRU for cache management, the cache is refreshed each time a memory request is generated. Initially, all entries in the cache have a default value assumed here to be zero. When a new request can be satisfied using an entry already stored in the cache, the entry is retrieved from the cache without going to main memory. The entry is moved to the top of the cache stack and other entries in the stack are pushed down one position in the stack without changing their relative order. 
     When a request cannot be satisfied with cached entries, the entry is retrieved from main memory, sent to the requesting system and also written into the position at the top of the stack. Existing stack entries are pushed down one position with the stack entry previously at the bottom of the stack being discarded. 
     Discussions of LRU, related cache algorithms and their performance can be found at page 378 of  Computer Architecture: a Quantitative Approach , 2 nd  edition, by J. Hennessy and D. Patterson, published in San Francisco by Morgan Kaufinan in 1990, and in R. Bachrach and Ran El-Yaniv,  Online list accessing algorithms and their applications: recent empirical evidence , Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms, (1997) Vol. 8, pages 53-62. 
     SUMMARY OF THE INVENTION 
     The present invention is an improvement over known LRU algorithms which is believed to provide a higher hit ratio and thus an improvement in overall system performance under typical operating conditions. 
     The invention makes use of a cache storage control having two stacks. The first stack, which may be referred to as a preliminary stack, and the second stack, which may be referred to as the real stack, are preferably but not necessarily the same size; that is, have the same number of storage locations. When a new label request is received, both stacks are checked to determine whether a label already exists in the stacks. If the requested label is found in either stack, it is retrieved from the stack in which it is found and processed to recover the associated data unit. A conventional LRU algorithm of the type discussed above is used to refresh both the first and the second stacks. If the requested label is not found in either stack, the second stack is tested to determine if the bottom stack position is empty. If the bottom position is empty, the requested label (retrieved from a primary data source in a separate operation) is written to the top position of the second stack and all prior stack entries are pushed down one stack location. If the bottom position of the stack is not empty, all existing stack entries at and below a predetermined insertion point are shifted down one position with the label previously at the bottom the stack being discarded. The requested label is then written into the predetermined insertion point in the second stack. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     While the specification concludes with claims particularly pointing out and distinctly claiming that which is regarded as the present invention, details of a preferred embodiment of the invention may be more really ascertained from the following technical description when read in conjunction with the accompanying drawings wherein: 
     FIG. 1 is a greatly simplified block diagram of a computer system showing the key elements required for implementation of the present invention; 
     FIG. 2 is a high level flow chart of cache management operations which may be performed using the specific techniques of the present invention; and 
     FIG. 3 is a more detailed flow chart of cache management operations performed in accordance with the present invention. 
    
    
     TECHNICAL DESCRIPTION 
     Referring to FIG. 1, an essential component in any caching system includes a central processing unit  10 , which is both the source of any requests for stored data and the user of any data retrieved in response to such requests. All data generated or needed for operations by the central processing unit  10  originates with a primary data source  12 . The most common type of primary data source would be a computer main memory which, as previously noted, is typically implemented using disk storage device technology. Any other memory technology capable of providing the necessary storage capacity at a commercially reasonable cost can be used for main memory. For environments in which caching is to be used for calculated values, the primary data source may be data processing logic (implemented either as hardwired logic or as processor controlling routines) which is invoked to calculate the data to be cached, with data typically being calculated on demand. Another essential component in any cache management system is obviously the smaller, faster, more expensive cache memory  14  itself. In a cache memory in accordance with the present invention, at least two access control stacks  16  and  18  are implemented within cache memory  14 . As noted above, locations within the stacks can used to store both data units and associated labels or, alternatively, to store only labels with the associated data units actually being stored in a separate cache memory element addressable using the labels. 
     Obviously, any working computer system also includes many components not shown in the drawing; e.g., input/output devices such as keyboards, pointing devices, monitors, printers, etc. Similarly, the disk storage may either take the form of disk drives using fixed and/or removable recording media. These components, which may be conventional in nature and which are not essential to an understanding of the invention, have been omitted from the drawing for the sake of simplicity. 
     FIG. 2 is a flow chart of the general process for using a cache. The CPU sends an initial label request to the cache in a step  20 . If the request can be satisfied with a label already stored in the cache, as indicated by a test  22 , the data unit associated with the cached label is retrieved from its storage location in step  24  and sent to the CPU. The labels in the cache are then rearranged using a cache management algorithm such as the Least Recently Used (LRU) algorithm discussed previously. 
     If test  22  indicates that a requested label does not exist in the cache, the label is employed in a separate process step  20  to retrieve the associated data unit from the primary data source. The data unit is forwarded to the central processing unit. The label for the retrieved data unit is then written into the cache in step  30  using a suitable algorithm, such as the LRU algorithm, in anticipation that the associated data unit item may again be requested. Typically, labels are arrayed in a single stack of memory locations. 
     The present invention, as already noted, makes use of a dual stack cache control structure. FIG. 3 is a flow chart of the process for using such a structure. Each time a label request is received in a step  32 , a test  34  is conducted to determine whether the label is already stored in either stack S 1  or stack S 2 . If the label is found, it is used to retrieve the associated data, which is then forwarded to the central processing unit. 
     If the label exists in either of the stacks, the LRU algorithm is used in a step  38  to write or relocate the label entry in the stack S 2 . Step  38  is followed by a similar step  50  which uses the same LRU algorithm to store the same label entry in stack S 1 . Once these steps are completed, the cache management routine waits for the next label request. 
     If the test  34  does not find the label in either of the dual stacks, the label is used in accessing the primary data source to recover the needed data. A slightly more complicated series of steps is performed to control the storage of the label in the stack S 2 . A test  40  is initially conducted to determine whether the last or bottom position in stack S 2  is empty. If the bottom position is empty, the retrieved label is moved to the top of the second stack in an operation  42  and all existing labels in the stack are shifted down by one position without altering their relative order. 
     If the bottom position in stack S 2  is occupied, which it typically is after a period of system operation, all stack entries at and below a predetermined insertion point in stack S 2  are pushed down by one position in operation  46  with the label at the bottom of the stack being discarded. The insertion point and various ways in which it can be determined are described below. The new label is then written into the insertion point in S 2  in operation  48 . 
     Three different processes have been described for refreshing stack S 2 , depending on whether the requested label exists anywhere in the cache and whether the bottom position in stack S 2  is initially empty. Regardless which of those processes is followed, stack S 1  is always refreshed the same way; that is, by using an LRU algorithm in step  50 . 
     As noted above, step  48  calls for a label to be inserted at an insertion point in stack S 2 , which is a stack location preferably between the top and bottom positions in the stack. The insertion point may be static or dynamic. A static insertion point may be selected by empirical observation of the behavior of the system when different possible insertion points have been tried. Obviously, an insertion point selected in this manner should be one which optimizes the hit ratio for the cache. 
     Alternatively, the insertion point may be initially assigned in the same manner as a static insertion point and then adjusted up or down as a function of changes in the observed hit ratio for the system. An increasing hit ratio indicates that more label requests are being satisfied using labels already in the cache. To reduce the chances that frequently accessed labels will be “bumped” out of the cache by newly added data, the insertion point may be moved downward in stack S 2 . Conversely, if the hit ratio has been declining, meaning the cache is losing its effectiveness in satisfying label requests, the insertion point may be moved upward in the stack in the hope that the newly inserted label will be more frequently accessed than at least some of the other labels already in the stack. 
     Examples of operations of the present invention are included in the following Examples. In all four Examples, stacks S 1  and S 2  initially contain the same label values arranged in the same order in the four memory locations in each stack. The labels finally contained in the memory locations of each stack vary as a function of whether a requested label is found in one or both of the stacks. 
     
       
         
           
               
             
               
                 EXAMPLE 1 
               
             
            
               
                   
               
               
                 Assume the memory request is for data having a memory label D 
               
            
           
           
               
               
               
               
            
               
                 Stack 1 - initial 
                 Stack 1 - final 
                 Stack 2 - initial 
                 Stack 2 - final 
               
               
                   
               
               
                 E 
                 D 
                 B 
                 B 
               
               
                 B 
                 E 
                 G 
                 G 
               
               
                 C 
                 B 
                 F 
                 D 
               
               
                 G 
                 C 
                 A 
                 F 
               
               
                   
               
            
           
         
       
     
     Because the requested label D does not initially exist in either stack S 1  or S 2 , it is shown as being written into S 2  at an insertion point in the third position in the stack. Using the conventional LRU algorithm, the label D is written into the top position in stack S 1 . 
     
       
         
           
               
             
               
                 EXAMPLE 2 
               
             
            
               
                   
               
               
                 Assume the memory request is for data having a memory label C 
               
            
           
           
               
               
               
               
            
               
                 Stack 1 - initial 
                 Stack 1 - final 
                 Stack 2 - initial 
                 Stack 2 - final 
               
               
                   
               
               
                 E 
                 C 
                 B 
                 C 
               
               
                 B 
                 E 
                 G 
                 B 
               
               
                 C 
                 B 
                 F 
                 G 
               
               
                 G 
                 G 
                 A 
                 F 
               
               
                   
               
            
           
         
       
     
     Because the requested label C exists initially in stack S 1 , it is written into the top position of stack S 2  using the present invention and also into the top position of stack S 1  by applying the conventional LRU algorithm. Label A is discarded from stack S 2 . No labels need to be discarded from stack S 1 . 
     
       
         
           
               
             
               
                 EXAMPLE 3 
               
             
            
               
                   
               
               
                 Assume the memory request is for data having a memory label A 
               
            
           
           
               
               
               
               
            
               
                 Stack 1 - initial 
                 Stack 1 - final 
                 Stack 2 - initial 
                 Stack 2 - final 
               
               
                   
               
               
                 E 
                 A 
                 B 
                 A 
               
               
                 B 
                 E 
                 G 
                 B 
               
               
                 C 
                 B 
                 F 
                 G 
               
               
                 G 
                 C 
                 A 
                 F 
               
               
                   
               
            
           
         
       
     
     Since the requested label initially exists in stack S 2 , the same operations that were performed in Example 2 are performed in this Example. 
     
       
         
           
               
             
               
                 EXAMPLE 4 
               
             
            
               
                   
               
               
                 Assume the memory request is for data having a memory label G 
               
            
           
           
               
               
               
               
            
               
                 Stack 1 - initial 
                 Stack 1 - final 
                 Stack 2 - initial 
                 Stack 2 - final 
               
               
                   
               
               
                 E 
                 G 
                 B 
                 G 
               
               
                 B 
                 E 
                 G 
                 B 
               
               
                 C 
                 B 
                 F 
                 F 
               
               
                 G 
                 C 
                 A 
                 A 
               
               
                   
               
            
           
         
       
     
     Note that the requested label initially existed in both stacks S 1  and S 2 . The same operations described for Example 2 apply to this Example. 
     While there has been described what is considered to be a preferred embodiment of the present invention, variations and modifications in the preferred embodiment may occur to those skilled in the relevant art. It is therefore intended that the following claims shall be construed to include both the preferred embodiment and all such variations and modifications as fall within the true spirit and scope of the invention.