Browse Prior Art Database

Method for Predicting the Performance of Set-Associative Cache Memories

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

Publishing Venue

IBM

Related People

Natarajan, KS: AUTHOR

Abstract

An analytic method is set forth for predicting the hit-ratio performance of a cache memory organized as a set-associative cache; the method can be used in a tool for fast prediction of cache performance for different cache sizes. The design of cache memories for use in main memory of computer systems can be facilitated by fast and effective tools that can predict the performance for a wide range of cache configuration parameters. Set-associative mapped cache memory organization is commonly used in modern computer systems [1]. Three key parameters that are used to characterize such caches are a) the number of congruence classes (N), b) degree of associativity (K), the number of lines per class, and c) the number of bytes (L) per line. The size of the cache, S, is the product NKL. For our present discussion, let L=1.

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

Page 1 of 3

Method for Predicting the Performance of Set-Associative Cache Memories

An analytic method is set forth for predicting the hit-ratio performance of a cache memory organized as a set-associative cache; the method can be used in a tool for fast prediction of cache performance for different cache sizes. The design of cache memories for use in main memory of computer systems can be facilitated by fast and effective tools that can predict the performance for a wide range of cache configuration parameters. Set-associative mapped cache memory organization is commonly used in modern computer systems [1]. Three key parameters that are used to characterize such caches are
a) the number of congruence classes (N), b) degree of associativity
(K), the number of lines per class, and c) the number of bytes (L) per line. The size of the cache, S, is the product NKL. For our present discussion, let L=1. During the design stage of a computer system, alternate cache designs are evaluated against the memory reference characteristics of typical workloads that will be presented to the system. Previous work reported in the literature [2, 3] has relied primarily on the use of trace-driven simulation for evaluating the performance of cache designs. Since simulation runs tend to be computationally expensive, the extent of the cache design space that can be examined is inherently limited. Thiebaut [4] has recently shown that the address-reference behavior of programs can be modeled by a fractal process. 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 a function of t, the total number of references made by a program, follows the equation u(t)=At1/r . In this characterization, the parameter r has been called the fractal dimension of the process, with large values of r signifiying 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 full-associative caches (i.e., N=1) as a function of the fractal parameters A,r, and the cache size. This method is an extension of (1) for fast evaluation of the miss-ra...