Browse Prior Art Database

Cache Miss History Table

IP.com Disclosure Number: IPCOM000045740D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 64K

Publishing Venue

IBM

Related People

Rechtschaffen, RN: AUTHOR

Abstract

In a model of program behavior involving re-entrant code, the re-execution of a code segment will recreate cache accesses if the contents of the base registers are the same. It has been found that there is a high degree of register reuse and that the memory address can serve as a surrogate for the contents of the registers. These results lead one to suspect that the cache can predict accesses accurately based only on the sequence of cache accesses. The common aging process that cache lines undergo and their eventual replacement under LRU (Least Recently Used) algorithms change the access aspect of the above phenomena to misses. That is, a relationship exists between the address of the current miss and the next miss. Such repetitive patterns have been observed in cache simulations.

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 53% of the total text.

Page 1 of 3

Cache Miss History Table

In a model of program behavior involving re-entrant code, the re-execution of a code segment will recreate cache accesses if the contents of the base registers are the same. It has been found that there is a high degree of register reuse and that the memory address can serve as a surrogate for the contents of the registers. These results lead one to suspect that the cache can predict accesses accurately based only on the sequence of cache accesses. The common aging process that cache lines undergo and their eventual replacement under LRU (Least Recently Used) algorithms change the access aspect of the above phenomena to misses. That is, a relationship exists between the address of the current miss and the next miss. Such repetitive patterns have been observed in cache simulations. The following invention proposes to capture information about miss patterns and use that information to prestage cache lines, thereby reducing the penalty associated with a cache miss.

The processor maintains the history of cache misses by building and updating a Cache Miss History Table (Fig. 1). Each entry in the Cache Miss History Table (CMT) contains two cache line addresses which are the addresses of two successive cache misses. The CMT is accessed using a portion of the cache line address (size of CMT determines portion of line address) on which the processor missed and which points to a set of entries. In the implementation shom, a 4-way set associative CMI is illustrated. Here, the address used to access the table drives out 4 candidate entries. A subsequent comparison on the first address or "current miss address field" of the entry establishes a hit or miss in the CMT. In the event of a miss (no comparison), th...