This brief contribution introduces a method of quantifying the locality in a given reference sequence and visually representing it as a three dimensional surface. We explore some of the properties of this formulation of locality and show the correlation between graphical features and specific reference patterns. The utility of our formulation of locality is demonstrated through two of its potential applications as a visualizations tool: characterizing and summarizing workload locality, and evaluating the effectiveness of benchmark programs in exercising memory hierarchies.

A new disk caching algorithm is presented that uses an adaptive prefetching scheme to reduce the average service time for disk references. Unlike schemes which simply prefetch the next sector or group of sectors, this method maintains information about the order of past disk accesses which is used to accurately predict future access sequences. The range of parameters of this scheme is explored, and its performance is evaluated through trace-driven simulation, using traces obtained from three different UNIX minicomputers. Unlike disk trace data previously described in the literature, the traces used include time stamps for each reference. With this timing information-essential for evaluating any prefetching scheme-it is shown that a cache with the adaptive prefetching mechanism can reduce the average time to service a disk request by a factor of up to three, relative to an identical disk cache without prefetching.>