Libre RISC-V Mailing list Archives (accessible via public-inbox)
 help / color / Atom feed
* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01 20:23 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

--- Comment #8 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Jacob Lifshay from comment #7)

> That's true for correctness, but not for performance. Delaying 20 cycles on
> every forwarding operation would seriously reduce the performance, probably
> by at least 10x, so, obviously, that should be avoided.

sorry, i meant, "delayed not deliberately but because the total bandwidth
(paths) between FU-result latches and FU-input latches is limited".

whether that path is via the regfile or via a forwarding bus doesn't matter:
if the forwarding bus isn't available for 5-10 cycles, there's always the
write-port on the regfile.

Mitch's analysis was, i believe, that we should expect a ratio of... what
was it... 1.3 reg reads to writes?  i.e. each result produced by one FU is
"consumed" by an average of 1.3 other FUs.

he noted that, therefore, even if the forwarding bus is used just once,
forwarding to just one other FU before the value is dropped on the floor,
in a cascade it actually saves a lot of regfile activity.

unfortunately, to reduce this regfile pressure assumes that you can detect
write-after-write and also "discards".  that *is* possible, however the
discussion was now over a year ago, and we simply haven't got time in
this round to make the necessary DM modifications.

so what we will gain with a forwarding bus is: decreased latency.  this because
with the register file being a bottleneck, even one extra bus (fwd) means that
some of the operations that would otherwise need to have waited for the write
(and followup read) through the regfile, instead may start that much earlier.

yes, ultimately: if access to that forwarding bus (which _will_ itself be
resource-contended) can be done early (same clock cycle, even), obviously that
latency is decreased much more.

summary: for a 6600-based DM system it's strongly desirable for the fwd
bus to be same (or 1 clock) cycle: it's not however a make-or-break mandatory
requirement.  for an in-order system, on the other hand, it's not only
far more difficult to *add* a forwarding bus, it is, if i recall correctly,
timing-critical.  i.e. the consequences of missing the slot are that the
entire pipeline (right the way back to issue) is forced to stall.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] Verilog book
From: Hendrik Boom @ 2020-05-01 20:08 UTC (permalink / raw)
  To: libre-riscv-dev

Springer is allowing a number of books to be downloaded for free during 
the Covid-19 pandemic.

I found the Quick Start to Verilog, in case anyone is interested:

https://link.springer.com/book/10.1007/978-3-030-10552-5

The main book list is at:
https://link.springer.com/search?facet-content-type=Book&package=mat-covid19_textbooks

-- hendrik


_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 298] New: consider using sum-addressed decoder in L1 cache (maybe also L1 I cache)
From: bugzilla-daemon @ 2020-05-01 19:17 UTC (permalink / raw)
  To: libre-riscv-dev

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

            Bug ID: 298
           Summary: consider using sum-addressed decoder in L1 cache
                    (maybe also L1 I cache)
           Product: Libre-SOC's first SoC
           Version: unspecified
          Hardware: All
                OS: All
            Status: CONFIRMED
          Severity: enhancement
          Priority: ---
         Component: Source Code
          Assignee: lkcl@lkcl.net
          Reporter: programmerjake@gmail.com
                CC: libre-riscv-dev@lists.libre-riscv.org
   NLnet milestone: ---

combines binary adder with address decoder, saving a few gate delays.
https://en.wikipedia.org/wiki/Sum-addressed_decoder
The patents appear to have expired.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01 19:12 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

