Experiments with program locality.

Abstract

Attempt to validate experimentally several intrinsic models for the concept of program locality. The models considered are a two-parameter simple locality model, a simple least recently used stack model, and an independent reference model. The first two models appear to produce good approximations to real world behavior, while the independent reference model, because of its static concept of locality, does very poorly. The working set is shown to be a good estimator of the simple two-parameters model's locality, provided that the locality does not change too rapidly. The working set exactly measures the locality in the case of the least recently used stack model and is thus nearly optimal for programs whose behavior can be closely approximated by this model.