* [libre-riscv-dev] [Bug 314] Create Condition Register pipeline
From: bugzilla-daemon @ 2020-05-16 19:30 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-314-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=314
--- Comment #11 from Michael Nolan <mtnolan2640@gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #9)
> ugh, ugh.
>
> i have a horrible feeling about "undefined" behaviour. we need to properly
> investigate and find out exactly what happens during that "undefined"
> behaviour by running native assembler on the TALOS-II workstation, with
> a full range of FXM bits (only 256 instructions), and a random set of
> CR and RS (times 256).
>
> this will tell us exactly what happens.
Could you send me the login for the talos server so I can test this?
--
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 314] Create Condition Register pipeline
From: bugzilla-daemon @ 2020-05-16 20:07 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-314-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=314
--- Comment #12 from Michael Nolan <mtnolan2640@gmail.com> ---
# NOTE: we really should be doing the field decoding which
# selects which bits of CR are to be read / written, back in the
# decoder / insn-isue, have both self.i.cr and self.o.cr
# be broken down into 4-bit-wide "registers", with their
# own "Register File" (indexed by bt, ba and bb),
# exactly how INT regs are done (by RA, RB, RS and RT)
# however we are pushed for time so do it as *one* register.
We can do this for crand and friends, as well as mcrf, but it doesn't work for
mtcrf or mfcr because they can read or write the whole cr register
--
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] Scoreboard vs Tomasulo
From: Jeremy Singher @ 2020-05-16 20:16 UTC (permalink / raw)
To: Libre-RISCV General Development
In-Reply-To: <CAPweEDx_TMOxQHLrhbdhnXsBE1s-u2mz3xD2DDFCMi6m9BZCZg@mail.gmail.com>
> However, the scoreboard is limited in that it does not handle WAR and WAW
> hazards very well.
> the original 6600 handles WAR extremely well, only stalling on WaW
> condition, detection which did not matter greatly because the pipelines
> were only at most 2 stages long anyway (Mitch only noticed after rereading
> last year that the FP ADD of the 6600 was 2 stage pipelined. no academic
> literature has acknowledged or noticed this).
I would argue that the CDC6600 handles WAR better than an in-order
machine, but not better than a machine with full renaming. In the
CDC6600, the scoreboard would block the completion of the W inst until
the R inst has read its operands. In Tomasulo, the W inst can proceed
immediately before the R inst is ready, since the destination register
is physically renamed.
> ROB is a CAM,
What? This is not true. Instructions in flight track their index in
the ROB, at completion, they write success bit according to the index
they have. Not a CAM. Simple addressed write.
> given that Intel processors use Tomasulo, we start to see why Intel
> processors suck so much power.
Power consumption on a processor is primarily from high switching
rates on large register files, and SRAM leakage. The scheduling logic
is a miniscule portion. Intel cores are power-hungry because
historically they have targeted the desktop/workstation market, and do
not have as many decades of experience as other firms optimizing for
power-constrained environments.
Also almost all modern OOO cores use Tomasulo because Tomasulo is
better at avoiding false hazards compared to scoreboarding. Tomasulo
also makes it easier to implement precise traps, something which is
notoriously challenging with just a scoreboard.
Lets be clear here. The CDC6600 AVOIDS WAR and WAW hazards by BLOCKING
younger instructions (See pg3 in Mitch Alsup's text). Tomasulo's
supports OOO execution PAST WAR and WAW hazards, enabling the core to
exploit more ILP across its functional units.
Luke, I agree with you that the reservation station rows in Tomasulo's
can be equivalent to the operand latches in Scoreboarding. However,
adding many operand-latches (by having many functional units) does not
scale as nicely as just adding a few more rows to Tomasulo's
reservation stations. Especially since designing the CAMs for
Tomasulo's is a well studied, and well-understood problem
> 3. Expand the number of RSes so that if you were to count the total number
> of places operands are stored, they are the same.
> (another way to put this is, "flatten all 2D RSes into 1D")
This does not scale well. A 2D CAM is far more area efficient than a
1D flattened vector.
> 7. rename RSes to "Function Units" (actually in Thornton's book the phrase
> "Computation Units" is used)
So a Tomasulo's design with 4 rows now becomes a "flattened" design
with 4 functional units? The additional cost of the functional units
is enormous.
On Sat, May 16, 2020 at 10:33 AM Luke Kenneth Casson Leighton
<lkcl@lkcl.net> wrote:
>
> On Saturday, May 16, 2020, Yehowshua <yimmanuel3@gatech.edu> wrote:
>
> > This is a very intricate and complicated subject matter for sure.
>
>
> yes, except it doesn't have to be. the actual
> https://en.wikipedia.org/wiki/Levenshtein_distance between Tomasulo and
> 6600 really is not that great.
>
> i thought it would be fun to use a new unpronounceable word i learned
> yesterday :)
>
>
> > At some point, it be great to really break things down and make them more
> > accessible.
>
>
> yes. it comes down to time.
>
> start with this.
>
> 1. Begin from Tomasulo. neither TS nor original 6600 have precise
> exceptions so we leave that out for now.
>
> 2. Start by only allowing one row per Reservation Station.
>
> 3. Expand the number of RSes so that if you were to count the total number
> of places operands are stored, they are the same.
>
> (another way to put this is, "flatten all 2D RSes into 1D")
>
> 4. where pipelines were formerly connected exclusively to one RS,
> *preserve* those connections even though the rows are now 1D flattened.
>
> (another way to put this is: we have a global 1D naming scheme to reference
> the *operand latches* rather than a 2D scheme involving RS number in 1
> dimension and the row number in the 2nd)
>
> 5. give this 1D flattening an UNARY numbering scheme.
>
> 6. make the size of the Reorder Buffer EXACTLY equal to the number of 1D
> flattened RSes.
>
> 7. rename RSes to "Function Units" (actually in Thornton's book the phrase
> "Computation Units" is used)
>
> thus, at this point in the transformation, the ROB row number *IS* the
> Function Unit Number, the need to actually store the ROB # in the
> Reservation Station Row is REMOVED, and consequently the Reservation
> Stations are NO LONGER A CAM.
>
> 8. give all register file numbers (INT FP) an UNARY numbering.
>
> this means that in the ROB, the CAM, which has to look up the register
> number by hitting the CAM on every cycle, now only has to match a single
> AND gate.
>
> bitvectors therefore replace CAMs.
>
> with the ROB now having rows of bitvectors, it is now termed a "Matrix".
>
> the left side of the ROB, which used to contain the RS Number in unary, now
> contains a *bitvector* Directed Acyclic Graph of the FU to FU dependencies,
> and is split out into its own Matrix.
>
> this we call the FU-FU Dependency Matrix.
>
> the remainder of the "ROB" contains the register numbers in unary Matrix
> form, and with each row being directly associated with a Function Unit, we
> now have an association between FU and Regs which preserves the knowledge
> of what instruction required which registers, *and* who will produce the
> result.
>
> this we call the FU-Regs Dependency Matrix.
>
> that *really is it*.
>
> take some time to absorb the transformation which not only preserves
> absolutely every functional aspect of the Tomasulo Algorithm, it
> drastically simplifies the implementation, reduces gate count, reduces
> power consumption *and* provides a strong foundation for doing arbitrary
> multi-issue execution with only an O(N) linear increase in gate count to do
> so.
>
>
> further hilariously simple additional transformations occur to replace
> former massive resource constrained bottlenecks, due to the binary
> numbering on both ROB numbers and Reg numbers, with simple large unary NOR
> gates:
>
> * the determination of when hazards are clear, on a per register basis, is
> a laughably trivial NOR gate across all columns of the FU-REGs matrix,
> producing a row bitvector for each read register and each write register.
>
> * the determination of when a Function Unit may proceed is a laughably
> trivial NOR gate across all *rows* of the *FU-FU* Matrix, producing a
> row-based vector, determining that it is "readable" if there exists no
> write hazard and "writable" if there exists no read hazard.
>
> * the Tomasulo Common Data Bus, formerly being a single chokepoint
> binary-addressing global Bus, may now be upgraded to *MULTIPLE* Common Data
> Buses that, because the addressing information about registers is now in
> unary, is likewise laughably trivial to use cascading Priority Pickers (a
> nmigen PriorityEncoder and Decoder, back-to-back) to determine which
> Function Unit shall be granted access to which CDB in order to receive (or
> send) its operand (or result).
>
> * multi-issue as i mentioned a few times is an equally laughably trivial
> matter of transitively cascading the Register Dependency Hazards (both read
> and write) across future instructions in the same multi issue execution
> window. instr2 has instr1 AND instr2's hazards. instr3 has instr1 AND
> instr2 AND instr3's hazards and so on. this just leaves the necessity of
> increasing register port numbers, number of CDBs, and LD/ST memory
> bandwidth to compensate and cope with the additional resource demands that
> will now occur.
>
> the latter is particularly why we have a design that, ultimately, we could
> take on ARM, Intel, and AMD.
>
> there is no reason technically why we could not do a 4, 6 or 8 multi issue
> system, and with enough Function Units and the cyclic buffer system (so as
> not to require a full crossbar at the Common Data Buses), and proper
> stratification and design of the register files, massive Vector parallelism
> at the pipelines would be kept fully occupied without an overwhelming
> increase in gates or power consumption that would normally be expected, and
> scalar performance would be similarly high as well.
>
> 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
_______________________________________________
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 314] Create Condition Register pipeline
From: bugzilla-daemon @ 2020-05-16 20:30 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-314-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=314
--- Comment #13 from Michael Nolan <mtnolan2640@gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #9)
> ugh, ugh.
>
> i have a horrible feeling about "undefined" behaviour. we need to properly
> investigate and find out exactly what happens during that "undefined"
> behaviour by running native assembler on the TALOS-II workstation, with
> a full range of FXM bits (only 256 instructions), and a random set of
> CR and RS (times 256).
>
> this will tell us exactly what happens.
Qemu seems to do nothing when it's not onehot
lis 1, 0xdead
ori 1, 1, 0xbeef # r1 = 0xdeadbeef
lis 2, 0x1234
ori 2, 2, 0x5678 # r2 = 0x12345678
mtcr 1 # cr = 0xdeadbeef
mtcrf 0xf, 2
mfcr 3 # r3 should be 0xdead5678
mtcr 1 # cr = 0xdeadbeef again
# mtocrf 0xf, 2
.byte 0x7c, 0x50, 0xf1, 0x20
mfcr 4 # who knows
(gdb) p/x $r3
$1 = 0xdead5678
(gdb) p/x $r4
$2 = 0xdeadbeef
--
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] Introduction and Questions
From: Jeremy Singher @ 2020-05-16 20:34 UTC (permalink / raw)
To: Libre-RISCV General Development
In-Reply-To: <7c84f530-fc12-0f4e-8a1c-7e58a1b498c3@fibraservi.eu>
> Ok after some reflection I do see the most possible performance
> difference in procedures calls. Most of the time in procedures some
> scratch registers are pushed on the stack at entering.
Its actually a performance difference on more cases than this. In the
case of W R W R sequence to the same register, the second Write should
be allowed to proceed before the first Write is executed, which also
unblocks the second R.
On Sat, May 16, 2020 at 4:31 AM Staf Verhaegen <staf@fibraservi.eu> wrote:
>
>
> Op 16/05/2020 om 11:47 schreef Staf Verhaegen:
> > Jeremy Singher schreef op vr 15-05-2020 om 16:49 [-0700]:
> >>
> >> Hmmm, ignoring WAW will significantly limit the ability of the core to
> >> exploit ILP, which is one of the fundamental reasons for going OOO.
> > I've wondered about this myself. Can you give concrete example of where
> > not supporting a WAW hazard blocks ILP ?
> > I am asking because just a WAW hazard could be easily avoided by a good
> > peep hole optimizer in software because it would see that the output of
> > the first write is never used.
>
> Ok after some reflection I do see the most possible performance
> difference in procedures calls. Most of the time in procedures some
> scratch registers are pushed on the stack at entering.
>
> Assume a write to a scratch register is still pending when doing a
> procedure. With real register renaming the register stack push does not
> need to block until write to register is complete, if it doesn't the
> register push will block.
>
> The question is special hardware provision need to be done to optimize
> this case or if one would rely on proper inlining of functions by the
> compiler for performance critical code. Personally I don't see a problem
> with relying on the latter.
>
> greets,
> Staf.
>
>
> _______________________________________________
> libre-riscv-dev mailing list
> libre-riscv-dev@lists.libre-riscv.org
> http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev
_______________________________________________
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] daily kan-ban update 16may2020
From: Cole Poirier @ 2020-05-16 20:46 UTC (permalink / raw)
To: Libre-RISCV General Development; +Cc: Libre-RISCV General Development
In-Reply-To: <CAPweEDz563y3MB-Bd+BoH8Cv6uOP8BWzrjwiZpzig5VezMd55A@mail.gmail.com>
Yesterday I made my first attempt at implementing the bperm instruction
(function unit?), with significant help from Luke and Yehowshua. Luke
has left me TODOs to fix on the file bperm.py. I have done a git pull,
and I am now going to edit bperm.py to bring it up to spec with Luke's
corrections.
_______________________________________________
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 21:15 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
--- Comment #16 from Cole Poirier <colepoirier@gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #15)
> i've put a stack of TODO comments in for you. always remember to "git pull"
> before doing any editing. keep people informed what you are doing,
> "i am going to edit this file, now" for example, because this will help you
> to avoid edit-conflicts (because the other person knows to coordinate with
> you).
>
> for example, if you had fixed the thing in the previous comment *without*
> a "git pull", committed it, *then* tried "git pull" you would now have
> a conflict to resolve, because you edited the exact same line that i had
> also edited.
>
> we will soon see if you are checking the bugtracker and reading all
> comments... :)
Thank you for the very helpful TODOs Luke. I think I've made the necessary
changes, and the graph looked quite different as a made each change. Especially
the first one, as prior to that as you had noted I had neglected to 'connect' a
key component.
```
for i,n in enumerate(signals):
- n.eq(self.rb[i])
+ m.d.comb += n.eq(self.rb[i])
```
I have committed the changes. Now I am going to go over Robert Baruch's nmigen
tutorials and search out resources on writing unit tests, and formal proofs for
hardware. Then I will attempt to write an appropriate unit test for this class.
--
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] Scoreboard vs Tomasulo
From: Luke Kenneth Casson Leighton @ 2020-05-16 21:37 UTC (permalink / raw)
To: Libre-RISCV General Development
In-Reply-To: <CAEoCstRd+hLfF5YtUbnS2gukPxVAjmheJrZ29QvJD3y4Y928JQ@mail.gmail.com>
On Sat, May 16, 2020 at 9:16 PM Jeremy Singher <thejsingher@gmail.com> wrote:
> > However, the scoreboard is limited in that it does not handle WAR and WAW
> > hazards very well.
>
> > the original 6600 handles WAR extremely well, only stalling on WaW
> > condition, detection which did not matter greatly because the pipelines
> > were only at most 2 stages long anyway (Mitch only noticed after rereading
> > last year that the FP ADD of the 6600 was 2 stage pipelined. no academic
> > literature has acknowledged or noticed this).
>
> I would argue that the CDC6600 handles WAR better than an in-order
> machine, but not better than a machine with full renaming.
Jeremy: 6600 designs *do* have register "renaming". i said already,
a number of times. and if you have studied and listened to the Academic
literature - and believe it - you are misinformed by that literature, and will
continue to be misinformed by that literature.
please understand: i have spent over nine months studying this, learning
from Mitch Alsup, one of the world's leading high-performance computing
architects, implementing this and it's not going to get chucked out to
implement something that takes six MONTHS to fully understand is a
better design, to be replaced by something that would take another six
months to implement *and we then could not do multi-issue on top of it*.
please therefore take the time to understand this design, particularly when
we are right in the middle of a time-critical deadline.
> In the
> CDC6600, the scoreboard would block the completion of the W inst until
> the R inst has read its operands. In Tomasulo, the W inst can proceed
> immediately before the R inst is ready, since the destination register
> is physically renamed.
Jeremy: the "renaming" carried out by the 6600 does exactly this same
job.
Academics unfortunately have *only* studied the *patent* - not Thornton's
book nor read Mitch Alsup's book chapters which he wrote based on 30+
years experience of implementing 6600-style execution in the 88100,
AMD K9 and AMD Opteron Series of CPUs.
the 6600 patent *ONLY* covers the Q-Tables.
the description of the Q-Tables does *NOT* include the Computation Units
where the operand latches are.
these latches *ARE* the "renamed registers" (actually, nameless registers).
> > ROB is a CAM,
>
> What? This is not true. Instructions in flight track their index in
> the ROB, at completion, they write success bit according to the index
> they have. Not a CAM. Simple addressed write.
ah appreciated the correction. i knew there were CAMs somewhere.
when i discovered that, i dropped further investigation.
i am however aware that if you wish to do multi-issue, the ROB will need
to be multi-ported SRAM. without multi-porting the SRAM, you simply
cannot write multiple entries.
this is where the problems (read: nightmares) for Tomasulo start to manifest,
and progress from there through multiple Common Data Bus channels into
multi-ported (NxR, NxW) CAMs at the Reservation Station level.
i've been through this, ok, over 18 months ago.
by contrast, when converted to single-bit unary vectors, each entry in the
Matrices (covered by a single SR NAND latch) is *independent*. multiple
of those may be set in a single cycle.
there has been a *massive* amount of thought gone into this, ok?
> > given that Intel processors use Tomasulo, we start to see why Intel
> > processors suck so much power.
>
> Power consumption on a processor is primarily from high switching
> rates on large register files, and SRAM leakage.
given that we're planning around 28 Function Units and have a 128-entry
register file, the calculations that i did for that would put the Dependency
Matrices around a whopping 50,000 gates, using SR NAND Latches.
(if we did it as DFFs it would be an unacceptable 250,000 gates)
> The scheduling logic is a miniscule portion.
not for the large-scale out-of-order systems that we are planning to
do, it's not,
due to the large sized GPU register file (128 entries. actually 2x
128 - 128 FP,
128 INT).
we may have to *down*-scale via a regfile cache to cope with that.
discussion for another time.
> Intel cores are power-hungry because
> historically they have targeted the desktop/workstation market, and do
> not have as many decades of experience as other firms optimizing for
> power-constrained environments.
appreciated the insight.
> Also almost all modern OOO cores use Tomasulo because Tomasulo is
> better at avoiding false hazards compared to scoreboarding.
in the versions of scoreboards implemented by academics - because they
fail to comprehend them properly - because they only read the patent
on Q-Tables - yes.
in the version that Mitch Alsup - a world leading expert on Scoreboard
Mechanics - taught me:
no.
also, the IIT Madras RISE Group Shakti E-Class processor is *also* a
scoreboard design. this was designed "from first principles" by Professor
Kamatoti, and it was only through learning from Mitch that i was able
to recognise what he had done as being identical to a 6600 scoreboard.
> Tomasulo
> also makes it easier to implement precise traps, something which is
> notoriously challenging with just a scoreboard.
no it is not. this is *yet again* complete factual misinformation and ignorance
from Academic literature.
can i ask: have you read Patterson's book? this is the usual place where
most people get their misinformation from. the release of this misinformation
was why Mitch Alsup - a very pissed-off and exasperated Mitch - wrote those
two chapters, back around... 2008 (i think).
precise exceptions, traps, interrupts, branch speculation and predication may
all be achieved through "shadowing". see the latter part of the 2nd chapter of
Mitch's book.
see the section "Shadowing" in this page:
https://libre-soc.org/3d_gpu/architecture/6600scoreboard/
it's very simple: you hold write until such time as the opportunity for "damage"
is cleared. Operand Forwarding allows instructions to run ahead, using results
that would otherwise have to be received only first by going through
the Regfile.
*this is already implemented* and the unit tests demonstrated it as
*fully functional*
> Lets be clear here. The CDC6600 AVOIDS WAR and WAW hazards by BLOCKING
> younger instructions (See pg3 in Mitch Alsup's text). Tomasulo's
> supports OOO execution PAST WAR and WAW hazards, enabling the core to
> exploit more ILP across its functional units.
this is only because the 1965 CDC6600 did not have an Operand Forwarding Bus
(instead it used the regfile as a same-clock forwarding bus, by reading on one
edge and writing on the other. this unfortunately meant that without an OpFwd
Bus, stall had to occur).
this DOES NOT INHERENTLY MEAN that **ALL** Scoreboards are rubbish.
if you add an Operand Forwarding Bus (equivalent to the CDB in Tomasulo)
the exact same parity functionality is achieved (without the severe downsides).
> Luke, I agree with you that the reservation station rows in Tomasulo's
> can be equivalent to the operand latches in Scoreboarding. However,
> adding many operand-latches (by having many functional units) does not
> scale as nicely as just adding a few more rows to Tomasulo's
> reservation stations.
this is incorrect. you may be under the mistaken impression that the pipelines
duplicated as well. this clearly would be inadviseable because the FU's job
is to serve one and only one result. therefore you know that this is a mistaken
understanding, and that consequently you have multiple FUs for the same
pipeline. (termed "Concurrent Computation Unit").
therefore it's minimal. excluding the latches themselves (the rows
have latches, the
CompUnits - aka FunctionUnits have latches, the total number of latches after
flattening is the same), the number of gates added by each CompUnit is
minimal: around... 80, maximum.
that's peanuts.
> Especially since designing the CAMs for
> Tomasulo's is a well studied, and well-understood problem
the key is the combination of those two:
A) well-understood... *and*
B) a problem.
have a look at how multi-issue is done using Tomasulo. it's shockingly bad.
> > 3. Expand the number of RSes so that if you were to count the total number
> > of places operands are stored, they are the same.
>
> > (another way to put this is, "flatten all 2D RSes into 1D")
>
> This does not scale well. A 2D CAM is far more area efficient than a
> 1D flattened vector.
a 1D bitvector. a single, 1D bitvector. of 32 bits in length.
compared to 32 5-bit binary addresses.
just the latches alone, that math does not stack up.
now let's take it to 2D.
let's say that we have 10 FUs and 32 Regs.
in Tomasulo that is a 5-bit address. 10x5 = 50 DFF latches. DFF
latches are 10 gates so that's 500 gates.
in 6600 that is 10x32 = 320 SR NAND Latches. SR NAND latches are 2
gates. 320x2 is 640 gates.
not very different in terms of latch count, is it?
now let's do the address-checking.
to check a register as "active" - bear in mind that this is per
register and consequently
if doing multi-issue that's a batch of address-checking gates *per register*.
for Tomasulu, this requires 10x5 = 500 XOR gates (plus some
multi-input AND gates on each row) XOR is 4 gates, so that's 2,000
gates *PER MULTI-ISSUE LANE*.
for the 6600, that's 10x32 **AND** gates. 320 AND gates.
and of those 320 AND gates, they are re-useable for multi-issue
WITHOUT REQUIRING ADDITIONAL GATES.
so that is 320 AND gates for single-issue
that is zero extra gates for dual-issue
that is zero extra gates for quad-issue
zero extra gates for octal-issue.
start to make sense now, why unary encoding as 1D vectors is less
gates and less power than binary CAMs?
if you want to check multiple unary bits (a critical prerequisite for
multi-issue), all you do is... set... multiple... bits.
what happens? multiple AND gates fire. in the same clock. and
that's exactly what we want.
> > 7. rename RSes to "Function Units" (actually in Thornton's book the phrase
> > "Computation Units" is used)
>
> So a Tomasulo's design with 4 rows now becomes a "flattened" design
> with 4 functional units? The additional cost of the functional units
> is enormous.
no, it's 4 x 80 gates (approx). that's not 4x duplication of ALU
pipelines *behind* those 4 Function Units. see Mitch's 2nd Chapter,
"Concurrent Computation Unit"
https://libre-soc.org/3d_gpu/architecture/6600scoreboard/600x-concurrent_comp_unit.png
Jeremy: it's rather unfortunate timing. six to twelve months ago, we
could have had this debate and it would have been fun, informative,
useful and productive. it would also have been possible to bring you
in to the discussions that took place (Nov 2018 to around Apr-May
2019) between myself, Samuel Falvo, Mitch Alsup and the team either
here on this list, or on comp.arch.
however with the upcoming deadline, this kind of otherwise really
valuable discussion is, sadly, something that we *do not have time
for*.
retrospective recommendation that we reconsider and use Tomasulo would
not only result in us completely missing the upcoming Oct 2020
deadline, we would end up with an exceptionally poorly-performing,
limited and seriously problematic processor as well. worse than that,
sadly i have to say that i am concerned that any retrospective
discussion would itself (aside from valuable corrections and
assistance in creating a comparative analysis) become a serious
distraction.
it's liitterallly taken 18 MONTHs to get to the point where we are now
with the code and the design. we need to finish the design in a very
short timeframe (14 weeks), and as Yehowshua points out, due to the
complexity of this particular area of Computer Science, that in turn
implies that you'll need to trust me on the architectural analysis
(which took 5 months to complete, under Mitch's guidance).
so, my apologies for needing to be firm on this: the opportunity to
help exists within the time-frame and financial constraints that were
determined and set, over 18 months ago, before you joined.
therefore, if you'd like to help, then asking questions which are
related to *understanding* of the precise-augmented Scoreboard system,
targetted very specifically at allowing you to engage and assist us in
meeting that deadline, are very welcome.
anything other than that very specific goal-orientated focus, i am
really sorry, we really need to move it to one side, and for that, i
recommend comp.arch.
therefore, if you would like to discuss the merits of Tomasulo vs
Scoreboard (particularly those that pursue recommending Tomasulo
*over* Scoreboard) further, i recommend doing so on comp.arch, which
is where Mitch Alsup most regularly may be found. with the right
interesting question, both he and many others will pitch in.
the one thing that you need to be aware of is that Mitch is both
hyper-intelligent, and second that he does not tolerate people who
cannot keep up with him, especially if they try to convince him of
something without having first demonstrated that they've understood
*him*. he's well over 70, he's retired, he made enough "xxxx-you"
money on selling GPU patents to Samsung, so he doesn't have to put up
with anything that he doesn't want to :)
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] Introduction and Questions
From: Luke Kenneth Casson Leighton @ 2020-05-16 21:42 UTC (permalink / raw)
To: Libre-RISCV General Development
In-Reply-To: <CAEoCstQLUzbeAyBBWE_FH8=AD78nd-qG8eAJo_cXaTG_Wz4ysQ@mail.gmail.com>
On Sat, May 16, 2020 at 9:34 PM Jeremy Singher <thejsingher@gmail.com> wrote:
> > Ok after some reflection I do see the most possible performance
> > difference in procedures calls. Most of the time in procedures some
> > scratch registers are pushed on the stack at entering.
>
> Its actually a performance difference on more cases than this. In the
> case of W R W R sequence to the same register, the second Write should
> be allowed to proceed before the first Write is executed, which also
> unblocks the second R.
in a strict historically-accurate 6600 (which we are not doing), it would block
at that 2nd W.
in the precise-augmented 6600-like design, the Operand Forwarding Bus
would provide the means for the second W to communicate the required
result to the 2nd R, allowing it to proceed, because Operand Forwarding
Buses provide the extra missing path that is not in the *original* 6600
that makes the register data paths functionally identical to a Common
Data Bus.
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 21:47 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
--- Comment #17 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Cole Poirier from comment #16)
> I have committed the changes.
fantastic: feel free to do another "git pull" because i just made some
PEP8-like
changes.
btw notice in cr/main_stage.py, michael also does the same "indexing" trick :)
in particular notice what he does with the name argument:
cr_out_arr = Array([Signal(name=f"cr_out_{i}") for i in range(32)])
if you try that out you will end up with actual properly-named Signals rather
than "stuff that's randomly named $1, $2, $3.... $64".
> Now I am going to go over Robert Baruch's
> nmigen tutorials and search out resources on writing unit tests, and formal
> proofs for hardware. Then I will attempt to write an appropriate unit test
> for this class.
great. formal proofs are... odd. i can barely get my head round them.
--
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 21:49 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
Michael Nolan <mtnolan2640@gmail.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |mtnolan2640@gmail.com
--- Comment #18 from Michael Nolan <mtnolan2640@gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #17)
> (In reply to Cole Poirier from comment #16)
>
> btw notice in cr/main_stage.py, michael also does the same "indexing" trick
> :)
> in particular notice what he does with the name argument:
>
> cr_out_arr = Array([Signal(name=f"cr_out_{i}") for i in range(32)])
>
> if you try that out you will end up with actual properly-named Signals rather
> than "stuff that's randomly named $1, $2, $3.... $64".
ROFL, I got the idea of using Arrays from your conversations yesterday.
>
>
> > Now I am going to go over Robert Baruch's
> > nmigen tutorials and search out resources on writing unit tests, and formal
> > proofs for hardware. Then I will attempt to write an appropriate unit test
> > for this class.
>
> great. formal proofs are... odd. i can barely get my head round them.
I'd be happy to help with formal proofs when you're ready.
--
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 21:52 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
--- Comment #19 from Michael Nolan <mtnolan2640@gmail.com> ---
(In reply to Cole Poirier from comment #16)
>
> I have committed the changes. Now I am going to go over Robert Baruch's
> nmigen tutorials and search out resources on writing unit tests, and formal
> proofs for hardware. Then I will attempt to write an appropriate unit test
> for this class.
For writing unit tests, take a look at
https://git.libre-soc.org/?p=soc.git;a=blob;f=src/soc/shift_rot/test/test_maskgen.py;h=1a4d34e676154b250f95ef120932a9b88fcaf937;hb=3c65f5ff7893bb34696c476abacfe34ad739bf18
for decent starting place
--
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 314] Create Condition Register pipeline
From: bugzilla-daemon @ 2020-05-16 22:06 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-314-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=314
--- Comment #14 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Michael Nolan from comment #12)
> We can do this for crand and friends, as well as mcrf, but it doesn't work
> for mtcrf or mfcr because they can read or write the whole cr register
ah good catch. updated. yes you're right. this would be where the "multi-bit
hazard" detection would come into play. the bit-vector would be
0 1 ... 7 8
CR0 CR1 ... CR7 {ALLCRs}
for crand the decoding of BA (etc) would set the corresponding CR register
hazard *and* on vector bit 8 {ALLCRs}... but not the other bits.
thus it would be possible to have multiple parallel overlapping crand(s) (etc)
as long as the read/write dependencies on CR0-CR7 do not clash
however mtcrf would set bit 8 {ALLCRs} *AND* it would set *ALL* other bits 0
thru 7.
as it's an optimisation it's off the TODO list for now.
--
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 317] New: multi-bit dependency tracking of split (ganged) regfile ports
From: bugzilla-daemon @ 2020-05-16 22:10 UTC (permalink / raw)
To: libre-riscv-dev
https://bugs.libre-soc.org/show_bug.cgi?id=317
Bug ID: 317
Summary: multi-bit dependency tracking of split (ganged)
regfile ports
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: ---
see https://bugs.libre-soc.org/show_bug.cgi?id=314#c14
this is a general technique which can be implemented on the INT and FP
regfiles as well as the Condition Registers and sub-fields of other SPRs
to provide W & R hazard protection against *portions* of a regfile.
it critically requires as a direct knock-on consequence that the protected
portion have its own read and write enable line.
thus the regfile may instead of being considered e.g. "64-bit wide" may
instead be considered 8x 8-bit wide, where 64-bit operations must request
*eight* simultaneous read/write-enable lines.
it's sufficiently comprehensive that we need to leave this off the TODO list
for now.
--
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 317] multi-bit dependency tracking of split (ganged) regfile ports
From: bugzilla-daemon @ 2020-05-16 22:11 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-317-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=317
Luke Kenneth Casson Leighton <lkcl@lkcl.net> changed:
What |Removed |Added
----------------------------------------------------------------------------
See Also| |https://bugs.libre-soc.org/
| |show_bug.cgi?id=314
--
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 314] Create Condition Register pipeline
From: bugzilla-daemon @ 2020-05-16 22:11 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-314-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=314
Luke Kenneth Casson Leighton <lkcl@lkcl.net> changed:
What |Removed |Added
----------------------------------------------------------------------------
See Also| |https://bugs.libre-soc.org/
| |show_bug.cgi?id=317
--
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 314] Create Condition Register pipeline
From: bugzilla-daemon @ 2020-05-16 22:14 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-314-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=314
--- Comment #15 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Michael Nolan from comment #11)
> Could you send me the login for the talos server so I can test this?
oh - err, yes, sorry. except my laptop segfaulted and although i have a
mosh-screen session running that will still be open, i can't remember the
server's IP address! it doesn't have a domain name associated with it yet.
will find it tomorrow - 23:00 hrs here now.
(In reply to Michael Nolan from comment #13)
> Qemu seems to do nothing when it's not onehot
interesting. i think i have a hypothesis that fits: it's possible
that an early version of POWERPC had one version, they realised they
needed the other, but couldn't really retire the old one as it was
too commonly used.
--
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 22:24 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
--- Comment #20 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Michael Nolan from comment #18)
> ROFL, I got the idea of using Arrays from your conversations yesterday.
:)
> I'd be happy to help with formal proofs when you're ready.
really appreciated. (In reply to Michael Nolan from comment #19)
> For writing unit tests, take a look at
> https://git.libre-soc.org/?p=soc.git;a=blob;f=src/soc/shift_rot/test/
> test_maskgen.py;h=1a4d34e676154b250f95ef120932a9b88fcaf937;
> hb=3c65f5ff7893bb34696c476abacfe34ad739bf18 for decent starting place
Cole that's a really good template to start from.
(*sotto voice to michael*: i tend to just set mb = dut.mb as a temp
python variable, and do "yield dut.o" rather than spend the time
setting up copies of things that you can get at directly anyway).
so, Cole, note two things:
1) the establishment of the "DUT" - Device Under Test. the "yield"
statements to set the inputs, and the additional "yield" statement
to obtain the output
2) the use of a **PYTHON** function - not a nmigen function - which
computes the expected result. this function - MASK() in this
example by Michael - is given the EXACT SAME INPUT as was handed
to the hardware.
thus you have an "expected" result (done in python) and a "hardware-simulated"
result.
if those two do not match, throw a python unittest assert.
simple.
except, it is necessary to write a *lot* of these, catching and testing
different aspects of the hardware.
this is why we want to do Formal Proofs, because one Formal unit test,
if written correctly, covers *everything*.
--
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 22:28 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
--- Comment #21 from Cole Poirier <colepoirier@gmail.com> ---
(In reply to Michael Nolan from comment #19)
> (In reply to Cole Poirier from comment #16)
> >
> > I have committed the changes. Now I am going to go over Robert Baruch's
> > nmigen tutorials and search out resources on writing unit tests, and formal
> > proofs for hardware. Then I will attempt to write an appropriate unit test
> > for this class.
>
> For writing unit tests, take a look at
> https://git.libre-soc.org/?p=soc.git;a=blob;f=src/soc/shift_rot/test/
> test_maskgen.py;h=1a4d34e676154b250f95ef120932a9b88fcaf937;
> hb=3c65f5ff7893bb34696c476abacfe34ad739bf18 for decent starting place
Thanks Michael! This looks like it will be really helpful.
(In reply to Michael Nolan from comment #18)
> (In reply to Luke Kenneth Casson Leighton from comment #17)
> > (In reply to Cole Poirier from comment #16)
>
> >
> > btw notice in cr/main_stage.py, michael also does the same "indexing" trick
> > :)
> > in particular notice what he does with the name argument:
> >
> > cr_out_arr = Array([Signal(name=f"cr_out_{i}") for i in range(32)])
> >
> > if you try that out you will end up with actual properly-named Signals rather
> > than "stuff that's randomly named $1, $2, $3.... $64".
>
> ROFL, I got the idea of using Arrays from your conversations yesterday.
I just pushed I commit where I have tried to copy this, although I'm unsure if
I did it correctly, because rb_{n} shows up correctly in the graph, but I see
no idx_{n}'s. I took a second look at my code after using yosys to examine it,
and I'm not able to discern why idx would not show up... I just took a third
look and realized it was because I had neglected to delete my temporary
assignment of an 8-bit wide Signal from my first iteration to the variable
index, which I was actually using within the body of the for loop that makes up
the bulk of the function. Now both labels show up correctly. I have pushed this
new commit.
> > great. formal proofs are... odd. i can barely get my head round them.
Yeah.. I have the feeling that I'm wading into quite strange waters here :)
> I'd be happy to help with formal proofs when you're ready.
Thanks again Michael, I'm looking forward to working with you and learning from
your knowledge and experience. I have a prior obligation, so I'll have to push
writing the unit test until tomorrow. But, for my own understanding, once I
have the unit test is working, would it be wiser to search for optimization
opportunities, for example from Claire Wolf's bitmanip code, or to write the
formal proof? I'm guessing that the formal proof is specific to the function's
implementation and thus I should wait to write the formal proof until the
function is optimized but I am not sure.
(In reply to Luke Kenneth Casson Leighton from comment #17)
> (In reply to Cole Poirier from comment #16)
>
> > I have committed the changes.
>
> fantastic: feel free to do another "git pull" because i just made some
> PEP8-like
> changes.
Thanks Luke, and apologies for not perfectly conforming to PEP8 yet, I'm
working on getting my autopep8 working but have run into a problem, I should
have it sorted tomorrow.
--
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 22:36 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
--- Comment #22 from Cole Poirier <colepoirier@gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #20)
> (In reply to Michael Nolan from comment #18)
>
> > ROFL, I got the idea of using Arrays from your conversations yesterday.
>
> :)
>
> > I'd be happy to help with formal proofs when you're ready.
>
> really appreciated. (In reply to Michael Nolan from comment #19)
>
>
> > For writing unit tests, take a look at
> > https://git.libre-soc.org/?p=soc.git;a=blob;f=src/soc/shift_rot/test/
> > test_maskgen.py;h=1a4d34e676154b250f95ef120932a9b88fcaf937;
> > hb=3c65f5ff7893bb34696c476abacfe34ad739bf18 for decent starting place
>
> Cole that's a really good template to start from.
>
> (*sotto voice to michael*: i tend to just set mb = dut.mb as a temp
> python variable, and do "yield dut.o" rather than spend the time
> setting up copies of things that you can get at directly anyway).
>
> so, Cole, note two things:
>
> 1) the establishment of the "DUT" - Device Under Test. the "yield"
> statements to set the inputs, and the additional "yield" statement
> to obtain the output
>
> 2) the use of a **PYTHON** function - not a nmigen function - which
> computes the expected result. this function - MASK() in this
> example by Michael - is given the EXACT SAME INPUT as was handed
> to the hardware.
>
> thus you have an "expected" result (done in python) and a
> "hardware-simulated"
> result.
>
> if those two do not match, throw a python unittest assert.
>
> simple.
>
> except, it is necessary to write a *lot* of these, catching and testing
> different aspects of the hardware.
>
> this is why we want to do Formal Proofs, because one Formal unit test,
> if written correctly, covers *everything*.
Ah, thank you very much for these additional details Luke. Everything the both
of you (and Yehowshua) have said is proving critical to my ability to quickly
(or slowly...) get going with the various required aspects of our HDL_workflow.
Once I have finished this first small 'project'/assignment, I'd like to pause
for a few hours and update the documentation of the HDL_workflow with the
things I learned while scripting it, as well as all that I've learned in this
assignment. Some of this exists elsewhere on the wiki, however, most of the
getting started with nmigen stuff I've learned in the past two days does not
(as far as I am aware) and I believe this will be valuable to new members. But
right now I have a prior engagement I must attend to, so I'll attempt an
initial unit test tomorrow :)
--
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] Scoreboard vs Tomasulo
From: Jeremy Singher @ 2020-05-16 22:45 UTC (permalink / raw)
To: Libre-RISCV General Development
In-Reply-To: <CAPweEDxXGedm-4QwmU2UuYvb4G2nNaoAsy_P2eyviQ42pbmyXA@mail.gmail.com>
I have finally finished parsing Mitch's chapters, and now I see what
the primary confusion is from. The scoreboard being developed here has
been referred to in the mailing lists as a "CDC 6600-like" scoreboard,
while in reality, the final design is far extended far beyond the
original CDC 6600 implementation. I would suggest not calling it a
"CDC 6600-like scoreboard" in the future, instead a "extended
scoreboard" is more accurate.
Let me try to compose my thoughts.
In order for OOO execution to be possible, write data from
speculatively executed instructions must be buffered, for in the case
of misspeculation, they must not be allowed to commit into the
architectural register file.
In Tomasulo's, speculative write data are held in physically renamed registers.
In the extended scoreboard scheme, speculative write data are held in
compute unit latches.
In Tomasulo's, branch dependency masks are used to drain misspeculated
instructions.
In extended scoreboard, the misspeculated instructions drain
themselves from the system.
Both schemes can be designed to achieve similar OOO behaviors.
Thus, one cannot draw a performance conclusion just by seeing which
scheme is being used.
Ideally the above text should be uncontroversial, please let me know
if there is a large misunderstanding here.
My opinion is that Tomasulo's is a more elegant and well-proven scheme
for achieving OOO execution, compared to an extended scoreboard. I
also argue that the extended scoreboard scheme does not present
significant power/area advantages compared to Tomasulo's. Given that
estimates on power/area tend to be wildly inaccurate, I think we will
have to wait for power analysis of LibreSoC to get a definitive answer
to this debate :).
I deeply apologize if any of my thoughts could be interpreted as
criticism. I fully support this kind of exploration in OOO design. I
also apologize if I seem to suggest a change in design, as I
understand that hardware design is not nearly as flexible as software
design.
On Sat, May 16, 2020 at 2:38 PM Luke Kenneth Casson Leighton
<lkcl@lkcl.net> wrote:
>
> On Sat, May 16, 2020 at 9:16 PM Jeremy Singher <thejsingher@gmail.com> wrote:
>
> > > However, the scoreboard is limited in that it does not handle WAR and WAW
> > > hazards very well.
> >
> > > the original 6600 handles WAR extremely well, only stalling on WaW
> > > condition, detection which did not matter greatly because the pipelines
> > > were only at most 2 stages long anyway (Mitch only noticed after rereading
> > > last year that the FP ADD of the 6600 was 2 stage pipelined. no academic
> > > literature has acknowledged or noticed this).
> >
> > I would argue that the CDC6600 handles WAR better than an in-order
> > machine, but not better than a machine with full renaming.
>
> Jeremy: 6600 designs *do* have register "renaming". i said already,
> a number of times. and if you have studied and listened to the Academic
> literature - and believe it - you are misinformed by that literature, and will
> continue to be misinformed by that literature.
>
> please understand: i have spent over nine months studying this, learning
> from Mitch Alsup, one of the world's leading high-performance computing
> architects, implementing this and it's not going to get chucked out to
> implement something that takes six MONTHS to fully understand is a
> better design, to be replaced by something that would take another six
> months to implement *and we then could not do multi-issue on top of it*.
>
> please therefore take the time to understand this design, particularly when
> we are right in the middle of a time-critical deadline.
>
> > In the
> > CDC6600, the scoreboard would block the completion of the W inst until
> > the R inst has read its operands. In Tomasulo, the W inst can proceed
> > immediately before the R inst is ready, since the destination register
> > is physically renamed.
>
> Jeremy: the "renaming" carried out by the 6600 does exactly this same
> job.
>
> Academics unfortunately have *only* studied the *patent* - not Thornton's
> book nor read Mitch Alsup's book chapters which he wrote based on 30+
> years experience of implementing 6600-style execution in the 88100,
> AMD K9 and AMD Opteron Series of CPUs.
>
> the 6600 patent *ONLY* covers the Q-Tables.
>
> the description of the Q-Tables does *NOT* include the Computation Units
> where the operand latches are.
>
> these latches *ARE* the "renamed registers" (actually, nameless registers).
>
> > > ROB is a CAM,
> >
> > What? This is not true. Instructions in flight track their index in
> > the ROB, at completion, they write success bit according to the index
> > they have. Not a CAM. Simple addressed write.
>
> ah appreciated the correction. i knew there were CAMs somewhere.
> when i discovered that, i dropped further investigation.
>
> i am however aware that if you wish to do multi-issue, the ROB will need
> to be multi-ported SRAM. without multi-porting the SRAM, you simply
> cannot write multiple entries.
>
> this is where the problems (read: nightmares) for Tomasulo start to manifest,
> and progress from there through multiple Common Data Bus channels into
> multi-ported (NxR, NxW) CAMs at the Reservation Station level.
>
> i've been through this, ok, over 18 months ago.
>
> by contrast, when converted to single-bit unary vectors, each entry in the
> Matrices (covered by a single SR NAND latch) is *independent*. multiple
> of those may be set in a single cycle.
>
> there has been a *massive* amount of thought gone into this, ok?
>
>
> > > given that Intel processors use Tomasulo, we start to see why Intel
> > > processors suck so much power.
> >
> > Power consumption on a processor is primarily from high switching
> > rates on large register files, and SRAM leakage.
>
> given that we're planning around 28 Function Units and have a 128-entry
> register file, the calculations that i did for that would put the Dependency
> Matrices around a whopping 50,000 gates, using SR NAND Latches.
>
> (if we did it as DFFs it would be an unacceptable 250,000 gates)
>
> > The scheduling logic is a miniscule portion.
>
> not for the large-scale out-of-order systems that we are planning to
> do, it's not,
> due to the large sized GPU register file (128 entries. actually 2x
> 128 - 128 FP,
> 128 INT).
>
> we may have to *down*-scale via a regfile cache to cope with that.
> discussion for another time.
>
>
> > Intel cores are power-hungry because
> > historically they have targeted the desktop/workstation market, and do
> > not have as many decades of experience as other firms optimizing for
> > power-constrained environments.
>
> appreciated the insight.
>
> > Also almost all modern OOO cores use Tomasulo because Tomasulo is
> > better at avoiding false hazards compared to scoreboarding.
>
> in the versions of scoreboards implemented by academics - because they
> fail to comprehend them properly - because they only read the patent
> on Q-Tables - yes.
>
> in the version that Mitch Alsup - a world leading expert on Scoreboard
> Mechanics - taught me:
>
> no.
>
> also, the IIT Madras RISE Group Shakti E-Class processor is *also* a
> scoreboard design. this was designed "from first principles" by Professor
> Kamatoti, and it was only through learning from Mitch that i was able
> to recognise what he had done as being identical to a 6600 scoreboard.
>
> > Tomasulo
> > also makes it easier to implement precise traps, something which is
> > notoriously challenging with just a scoreboard.
>
> no it is not. this is *yet again* complete factual misinformation and ignorance
> from Academic literature.
>
> can i ask: have you read Patterson's book? this is the usual place where
> most people get their misinformation from. the release of this misinformation
> was why Mitch Alsup - a very pissed-off and exasperated Mitch - wrote those
> two chapters, back around... 2008 (i think).
>
> precise exceptions, traps, interrupts, branch speculation and predication may
> all be achieved through "shadowing". see the latter part of the 2nd chapter of
> Mitch's book.
>
> see the section "Shadowing" in this page:
> https://libre-soc.org/3d_gpu/architecture/6600scoreboard/
>
> it's very simple: you hold write until such time as the opportunity for "damage"
> is cleared. Operand Forwarding allows instructions to run ahead, using results
> that would otherwise have to be received only first by going through
> the Regfile.
>
> *this is already implemented* and the unit tests demonstrated it as
> *fully functional*
>
>
> > Lets be clear here. The CDC6600 AVOIDS WAR and WAW hazards by BLOCKING
> > younger instructions (See pg3 in Mitch Alsup's text). Tomasulo's
> > supports OOO execution PAST WAR and WAW hazards, enabling the core to
> > exploit more ILP across its functional units.
>
> this is only because the 1965 CDC6600 did not have an Operand Forwarding Bus
> (instead it used the regfile as a same-clock forwarding bus, by reading on one
> edge and writing on the other. this unfortunately meant that without an OpFwd
> Bus, stall had to occur).
>
> this DOES NOT INHERENTLY MEAN that **ALL** Scoreboards are rubbish.
>
> if you add an Operand Forwarding Bus (equivalent to the CDB in Tomasulo)
> the exact same parity functionality is achieved (without the severe downsides).
>
>
> > Luke, I agree with you that the reservation station rows in Tomasulo's
> > can be equivalent to the operand latches in Scoreboarding. However,
> > adding many operand-latches (by having many functional units) does not
> > scale as nicely as just adding a few more rows to Tomasulo's
> > reservation stations.
>
> this is incorrect. you may be under the mistaken impression that the pipelines
> duplicated as well. this clearly would be inadviseable because the FU's job
> is to serve one and only one result. therefore you know that this is a mistaken
> understanding, and that consequently you have multiple FUs for the same
> pipeline. (termed "Concurrent Computation Unit").
>
> therefore it's minimal. excluding the latches themselves (the rows
> have latches, the
> CompUnits - aka FunctionUnits have latches, the total number of latches after
> flattening is the same), the number of gates added by each CompUnit is
> minimal: around... 80, maximum.
>
> that's peanuts.
>
> > Especially since designing the CAMs for
> > Tomasulo's is a well studied, and well-understood problem
>
> the key is the combination of those two:
>
> A) well-understood... *and*
> B) a problem.
>
> have a look at how multi-issue is done using Tomasulo. it's shockingly bad.
>
>
> > > 3. Expand the number of RSes so that if you were to count the total number
> > > of places operands are stored, they are the same.
> >
> > > (another way to put this is, "flatten all 2D RSes into 1D")
> >
> > This does not scale well. A 2D CAM is far more area efficient than a
> > 1D flattened vector.
>
> a 1D bitvector. a single, 1D bitvector. of 32 bits in length.
>
> compared to 32 5-bit binary addresses.
>
> just the latches alone, that math does not stack up.
>
> now let's take it to 2D.
>
> let's say that we have 10 FUs and 32 Regs.
>
> in Tomasulo that is a 5-bit address. 10x5 = 50 DFF latches. DFF
> latches are 10 gates so that's 500 gates.
>
> in 6600 that is 10x32 = 320 SR NAND Latches. SR NAND latches are 2
> gates. 320x2 is 640 gates.
>
> not very different in terms of latch count, is it?
>
>
> now let's do the address-checking.
>
> to check a register as "active" - bear in mind that this is per
> register and consequently
> if doing multi-issue that's a batch of address-checking gates *per register*.
>
> for Tomasulu, this requires 10x5 = 500 XOR gates (plus some
> multi-input AND gates on each row) XOR is 4 gates, so that's 2,000
> gates *PER MULTI-ISSUE LANE*.
>
> for the 6600, that's 10x32 **AND** gates. 320 AND gates.
>
> and of those 320 AND gates, they are re-useable for multi-issue
> WITHOUT REQUIRING ADDITIONAL GATES.
>
> so that is 320 AND gates for single-issue
> that is zero extra gates for dual-issue
> that is zero extra gates for quad-issue
> zero extra gates for octal-issue.
>
> start to make sense now, why unary encoding as 1D vectors is less
> gates and less power than binary CAMs?
>
> if you want to check multiple unary bits (a critical prerequisite for
> multi-issue), all you do is... set... multiple... bits.
>
> what happens? multiple AND gates fire. in the same clock. and
> that's exactly what we want.
>
>
> > > 7. rename RSes to "Function Units" (actually in Thornton's book the phrase
> > > "Computation Units" is used)
> >
> > So a Tomasulo's design with 4 rows now becomes a "flattened" design
> > with 4 functional units? The additional cost of the functional units
> > is enormous.
>
> no, it's 4 x 80 gates (approx). that's not 4x duplication of ALU
> pipelines *behind* those 4 Function Units. see Mitch's 2nd Chapter,
> "Concurrent Computation Unit"
>
> https://libre-soc.org/3d_gpu/architecture/6600scoreboard/600x-concurrent_comp_unit.png
>
> Jeremy: it's rather unfortunate timing. six to twelve months ago, we
> could have had this debate and it would have been fun, informative,
> useful and productive. it would also have been possible to bring you
> in to the discussions that took place (Nov 2018 to around Apr-May
> 2019) between myself, Samuel Falvo, Mitch Alsup and the team either
> here on this list, or on comp.arch.
>
> however with the upcoming deadline, this kind of otherwise really
> valuable discussion is, sadly, something that we *do not have time
> for*.
>
> retrospective recommendation that we reconsider and use Tomasulo would
> not only result in us completely missing the upcoming Oct 2020
> deadline, we would end up with an exceptionally poorly-performing,
> limited and seriously problematic processor as well. worse than that,
> sadly i have to say that i am concerned that any retrospective
> discussion would itself (aside from valuable corrections and
> assistance in creating a comparative analysis) become a serious
> distraction.
>
> it's liitterallly taken 18 MONTHs to get to the point where we are now
> with the code and the design. we need to finish the design in a very
> short timeframe (14 weeks), and as Yehowshua points out, due to the
> complexity of this particular area of Computer Science, that in turn
> implies that you'll need to trust me on the architectural analysis
> (which took 5 months to complete, under Mitch's guidance).
>
> so, my apologies for needing to be firm on this: the opportunity to
> help exists within the time-frame and financial constraints that were
> determined and set, over 18 months ago, before you joined.
>
> therefore, if you'd like to help, then asking questions which are
> related to *understanding* of the precise-augmented Scoreboard system,
> targetted very specifically at allowing you to engage and assist us in
> meeting that deadline, are very welcome.
>
> anything other than that very specific goal-orientated focus, i am
> really sorry, we really need to move it to one side, and for that, i
> recommend comp.arch.
>
> therefore, if you would like to discuss the merits of Tomasulo vs
> Scoreboard (particularly those that pursue recommending Tomasulo
> *over* Scoreboard) further, i recommend doing so on comp.arch, which
> is where Mitch Alsup most regularly may be found. with the right
> interesting question, both he and many others will pitch in.
>
> the one thing that you need to be aware of is that Mitch is both
> hyper-intelligent, and second that he does not tolerate people who
> cannot keep up with him, especially if they try to convince him of
> something without having first demonstrated that they've understood
> *him*. he's well over 70, he's retired, he made enough "xxxx-you"
> money on selling GPU patents to Samsung, so he doesn't have to put up
> with anything that he doesn't want to :)
>
> l.
>
> _______________________________________________
> libre-riscv-dev mailing list
> libre-riscv-dev@lists.libre-riscv.org
> http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev
_______________________________________________
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 22:47 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
--- Comment #23 from Michael Nolan <mtnolan2640@gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #20)
> Cole that's a really good template to start from.
>
> (*sotto voice to michael*: i tend to just set mb = dut.mb as a temp
> python variable, and do "yield dut.o" rather than spend the time
> setting up copies of things that you can get at directly anyway).
I think I did this because when I was first starting nmigen there was a bug
where the vcd dump didn't show the top level signals unless you did this. I
haven't seen it happen in a while so maybe it's fixed...?
> except, it is necessary to write a *lot* of these, catching and testing
> different aspects of the hardware.
>
> this is why we want to do Formal Proofs, because one Formal unit test,
> if written correctly, covers *everything*.
I haven't closely examined bpermd, but for maskgen I didn't bother writing a
proof because it was easy and quick enough to exhaustively test the input
space. I suspect you won't be able to do that for bpermd though.
--
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 316] bperm TODO
From: bugzilla-daemon @ 2020-05-16 23:26 UTC (permalink / raw)
To: libre-riscv-dev
In-Reply-To: <bug-316-13@https.bugs.libre-soc.org/>
https://bugs.libre-soc.org/show_bug.cgi?id=316
--- Comment #24 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Michael Nolan from comment #23)
> (In reply to Luke Kenneth Casson Leighton from comment #20)
>
> > Cole that's a really good template to start from.
> >
> > (*sotto voice to michael*: i tend to just set mb = dut.mb as a temp
> > python variable, and do "yield dut.o" rather than spend the time
> > setting up copies of things that you can get at directly anyway).
>
> I think I did this because when I was first starting nmigen there was a bug
> where the vcd dump didn't show the top level signals unless you did this.
ah HA! i half-expected that might be why.
> I haven't seen it happen in a while so maybe it's fixed...?
it's not. if you can see if there's a bugreport raised for nmigen, and
cross-reference the discussion here, that would be really handy.
> > this is why we want to do Formal Proofs, because one Formal unit test,
> > if written correctly, covers *everything*.
>
> I haven't closely examined bpermd, but for maskgen I didn't bother writing a
> proof because it was easy and quick enough to exhaustively test the input
> space. I suspect you won't be able to do that for bpermd though.
yehyeh. Cole: maskgen is... 8-bit wide? so running 2x for-loops @ 256 x 256
cycles, for such a small amount of code that's perfectly feasible.
however if it was say 64-bit wide? (as is the case for bpermd) - that's
flat-out
impractical. we can't possibly run 2^64 times 2^64 clock cycles to cover
all permutations for inputs.
hence: formal proofs
--
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] Scoreboard vs Tomasulo
From: Yehowshua @ 2020-05-17 0:47 UTC (permalink / raw)
To: Libre-RISCV General Development
In-Reply-To: <CAEoCstSGxwV88JUHTQmUp=75kHWxSZNSPu==_pxsUYf29ctd9w@mail.gmail.com>
> On May 16, 2020, at 6:45 PM, Jeremy Singher <thejsingher@gmail.com> wrote:
>
> Let me try to compose my thoughts.
> In order for OOO execution to be possible, write data from
> speculatively executed instructions must be buffered, for in the case
> of misspeculation, they must not be allowed to commit into the
> architectural register file.
This sounds correct to me.
> I think we will
> have to wait for power analysis of LibreSoC to get a definitive answer
> to this debate :).
Probably.
Yehowshua
_______________________________________________
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] Scoreboard vs Tomasulo
From: Luke Kenneth Casson Leighton @ 2020-05-17 0:53 UTC (permalink / raw)
To: Libre-RISCV General Development
In-Reply-To: <CAEoCstSGxwV88JUHTQmUp=75kHWxSZNSPu==_pxsUYf29ctd9w@mail.gmail.com>
On Sat, May 16, 2020 at 11:45 PM Jeremy Singher <thejsingher@gmail.com> wrote:
>
> I have finally finished parsing Mitch's chapters, and now I see what
> the primary confusion is from. The scoreboard being developed here has
> been referred to in the mailing lists as a "CDC 6600-like" scoreboard,
> while in reality, the final design is far extended far beyond the
> original CDC 6600 implementation.
yes. well... far beyond it in *functionality*, but not that far in
terms of gate
count [caveat: if we were only doing the same 3 regfiles, A B and X.
as we are doing 32x INT, 32x FP, plus SPR regs *and* Condition Regs
all under the control of Dependency Matrices, a direct comparison is unfair]
oh. ah. one definite enhancement: in the diagrams you see in Mitch's
chapters, there is only one GO-READ and only one GO-WRITE. one GO-READ
indicates a desire to request *multiple* Regfile Read ports.
because POWER9 has in some cases up to *five* incoming registers and
*three* outgoing registers (in different Regfiles - INT/FP, SPR, CR), we needed
to split those out into individual lines. GO-READ1/READ-REQ1,
GO-READ2/READ-REQ2 etc.
currently i am struggling with this FSM which implements 3-operand in,
immediates, 2-operand out *and* manages the address, GO-ST, address
exceptions and deals with POWER9 LD/ST "Update" mode.
https://libre-soc.org/3d_gpu/ld_st_comp_unit.jpg
this i reaaaally need some help with.
> I would suggest not calling it a
> "CDC 6600-like scoreboard" in the future, instead a "extended
> scoreboard" is more accurate.
appreciated. if you could consider helping change the wiki to reflect this (and
help us to maintain the advantages below) this would be fantastic.
i've used a range of terms - "augmented 6600 scoreboard", and others.
the historic
link and the effective revival of something long-forgotten which was
both elegant
and staggeringly gate-efficient (out of necessity): i don't want to use the word
"political" in any sentence however there is a considerable publicity
"wow factor"
to doing something as surprising as reviving a 55-year-old design.
since interacting with Mitch Alsup last year, you're the first additional person
to actually do any kind of significant analysis: consequently terminology has
not really been discussed... because there wasn't anyone to discuss it with!
> Let me try to compose my thoughts.
> In order for OOO execution to be possible, write data from
> speculatively executed instructions must be buffered, for in the case
> of misspeculation, they must not be allowed to commit into the
> architectural register file.
mis-speculation, LD/ST page-faults, predicated instructions where the operand
that contains the bitmask is in a register that has not been read yet, and even
simple external NMI interrupts: all of these need a means and method of
killing in-flight data, yes.
> In Tomasulo's, speculative write data are held in physically renamed registers.
> In the extended scoreboard scheme, speculative write data are held in
> compute unit latches.
these two effectively having a very low Levenshtein distance, but not quite
zero.
* in Tomasulo, the reason for the explicit renaming is down to the 2D
nature of RS's.
hence the ROB row number needs to be stored in the RS
* in extended-scoreboard, the FU's index / column-number *is* that "name";
with there only *being* a one-to-one path, there is no need for a
name *at all*,
hence why i refer to the CU latches as "nameless registers".
the ROB row number *is* the FU number which *is* the renamed-register-number
and consequently by being one-to-one in every aspect, needs no name.
this aspect of 6600 scoreboards - the complete lack of naming and even the
lack of significance drawn to it even by James Thornton himself in his book,
and certainly in the patents, is why the 6600 is *believed* not to have register
renaming of *any* kind.
ah - one other really critical thing (i will add to the page):
* Tomasulo ROB Row numbers preserve instruction order through sequential
numbering by the actual row number
* 6600 scoreboards preserve instruction order in the FU-FU Matrix with
a NxN bit-level matrix of SR Latches implementing a "linked list" (the
Directed Acyclic Graph) of ordered dependencies, using the *register*
dependencies at the time the instruction is inserted into the *FU-REGS*
Matrix to determine the FU-FU DAG. this has more in common with a
"linked list" data structure, to use software terminology.
this latter aspect is a crucial one that even James Thornton notes is really
*really* complex to explain, yet paradoxically requires an extraordinarily
small number of actual gates to implement.
however understanding the difference between the (binary) ROB Row
numbering (which preserves the DAG of instruction order by way
of binary-addressed instruction ROB Row N+1 being a greater index
than binary-addressed instruction ROB Row N) and this
"functionally-equivalent" linked-list system equally successfully preserving
a DAG but using unary SR Latches to do so, is key to recognising
and appreciating that Tomasulo and Scoreboards *really are* functionally
directly equivalent.
here it should become clear as to another aspect of why multi-issue is
problematic in Tomasulo. where detection of "readiness to commit" in
a single-issue Tomasulo is a simple matter of checking *one* row
"is your result ready, if yes commit it and cyclically increment the pointer
to the ROB row to the next item, ready for test-or-commit on the *next*
cycle", this must be updated to testing of *multiple* row "readiness"
states, which clearly requires a multi-ported SRAM.
this is where "solutions" that i have seen actually stratify the ROB
into 4 (or N) interleaved banks. crossbars are required... it's where
the nightmares begin.
> In Tomasulo's, branch dependency masks are used to drain misspeculated
> instructions.
are these unary-encoded or binary-encoded? by masks i would expect them
to be unary-encoded and thus allow multiple bits to be set, allowing multiple
operations to be cancelled.
if not, and binary masks are used, then each unit must have an arithmetic
comparator, "is my binary index less than or equal to the branch dependency
mask, if less than, then this means i must die".
the Shakti 6600-like (extended) scoreboard system in their E-Class design
uses *binary* numbering, which means that they use that scheme. effectively
the mask is not a mask per se, it is a shortened version of the instruction
sequential number.
BOOM uses unary bit-masks. i think. i had a brief conversation about it
with someone, somewhere, a few months back.
i greatly prefer the unary system. it allows interleaving of multiple
simultaneous
cancellations to *automatically* sort themselves out, by ORing the cancellations
together to produce the mask!
this is an "accidental" side-effect of the Shadow Matrix concept,
described below.
a binary-indexed cancellation system requires a *central resource* to calculate
the lowest-numbered "index", followed by broadcasting that index across the
one (and only one) permitted cancellation datapath.
> In extended scoreboard, the misspeculated instructions drain
> themselves from the system.
ah no. we'll be cancelling them explicitly, via an unary bit-mask,
that is global
and combinatorial in nature, extending right the way through the entirety
of the Function Unit, CompUnits *and* the associated pipelines.
the unary mask is basically a conversion of the *binary* indices of the
CompUnit number on any given Concurrent Computation Unit. 0-3
in this diagram here:
https://libre-soc.org/3d_gpu/architecture/6600scoreboard/600x-concurrent_comp_unit.png
thus in that case the unary cancellation mask would be 4-bit wide.
these are linked directly to - and are equal to - the "GO_DIE" signals in *this*
diagram:
https://libre-soc.org/3d_gpu/shadow.jpg
note in that diagram the existence per cell in the Dependency Matrices of *two*
Shadow Latches.
the first Shadow Latch is for the first Branch Unit to indicate "speculative
execution underway as controlled and directed by Branch Unit 1".
the second Shadow Latch is for the *second* Branch Unit to do likewise.
a third Shadow Latch exists for predicated execution. one bit each of the
predicate register (once read) will be thrown at the "FAILED-3" line if that
bit is zero, and at the "SUCCESS-3" line if that bit is 1. if "failed" is
asserted, then so is the "GO_DIE". that "GO_DIE", being connected to
the cancellation masks, *INSTANTLY* kills not just the register hazard
allocation, it resets the Function Unit to idle *and* kills the partial result
generation actually in the pipeline itself.
if "success" is asserted, the shadow latches are cleared, and "WRITE_REQUEST"
is no longer prevented and prohibited from asserting. the result (if it was
ready), is allowed to proceed "I now request a Regfile Write Port".
if the result
happened not to be ready, then when the result *is* ready it will not
be held up.
a fourth Shadow latch exists for cancellation of operations in the "shadow"
of a LD/ST Unit's page-fault / address exception.
as you can see this requires a trivial number of gates per cell, however
it is *each* exception or cancellation opportunity that requires these Shadows,
on a *per FU basis*, across all *other* FUs.
consequently i designed a "Shadow Matrix" that takes care of that.
> Both schemes can be designed to achieve similar OOO behaviors.
> Thus, one cannot draw a performance conclusion just by seeing which
> scheme is being used.
no. hence why we haven't done that kind of analysis: we're focussing
on implementation.
> Ideally the above text should be uncontroversial, please let me know
> if there is a large misunderstanding here.
nono looks great, really appreciate the insights raised. the missing piece
is the true significance of the role of the Shadow Matrices as being *the*
provision of precise exception capability, speculation, predication, everything.
yes i am aware that without "predication prediction" yes those are two
different words we end up with exactly the same situation as for Branch
Prediction: predicated operations that are issued, cause FUs to become
full / allocated, that are cancelled moments later because the majority
of the predicate register turns out to be full of zeros.
this is *not* a high priority item right now :)
> My opinion is that Tomasulo's is a more elegant and well-proven scheme
> for achieving OOO execution, compared to an extended scoreboard. I
> also argue that the extended scoreboard scheme does not present
> significant power/area advantages compared to Tomasulo's.
Mitch Alsup is better equipped, from 40 years experience at gate-level
design (which he kept and *refined* when working for AMD, hence some
of the blistering withering words to less experienced, less-knowledgeable
people trying to tell him that HDLs were inherently better), to answer this
one.
> Given that
> estimates on power/area tend to be wildly inaccurate, I think we will
> have to wait for power analysis of LibreSoC to get a definitive answer
> to this debate :).
if we have to use DFFs rather than SR NAND, the argument is instantly
won by Tomasulo because we have quite literally a 5-fold increase in
gate count right across the board, in every single Matrix. Shadow,
FU-Regs, FU-FU - the lot. everywhere you see an SR-Latch diagram
(2 gates), instead add 10 gates for a DFF.
for the 180nm ASIC this would jump approximately.... mmm... 10,000 gates
up to 50,000.
we may have to do that. it will suck.
> I deeply apologize if any of my thoughts could be interpreted as
> criticism. I fully support this kind of exploration in OOO design. I
> also apologize if I seem to suggest a change in design, as I
> understand that hardware design is not nearly as flexible as software
> design.
appreciated, Jeremy. if this discussion was taking place 6 to 12 months ago
the "mode" we would be in was radically different. now is "full-bore
time-critical implementation mode", and will be until the other side
of Oct 2020.
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
page: next prev 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