--- Comment #7 from Jacob Lifshay <programmerjake@gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #6)
> (In reply to Jacob Lifshay from comment #2)
> > Seems like a good idea, however out-of-order (and in-order) processors
> > depend on single-cycle forwarding between the results of one operation and
> > the input of the next for most of their performance, the forwarding network
> > would need to keep that property (haven't fully thought through if this idea
> > keeps that property).
> 
> luckily, in a Dependency-Matrix-based system, nothing is timing-dependent.
> the DMs (the combination of the FU-Regs and FU-FU matrices) preserve a
> Directed Acyclic Graph of the relationships between all in-flight operations,
> based on the register numbers, *not* based on the time taken to completion
> *of* each operation, in any way.  FSMs, pipelines, async FUs,
> variable-pipelines,
> it's all the same to the 6600-DMs.
> 
> therefore (the point of explaining that is:) it doesn't _actually_ matter if
> the forwarding between result latches at the output side of the Function
> Units
> is delayed even 5-20 cycles in reaching the input latches of the FUs that
> need
> that result.

That's true for correctness, but not for performance. Delaying 20 cycles on
every forwarding operation would seriously reduce the performance, probably by
at least 10x, so, obviously, that should be avoided.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* Re: [libre-riscv-dev] sum-addressed decoder
From: Luke Kenneth Casson Leighton @ 2020-05-01 19:09 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAC2bXD7tkWQP7g8WosEuYSaw_Fwma9gqi7hCOmD1gEcOQwP1bg@mail.gmail.com>

On Friday, May 1, 2020, Jacob Lifshay <programmerjake@gmail.com> wrote:

> I found this interesting idea:
> https://en.wikipedia.org/wiki/Sum-addressed_decoder
> The patents appear to have expired.


"If the reader feels that this was an inordinate amount of brain-twisting
work for a three gate improvement in a multi-cycle critical path, then the
reader has a better appreciation for the level to which modern CPUs are
optimized."

hilarious :)

could you raise a bugreport for it, as a future enhancement? it would be
good to look at this later

l.



-- 
---
crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01 18:54 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

--- Comment #6 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Jacob Lifshay from comment #2)
> Seems like a good idea, however out-of-order (and in-order) processors
> depend on single-cycle forwarding between the results of one operation and
> the input of the next for most of their performance, the forwarding network
> would need to keep that property (haven't fully thought through if this idea
> keeps that property).

luckily, in a Dependency-Matrix-based system, nothing is timing-dependent.
the DMs (the combination of the FU-Regs and FU-FU matrices) preserve a
Directed Acyclic Graph of the relationships between all in-flight operations,
based on the register numbers, *not* based on the time taken to completion
*of* each operation, in any way.  FSMs, pipelines, async FUs,
variable-pipelines,
it's all the same to the 6600-DMs.

therefore (the point of explaining that is:) it doesn't _actually_ matter if
the forwarding between result latches at the output side of the Function Units
is delayed even 5-20 cycles in reaching the input latches of the FUs that need
that result.

btw in the original 6600, regfile read was done on the leading edge, regfile
write
was done on the falling edge.  this had the fascinating property that the
data coming in on a write could be available on the *same* clock cycle as a
read, effectively making the register file its own "Forwarding Bus".

anyway: unlike the 6600, we have a bit of a problem in that we cannot have
massive
register file porting.  the 6600's "A" regfile had *FIVE* read ports and *TWO*
write ports!

we are going to be under-ported because it's not really practical to design a
multi-ported (multi-write) SRAM in the time that we have (and their gate count
and power consumption is pretty high).  so, therefore, there will be quite a
few
times where data is generated faster than it can be written to the regfile.

therefore, operand-forwarding - even if it's a couple of cycles delayed - is
actually going to really important.

LOAD-STORE Computation Units, the LOAD in UPDATE mode can generate *two*
register writes.  fortunately, the ADDR-GEN side may be available one clock
cycle *before* the actual LOAD result.  however we need to plan for worst-case:
that the two are available simultaneously.

what we do *not* want to happen is that just because there is only 1W on the
regfile, the two writes from LOAD-UPDATEmode causes a bottleneck through the
regfile, when trying to get either of those two writes to the FunctionUnits
waiting for them.

therefore, if the cyclic buffer can forward at least one of those results
into the *read* cyclic buffer, then:

* one of the writes will go through the regfile and (if we design it
  right, a la 6600 regfile) *back* out through one of the read ports
  *on the same clock cycle*

* the other write will go through the end of the write cyclic buffer into
  the beginning of the read cyclic buffer, and if the Function Unit that
  needs that register happens to be RD1 (REQ_RD1 is asserted) it *will*
  get that result on the same clock cycle.

  if not, it will get it on the next clock (when shift-passed to RD2).

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01 18:33 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

--- Comment #5 from Luke Kenneth Casson Leighton <lkcl@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.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01 18:19 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

