Libre RISC-V Mailing list Archives (accessible via public-inbox)
 help / color / Atom feed
* Re: [libre-riscv-dev] Scoreboard vs Tomasulo
From: Luke Kenneth Casson Leighton @ 2020-05-16 15:00 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <13EDF987-9A19-4C96-89C2-6DB784CF2C96@gatech.edu>

On Saturday, May 16, 2020, Yehowshua <yimmanuel3@gatech.edu> wrote:

> This website gives an excellent comparison
>
> https://www.cs.umd.edu/~meesh/cmsc411/website/projects/dynamic/intro.html
> <https://www.cs.umd.edu/~meesh/cmsc411/website/projects/dynamic/intro.html
> >


ah good find.  particularly because, like all Academic literature on the
6600, it is factually partially correct but at the same time dangerously
misleading and factually wrong.  this for example is wrong:

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

you have to understand that the majority of designs at the time were around
10 to 12 clocks per instruction.  the CDC6600 got that down to FOUR and
consequently represented a 2 to 3 fold increase in performance.



> In general, it says that Tomasulo is a distributed scoreboard.


mmm no.  the ROB, which is the key component, is centralised, and the CDB
is a central resource.



> The biggest drawback of Tomasulo is the central data bus as the messaging
> scheme. One could use a mesh NOC between functional units.


ah, not quite the biggest: as you correctly say, all you need is multiple
CDBs and that problem is solved.

no, the biggest draw of Tomasulo is that the ROB (reorder buffer) numbering
is in *binary*, and bear in mind that the ROB is a CAM, the larger that
gets the more power it takes.

let us say we have a 32 entry ROB, let us say we have 5 bits for the ROB
CAM key.

this not only means that when trying to put a result into the CAM we have
5x32 XOR gates to fire - on every cycle - if we want 2 Common Data Buses we
now need DOUBLE that...

... *and we need clash detection*.

by contrast, 6600 scoreboards have *unary* numbering and consequently the
CAM is degenerate and becomes a single AND gate activation.

not only that but if you wish to check or activate more than one register
simultaneously then that... is... just... more than one corresponding AND
gate activating at the CAM.

perfectly simple, very little power, perfect for dropping multi issue on
top.




> Given that we have well over 15 functional units, I would have thought a
> distributed scoreboard instead of a centralized one makes more sense.


the document, whilst useful as a starting point, has misled you on two
counts (so far)

the key is that binary numbering requires power sucking CAMs.  hence why
the 6600 scheme, augmented to precise, and even the original 6600 Q Table
numbering has been converted from binary to unary.

not Tomasulo.

actually.... in 6600, the DMs are still centralised, it is however the case
that the unary numbering results implicitly in opportunities for
parallelism (see below) and consequently could be termed "distributed".

also, the role of the Function Units, the GORD/REQ latching, that is done
as part of the critical acknowledgement and communication *with* the
scoreboards, and is done very close to the pipelines, *not* in the DMs
themselves, so in that regard, yes it is "distributed".

Function Units are equivalent to "Reservation Station Rows" from Tomasulo
terminology.  the multiple rows per Tomasulo Reservation Station *also*
requires that those be CAMs!

yet more power-sucking!

given that Intel processors use Tomasulo, we start to see why Intel
processors suck so much power.


> Of course, I have no numbers to back this up. But these are just some
> thoughts.
>
>
> I know we’re using a ring/circular buffer for messaging at the moment.


yes for the future version.

for the simple 180nm version it will be simple direct regfile port
broadcast buses, connected one to one with the corresponding Function Unit
Operand input.

thus, FU operand 1 will be directly connected to Regfile Port1 Broadcast
Bus.

FU operand 2 - if there *is* an operand 2 - will connect to Regfile Port2
Broadcast Bus.

*if we have time* then we can drop in the cyclic buffers, and when data
comes out of Regfile Port2 it is cyclically shifted to Op... 1 or Op3 or
whatever is required.



> Given that we have hard deadlines and limited resources, we can stick with
> this. But these are questions I do wonder about the answer to. I wonder if
> there are any papers where this has been explored at sufficient depth to
> draw conclusions.


i encountered when i investigated Tomasulo a way to do multi issue in an
academic paper.

the method, which involved stratifying the Reorder Buffer into 4 separate
slices, was awful.

