Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Algorithm for Non-Sequential Cache Prefetching

IP.com Disclosure Number: IPCOM000121106D
Original Publication Date: 1991-Jul-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Ignatowski, M: AUTHOR [+2]

Abstract

Disclosed is an algorithm for initiating cache prefetches for data to potentially non-sequential cache lines, based on the past history of cache misses.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Algorithm for Non-Sequential Cache Prefetching

      Disclosed is an algorithm for initiating cache prefetches
for data to potentially non-sequential cache lines, based on the past
history of cache misses.

      Prefetching cache lines is a way to reduce the memory access
penalty in computer systems employing caches.  The simplest
prefetching algorithms involve prefetching the cache line with the
next sequential address after the line being currently accessed.  An
improvement can be made on this scheme by allowing for a prefetch to
any arbitrary cache line.  The disclosed algorithm makes use of the
past pattern of misses from a processor's cache as a guide to select
which line to prefetch next.  Such lines need not be, and often are
not, the next sequential line.

      The disclosed algorithm requires hardware registers, called
"previous miss registers", to keep track of the most recent cache
miss from each processor.  It also requires a hardware "history"
table to keep track of pairs of addresses.  Each pair of addresses
consists of a past miss, and the next miss to occur after it.  These
will usually be located in a system control or memory control
element.

      The algorithm also introduces a new memory request type, called
a pseudo-miss.  It will be sent to the prefetching mechanism the
first time a prefetched line is actually used by a processor.  A
pseudo-miss will not actually return any data (since that line is
already in the cache).  However, it will be used by the prefetching
mechanism just like any other miss to update the previous miss
register, th...