Browse Prior Art Database

Algorithm for Using Cache Misses Using a Shadow Cache Directory

IP.com Disclosure Number: IPCOM000034924D
Original Publication Date: 1989-May-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 3 page(s) / 66K

Publishing Venue

IBM

Related People

Pomerene, J: AUTHOR [+4]

Abstract

Current system cache directories conform to the size of the cache data array. They, therefore, can maintain no historical information related to the recentness of the existence of a line in the cache. By doubling the directory size, that is, by maintaining a directory on twice as many lines as the cache can hold, a means is established for assessing the dynamic behavior of the lines as they reenter the cache. There are several ways to use the additional information derived from a hit in the shadow directory. 1. Such lines can be flagged for special treatment by the cache replacement algorithm. 2.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 58% of the total text.

Page 1 of 3

Algorithm for Using Cache Misses Using a Shadow Cache Directory

Current system cache directories conform to the size of the cache data array. They, therefore, can maintain no historical information related to the recentness of the existence of a line in the cache. By doubling the directory size, that is, by maintaining a directory on twice as many lines as the cache can hold, a means is established for assessing the dynamic behavior of the lines as they reenter the cache. There are several ways to use the additional information derived from a hit in the shadow directory. 1. Such lines can be flagged for special treatment by the cache replacement algorithm.

2. Such lines can be flagged for special treatment by the cache

replacement algorithm if the number of hits in the shadow

directory (that is, missed from the cache) falls within a

pre-specified range.

(Image Omitted)

3.

Under a pre-specified criteria for the shadow hits, the cache

can reconfigure itself to half-line size, thereby keeping the

most used half lines within the congruence class rather than

the most recently used whole lines. 4. Standard next sequential line prefetching can be derived from

the shadow directory. That is, if the current miss has its

next sequential line also in the shadow directory, prefetch

it. The next sequential line can be generalized to include

the preceding sequential line as well. 5. The cache replacement algorithm can be based on the total

information maintained by the shadow directory rather than the

member of the actual cache. The algorithm shown above illustrates one of the potential uses that can be made of the shadow directory to modify the replac...