[libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
bugzilla-daemon at libre-soc.org
bugzilla-daemon at libre-soc.org
Fri May 1 19:33:05 BST 2020
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.
More information about the libre-riscv-dev
mailing list