--- Comment #4 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
i believe it may be possible to use existing components for this: the
mask-cancellable Pipeline class (where the "mask" is the
GLOBAL_READ_PENDING_VEC
or GLOBAL_WRITE_PENDING_VEC) plus the multi-input pipe:

https://git.libre-soc.org/?p=nmutil.git;a=blob;f=src/nmutil/multipipe.py;h=95279250d005ecda96545c9ac3d5aec74ef4d082;hb=22bb7e4a3ec7d5f6139ed0bd427609af33ddafb3#l255

this allows input from multiple sources, and one of those input sources would
be the *other end* of the pipeline, thus creating a cyclic ring buffer that
has two key additional abilities:

1) the ability to "pause" the data being passed down the pipeline (without
   losing any data).  this because each stage is protected by ready/valid
   signals

2) the ability to "accept" extra data, from (multiple) other sources.

examples of (2) include an operand-forwarding capability.  this can be
implemented very simply: the output from the *write* cyclic buffer is connected
also to one of the multi-input ports on the *read* cyclic buffer!


  +------------------------------<-----------<-------+
  v                                                  ^
  |                                                  |
  +-- RD1 --> RD2 --> RD3 ---+    +-- WR1 --> WR2 ---+
  |                          |    |                  |
  ^                          v    ^                  v
  +------<-----------<-------+    +------<------<----+

if we have *multiple* of these cyclic buffers, split to deal with 32-bit
data in 4 banks (HI-32 ODD, LO-32 ODD, HI-32 EVEN, LO-32 EVEN) we can have
the appearance of up to 16R4W for 32-bit vector operations.

not only that, but "crossing over" between these 4 "lanes" is a simple
matter of putting additional inputs onto the front of the buffer.

i'm also going to recommend that we have at least two of these cyclic
buffers per regfile read/write bank.  this because, note:

* RD1 is *only* connected to the broadcast bus linked to all Function Unit's
  Reg-Read1.
* RD2 is *only* connected likewise to all FU's Reg-Read2
* etc.

and if a register was read by RD1 but is needed by RD2, we *have* to pass
it over to RD2 on the next clock cycle... but in doing so we *cannot do a
read on the regfile Port 2* on that next clock cycle, because the Cell for
RD2 is *already going to have data in it* (received from the cyclic shift
of data previously in RD1).

therefore, to solve this, i think we should have two rows.  this gives an
opportunity to always hit the regfile with multiple RDs in every clock cycle,
whilst still also being able to pass data over the broadcast bus(es) to any
listening FunctionUnits.

this does however mean that the columns need to collaborate.  there will be
*two* RD1 Cells vying for access to the Reg-Read1 Broadcast Bus.  there will
be *two* RD2 Cells vying for access to the Reg-Read2 Broadcast Bus.
fortunately, this just needs OR-gates (a 2-in 1-out MUX).

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 297] nmutil "flatten" function already exists
From: bugzilla-daemon @ 2020-05-01 14:35 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-297-13@https.bugs.libre-soc.org/>

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

Jacob Lifshay <programmerjake@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|lkcl@lkcl.net               |whitequark@whitequark.org
                 CC|                            |programmerjake@gmail.com,
                   |                            |whitequark@whitequark.org

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] sum-addressed decoder
From: Jacob Lifshay @ 2020-05-01 14:32 UTC (permalink / raw)
  To: Libre-RISCV General Development

I found this interesting idea:
https://en.wikipedia.org/wiki/Sum-addressed_decoder
The patents appear to have expired.

Jacob
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 216] LOAD STORE buffer needed
From: bugzilla-daemon @ 2020-05-01 13:33 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-216-13@https.bugs.libre-soc.org/>

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

--- Comment #31 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Luke Kenneth Casson Leighton from comment #30)

> the class is called "RippleLSB":
> https://git.libre-soc.org/?p=ieee754fpu.git;a=blob;f=src/ieee754/part_cmp/
> ripple.py;h=032512047f2e58c3ce50bc869e4a064738647943;
> hb=cec6f51e8b2a1ba2c2f83965be7219885ea163f0#l13
> 
> this can be moved to nmutil.

