Browse Prior Art Database

Least Recently Used Stack Distance Algorithm

IP.com Disclosure Number: IPCOM000084163D
Original Publication Date: 1975-Sep-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 27K

Publishing Venue

IBM

Related People

Bennett, BT: AUTHOR [+2]

Abstract

The trace driven simulation of a storage hierarchy with Least-Recently Used (LRU) replacement, is accomplished by first calculating the stack distance for each reference in the address trace. There is described herein a new algorithm for calculating the stack distances.

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

Page 1 of 2

Least Recently Used Stack Distance Algorithm

The trace driven simulation of a storage hierarchy with Least-Recently Used (LRU) replacement, is accomplished by first calculating the stack distance for each reference in the address trace. There is described herein a new algorithm for calculating the stack distances.

An LRU stack is a list of referenced addresses in order of most recent reference. The stack distance for a reference is the position on the stack of the address being referenced. Previous methods of calculating the stack distance involve maintaining the stack and searching it from the top to find the referenced address.

For some address traces the average stack distance is large and thus the amount of searching in the stack is excessive. The present algorithm described avoids searching the stack, and is much more efficient when the average stack distance is large.

Since each address in a LRU stack which is above a particular address alpha represents a distinct address which has been referenced after alpha was last referenced, the stack distance is equivalent to one plus the number of distinct addresses which were referenced since the current address was last referenced.

Consider a bit string B degree whose positions correspond to references and contain 1's if the address referenced there has not been rereferenced. When processing the t/th/ reference the bit string represents the situation after t-1 references, and if the address referenced at time t was...