As caches are ubiquitous in computer system design, understandingthe limits of their performance is of interest. In most situations,optimizing just the traffic (measured in lines or pages moved) is anincomplete optimization, because it is often less expensive to moveseveral lines or pages at once to an upper memory level.

Belady’s MIN algorithm, which relies on knowledge of futurereferences, is the optimal replacement algorithm in terms of traffic. Inthis paper, Belady’s algorithm is extended to include spatiallocality.

On a miss, multiple spatially associated lines or pages includingthe referenced line or page can be moved. The algorithm minimizes themisses. Experiments using SPEC95 benchmarks show that minimizing themisses produces nearly minimal memory traffic.