[libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=296

--- Comment #5 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to Yehowshua from comment #3)

> We don't need a full crossbar. We can use a strong-sense non-blocking benes
> network with a reconfiguration lookup table.
> 
> I can whip one up next week if you want. They use less gates than full
> crossbars...

http://homepages.inf.ed.ac.uk/cgi/rni/comp-arch.pl?Networks/benes.html,Networks/benes-f.html,Networks/menu-dyn.html

oh _that_!  yeah i did one for my 3rd year project in 1991, actually two
back-to-back
termed a "butterfly" network, and demonstrated that a permutation could be
solved
in O(log N + N) time with 100% throughput.  it did require that the inputs to
outputs
*be* a permutation, otherwise it would not complete the routing.  i ran out of
time
to investigate further.

Lambda Networks - what the Imperial College team working on the ALICE
Transputer
Network in conjunction with Plessey - and what has now the name "Benes
Networks" -
have the unfortunate property of reducing the throughput in an exponential
fashion,
when presented with arbitrarily-random source-to-destination requests.

* a 16-to-16 Lambda / Benes Network will have a random-to-random maximum
throughput
  of 50%
* a 64-to-64 Lambda / Benes Network will have a random-to-random maximum
throughput
  of 25%

and so on.

unless the data is particularly uniform (strictly controlled), it actually
gets pretty bad.

hence the reason why i investigated back-to-back Lambda / Benes Networks, which
fascinatingly have the property of providing *two* possible paths to each
destination, per bit-per-layer.  i used this property to cascade-solve a
permutation
and got 100% guaranteed routing.

however... it requires (A) a permutation and (B) close to double the amount of
actual gates and (C) a delay whilst solving the permutation.

yes, yehowshua, i've done a hell of a lot of stuff, in a lot of different areas
:)

wait... no, just looking at Figure 2: Figure 2 *is* what i came up with. 
sorry:
what Imperial College did in the ALICE Project was a *half* Benes Network (cut
that network in half down the middle).

Lambda Networks have exponential drop-off throughput characteristics (each
layer blocks other layers, in a cascade).  Benes Networks require double the
hardware of Lambda Networks, but the routing decision-making is... quite a
bit more complex, as there are always 2 paths.

-- 
You are receiving this mail because:
You are on the CC list for the bug.