the binary numbering on the ROB causes massive headaches because it
required special queues of binary ROB indices to represent the multi issue
requests.

when converted to unary, multiple bits may be set to indicate REG1 REG5
REG7 *in one cycle* on the *same wires* because one wire is dedicated to
each reg.

this is precisely and exactly what you need for multi issue and it is so
laughably simple.

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

* Re: [libre-riscv-dev] Scoreboard vs Tomasulo
From: Luke Kenneth Casson Leighton @ 2020-05-16 15:06 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <13EDF987-9A19-4C96-89C2-6DB784CF2C96@gatech.edu>

https://www.cs.umd.edu/~meesh/cmsc411/website/projects/dynamic/example1.html

we have converted Fi Fj Fk and Rk Rj and Qk Qj to UNARY.

bit level.

this is how we can push multiple entries per clock (implement multi issue)
into the DMs.

in the original 6600 reg numbers were sometimes unary and sonetimes binary,
with encoder-decoders converting between them.

this reduced gate count at the cost of making the encoders and decoders a
one data per clock bottleneck.

by preserving everything as unary we can transfer up to the full number of
unary bits as hazard information, in one cycle.

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

* Re: [libre-riscv-dev] Scoreboard vs Tomasulo
From: Luke Kenneth Casson Leighton @ 2020-05-16 15:13 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <13EDF987-9A19-4C96-89C2-6DB784CF2C96@gatech.edu>

https://www.cs.umd.edu/~meesh/cmsc411/website/projects/dynamic/tomasulo.html

register renaming to eliminate output and anti-dependences, i.e. WAW and
WAR hazards

also misleading in that it completely misses that the 6600 Q-Tables also
provide the concept of register renaming.

the Latches at the Function Unit are directly equivalent to RS Row latches
and are consequently "nameless registers".

hence you start to see why the Academic literature is hopelessly misleading
and why Mitch was pretty much compelled to write those two book chapters.

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

* Re: [libre-riscv-dev] Scoreboard vs Tomasulo
From: Luke Kenneth Casson Leighton @ 2020-05-16 15:16 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAPweEDyDcmAJbJx+PKkL8MotPMNyHyFOEtuNOKP+V2PmmY5HvA@mail.gmail.com>

Tomasulo's algorithm implements register renaming through the use of what
are called reservation stations.

see? total failure to mention the 6600 Computation Unit latches as being
directly equivalent to that.

therefore total systematic failure in the academic literature *world wide*
to mention that the 6600 had and was the world's first computer design to
have register renaming.


On Saturday, May 16, 2020, Luke Kenneth Casson Leighton <lkcl@lkcl.net>
wrote:

> https://www.cs.umd.edu/~meesh/cmsc411/website/projects/
> dynamic/tomasulo.html
>
> register renaming to eliminate output and anti-dependences, i.e. WAW and
> WAR hazards
>
> also misleading in that it completely misses that the 6600 Q-Tables also
> provide the concept of register renaming.
>
> the Latches at the Function Unit are directly equivalent to RS Row latches
> and are consequently "nameless registers".
>
> hence you start to see why the Academic literature is hopelessly
> misleading and why Mitch was pretty much compelled to write those two book
> chapters.
>
> l.
>
>
>
> --
> ---
> crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68
>
>

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

* Re: [libre-riscv-dev] Scoreboard vs Tomasulo
From: Luke Kenneth Casson Leighton @ 2020-05-16 15:19 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAPweEDyw+LSW2S4sKWk-V24NSHYe2qqWO+KFqikQ34Q1Guhaig@mail.gmail.com>

https://www.cs.umd.edu/~meesh/cmsc411/website/projects/dynamic/tomasulo.html

Thus, unlike in scoreboarding where the functional unit would stall during
a WAR hazard, the functional unit is free to execute another instruction

idiot.

utterly false and misleading.

i am too irritated by these repeated glaring errors and misunderstandings
right now to go into it in detail.

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

* Re: [libre-riscv-dev] Scoreboard vs Tomasulo
From: Luke Kenneth Casson Leighton @ 2020-05-16 15:23 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAPweEDyw+LSW2S4sKWk-V24NSHYe2qqWO+KFqikQ34Q1Guhaig@mail.gmail.com>

 In Tomasulo's algorithm, the control logic is distributed among the
