Efficient determination of spacetime product performance in a virtual memory computer
Gary Chastek · 1983
The intimate connection between the spacetime product and multiprogramming throughput has established spacetime product as an important virtual memory performance metric. However, as programs typically generate a very large number of references, the experimental use of this already complicated metric has been limited. Such experiments typically investigate the performance of a combination of three memory management strategies. These are (1) Denning's Working Set, an implementable strategy, (2) VMIN, an approximately optimal strategy, and (3) DMIN, an optimal strategy. To increase the practicality of such experiments, we present three major results. The first is a powerful dynamic programming algorithm which, for a large class of programs, efficiently determines optimal spacetime product. The second result is an organized method for quickly extending the results of an optimal strategy over a range of values. Finally, the third result provides a dramatically more efficient method for determining the optimal spacetime product performance of Denning's Working Set and VMIN over the entire range of their natural parameters.