done

https://git.libre-soc.org/?p=ieee754fpu.git;a=blob;f=src/ieee754/part_cmp/ripple.py;hb=HEAD

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 297] New: nmutil "flatten" function already exists
From: bugzilla-daemon @ 2020-05-01 13:31 UTC (permalink / raw)
  To: libre-riscv-dev

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

            Bug ID: 297
           Summary: nmutil "flatten" function already exists
           Product: Libre-SOC's first SoC
           Version: unspecified
          Hardware: PC
                OS: Linux
            Status: CONFIRMED
          Severity: enhancement
          Priority: ---
         Component: Source Code
          Assignee: lkcl@lkcl.net
          Reporter: lkcl@lkcl.net
                CC: libre-riscv-dev@lists.libre-riscv.org
   NLnet milestone: ---

nmigen already has a flatten function:
from nmigen._utils import flatten

whether we can rely on that staying there needs to be investigated
with whitequark

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 216] LOAD STORE buffer needed
From: bugzilla-daemon @ 2020-05-01 13:27 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-216-13@https.bugs.libre-soc.org/>

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

--- Comment #30 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
https://www.youtube.com/watch?v=6Yiyw4abJpE

a walkthrough video which explains the components (the ones that
already exist) and explains what's needed.  crucially, the existing
components provide certain guarantees that, by the time it comes
to what the L0 Cache/Buffer has to do, is a ridiculously simple
job.

i forgot to mention: after the PriorityPicker, the "selection" of the
units which are "above" that first-picked row, we actually already
have some code which does that: michael wrote it, for the LE/GE/EQ
"PartitionedSignal" comparators.

the class is called "RippleLSB":
https://git.libre-soc.org/?p=ieee754fpu.git;a=blob;f=src/ieee754/part_cmp/ripple.py;h=032512047f2e58c3ce50bc869e4a064738647943;hb=cec6f51e8b2a1ba2c2f83965be7219885ea163f0#l13

this can be moved to nmutil.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* Re: [libre-riscv-dev] sun opensparc t2
From: Luke Kenneth Casson Leighton @ 2020-05-01 13:22 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAC2bXD4j4Ga=Z0n3b7QWMQ0C6FjxsZXHyeTt28H+G4=vJYuBEA@mail.gmail.com>

On Thu, Apr 30, 2020 at 11:50 PM Jacob Lifshay <programmerjake@gmail.com> wrote:

> the opensparc t2 is open source under the GPLv2, seems like it might be a
> useful reference.

really what we need, the immediate priorities are:

* the L0 cache/buffer
* a TLB (Radix) implementation to study (Paul Mackerras's microwatt
may be the first)
* a (long, important) discussion on how many ALU and LD/ST Comp Units to
  allocate, and how they should be connected to the register file(s).

these things stem from the requirements as a GPU/Hybrid OoO
multi-issue Vector-capable design with an augmented POWER front-end,
where we will run GNU/Linux OS workloads, and we're going for
single-core at the moment.  consequently there's unlikely to be much
we could use from it *right now*.

however looking at this:
http://fpga.ashishbanerjee.com/opensparc/t2-architecture

opensparc T2 apparently has some important characteristics which we
will need for the next version: L1 cache crossbar interconnect, and it
uses the opencores.org wishbone memory controller, which we should
definitely track down.

> it is a barrel processor, hence doesn't get very good single-threaded
> performance.

interesting...

l.

_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* Re: [libre-riscv-dev] load/store execution queue idea
From: Luke Kenneth Casson Leighton @ 2020-05-01 11:24 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAC2bXD7uY+dxiA1D5vSoNDVg=xtxgdHQk8DrDbB9nx5ZHbDHrg@mail.gmail.com>

On Fri, May 1, 2020 at 3:54 AM Jacob Lifshay <programmerjake@gmail.com> wrote:

> I filled out some notes on my load/store execution queue idea here:
> https://libre-soc.org/3d_gpu/architecture/alternative-design-idea/

excellent.

> The design should be suitable for the final 28nm SoC and should be
> able to execute 4 loads or 4 stores or 4 AMOs or 4 fences per cycle,
> completely adjustable to some other number if we desire. This totally
> replaces the memory dependency matrix.

