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

Spatial-Temporal Cache Block Replacement

IP.com Disclosure Number: IPCOM000120799D
Original Publication Date: 1991-Jun-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 1 page(s) / 37K

Publishing Venue

IBM

Related People

Roberson, K: AUTHOR [+2]

Abstract

Provided is a technique for replacing blocks in computer caches based upon principles of spatial and temporal locality in order to overcome deficiencies with use of conventional techniques.

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

Spatial-Temporal Cache Block Replacement

      Provided is a technique for replacing blocks in computer
caches based upon principles of spatial and temporal locality in
order to overcome deficiencies with use of conventional techniques.

      Spatial locality dictates that a cache keep blocks of
information close to what is currently being used, while temporal
locality dictates that a cache keep recently used information.  When
combined into a single algorithm, the principles of temporal and
spatial locality lead designers to keep in the cache information that
is close to the current execution point and that has been recently
used. The Spatial- Temporal Replacement Algorithm keeps in the cache
blocks of instructions and data which are close to what is being used
and that have been used recently.  The Spatial-Temporal Algorithm
finds the cache block whose execution point is furthest away from the
current execution point and is not the most recently used.  If a
block must be replaced, the algorithm performs the following:  find
candidate blocks whose execution space is far away from the current
block; if the candidate block has not been used recently, then
replace it; if the candidate block has been recently used, search for
the next block closest to the current execution point; if no such
block can be found, then replace the farthest block using Least
Recently Used algorithms.

      The benefits of the Spatial-Temporal Replacement Algorithm is
better intern...