James G. Thompson and Alan Jay Smith

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-358
June 1987

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-358.pdf

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 sub-block) caches, in which a sector (associated with an address tag) consists of sub-sectors (or sub-blocks) which can be loaded independently. (The key observation here is that a sub-sector 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 non-stack techniques.

BibTeX citation:

@techreport{Thompson:CSD-87-358,
    Author = {Thompson, James G. and Smith, Alan Jay},
    Title = {Efficient (Stack) Algorithms for Analysis of Write-Back and Sector Memories},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1987},
    Month = {Jun},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6215.html},
    Number = {UCB/CSD-87-358},
    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 <i>C</i> 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 sub-block) caches, in which a sector (associated with an address tag) consists of sub-sectors (or sub-blocks) which can be loaded independently. (The key observation here is that a sub-sector is present only in caches of size <i>C</i> 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 non-stack techniques.}
}

EndNote citation:

%0 Report
%A Thompson, James G.
%A Smith, Alan Jay
%T Efficient (Stack) Algorithms for Analysis of Write-Back and Sector Memories
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-358
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6215.html
%F Thompson:CSD-87-358