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

Prefetching for the Iterations of an Indexed Loop

IP.com Disclosure Number: IPCOM000104217D
Original Publication Date: 1993-Mar-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 98K

Publishing Venue

IBM

Related People

Pomerene, J: AUTHOR [+2]

Abstract

An indexed loop contains repetitive reference patterns that involve the use of one register that supplies the base address (B) and a second register that supplies the index (X) for accesses performed by instructions. The means of using this information within a prefetching mechanism in order to anticipate these misses is disclosed. The result of monitoring the miss activity within an index loop provides for information about access patterns to lines within an iteration and between successive iterations. This results in a shortening of iteration time as unnecessary data is not transferred into the L1, data from different cache lines is presented on a timely basis, and improvements in cache dynamics can be anticipated.

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

Prefetching for the Iterations of an Indexed Loop

      An indexed loop contains repetitive reference patterns that
involve the use of one register that supplies the base address (B)
and a second register that supplies the index (X) for accesses
performed by instructions.  The means of using this information
within a prefetching mechanism in order to anticipate these misses is
disclosed.  The result of monitoring the miss activity within an
index loop provides for information about access patterns to lines
within an iteration and between successive iterations.  This results
in a shortening of iteration time as unnecessary data is not
transferred into the L1, data from different cache lines is presented
on a timely basis, and improvements in cache dynamics can be
anticipated.

      The underlying principle in I x D -> D prefetching is that a
location can be a surrogate for a value.  Further, a piece of data
can be accessed in different ways depending on the program.  If the
elements of a matrix are accessed in column order by one algorithm
and in row order by another algorithm the an ordinary D -> D
prefetching strategy will fail but a mechanism that maintains a form
of D -> D  as subordinate to an I-LINE is better.  Such a mechanism
is called I x D -> D.  A superior prefetching strategy for D-CACHE
lines is to use I sub VALUE x D sub VALUE -> D sub LOC as opposed to
I sub LOC x D sub LOC -> D sub LOC because the former mimics the
Address Generation (AGEN) Process while the latter works only when
values and locations which are the source of GPR's do not change.

      The approach taken in some situations is to restrict one's
attention to the misses that are caused by instructions which use a
single register that has not been modified as the basis for the
address generation (AGEN) that caused the D-MISS.  The operation of
addressing within indexed loops, where the loop closing instructions
are BRANCH ON INDEX do not fall into this case but offer an
attractive opportunity for prefetching.

      PREFETCHING FOR THE ITERATIONS OF AN INDEXED LOOP - There are
several interrelated aspects of loop operations that must all be
properly managed for the advantages of prefetching for D-CACHE MISSES
to be effective:

o   PREFETCHING MUST BE PROPERLY DETECTED AND CORRECTLY APPLIED
o   PREFETCHING MUST BE PACED PROPERLY IF MISSES ARE INTER-_
    DIGITATED
o   RESTRICT THAT WHICH IS PREFETCHED TO THAT WHICH IS USED

      PREFETCHING MUST BE PROPERLY DETECTED AND CORRECTLY APPLIED -
The means of detecting the prefetching is for the processor to become
cognizant that a certain I-LINE is generating a set of D-MISSES for
which the I x D -> D mechanism that anticipates misses has no
entries.  This is in conjunction with BHT information that a BRANCH
ON INDEX terminates the loop.  A loop forming or loop closing BRANCH
ON INDEX can pr...