Browse Prior Art Database

THE AO INVERSION MODEL OF PROGRAM PAGING BEHAVIOR

IP.com Disclosure Number: IPCOM000128295D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 14 page(s) / 46K

Publishing Venue

Software Patent Institute

Related People

Forest Baskett: AUTHOR [+4]

Abstract

When the parameters of a simple stochastic model of the memory referencing behavior of computer programs are carefully selected, the model is able to mimic the paging behavior of a set of actual programs, The mimicry is successful using several different page replacement algorithms and a wide range of real memory sizes in a virtual memory environment, The model is based on the independent reference model with a new procedure for determining the page reference probabilities, the parameters of the model, We call the result the AO inversion independent reference model, Since the fault rate (or miss ratio) is one aspect of program behavior that the model is able to capture for many different memory sizes, the model should be especially useful for evaluating multilevel memory organizations based on newly emerging memory technologies, *Work partially supported by the Energy Research and Development Adminis-tration under Contract E(043)515. "Work partially supported by National Science Foundation, NSF Grant GJ35720

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

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE AO INVERSION MODEL OF PROGRAM PAGING BEHAVIOR

by Forest Baskett and Abbas Rafii

Stanford Linear Accelerator Center* P.O. Box 4349, Stanford, California 94305 and Computer Science Department" Stanford University, Stanford, California

Abstract

When the parameters of a simple stochastic model of the memory referencing behavior of computer programs are carefully selected, the model is able to mimic the paging behavior of a set of actual programs, The mimicry is successful using several different page replacement algorithms and a wide range of real memory sizes in a virtual memory environment, The model is based on the independent reference model with a new procedure for determining the page reference probabilities, the parameters of the model, We call the result the AO inversion independent reference model, Since the fault rate (or miss ratio) is one aspect of program behavior that the model is able to capture for many different memory sizes, the model should be especially useful for evaluating multilevel memory organizations based on newly emerging memory technologies,

*Work partially supported by the Energy Research and Development Adminis-tration under Contract E(043)515. "Work partially supported by National Science Foundation, NSF Grant GJ35720

KEYWORDS AND PHRASES

program models program page reference behavior stochastic program models paging algorithms program behavior replacement algorithms program paging behavior virtual memory

1. Introduction

Computing systems in which several types of storage are automatically made to appear as one uniform type of storage are likely to be a major part of our computing environment for some time to come. Memory transparency or automatic folding or virtual memory has been accepted as a necessary tool for the convenient solution of many computing problems in much the same way as higher level languages were accepted as a necessary evil many years ago, In fact, paging techniques [8] are being used to automatically manage small, very high speed buffers (caches) for high speed CPU's [2, 71 and to manage large, slow disk buffers for much larger and slower automated filing systems

[3] , as well as being used more conventionally to automatically manage main memory in a wide variety of computers.

Stanford University Page 1 Dec 31, 1976

Page 2 of 14

THE AO INVERSION MODEL OF PROGRAM PAGING BEHAVIOR

This wide use of paging techniques.together with the ever changing performance parameters of the memory technologies on which these paging techniques are implemented,point up the need for efficient and effective methods for evaluating the performance of different memory hierarchy designs. Central to such methods will be some model of how computer programs reference memory. The choice of that model of memory referencing behavior will determine the accuracy, efficiency, generality, and even the feasibility of the evaluation method in which it...