Efficient (stack) algorithms for analysis of write-back and sector memories

Abstract

For the class of replacement algorithms known as stack algorithms, existing analysis techniques permit the computation of memory miss ratios for all memory sizes simultaneously in one pass over a memory reference string. We extend the class of computations possible by this methodology in two ways. First, we show how to compute the effects of copy-backs in write-back caches. The key observation here is that a given block is clean for all memory sizes less than or equal to C blocks and is dirty for all larger memory sizes. Our technique permits efficient computations for algorithms or systems using periodic write-back and/or block deletion. The second extension permits stack analysis simulation for sector (or subblock) caches in which a sector (associated with an address tag) consists of subsectors (or subblocks) that can be loaded independently. The key observation here is that a subsector is present only in caches of size C or greater. Load forward prefetching in a sector cache is shown to be a stack algorithm and is easily simulated using our technique. Running times for our methods are only slightly higher than for a simulation of a single memory size using nonstack techniques.