Hit-density-based replacement for data cache with prefetching

A least recently used cache replacement system in which the data cache is logically partitioned into two separate sections, demand and prefetch. A cache directory table and a least recently used table are used to maintain the cache. When a new demand data page is added to the cache, a most recently used (MRU) pointer is updated and points to this new page. When a prefetch page is added to the cache, the least recently used pointer of the demand section is updated with its backward pointer pointing to this new page. A cache hit on a demand of prefetch page moves that page to the top of the least recently used table. When a free page is needed in the cache, it is selected from the demand or prefetch sections of the memory based on a comparison of the demand hit density and the prefetch hit density so to maintain a balance between these two hit densities.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The present invention generally relates to an improved method for managing 
the operation of a cache memory in which both demand and prefetched data 
can be stored, and more particularly to an improved method for allocating 
space in the memory between demand and prefetched data on the basis of 
frequency of use. 
2. Description of the Prior Art 
In many data processing systems, a high-speed memory commonly called a 
"cache" is provided between the working memory of the central processing 
unit and a main memory. The cache enables a relatively fast access to a 
subset of data which has been previously transferred from main memory to 
the cache and thus improves the overall speed of the data processing 
system. Commonly, data transfers from main memory to cache are in pages or 
blocks of data and include both demand data pages and prefetched data 
pages. Demand data is data transferred to the cache as a result of a 
specific request from the central processing unit. When transferring 
demand data to the cache, it is advantageous to also transfer additional 
unrequested data (i.e. prefetched data) at the same time if it is likely 
the additional data will be soon requested. 
When a cache is filled, data must be removed from the cache when new data 
is written in. Commonly, data cache management systems use the frequency 
of use of data in the cache as a criteria for selecting data to be removed 
from the cache. Least recently used (LRU) is a common criteria for 
replacement because of its simplicity and efficiency. 
In the prior art, in replacing data in the cache, demand and prefetched 
data has been treated equally, without regard to the size of the incoming 
data of each type. Under this condition too large a portion (in terms of 
finding demanded data in cache) of the total cache storage capacity may be 
allocated to store prefetched data, especially when large amounts of data 
are prefetched in connection with each main memory demand data access. 
U.S. Pat. No. 4,489,378, entitled Automatic Adjustment of the Quantity of 
Prefetch Data in a Disk Cache Operation, describes a dynamic mechanism to 
determine the number of prefetched data blocks in each disk cache 
operation. U.S. Pat. No. 4,807,110, entitled Prefetching System for a 
Cache Having a Second Directory for Sequentially Accessed Blocks, 
describes a way to select the data blocks for prefetching using two-level 
cache directories. Both these patents consider prefetching in the cache 
operation but use a conventional Least Recently Used (LRU) scheme for 
replacement. 
SUMMARY OF THE INVENTION 
An object of this invention is the provision of a cache management data 
system that automatically adjusts the size of the storage areas of cache 
allocated for demand and prefetched data to balance the allocated areas on 
the basis of area-performance (i.e. cache hit density) during operation; a 
system which operates independently of the prefetch algorithm used. A 
system which is simple and straightforward in its design. 
Briefly, this invention contemplates the provision of a least recently used 
cache replacement system in which the data cache memory is logically 
partitioned into two separate sections, demand and prefetch. A cache 
directory table and a least recently used table are used to maintain the 
cache. When a new demand data page is added to the cache, a most recently 
used (MRU) pointer is updated and points to this new page. When a prefetch 
page is added to the cache, the least recently used pointer of demand 
section is updated with its backward pointer pointing to this new page. A 
cache hit on a page in the demand or prefetch section moves that page to 
the top of the least recently used table. When a free page is needed in 
the cache, it is selected from the demand or prefetch sections of the 
memory based on a comparison of the demand hit density and the prefetch 
hit density so as to maintain a balance between these two hit densities. 
The demand hit density is the ratio of the demand hit probability to the 
number of entries in the demand section of the least recently used table. 
Similarly, the prefetch hit density is the ratio of the prefetch 
probability to the number of entries in the prefetch section of the least 
recently used table.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION 
Referring now to FIG. 1, the cache directory table contains entries common 
to directory tables in prior art cache management systems. It contains a 
single bit entry 10 indicating whether a cell in cache is free or used, a 
home indicator 12 and a file block address 14. A forward pointer 16 and a 
backward pointer 18 provide addresses to next list entries. A cache 
address 20 is provided as well as information, as indicated at 22. A first 
free page pointer 26 provides the cache address of the free page or cell 
in cache next to be written to and a free page counter 24 keep a running 
total of the free pages in cache. 
FIG. 2 shows the organization of the Least Recently Used table. Forward 
pointers 16 and backward pointers 18 along with directory table pointers 
28 are maintained in a push down stack, logically separated into a demand 
section 30 and a prefetch section 32. In the table, the pointers 16, 18 
and 28 for the most recently used page in cache are entered at the top of 
the table and indicated by a most recently used pointer 34. Pointers for 
demand pages newly transfer from main store are entered at the top of the 
table as most recently used. Pointers for new prefetch pages are entered 
at the top of the prefetch section of the table. A least recently used 
pointer 36 points to the last entry in the demand section of the table and 
another least recently used pointer 38 points to the last entry in the 
prefetch section of the table. It will be appreciated that in accordance 
with the teachings of this invention, the size of the demand section 30 
and size of the prefetch section 32 can change depending on the hit 
density of the demand section relative to the hit density of the prefetch 
section. 
In order to compute hit densities for both demand and prefetch sections of 
the cache, a cache history window is defined to limit the size of the 
historical data in the computation process; for example 32 input/output 
requests. The following Chart 1 defines the cache parameters used herein 
and Chart 2 defines the terms of the hit density computation. 
______________________________________ 
Chart 1: Caching Parameter Definition 
______________________________________ 
.smallcircle. 
Cache History Windows: 
The whole caching 
CHW(i) history is partitioned 
into CHW with each 
window contains the 
same number (say 32) 
of file I/O requests. 
.smallcircle. 
In each CHW(i), N.sub.d (i) = total number of 
demand pages 
N.sub.p (i) = total number of 
prefetch pages 
N.sub.dh (i) = total number of 
demand hits 
N.sub.ph (i) = total number of 
prefetch hits 
.smallcircle. 
History Working Set: 
The most recent set 
(e.g. 4 or 5) of 
windows selected for 
caching history 
computation. 
.smallcircle. 
N.sub.d = number of demand pages in the current file 
I/O. 
.smallcircle. 
N.sub.p = number of prefetch pages in the current I/O. 
.smallcircle. 
L.sub.d = number of entries in the Demand Section of 
Least Recently Used (LRU) table. 
.smallcircle. 
L.sub.p = number of entries in the Prefetch Section of 
LRU table. 
.smallcircle. 
N.sub.dt,N.sub.pt, N.sub.dht, N.sub.pht = accumulated parameter 
count. 
.smallcircle. 
CWC = complete window count 
.smallcircle. 
I count = file I/O count in the current windows. 
______________________________________ 
______________________________________ 
Chart 2: Caching Hit Density Computation 
______________________________________ 
Consider History Working Set = 
{CHW(i), CHW(i + 1), CHW(i + 2), 
CHW(i + 3), CHW(i + 4)} 
##STR1## 
##STR2## 
##STR3## 
##STR4## 
______________________________________ 
Referring now to FIG. 3, the overall cache management operation starts with 
an examination at block 40 of each input/output request to see if it 
includes a cache bypass instruction. If the cache is not bypasses, a 
determination at decision block 42 is made as to the type of cache 
request; read or write. Here it should be noted that all write to cache 
requests are treated as demand read requests. If the I/O request is a read 
from cache, at block 44 a determination is made whether or not it is a 
prefetch read. If it is not, or if the I/O is a write command (block 42), 
the number of prefetch pages (n.sub.p) in this I/O file is zero (0) and 
the operation advances to cache management block 48 in the case of a write 
request and to a fetch operation, block 50, in the case of a demand read. 
For a prefetch read, a prefetch algorithm determines the number of 
prefetch pages in the read request, block 52, and the pages are fetched at 
block 50. The remaining operations are: cache management, block 48, which 
will be explained in connection with FIGS. 4 and 5; a computation of hit 
density, block 56, which will be explained in connection with FIG. 6; and 
an updated window count, block 58, which will be explained in connection 
with FIG. 7. 
Referring now to FIG. 4, in the management of the cache, for each page 
fetched (block 50, FIG. 3), a search is made in the cache directory table 
(FIG. 1) to determine if the page is in cache, block 60. If the page is 
not in cache, the page is added, as will be explained in more detail in 
connection with FIG. 5. If the request page is in cache, block 62, a 
determination is made at block 64 whether or not it is the I/O page 
demanded. If a page is fetched other than the demanded page there is an 
exit from the remaining steps of the operation shown in this FIG. 4. For 
the demanded page in cache, a determination at block 66 whether the 
demanded page is in the demand section 30 or prefetch section 32. The 
total number of demand hits for the window set (N.sub.dh i) or total 
number of prefetch hits for the window set (N.sub.ph i) is updated 
accordingly (blocks 65 and 67 respectively) and the most recently use 
pointer is updated to point to the demanded page, block 68. 
Referring now to FIG. 5, in adding a new page to the cache, an initial 
check is made at block 69 to determine if there is a free page or cell in 
the cache to accept the page to be added. If there is a free page 
available, a determination is made at block 70 as to the type of page to 
be added, demand or prefetch. If demand, the page is inserted at the top 
of the demand section of the cache, block 72, the demand section most 
recently used pointer is updated to point to this page, and the demand 
section entry count is updated, block 74. Similarly, if a prefetch page is 
added, it is placed at the top of the prefetch section of the cache at 
block 76 and the prefetch section entry count is updated. 
If the determination at block 68 is that there is no free page available in 
the cache, a page is first deleted from either the demand or prefetch 
section of the cache. At block 78 a determination is made whether the 
demand hit density (DHD) is greater than or equal to the prefetch hit 
density (PHD) (DHD.gtoreq.PHD); RD is assigned a value equal to 1 if DHD 
is less than PHD DHD&lt;PHD. If the demand hit density is greater than or 
equal to the prefetch hit density, the least recently used page in the 
prefetch section of the cache is deleted, block 80, and the number of 
entries in the prefetch section counter is decremented by 1. Similarly, if 
the demand hit density is less than the prefetch hit density, the least 
recently used page in the demand section of the chase is deleted, block 
82, and the number of entries in the demand section entry counter is 
decremented by 1. 
Referring now to FIG. 6, in computing the demand and prefetch hit 
densities, this example assumes a working history set of the five (5) most 
recent windows; i.e., N.sub.d (5) and N.sub.p (5). The operation starts, 
block 81 by updating the total number of demand N.sub.d (5) and prefetch 
N.sub.p (5) pages for the working history set by the number of pages 
N.sub.d of N.sub.p of the present I/O request. If the number of pages in 
the demand section L.sub.d is zero (0) RD is set to zero, block 84. 
Similarly, if the number of pages in the prefetch section is zero (0) RD 
is set for one (1), block 86. If there are demand and prefetch pages in 
the cache, the demand hit rate and the prefetch hit rate is calculated at 
block 86. 
The demand hit density (DHD) is the ratio of the demand hit probability to 
the number of entries in the demand section of the cache. The demand hit 
probability is the ratio of the total number of demand hits for the 
working set history to the number of demand page requests for the history: 
##EQU1## 
The prefetch hit density (PHD) is the ratio of the prefetch hit probability 
to the number of entries in the prefetch section of the cache. The 
prefetch hit probability is the ratio of the total number of prefetch hits 
for the working set history to the number of prefetch page requests for 
the history: 
##EQU2## 
At block 90 a comparison is made between the demand hit density DHD and the 
prefetch hit density PHD; if DHD is greater than or equal to PHD, RD is 
assigned a value of zero (0). If DHD is less than PHD, RD is assigned a 
value of one (1). 
Referring now to FIG. 7, it shows the window update operation. This example 
assumes 32 I/O requests per window and five (5) windows in the rolling 
history set. 
The operation starts in response to an input request "I" at block 92 by 
incrementing the request count "I" by one (1) in response to each request. 
The count is tested against the number of requests per window (e.g. 32 in 
this example) at block 94. A count of thirty-two indicates a complete 
window, and when this count is reached the complete window count 
increments by one (1), block 96. The complete window count is tested 
against the assigned working set history number, here five (5) at block 
100. The remaining logic acts to keep the hit density data parameters 
current for a rolling history comprised of a set of windows by deleting 
the data for the oldest complete window in the set (here five) and adding 
the last window data each time a window is complete. A count of demands 
pages (N.sub.d), prefetch pages (N.sub.p), demands hits (N.sub.dh) and 
prefetch hits (N.sub.ph) for each window are determined, block 101. When a 
window is complete (i.e., CCW=5, blook 100) the oldest case history window 
in the set is in effect deleted at block 106, by incrementing the value K 
to K+1. The complete window count is decremented by one, block 105. The 
accumulated parameter counts for demand and prefetch page requests and 
demand and prefetch hits are determined for this updated set of windows in 
block 102. In block 104 the hit density data parameters of the complete 
window count (block 101) are reset to ZERO. 
Thus it will be appreciated that the objects of the invention has been 
accomplished. The invention provides a cache management data system that 
automatically adjusts the size of the storage areas of cache allocated for 
demand and prefetched data to balance the allocated areas on the basis of 
area-performance (i.e. cache hit density) during operation; a system which 
operates independently of the prefetch algorithm used. A system which is 
simple and straightforward in its design. 
While the invention has been described in terms of a single preferred 
embodiment, those skilled in the art will recognize that the invention can 
be practiced with modification within the spirit and scope of the appended 
claims.