hmm.   the MDM is specifically designed to identify separate and
distinct LD-batches from ST-batches from Atomic-batches, in an
extremely gate-efficient fashion.  we don't need TSO, we just need to
preserve the order of batches (and also identify overlaps).


> One downside is it doesn't
> support forwarding from stores to later loads without going through
> the L1 cache.

that's ok.

ok, a critical aspect to understand about Computational Units: they do
*not* proceed until the "purpose" that they manage is entirely finished.
they then *notify* the Dependency Matrices that the "result" is done
(available), and *then* they drop their "busy" flag, ready for re-use for
another operation.

this is the total opposite of a pipeline or queue, where you chuck data
at it, abdicate responsibility for its management, and at some arbitrary
point in the future, the result comes out, but by that time everything
has moved on.

an out-of-order scheduling system *cannot* - in any way - permit that
to happen.  the results would be catastrophic.

therefore in the ALU Computational Units which manage a pipeline
(or pipelines), we *must* have equal or greated CompUnits than
there is pipeline depth.

* greater than that is ok: instructions will be able to run ahead.
  the DESIRE to run instructions (and the order as a DAG) is
  recorded, however their ACTUAL execution must wait until
  there is a free pipeline slot.
* less than that is NOT really ok (a waste of silicon) because there
  is not enough to track the progress of each and every operation
  going through each and every pipeline stage.

when it comes to managing Memory, the implications are as follows:

* to have more LD/ST Computation Units than there are "Cells"
  is likewise ok.  instructions will be able to run ahead.
* to have LESS LD/ST CUs than there are "Cells" is *NOT* ok,
  because the ComputationUnits will NEVERRRRR issue a
  LD or ST until it knows - absolutely and without any shadow of
  doubt - that the operation it monitors has 100% absolute guaranteed
  completed.

so that's really crucial information that has implications for the
design of the LD/ST Buffer, important as context, below.


notes:

1) the cell arrangement still needs an 8-input (8 LD/ST Computation Units)
to 4-output (head of each "column" of each queue) multiplexer.
unless i've misunderstood, that alone is a killer.

dropping each of the 8-input queue entries into the first 8 cells *then*
performing shifting, *that* is okay.  but allowing each and every single
one of those 8 LD/ST CompUnits to write to cells 0-4? the wiring alone
is insane.

assume 128 bits per operation (48 address, 64 data, some control lines
let's round it up to 128 bits): with 128-wide data paths times 8 LD/ST
Comp Units times *4* to be able to arbitrarily write to any one of
4 "top row" cells?  that's a MASSIVE 4096 wires!

we can't possibly have that many wires.

if you meant that the queue width should match the number of LD/ST
Units - 8-wide because we need 8 LD/ST CompUnits (we might be
able to get away with only 6) - then the remaining entries will actually
remain permanently empty, because there *has* to be a direct
one-to-one match between LD/ST CompUnits and the LD/ST that
it "manages".

so there would only be 8 LD/STs, and a row depth of 1.

if however we do 2-ports per CompUnit (to cover misaligned), then there
would be an 8-wide by 2-row arrangement of Cells.

with only a Cell Depth of 1 or 2, the purpose *of* the Cells is defeated
entirely.  there's no need for shifting: the entries might as well stay
where they are.

this particularly because even for the "misalignment" case, the LD/ST
CompUnit is *NEVERRR* going to place anything other than the
2 requests it is responsible for into the queue:

* first one covering the lower part of the misaligned request
* second one covering the upper part.

no matter how many columns (assuming that there is one
per LDSTCU) all other rows *will* remain empty.

and if the columns are halved (4 wide to cover 8 LD/ST CUs)
now we have a much more serious problem: the total data bandwidth
is shrunk to only 4x 64-bit operations *and* there is a multiplexing
problem actually getting data into the first 2 rows (actually, now,
4 rows if there are 2 ports per LD/ST CU, one for lower-misaligned
one for upper-misaligned).

do we stall the requests if they do not have access?  that means
that opportunities to keep the L1 cache-line requests 100% full
are missed, where the current design can *even catch misaligned
element-strided data requests* and can 100% merge them into
a full cache-line request.



"and the L1 cache line address it would use is broadcast to all cells."

this is a full XOR-comparison of the entire address, against every single cell.

if the address is 48 bits and there are 12 cells, using bits 3 and above of
the address will require 528 XOR gates.

if we want *two* L1 cache line addresses simultaneously (rather than
going to 256-bit-wide L1 cache lines), that's *two* broadcasts, each 528
XOR gates.


2) how are overlapping addresses detected?  or, more to the point,
how are non-overlapping addresses detected such that they can be
passed through as a group, and given the opportunity to be done in
parallel?