reservation stations, whereas in scoreboarding, the scoreboard keeps track
of everything.

false and misleading.

as previously mentioned, the Computation Unit latches (equivalent to RS
Row) contain READ REQUEST and GOREAD synchronisation that effectively is
just as "distributed" as Tomasulo.

also as previously mentioned the ROB CAM is just as centralised as the DMs.

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

* Re: [libre-riscv-dev] daily kan-ban update 16may2020
From: Michael Nolan @ 2020-05-16 15:37 UTC (permalink / raw)
  To: libre-riscv-dev
In-Reply-To: <CAPweEDxVm-gXw=m2YiVix6zDO3DO2mdTYrHn5ain=X3dy2S0ag@mail.gmail.com>

Yesterday I worked on the branch Function Unit and implemented (I think) 
all the types of regular branches (no traps though). Today, I'd like to 
finish up the CR Function unit, and do some general tidying.

--Michael


_______________________________________________
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 15:52 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAPweEDyw+LSW2S4sKWk-V24NSHYe2qqWO+KFqikQ34Q1Guhaig@mail.gmail.com>

https://www.cs.umd.edu/~meesh/cmsc411/website/projects/dynamic/modern.html

this entire section is misleading in several ways. it's not wrong per se,
it's just not the only solution.

the *other* solution is to have "precise shadowing".

this is a system (described at the end of Mitch 2nd chapter) which allows
result *computation* to run ahead but where result *commit* is prevented
and prohibited.

(the gate count required to do so is extremely low.)

this on the face of it would seem to stop FUs from progressing because they
cannot do so until they receive their operands... and um how could they do
that if writing to the regfile is prohibited?

the answer is very simple: that is what Operand Forwarding is for, aka
"Common Data Bus(es)".

so by preventing write commit, we can run ahead for a considerable time, no
stalling at all.

when the branch prediction resolves, we then either:

* release the shadow which allows a ton of results to begin committing.
order is not strictly relevant except as preserved by the hazard detection

* call the "go die" line which drops absolutely every downstream result and
partial computation underway on the floor.  the PC then issues ops down the
alternative path.

(i did actually try dual path execution: theoretically our engine can do
it, i just could not get it to work last year, it was taking too long to
debug, and i had to focus on other things).


the thing that is particularly misleading about this particular section is
that it instills in the reader's mind the false impression that there is a
mandatory correlation between speculative execution and operand order
committing.

this is just false.

if the commit can be stalled until it is guaranteed known that, after that
point it is perfectly *safe* to commit (the operation is 100% going to
succeed)

    AND

if there are no hazards remaining

   THEN

who _cares_ what order results are committed? answer: nobody.



so... useful inasmuch as it is written by an academic and thus is really
readable.

sadly though it contains the usual glaring errors, misunderstandings and
omissions which are widely pervasive and common throughout the *entire*
academic world, even by those who claim to have studied 6600 scoreboards,
even by those who claim to be experts on RISC design.

for the most part that involves cursory reading the patent on 6600 Q
Tables, *not* studying Thornton's book in great depth and taking the time
to translate the (now archaic) transistor level diagrams into modern IEEE
standard electronics symbols - something that Mitch went to a lot of
trouble to do.

i trust that this gives you something of an eyeopener into the extent of
the misapprehensions that the Academic community is under, regarding out of
order engine design.

the closest working implementation i have seen similar to what we are doing
is a conversion of an existing RV32 design to superscalar and multi issue
by a chinese guy who has not revealed his name, online.

he also did multi-bit unary transitive relationships and dependency
tracking in exactly the same way that we will, having re-derived 6600
scoreboards with no reference to any academic literature.

however he did not at the same time increase load store data bandwidth, and
on top of RV32I it is a hell of a lot of extra work to bring up to where we
can use it... and it's all in verilog.

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

* Re: [libre-riscv-dev] daily kan-ban update 16may2020
From: Luke Kenneth Casson Leighton @ 2020-05-16 15:56 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <3343e5fc-bb95-a1d2-9598-24e9f0b8e5c5@gmail.com>

On Saturday, May 16, 2020, Michael Nolan <mtnolan2640@gmail.com> wrote:

> Yesterday I worked on the branch Function Unit and implemented (I think)
> all the types of regular branches (no traps though). Today, I'd like to
> finish up the CR Function unit, and do some general tidying.


