From: rschnapp@metaflow.com (Russ Schnapp)
Subject: Re: implementing random replacement
Organization: Metaflow Technologies Inc.
Date: Thu, 1 Oct 1992 20:08:35 GMT

In article <FPJ.92Oct1082238@ingrina.inesc.pt>, fpj@ingrina.inesc.pt (Fernando Pereira Jesus) writes:
|> In article <BvEMG3.4z0@metaflow.com> rschnapp@metaflow.com (Russ Schnapp) writes:
|> Suppose you have a N-stage shift register with outputs (o1, o2, ...,
|> oN). At power up o1 is seted and all others reseted, so only one
|> output is active at a time (this is the important point I haven't
|> mentioned). So, at time 0 the state of the shift register is 100...,
|> after about 10ns the state is 0100..., after 10ns more, 00100..., and
|> so on. After 10ns * N we have the initial state again...

Ah!  You have a degenerate FSR, where the feedback is an end-around input.
When I heard feedback shift register, I assumed you meant a linear feedback
shift register, which is the most popular circuit for generating pseudo-
random numbers.  

|> >   |>                       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
|> >   |> ...
|> >   This doesn't help ensure that all lines are visited in less time.  It
|> >   can also decrease the liklihood of selecting an unused line.
|> You can stop the root shift register (maybe I shouldn't have call it a
|> counter) if it steps to a stoped second level shift register.

I see.  Ok, in order to guarantee that it always points to a
replaceable line, you would have to break it into enough stages such
that all lines are scanned in less time than it takes between possible
replacement requests.  Otherwise, you have to be able to stall
replacement until such a line is selected.

I'm still not sure how you can implement locked lines without
introducing a stall.  Hmmm.  I suppose you could adopt the fence
register idea, to select the shift register bit to carry around to bit 0.

|> >   |> 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.  
|> The number of transistors involved in one step is less than 15 (I
|> don't remember the exact number now). About 1/2 of this transistors
|> are pass gates which are allmost always "on" or "off".  A counter is
|> more complex, because of the carry, so I don't beleave that (with the
|> same technology) a counter can run as fast as this shift-register.

Quite right.  

Anyway, the main advantage of your shift register over a clock counter,
so far as replacement function goes, is the fact that it runs
asynchronously, and with nondeterministic speed.  Still, it is almost
as likely to exhibit thrashing as the counter version (which I still
believe to be extremely rare).

|> >   Now I'm sure I don't understand what your design is, since an FSR can't
|> >   ...
|> I hope this is more clear now.

Yup.
-- 

...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!
Newsgroups: comp.arch