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

Non-Unit Stride Pattern Recognition

IP.com Disclosure Number: IPCOM000100154D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 52K

Publishing Venue

IBM

Related People

Peterson, MJ: AUTHOR

Abstract

Disclosed is a method of automatically recognizing that a program is using data at an address offset other than 1 ("non-unit strides"). The method saves the addresses accessed on a stack and algorithmically finds a pattern in the accesses. The cache can then be loaded by extrapolating the pattern found.

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

Non-Unit Stride Pattern Recognition

       Disclosed is a method of automatically recognizing that a
program is using data at an address offset other than 1 ("non-unit
strides").  The method saves the addresses accessed on a stack and
algorithmically finds a pattern in the accesses.  The cache can then
be loaded by extrapolating the pattern found.

      Many programs naturally access data at non-unit strides due to
the memory layout of multi-dimensional arrays. Processor hardware can
be built to recognize these non-unit stride patterns.

      Assume that the pattern data will be accessed with only 1 or 2
other accesses in between and that 3 equidistant addresses indicate a
pattern.  (Note that these assumptions can be changed with only
slight modifications.)  The following steps are implemented in
hardware:
1.  Save all addresses accessed recently on a stack "Z" where X0, X1,
and X2 are the pattern data.  A, B, C, and D are other accesses.
 THE FOLLOWING CASES EXIST FOR THESE ASSUMPTIONS:
         Case -  1   2   3   4   5   6   7   8
           Z0 = X1
           Z1 =  A  X1  X1
           Z2 =  B   A   A  X1  X1
           Z3 = X2  X2   B   A   A  X1  X1
           Z4 =  C   B  X2  X2   B   A  X2  X1
           Z5 =  D   C   C   B  X2  X2   A  X2
      Current = X3  X3  X3  X3  X3  X3  X3  X3
2.  Check for all 8 ca...