[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [f-cpu] Shifter, like during the good old days ;p



On Sun, Nov 04, 2001 at 05:20:27PM +0100, Yann Guidon wrote:
[...]
> > > i'd like to see a "textual" architectural description.
> > > The choice of an omega network looks curious to me.
> > Didn't you suggest that a while ago?
> I have analysed it a bit but the "routing" algorithm
> doesn't seem straightforward...

It's pretty simple, once you figure out how the bits move in each stage.
The bit index transformation is `x -> (x + p * N) / 2', or
`x -> 2 * x % N + q' in the other direction (where N is the number of
bits, and p and q are 0 or 1, depending on the source and/or destination
index).  That is, if you have 64 bits and want to route bit 17 to bit 23,
the sequence is (using the second formula):

	stage 1: 17 -> 2 * 17 % 64 + 0 = 34
	stage 2: 34 -> 2 * 34 % 64 + 1 =  5
	stage 3:  5 -> 2 *  5 % 64 + 0 = 10
	stage 4: 10 -> 2 * 10 % 64 + 1 = 21
	stage 5: 21 -> 2 * 21 % 64 + 1 = 43
	stage 6: 43 -> 2 * 43 % 64 + 1 = 23

Where I got the `q' values from?  Have a look at them...  if you take
them and write them in a row, you get 010111, which is decimal 23 --
the index of the destination bit (one can prove that this is always true,
no matter what the source index is).  It's slightly more complex in the
other direction, but we only need one direction in order to calculate
all the switch settings :)

> I preferred to investigate networks that allow better signal
> integrity on the wire. Think about it : Omega network stages
> have 2 wires that cross 1/2 of the shift circuit. This means
> that every stage adds a "worst case" latency (concerning the timing).
> I tried to find a simpler network where each stage is regular,
> even if the stages are not like each others.

A butterfly network, maybe?  It's functionally equivalent to an omega
net, but uses another layout.  I don't like it because the final stage
is *really* heavy -- in the last stage of the 64-bit version, there
are more lines crossing each other than in the whole 6-stage omega net.

The omega network uses the best wiring I've seen so far -- there are only
2976 crossing points (496 per stage; max. 31 / avg. 15.5 per individual
line, control lines and post-processing not counted), and no triple
crossings.

-- 
 Michael "Tired" Riepe <Michael.Riepe@stud.uni-hannover.de>
 "All I wanna do is have a little fun before I die"
*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/