3) how would misaligned addresses handled?

4) i'm not seeing how requests could be merged into "100% full cache
line" requests, which the current design is capable of doing, by using
simple bit-wise ANDing and ORing.  the Abstract Prefix Sum class
doesn't look obvious as to how that happens, and is likely to be
much more costly than a simple AND and OR network.

5) how are clashes of addresses *inter-row* detected?  if Cell 0 has a ST
of 8-bits to address 0x0001 and Cell 1 has a ST of 8 bits to address
0x0002 (a 7 byte overlap), how is this detected *in the row*?

in the column it is fine, because only one row is ever done at once
(which has implications for mis-aligned data requests, there will never
be a 100% merge opportunity)


all of these things took several *months* to factor in to the design, in
several stages.  it's massively complex and inter-dependent.

l.

_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01  5:03 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

Yehowshua <yimmanuel3@gatech.edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |yimmanuel3@gatech.edu

--- Comment #3 from Yehowshua <yimmanuel3@gatech.edu> ---
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...

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01  3:02 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

Jacob Lifshay <programmerjake@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |programmerjake@gmail.com

--- Comment #2 from Jacob Lifshay <programmerjake@gmail.com> ---
Seems like a good idea, however out-of-order (and in-order) processors depend
on single-cycle forwarding between the results of one operation and the input
of the next for most of their performance, the forwarding network would need to
keep that property (haven't fully thought through if this idea keeps that
property).

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] load/store execution queue idea
From: Jacob Lifshay @ 2020-05-01  2:53 UTC (permalink / raw)
  To: Libre-RISCV General Development

I filled out some notes on my load/store execution queue idea here:
https://libre-soc.org/3d_gpu/architecture/alternative-design-idea/

The design should be suitable for the final 28nm SoC and should be
able to execute 4 loads or 4 stores or 4 AMOs or 4 fences per cycle,
completely adjustable to some other number if we desire. This totally
replaces the memory dependency matrix. One downside is it doesn't
support forwarding from stores to later loads without going through
the L1 cache.

There's also a section on generalizing the carry look-ahead networks
to be usable for any associative binary operation (the prefix-sum
section).

Jacob

_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01  2:10 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

Luke Kenneth Casson Leighton <lkcl@lkcl.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
    NLnet milestone|---                         |NLnet.2019.02

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01  2:10 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-296-13@https.bugs.libre-soc.org/>

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

--- Comment #1 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
an idea for a cyclic hopper:

here is an 

https://groups.google.com/d/msg/comp.arch/qeMsE7UxvlI/6nvrtmBoAQAJ

> Since you separated the signals, can I suggest placing a hopper between 
> reading register specifiers out of FUs and the RF ports. Each cycle a 
> number of specifiers are dropped into the hopper, and each cycle as many 
> RF read ports as you have are read and then delivered to instructions 
> at the calculation units. Then each calculation unit picks instructions 
> into execution. 

*sigh* unfortunately we are a little bit hamstrung by having lost the register 
binary indices, using instead the Dependency Matrix unary encoding to 
directly enable the regfile row.  i mean, we _could_ use the unary encoding 
as the register specifier... 

by "hopper" do i take it that you mean a cyclic shift register where each 
bucket contains the register specifier, type of operation (R/W), and, say, the
FU 
number? 

or, actually, if the register specifier is in unary... 

oo i have an idea.  it may well be the same idea. 

* for all registers being requested by all FUs, merge the unary register
indices 
   into a single "these registers need to be read" vector.  i think, in fact,
