Sequential prefetching with deconfirmation
First Claim
1. A computer performed method for prefetching sequential lines from main memory into a processor cache memory of a computer, said cache memory including an S-vector comprising an S-bit associated with lines in main memory, said S-b being indicative of whether a succeeding line is likely to be accessed when a line in memory corresponding to said S-bit is accessed, the S-bits of said S-vector initially being set on, said method comprising the steps of:
- testing an access to the cache memory to determine if an accessed line is in the cache memory, and if it is, accessing the line;
otherwise, fetching the accessed line from main memory;
testing the accessed line in the cache memory to determine if it is in a Most-Recently-Used position, and if it is not, making the line the Most-Recently Used;
testing said S-bit for the accessed line to determine if it is on, and if it is, testing to determine if a sequential next line is in the cache memory; and
if said sequential next line is not in the cache memory, prefetching the sequential next line into the cache memory as a new line and keeping the new line at a Least-Recently-Used position in the cache memory.
0 Assignments
0 Petitions
Accused Products
Abstract
A computer memory management method for cache memory uses a deconfirmation technique to provide a simple sequential prefetching algorithm. Access sequentially is predicted based on simple histories. Each memory line in cache memory is associated with a bit in an S-vector, which is called the S-bit for the line. When the S-bit is on, sequentiality is predicted meaning that the sequentially next line is regarded as a good candidate for prefetching, if that line is not already in the cache memory. The key to the operation of the memory management method is the manipulation (turning on and off) the S-bits.
-
Citations
24 Claims
-
1. A computer performed method for prefetching sequential lines from main memory into a processor cache memory of a computer, said cache memory including an S-vector comprising an S-bit associated with lines in main memory, said S-b being indicative of whether a succeeding line is likely to be accessed when a line in memory corresponding to said S-bit is accessed, the S-bits of said S-vector initially being set on, said method comprising the steps of:
-
testing an access to the cache memory to determine if an accessed line is in the cache memory, and if it is, accessing the line; otherwise, fetching the accessed line from main memory; testing the accessed line in the cache memory to determine if it is in a Most-Recently-Used position, and if it is not, making the line the Most-Recently Used; testing said S-bit for the accessed line to determine if it is on, and if it is, testing to determine if a sequential next line is in the cache memory; and if said sequential next line is not in the cache memory, prefetching the sequential next line into the cache memory as a new line and keeping the new line at a Least-Recently-Used position in the cache memory. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. In a computer system having a processor, a memory for storing a plurality of storage lines for use by said processor, and a cache for holding storage lines received from said memory for use by said processor, prefetching apparatus comprising:
-
means for storing a plurality of S-bits, each storage line in said memory corresponding with one of said S-bits, each S-bit having first and second alternate states, said first alternate state indicating that when a corresponding storage line is accessed by said processor, the next sequential storage line also is likely to be accessed soon by said processor, and said second alternate state indicating that when a corresponding storage line is accessed by said processor, the next sequential storage line is not likely to be accessed soon by said processor; means for determining whether the S-bit corresponding with a storage line accessed by said processor is in said first state; means responsive to said S-bit state determining means for prefetching into said cache the next sequential storage line when said S-bit is in said first state unless said next sequential storage line is already in said cache; deconfirmation means for determining whether said prefetched next sequential storage line was accessed by said processor before it was replaced in said cache; and means responsive to said deconfirmation means for setting the state of the S-bit corresponding with the storage line preceding said prefetched next sequential storage line to said second state in the event that said deconfirmation means determines that said prefetched next sequential storage line was not accessed by said processor before it was replaced in said cache. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification