Report Number: CSL-TR-75-95
Institution: Stanford University, Computer Systems Laboratory
Title: The stack working set: a characterization of spatial locality
Author: Rau, B. Ramakrishna
Date: July 1975
Abstract: Multilevel memory hierarchies are attractive from the point
of view of cost-performance. However, they present far
greater problems than two-level hierarchies when it comes to
analytic performance evaluation. This may be attributed to
two factors: firstly, the page size (or the unit of
information transfer between two levels) varies with the
level in the hierarchy; secondly, the request streams that
the lower (slower) levels see are the fault streams out of
the immediately higher levels. Therefore, the request stream
seen by each level is not necessarily the same as the one
generated by the processor. Since the performance depends
directly upon the properties of the request stream, this
poses a problem.
A model for program behavior, which explicitly characterizes
the spatial locality of the program, is proposed and
validated. It is shown that the spatial locality of a program
is an invariant of the hierarchy when characterized in this
manner. This invariance is used to solve the first problem
stated - that of the varying page sizes. An approximate
technique is advanced for the characterization of the fault
stream as a function of the request stream and the capacity
of the level. A procedure is then outlined for evaluating the
performance of a multilevel hierarchy analytically.
http://i.stanford.edu/pub/cstr/reports/csl/tr/75/95/CSL-TR-75-95.pdf