sounds great.

i don't know about you, i was deeply impressed that crand etc are all
implemented in about 2 key lines of code by using the actual instruction
bitfield as a 4 row truth table.

this is so ridiculously minimalistic that it is worth documenting properly,
otherwise it is easy to overlook, a la "where's the damn switch
statement??" :)

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

* Re: [libre-riscv-dev] Scoreboard vs Tomasulo
From: Yehowshua @ 2020-05-16 15:59 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAPweEDweXSC5c_ROQ8a3Y4hQMaJYmD_jAriadcZk9PRrkjOXvA@mail.gmail.com>

This is a very intricate and complicated subject matter for sure.

At some point, it be great to really break things down and make them more accessible.

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

* [libre-riscv-dev] Priority Encoder
From: Yehowshua @ 2020-05-16 16:17 UTC (permalink / raw)
  To: Libre-RISCV General Development

Do we have a priority encoder in our codebase?
I didn’t see on in nmutil.

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] Priority Encoder
From: Luke Kenneth Casson Leighton @ 2020-05-16 16:27 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <16F915EC-9270-4A28-80E0-0D36029AC6A1@gatech.edu>

On Saturday, May 16, 2020, Yehowshua <yimmanuel3@gatech.edu> wrote:

> Do we have a priority encoder in our codebase?


nmigen.hdl.coding.

cd nmigen
grep -ri encoder


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

* Re: [libre-riscv-dev] Priority Encoder
From: Yehowshua @ 2020-05-16 16:29 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <CAPweEDxsrKHFyoyTC1mem4Z2GJZR5P4YmsMRaKwbXdnKfNX3jQ@mail.gmail.com>

Ah. Thanks.

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-16 17:33 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <25AC8A2E-D48F-439F-AF9D-0EB3DC08D7CC@gatech.edu>

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

^ permalink raw reply

* Re: [libre-riscv-dev] Priority Encoder
From: Luke Kenneth Casson Leighton @ 2020-05-16 17:40 UTC (permalink / raw)
  To: Libre-RISCV General Development
In-Reply-To: <E22D6C66-7663-410C-9AAD-6FECAAD95E36@gatech.edu>

On Saturday, May 16, 2020, Yehowshua <yimmanuel3@gatech.edu> wrote:

> Ah. Thanks.


nmigen Encoder (unary onehot to binary) and Decoder (binary to unary
onehot) back to back is called a PriorityPicker.

do it exactly like that and you end up with significantly suboptimal output
from yosys due to the use of an unnecessary pmux, created by the use of an
Encoder, that yosys cannot in any way optimise out, even if you flatten the
two modules.

this is why nmutil PriorityPicker exists *and is not based on Encoder or
Decoder*.

yosys does a fantastic job of flattening nmutil PriorityPicker down to only
a 3 gate path, even for as high as 16 inputs-outputs.

this is on a par with the kind of gate level optimisation that Mitch Alsup
carries out in his designs.

yes, there was a discussion about that on comp.arch a couple months ago.

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 314] Create Condition Register pipeline
From: bugzilla-daemon @ 2020-05-16 18:00 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 #3 from Michael Nolan <mtnolan2640@gmail.com> ---
The hell? IBM separately defines mtcrf and mtocrf, and reserves a bit to
differentiate between the two. Except there's no functional difference between
the two that I can tell, and the assembler will even assemble some instances of
mtcrf as mtocrf. 


Basically mtcrf fxm, reg uses fxm to construct a 32 bit mask, where each bit in
fxm corresponds to 4 bits in the mask (so mtcrf 0xf1 would correspond to a mask
of 0xffff000f). It then uses this mask to choose between bits of CR and the
input register, and writes them back to CR

mtocrf fxm, reg assumes fxm is a one hot encoded index into the bits of reg. It
grabs those bits from reg and inserts them into cr, leaving the rest untouched.
If fxm is not onehot, then the result is undefined.

Why these are different, I don't know.

-- 
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 18:27 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 #4 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
btw apologies i did a code-munge on cr/main_stage.py - it did work prior to
a rebase-conflict... am investigating, will keep in touch if i spot the
discrepancy.

-- 
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 18:28 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 #5 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Luke Kenneth Casson Leighton from comment #4)
> btw apologies i did a code-munge on cr/main_stage.py - it did work prior to
> a rebase-conflict... am investigating, will keep in touch if i spot the
> discrepancy.