that 
   the Dependency Matrices might actually have this already (Read Vector 
   and Write Vector Pending) 

* for reads, throw that vector at a regfile "fetcher", which, using the read
vector, 
  simply fetches as many registers as there are available regfile ports 

  let's say that there are 4R regfile ports 

* the 4 read results, along with a *single* bit unary encoding of their
corresponding 
  reg number, are dropped into a cyclic 4-wide buffer (cyclic 4-wide shift reg) 

* all FUs "GoRead1" are connected to port 1 of the cyclic buffer 
* all FUs "GoRead2" are connected to port 2... 
* ............GoRead3 ..... 3 

* entries *remain* in the cyclic buffer for as long as the corresponding bit in
the 
   Read Vector remains set, continuing to cycle through, moving from port 1 to 
   2, 2 to 3, 3 to 4, 4 back to 1, on each clock 

* on any given clock cycle, *all* FUs may read that "broadcasted" entry from
their 
   corresponding cyclic buffer "hopper", as long as the unary reg index matches
up 

* when the reg index matches up, GO_RD1/2/3 is fired at that FU. 

* when the FU has read from that port, it may drop the REQ_RD1/2/3 

* this results in the (usual) dropping of the unary bit from the Read Vector
back at 
   the Dependency Matrix 

* this in turn also triggers the cyclic buffer to drop the reg value, freeing
up that 
   port for a refill opportunity. 

it's by no means perfect: the cyclic buffer moving only one value at a time
means 
that if an FU has 3 GO_RD/REQ_RD lines, it could have to wait for up to 3
cycles 
for the data to cycle round the shift-buffer... *per read-register*. 

if however a concerted effort is made to ensure that a REQ_RD1 always tries to
drop 
the read-request into cyclic-buffer entry 1, REQ_RD2 always tries to drop into
entry 2 
and so on, then the reads should just pass straight through. 

this does have the advantage that if there are multiple FUs waiting for the
same 
register, then as a "broadcast" bus system, they can in fact get the same value 
simultaneously. 

writes are very similar, and there is the additional advantage that the written
value 
can be read from the cyclic buffer by any FU that "sees" it, prior to the value
landing 
at the actual regfile. 

thus the cyclic buffer also happens to serve double-duty as a forwarding bus. 
or, 
more to the point, the role and distinction between "register bus" and
"forwarding 
bus" is now decoupled / moot. 

was that sort-of what you meant by "hopper"? :) 

l.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 296] New: idea: cyclic buffer between FUs and register file
From: bugzilla-daemon @ 2020-05-01  2:09 UTC (permalink / raw)
  To: libre-riscv-dev

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

            Bug ID: 296
           Summary: idea: cyclic buffer between FUs and register file
           Product: Libre-SOC's first SoC
           Version: unspecified
          Hardware: PC
                OS: Mac OS
            Status: CONFIRMED
          Severity: enhancement
          Priority: ---
         Component: Source Code
          Assignee: lkcl@lkcl.net
          Reporter: lkcl@lkcl.net
                CC: libre-riscv-dev@lists.libre-riscv.org
   NLnet milestone: ---

the issue that we have is that multiplexing between a dozen FUs with multiple
read/write ports, and the available regfile read/write ports, does not quite
match up.  full crossbars are completely impractical.

we therefore need something that allows FUs to receive / send values, without
a complete overload of wiring or muxes.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] sun opensparc t2
From: Jacob Lifshay @ 2020-04-30 22:50 UTC (permalink / raw)
  To: Libre-RISCV General Development

the opensparc t2 is open source under the GPLv2, seems like it might be a
useful reference.
it is a barrel processor, hence doesn't get very good single-threaded
performance.

Jacob
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 295] pay attention to these insights
From: bugzilla-daemon @ 2020-04-30 22:44 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-295-13@https.bugs.libre-soc.org/>

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

--- Comment #1 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
from mitch alsup
----------------

On Thursday, April 30, 2020 at 11:59:17 AM UTC-5, BGB wrote:


> But, don't know if I am doing well enough at this.
> Did recently encounter some people online who balked at the idea of
> including any VLIW-like aspects in an ISA, having the opinion that VLIW
> is worthless and evil, ...

