Browse Prior Art Database

Technique for Finding the Footprint Size of a Mixture of Programs

IP.com Disclosure Number: IPCOM000034365D
Original Publication Date: 1989-Feb-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Natarajan, KS: AUTHOR

Abstract

An analytic method is described for determining the footprint size of a composite mixture of programs that are combined in a fixed proportion; The method can be used in a tool for fast prediction of cache performance under realistic workload environment. Effective design of caches for use in main memory (or disk controllers) must take into account the memory reference (or disk reference) characteristics of what may be considered the typical workload that will be executed very frequently on the computer system. A particular cache design that is good with respect to one type of workload need not be effective when the nature of workload changes. Thus, there exists a need to design a cache that is effective for a combination of workload types.

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

Page 1 of 2

Technique for Finding the Footprint Size of a Mixture of Programs

An analytic method is described for determining the footprint size of a composite mixture of programs that are combined in a fixed proportion; The method can be used in a tool for fast prediction of cache performance under realistic workload environment. Effective design of caches for use in main memory (or disk controllers) must take into account the memory reference (or disk reference) characteristics of what may be considered the typical workload that will be executed very frequently on the computer system. A particular cache design that is good with respect to one type of workload need not be effective when the nature of workload changes. Thus, there exists a need to design a cache that is effective for a combination of workload types. Previous work reported in the literature [1,2] has relied primarily on the use of trace-driven simulation for evaluating the performance of memory hierarchies. Recent work by Thiebaut has shown that the address-reference behavior of programs can be modeled by a fractal process [3,4]. Let the footprint of a process be the set of unique addresses referenced by a program during the course of its execution. Thiebaut has shown that u(t), the number of unique addresses referenced by a program, as function of t, the total number of references made by a program, follows the equation u(t) = A t1/r . In this characterization, the parameter r has been called the fractal dimension of the process, with large values of r signifying high degrees of locality in the address-reference pattern of the program. Thiebaut has shown that a plot of the footprint function, u(t) plotted against t, on a log/log scale follows a straight line whose slope is 1/r and the intercept of the line determines the value of A. He has derived analytic expressions for the miss-ratio of fully associative caches as a function of the fractal parameters A, r, and the cache size. The described technique presents a method for determining the growth of the footprint function when multiple processes are combined in a specified proportion. Specifically, consider the following. Suppose there are n processes denoted as P1, P2,..., Pn . Let each process Pi belong to a particular type of workload and be characterized by its fractal parameters, say, Ai and ri . Let ti be the number of addresses-references made by Process Pi . The technique presents a method for estimating the number of unique address-references that will be made when the processes Pi through Pn are executed in some sequence. The basis of the technique is the observation that when two processes P1, P2, are executed in sequence, one can associate with the composite address-reference string an equivalent fractal process with parameters Ae, re . T...