[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


--- 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...


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

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

* a 16-to-16 Lambda / Benes Network will have a random-to-random maximum
  of 50%
* a 64-to-64 Lambda / Benes Network will have a random-to-random maximum
  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
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. 
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