oh: i think it's just that you added the unit test before adding the code.

-- 
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 18:38 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 #6 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Michael Nolan from comment #3)
> The hell? IBM separately defines mtcrf and mtocrf, and reserves a bit to
> differentiate between the two. Except there's no functional difference
> between the two that I can tell, and the assembler will even assemble some
> instances of mtcrf as mtocrf. 

bizarre.

* mtcrf FXM,RS

    mask <- ([FXM[0]]*4 || [FXM[1]]*4 || [FXM[2]]*4 || [FXM[3]]*4 ||
             [FXM[4]]*4 || [FXM[5]]*4 || [FXM[6]]*4 || [FXM[7]]*4)
    CR <- ((RS)[32:63] & mask) | (CR & ¬mask)

* mtocrf FXM,RS

    count <- 0
    do i = 0 to 7
      if FXM[i] = 1 then
        n <- i
        count <- count + 1
    if count = 1 then
        CR[4*n+32:4*n+35] <- (RS)[4*n+32:4*n+35]
    else CR <- undefined


> Basically mtcrf fxm, reg uses fxm to construct a 32 bit mask, where each bit
> in fxm corresponds to 4 bits in the mask (so mtcrf 0xf1 would correspond to
> a mask of 0xffff000f). It then uses this mask to choose between bits of CR
> and the input register, and writes them back to CR

> mtocrf fxm, reg assumes fxm is a one hot encoded index into the bits of reg.
> It grabs those bits from reg and inserts them into cr, leaving the rest
> untouched. If fxm is not onehot, then the result is undefined.
> 
> Why these are different, I don't know.

clueless.  suggest to use nmutil PriorityPicker on FXM (see nmutil) because it
can be used do the one-hot detection very efficiently.

if the output is not exactly equal to the input from a PriorityPicker
(and is not zero) then this is the condition for detection that FXM
is one-hot.

p = PriorityPicker
p.i.eq(FXM)

is_onehot.eq(p.i == p.o & p.i != 0)

-- 
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 18:38 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 #7 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Luke Kenneth Casson Leighton from comment #6)

sorry:

p = PriorityPicker(8)
comb += p.i.eq(FXM)
comb += is_onehot.eq(p.i == p.o & p.i != 0)

-- 
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 18:42 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 #8 from Michael Nolan <mtnolan2640@gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #6)

> 
> clueless.  suggest to use nmutil PriorityPicker on FXM (see nmutil) because
> it
> can be used do the one-hot detection very efficiently.
> 
> if the output is not exactly equal to the input from a PriorityPicker
> (and is not zero) then this is the condition for detection that FXM
> is one-hot.
> 
> p = PriorityPicker
> p.i.eq(FXM)
> 
> is_onehot.eq(p.i == p.o & p.i != 0)

For mtocrf I don't think this is necessary. If the onehot condition is not
satisfied, it lists the result as being undefined. This should mean that the
current behavior is acceptable

For mfocrf, the situation is similar, the extra bits of the output register are
undefined, unless the input is onehot, in which case they are set to 0. Setting
them to 0 for all bits not selected by the mask should be acceptable here too

-- 
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 18:46 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 #9 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
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.

my concern is that if we rely on the "undefined" behaviour to say "ok we
choose to make mtcrf and mtocrf the same", some assembly writers may
have chosen *specifically* to assume that CR is set to ZERO (or some
other value) after noting that that behaviour occurs on POWER9...

you follow where that goes?

i really do not like "undefined" behaviour in specifications.  it's always
a problem.

-- 
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 18:47 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 #10 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
(In reply to Michael Nolan from comment #8)

> For mtocrf I don't think this is necessary. If the onehot condition is not
> satisfied, it lists the result as being undefined. This should mean that the
> current behavior is acceptable
> 
> For mfocrf, the situation is similar, the extra bits of the output register
> are undefined, unless the input is onehot, in which case they are set to 0.
> Setting them to 0 for all bits not selected by the mask should be acceptable
> here too

except (cross-over) this may bite us due to incompatibility with the
"undefined"
behaviour that assembly writers use these for - in *direct* but de-facto
violation
of the standard.

royal nuisance.  let's not hyper-prioritise it 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 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

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