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

Management Technique for Memory Hierarchies

IP.com Disclosure Number: IPCOM000052470D
Original Publication Date: 1981-Jun-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

May, CM: AUTHOR

Abstract

A memory hierarchy system consists of multiple levels of devices used t store data. The highest level is typically the smallest, fastest, and most expensive (per byte), with size increasing and speed and cost decreasing as one moves down the hierarchy. Examples of memory hierarchies include: cache and main memory in a CPU, main memory and direct-access storage devices (DASDs) (when main memory is used to buffer records retrieved from DASD), random-access memory (RAM) and DASDs of buffered DASD subsystems, and the staging drives and cartridges of the Mass Storage System. (In all the foregoing examples, the higher level of the hierarchy is stated first.)

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 3

Management Technique for Memory Hierarchies

A memory hierarchy system consists of multiple levels of devices used t store data. The highest level is typically the smallest, fastest, and most expensive (per byte), with size increasing and speed and cost decreasing as one moves down the hierarchy. Examples of memory hierarchies include: cache and main memory in a CPU, main memory and direct-access storage devices (DASDs) (when main memory is used to buffer records retrieved from DASD), random-access memory (RAM) and DASDs of buffered DASD subsystems, and the staging drives and cartridges of the Mass Storage System. (In all the foregoing examples, the higher level of the hierarchy is stated first.)

The design of memory hierarchies consists of deciding the devices to use at each level, the amount of storage at each level, and the algorithm by which data is to flow among levels. A commonly-used algorithm for managing data flow is least recently used (LRU). A usual measure of goodness of a memory hierarchy is the miss ratio out of the highest level.

All else being equal, the performance of a memory hierarchy is profoundly affected by the characteristics of the stream of references presented to it (e.g., by the sequence of main memory addresses, for the cache/main memory hierarchy). It is relatively easy to design an algorithm for managing data flow that will perform well (i.e., yield low miss ratio) for one kind of reference stream and yet perform badly for another. For example, LRU performs well for reference streams with a high degree of locality, but badly for reference streams with a high degree of sequentiality.

In practice, reference streams generally have characteristics which are:

- a composite of those of simpler reference streams (e.g.,

a mix of sequential references with references that are

local and/or random),

- not knowable a priori, and

- changing over time.

Thus, it would be extremely desirable to have a memory management technique that could determine dynamically how each data element is being accessed and could manage that element accordingly. The technique described below does just that.

For the sake of simplicity, the remainder of the discussion deals with a two- level memory hierarchy. The data element that flows between the two levels is called a record. For concreteness, the algorithm will be described in terms of a memory hierarchy consisting of main memory and DASDs, with the main memory used to store DASD records. However, it should be kept in mind that the ideas presented apply to any memory hierarchy system.

If one wants to determine a record's access characteriastics dynamically, an easy way to do so is to ensure that the record stays in memory for some period of time, during which its behavior is "watched". After this trial period has elapsed, the record is dealt with according to its observed behavior.

1

Page 2 of 3

In the present system, this trial period is provided by dividing the main memory into two s...