From: rschnapp@metaflow.com (Russ Schnapp)
Subject: Re: implementing random replacement
Keywords: random cache replacement
Organization: Metaflow Technologies Inc.
Date: Wed, 30 Sep 1992 18:38:26 GMT

In article <FPJ.92Sep30160228@ingrina.inesc.pt>, fpj@ingrina.inesc.pt (Fernando Pereira Jesus) writes:
|> In article <BvCpp2.EFt@metaflow.com> rschnapp@metaflow.com (Russ Schnapp) writes:
|> 
|> >   |> Aditionaly, the shift register stops at empty (flushed) lines, thus
|> >   |> ensuring that empty lines are used before lines allready in use.
|> >
|> >   It seems to me that this would not "ensure" that unused lines are
|> >   pressed into service before valid lines are replaced.  There is no
|> >   guaranteed time before the random pointer has scanned all values.  The
|> >   time to scan all lines is probabilistic.
|> 
|> The time to scan all lines in the cache is (more or less) 10ns * N
|> N is the number of lines in the cache. If N is, say, 100, it will take
|> 1us to scan all lines. 

Perhaps I misunderstood your design.  I thought you said you were using
a feedback shift register to generate the random replacement pointer.
If so, then as far as I know, you cannot _guarantee_ that all N lines
will be visited until you have visited all the states in your shift
register.

For example, if you use a 16 bit shift register and an optimal feedback
network, there are 2**16 states.  If you use some subset of the
register bits as the replacement pointer, you have no guarantee that
all elements will be visited until 2**16 * 10ns, or 6.5 ms, unless I've
misplaced a decimal point.

Surely, you aren't using an N bit FSR to generate a pointer to 2**N
lines?  This would yield a deterministic visiting sequence, and would
be no better than a simple counter.

|>                       If this time is to high, or if N is a large
|> number, you can have two levels of counters: (a tree of counters) the
|> root level counter selects one of the second level counters which
|> selects a cache line (in most cases large caches are internally
|> splited to decrease response time, so this is easy).

This doesn't help ensure that all lines are visited in less time.  It
can also decrease the liklihood of selecting an unused line.
 
|> >   Using a simple counter has two advantages:  1) You can guarantee that
|> >   all lines will be scanned in a finite amount of time (granted, this is
|> >   probably just a nit-pick);
|> I can't see your point. With our shift register all lines will be
|> scanned in a finite amount of time, and since it runs assynchronously,
|> it will be faster than a simple counter.

A counter can be run asynchronously, and as fast as an FSR.  

|> 
|> >                              and 2) You can add a fence register to
|> >   protect some lines from replacement.  When the counter matches the
|> >   fence register, you reset it.  This is nice if you want to lock certain
|> >   lines into the cache.
|> In our design, this is possible to. With a few more transistors, it
|> is possible to make the "set" and "reset" signals skip over one stage,
|> so if on line is marked not to be replaced, the counter will not scan
|> this line.

Now I'm sure I don't understand what your design is, since an FSR can't
do this, so far as I know -- Suppose the pointer happens to be at a line
you don't want to replace, at the same time as a replacement is requested?
Do you introduce a stall until the pointer is at a replaceable line?  Or
can you really get your FSR to never point at locked lines?  If so, how? 
-- 

...Russ Schnapp
BIX: rschnapp           Email: uunet!metaflow!rschnapp or rschnapp@metaflow.com
Metaflow Technologies   Voice: 619/452-6608x230;  FAX: 619/452-0401
La Jolla, California    Unless otw specified, I`m speaking only for myself!