It would not help their point of view to tell them that microcode is VLIW.
>
>
>
> Apparently, the commercial failure of Itanium has soiled some people as
> to the possibility that there could be *any* merit of using some
> similar-sounding ideas in small embedded systems, they can't seem to
> help but imagine everything in terms of things trying to compete with
> modern x86 PC's or Xeons...
> The premise that someone might make a VLIW and then hope to have it be
> competitive against lower end ARM processors or microcontrollers seems
> alien to them.
>
> I guess the question is "does it make sense from a resource cost POV?",
> eg, a small VLIW competing in terms of resource cost and performance
> with a 2-wide in-order superscalar or similar.
>
> My guess is that a 2-wise superscalar could be doable on an FPGA, but
> may involve adding another pipeline stage, and probably adding a bit to
> branch latency (since now the PC advance can't be figured out until a
> later stage in the pipeline, such as ID2 or similar).

When one notices that, in general, we have::
a) 1 branch every 5 instructions, and 1 taken branch every 7.1 instructions
b) 1 load every 5 instructions
c) 1 store every 10 instructions
AND one has an instruction buffer where one FETCHes 4 instructions (wide)
and DECODEs out of that buffer::

a) branches do not deliver a result to the RF (rather to the IP)
b) stores do not write a result
So one should be able to get about 1.3 IPC from a 3R1W register file
(minus latencies and dependencies).
1.4× is about what a 2-wide superscalar IO machine.
So, we can get 80% of the gain of a 2-wide over a 1-wide by simply
CoIssuing BRs and STs with other instructions!

Now, given that we are FETCHing 4-wide, and we can decode the length of
the instruction in 4 gates of delay, we can identify branches in the
buffer far in advance of DECODEing the BR and we have time to FETCH the
target so it arrives without delay compared to BR entering execution.

So, CoIssue buys 30% and lookahead branches buys another 10%, we are
within spitting distance of a 2-wide SS machine while paying only a bit
more cost than a 1-wide machine--and we have not even added ports to the
RF yet!
>
> Or maybe have the PC advance work conservatively (*) and then use
> additional decoders to deal with the possibility that an operation may
> need to be skipped during ID2?...

That, too is possible for a 2%-4% gain.

>
> *: Will normally assume advancing 1 instruction at a time, but then be
> advanced after-the-fact by "how many instructions were actually
> executed". Fetch would then be the current (accurate) PC + 1 or 2
> instructions. ( Dunno; not actually implemented a proper superscalar yet.

Done in binary, this is medium hard, done in unary it is not.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 295] New: pay attention to these insights
From: bugzilla-daemon @ 2020-04-30 21:52 UTC (permalink / raw)
  To: libre-riscv-dev

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

            Bug ID: 295
           Summary: pay attention to these insights
           Product: Libre-SOC's first SoC
           Version: unspecified
          Hardware: PC
                OS: Linux
            Status: CONFIRMED
          Severity: enhancement
          Priority: ---
         Component: Source Code
          Assignee: lkcl@lkcl.net
          Reporter: lkcl@lkcl.net
                CC: libre-riscv-dev@lists.libre-riscv.org
   NLnet milestone: ---

https://groups.google.com/d/msg/comp.arch/leXwF1j7Z-A/VO99Gd55AwAJ

this is just a spectacularly insightful set of optimisations that
give huge improvements in IPC without needing a lot of infrastructure

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

* [libre-riscv-dev] [Bug 216] LOAD STORE buffer needed
From: bugzilla-daemon @ 2020-04-29 21:42 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <bug-216-13@https.bugs.libre-soc.org/>

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

--- Comment #29 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
jacob on looking at minerva they did something which i think would be really
useful to copy.

they created "cacheless" memory classes and "cached" versions conforming to the
same interface.

this allows an incremental approach where testing of one component is not
critically dependent on another that hasn't been written yet.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

^ permalink raw reply

page:   latest

Libre RISC-V Mailing list Archives (accessible via public-inbox)

Archives are clonable: git clone --mirror https://inbox.libre-soc.org/libre-riscv-dev

Example config snippet for mirrors


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git