Solving the compression dictionary problem

[Kelly Dean]

The privileged spec provides for switching between RV32 and RV64 modes using the MXL field, with the corresponding change of compression dictionary. That's great, but at least two more dictionaries will be useful for specialized workloads:

FP, including not just load/store, but also other common FP instructions.

Small embedded, with no FP instructions (not even load/store), but instead maybe byte/halfword load/store/computation, and bit manipulation. Standard RV32C dedicates 1/3 of the compressed encoding space to FP, which is a huge waste for embedded systems with no FPU.


Even though fully custom per-program dictionaries aren't technically practical, per-program selection from among a few dictionaries apparently is. It seems worthwhile to add 3 or 4 bits of user context to enable selection, with a few standard dictionaries and a few reserved for use by custom extensions.

Subroutines could switch the dictionary, though of course the standard calling convention would have to specify that the dictionary must be set to the canonical one for the base ISA.

If that's politically impractical, then at least the eight floating-point instruction encodings C.F[L|S][W|D][SP] standardized for RV32IC should be reserved for custom use for RV32EC.

[Cesar Eduardo Barros]

Em 16-03-2018 20:21, Kelly Dean escreveu:
> The privileged spec provides for switching between RV32 and RV64 modes using the MXL field, with the corresponding change of compression dictionary. That's great, but at least two more dictionaries will be useful for specialized workloads:
>
> FP, including not just load/store, but also other common FP instructions.
>
> Small embedded, with no FP instructions (not even load/store), but instead maybe byte/halfword load/store/computation, and bit manipulation. Standard RV32C dedicates 1/3 of the compressed encoding space to FP, which is a huge waste for embedded systems with no FPU.
>
>
> Even though fully custom per-program dictionaries aren't technically practical, per-program selection from among a few dictionaries apparently is. It seems worthwhile to add 3 or 4 bits of user context to enable selection, with a few standard dictionaries and a few reserved for use by custom extensions.

Unless the differences between them are minor, having 8 or 16 compressed
ISA variants is probably too much. I'm more of a software guy, but as
far as I understand, every extra gate in the critical path makes it
harder to reach higher speeds.

We already have two compressed ISA variants: the normal one, and one
where every compressed instruction is an illegal instruction. On an
embedded system with no FPU, having a third one where the compressed FPU
instructions (which normally would be illegal instructions, since
there's no FPU) mean something else should not be too costly. But I
don't see much of a point of having more than that, and every new
variant adds a cost to what can be a critical path.

> Subroutines could switch the dictionary, though of course the standard calling convention would have to specify that the dictionary must be set to the canonical one for the base ISA.

That would be bad for speed, since switching the compressed ISA variant
will require a flush of the pipeline (the already decoded instructions
have to be discarded, since the decoder was in the wrong state). If the
"uncompressed" instructions are cached, that cache would also need to be
flushed.

> If that's politically impractical, then at least the eight floating-point instruction encodings C.F[L|S][W|D][SP] standardized for RV32IC should be reserved for custom use for RV32EC.

Aren't they already reserved, as a side effect of the F extension not
being present? "If an implementation does not require floating-point,
then the seven major opcodes reserved for standard floating-point
extensions (LOAD-FP, STORE-FP, MADD, MSUB, NMSUB, NMADD, OP-FP) can be
reused for non-standard extensions." -- I'd argue that this applies also
to their compressed equivalents.

--
Cesar Eduardo Barros
ces...@cesarb.eti.br

[Albert Cahalan]

On 3/16/18, Kelly Dean <ke...@prtime.org> wrote:

> Even though fully custom per-program dictionaries aren't technically
> practical,

Depending on your definitions of "program" and "practical", IBM did
exactly this with the PowerPC 405 LP. It's called CodePack. It has a
60% compression ratio and doesn't tend to change performance.
SADC and CCRP are other methods it seems, not commercialized.

Paper:
https://researcher.watson.ibm.com/researcher/files/us-lefurgy/micro32.codepack.pdf

Slides:
https://researcher.watson.ibm.com/researcher/files/us-lefurgy/2005-03-23-UT-codecompression.pdf

[Kelly Dean]

That question raises another one: Will the compliance test suites only verify that mandatory features are present? Or also verify that opcodes reserved for future standard use (not custom use), e.g. RVC quadrant 0 #100, or the all-zero encoding (permanently defined as illegal), are not used for custom use?

If the latter, then what behavior is allowed? Illegal instructions are described in several places in riscv-spec-v2.2.pdf as raising exceptions. Page 7 says “The instruction descriptions in following chapters describe conditions that raise an exception during execution. Whether and how these are converted into traps is dependent on the execution environment”.

That suggests any behavior at all is allowed, which would make it impossible for the test suites to enforce reservation, which would make them useless for defending against uncooperative manufacturers, which could market RV32EC processors that use the reserved opcodes. Effectively, all opcodes reserved for future standard use are actually available for custom use, so the distinction is nothing more than a plea for cooperation.

Trapping appears to be mandated in only one place: p. 47 says “If frm is set to an invalid value (101111), any subsequent attempt to execute a floating-point operation with a dynamic rounding mode will cause an illegal instruction trap.” But any behavior is allowed in a trap handler too, including simply ignoring the exception, so it seems the test suite wouldn't even be able to verify that the trap happened.

[Allen Baum]

<compliance hat on>

That's a very good question, and my expectation is that compliance will test (any) base*+any extensions in MISA.

After that it gets (very) interesting.

Here is my canonical example: 

MUL is implemented in HW, but not DIV, with the expectation that DIV will trap and be handled by firmware.

But MISA.M is clear, since M-mode can't execute the mandatory DIV.

So, if the compliance test suite sees that MISA.M is 0, it should test to ensure that both MUL and DIV ops give illegal instruction traps.

DIV traps - but  MUL doesn't - so compliance test fails.

We will need to deal with cases like that, and others.

Attend the Compliance TG meeting if you want your opinions to be heard .

<compliance hat off>

--
You received this message because you are subscribed to the Google Groups "RISC-V ISA Dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to isa-dev+unsubscribe@groups.riscv.org.
To post to this group, send email to isa...@groups.riscv.org.
Visit this group at https://groups.google.com/a/groups.riscv.org/group/isa-dev/.
To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/9S6npfvWfw4MAezlVEIYzwR2ATIs7V0vZczYCX4ZPHL%40local.

[Cesar Eduardo Barros]

Em 17-03-2018 17:05, Allen Baum escreveu:
> <compliance hat on>
> That's a very good question, and my expectation is that compliance will
> test (any) base*+any extensions in MISA.
> After that it gets (very) interesting.
> Here is my canonical example:
>
> MUL is implemented in HW, but not DIV, with the expectation that DIV
> will trap and be handled by firmware.
> But MISA.M is clear, since M-mode can't execute the mandatory DIV.
> So, if the compliance test suite sees that MISA.M is 0, it should
> test to ensure that both MUL and DIV ops give illegal instruction traps.
> DIV traps - but  MUL doesn't - so compliance test fails.
>

But if MISA.M is clear, meaning the M extension isn't present, wouldn't
the M opcodes be available for non-standard extensions? In this
particular example, the non-standard extension happened to be identical
to "the MUL half of the M extension", but that wouldn't be guaranteed.

Or is it supposed to be possible to disable the decoding of any
non-standard extension? But then in the "custom coprocessor using the
RISC-V ISA as a base" case, you might be adding extra complexity to the
decode step just to be able to run the compliance test suite (for a
custom coprocessor, there'd be no real good reason to turn off the
custom instructions which are probably the main point of having the
coprocessor in the first place).

I think the main sticking point is M-mode itself. Is the compliance suit
going to focus on "below M mode", that is, everything needed to
implement M-mode software, or "above M mode", that is, the view M-mode
presents to S-mode and/or U-mode? How custom can M-mode be? Is M-mode
software going to be custom-made for each core, or is it supposed to be
very portable? If it's supposed to be portable, why do we need the
distinction between M-mode and S-mode?

In the particular MUL/DIV example, it would be very useful to validate
the view presented by M-mode to the layers above it, to make sure that
the DIV emulation is correct. On the other hand, this might force the
supplier of the hart to also supply the M-mode monitor, or at least the
part of it responsible for emulating the M extension.

In my opinion, for this particular example and others like it, the
compliance test for an extension should have four modes: absent (every
instruction traps), present (every instruction works), custom (do not
test the instructions since they'll do something else), and partial
(every instruction either works or traps, with the expectation that M
mode will emulate the ones which trap). Then for every extension, which
of the four modes are used would be listed in the compliance statement
(and in the test configuration).

Cesar Eduardo Barros
ces...@cesarb.eti.br

[Allen Baum]

(oops, resending with reply-to-all)

Yes, exactly - there are many ways to handle this; your 4 modes is one way, and exactly the method we choose.

My favored approach would be similar to yours, and we'll (eventually) be discussing the options in the compliance workgroup.

You above/below M-mode is a bit tricky. If someone is selling a chip, and want to use the trademark, they'll have to pass a compliance suite.

But (in my particular example) they have no control over whether someone will supply a handler that emulates DIV or not.

So how you handle that? If it's compliant in someone's platform, but not in someone elses - can you claim compliance?

We will have a lot to discuss...

[Kelly Dean]

Allen Baum writes:

> MUL is implemented in HW, but not DIV, with the expectation that DIV will
> trap and be handled by firmware.
> But MISA.M is clear, since M-mode can't execute the mandatory DIV.
> So, if the compliance test suite sees that MISA.M is 0, it should test to
> ensure that both MUL and DIV ops give illegal instruction traps.
> DIV traps - but MUL doesn't - so compliance test fails.

Where does the spec say that trapping illegal instruction exceptions is mandatory? Page 7 says that trapping exceptions is optional.

[Allen Baum]

That's a good point.

Krste said in the compliance TG meeting on Thursday that compliance tests should test only what is claimed to exist, and not what doesn't.

So, given that, I believe you are correct - it would not test any op in the M extension to see if it exists or not.

[Kelly Dean]

Allen Baum writes:

> Krste said in the compliance TG meeting on Thursday that compliance tests
> should test only what is claimed to exist, and not what doesn't.
> So, given that, I believe you are correct - it would not test any op in the
> M extension to see if it exists or not.

(From earlier in this thread): If that abstinence also includes opcodes reserved for future standard use (not custom use), e.g. RVC quadrant 0 #100, or the all-zero encoding (permanently defined as illegal), then all such opcodes are actually available for custom use; there's no enforcement of the distinction.

[kr...@berkeley.edu]

The compliance test should test for known illegal opcodes (16 0s, and
ILEN bits of all 1s), but not for reserved opcodes.

There is an important difference between reserved and custom opcodes.
Future standards can never use "custom" opcodes, while "reserved" are
reserved for future standards use.

An implementation can be non-conforming and use reserved opcodes for
additional implementation-specific instructions if the implementer
does not care about compatibility of that design with future
standards. It's a little outdated now, but Chapter 21 (Extending
RISC-V) describes "standards-compatible global encodings" as those in
which the supported standard extensions are present in the standard
places in the instruction encoding. The compliance test should pass
on such implementations if they correctly implement the standard
components they claim to have.

The primary reason to try to mechanically enforce the distinction
between "custom" and "reserved" is so that customers could be assured
the implementation could be made forwards-compatible using trap and
emulate. But even if we wanted to, I claim it's not simple to build
an effective modular compliance test that detects if non-implemented
standard or reserved opcodes are being trapped in an emulatable way.
Given that future standards use of the opcode space is unknowable,
this devolves into separate tests for each possible opcode
combination, which isn't really practical especially given that
instructions can also be many bits longer than 32. Moreover, checking
that an implementation traps on reserved opcodes isn't enough to
guarantee it would be forwards-compatible, as not every possible
future extension can necessarily be emulated in this way. Even among
the current set of extensions, the A extension is impossible to
emulate without specific system support.

Krste

| --
| You received this message because you are subscribed to the Google Groups "RISC-V ISA Dev" group.

| To unsubscribe from this group and stop receiving emails from it, send an email to isa-dev+u...@groups.riscv.org.

| To post to this group, send email to isa...@groups.riscv.org.
| Visit this group at https://groups.google.com/a/groups.riscv.org/group/isa-dev/.

| To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/Ou3f8yKGSpYoFLkL2SPlgGbwGg5Rd0KfShCnvXPQ7yY%40local.

[lkcl .]

On Mon, Mar 26, 2018 at 8:34 AM, <kr...@berkeley.edu> wrote:

> Moreover, checking
> that an implementation traps on reserved opcodes isn't enough to
> guarantee it would be forwards-compatible, as not every possible
> future extension can necessarily be emulated in this way.

in my mind that would indicate a red flag / failure in the standard.
question: what would the implications be of setting a hard rule which
*guarantees* that future extensions that cannot be emulated are simply
not to be considered? [see caveat below]

> Even among
> the current set of extensions, the A extension is impossible to
> emulate without specific system support.

Chapter 7, "A" is "Atomic". so, emulation of "Atomic" instructions
would... yes, by their very nature, be flat-out impossible to emulate,
unless there was a way to implement transactional roll-back, which
quickly becomes hell.

so clearly anything that's expected to be atomic in future extensions
would have to be exempt from the above proposed hard rule... unless
it's thought through *right now*. the [mandatory] addition of
hardware-level spin-locks would do the trick [with the inherent risk
of completely locking up an entire processor stone-dead...]

so *apart* from atomic operations, what would be the implications of
saying "if it can't be emulated using existing instructions that exist
*right now*, it can't be a future extension of the spec, end of
story?"

l.

[kr...@berkeley.edu]

Apart from the difficulty in sanely checking/reporting all reserved
opcode combinations, I don't have faith that everything we've defined
is enough to efficiently emulate everything we will want in the
future.

You've already had to insert caveats in your reasoning below to handle
the atomics example I gave. What makes you so sure that's the only
exception needed for future extensions? What about timing-sensitive?
DPA-resistant? Quantum?

Forwards compatibilty is nice but not a panacea, and will always be
limited in applicability. We don't want tail to wag the dog.

Krste

[lkcl .]

On Mon, Mar 26, 2018 at 9:40 AM, <kr...@berkeley.edu> wrote:
>
> Apart from the difficulty in sanely checking/reporting all reserved
> opcode combinations, I don't have faith that everything we've defined
> is enough to efficiently emulate everything we will want in the
> future.
>
> You've already had to insert caveats in your reasoning below to handle
> the atomics example I gave. What makes you so sure that's the only
> exception needed for future extensions?

i didn't ask the question rhetorically [or with a confrontational /
egoistical implication that indicated i knew the answer]: i was
inviting people to genuinely discuss it.

> What about timing-sensitive?
> DPA-resistant? Quantum?

ok these are fantastic examples. how would each of them be impacted
by such a rule? as in: i'm interested to know if there is
specifically anything other than Atomic which would *realistically* be
unimplementable. timing-critical extensions would clearly be
unimplementable, so that's two noteworthy examples. apologies but i'm
not familiar with the acronym "DPA" so can't say. quantum
extensions... i would actually expect those to be emulatable [with
some really REALLY complex and slow software, but still
implementable].

timing-sensitive extensions would come with their own set of
problems... thinking it through, i recall seeing a discussion about
how the number of registers in RISC-V has an adverse impact on
real-time / mission-critical interrupt response time.

so when you say timing-sensitive extensions what did you have in mind?
controlling external hardware? real-time low-latency response times,
nanosecond resolution, that sort of thing?

can anyone else think of some examples of extensions? what about
SIMD? or DSP (for say LTE base-band, which needs huge computational
low-latency resources)?

l.

[kr...@berkeley.edu]

Consensus is that compliance suites will need to have versions, and if
at some later date, there's agreement on truly useful
forward-compatibility checks, we can add them in later version.

Meanwhile, we should stick to compliance tests only checking for
existence and not checking for non-existence.

Krste

Yes.

[lkcl .]

On Mon, Mar 26, 2018 at 11:08 AM, <kr...@berkeley.edu> wrote:
>
> Consensus is that

whoa-who, krste, hang on a minute: i initiated an open discussion in
the spirit of enquiry so that other people would feel that they'd been
invited to engage in the development of RISC-V, and saying "consensus
is" without saying *who* is involved in that consensus, and without
allowing some time for people to contribute, is completely shutting
down the discussion - and an opportunity for wider consensus to be
reached - before it's even begun.

was that an oversight on your part?

l.

[Bruce Hoult]

There is in fact a Compliance Testing working group within the RISC-V foundation that any interested member of the foundation can join, to influence said consensus.

l.

--
You received this message because you are subscribed to the Google Groups "RISC-V ISA Dev" group.

To unsubscribe from this group and stop receiving emails from it, send an email to isa-dev+unsubscribe@groups.riscv.org.

To post to this group, send email to isa...@groups.riscv.org.
Visit this group at https://groups.google.com/a/groups.riscv.org/group/isa-dev/.

To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/CAPweEDy50BRmDq%3DJ66DyrvtJRzAMSrTexwO2kyExYsv_fojv1A%40mail.gmail.com.

[lkcl .]

On Mon, Mar 26, 2018 at 12:05 PM, Bruce Hoult <br...@hoult.org> wrote:

> There is in fact a Compliance Testing working group within the RISC-V
> foundation that any interested member of the foundation can join, to
> influence said consensus.

unfortunately bruce i asked if the RISC-V Foundation would agree (in
writing) to indemnify contributors (in the instance where the use of a
compliance-conformant processor resulted in the death of a person, and
the RISC-V Foundation was sued, would the RISC-V Foundation agree not
to sue the contributors?), but i have not received a response.

so it's not quite as straightforward as "anyone may join". anyone
joining would also need to have the financial resources to afford
indemnification and liability insurance.

l.

[Bruce Hoult]

So you're not at this moment sure whether members of a working group would be indemnified? Maybe they are, maybe they are not. Fair enough.

I'm no expert, but would it not be the case that someone outside such a working group, trying to influence the direction of the working group via, say, public mailing lists posts, would have absolutely no prospect of being protected from lawsuits in the event that their advice appeared to have been influential?

I prefer to worry more about technical matters than hypothetical lawsuits, but I don't see how it's any more dangerous contributing from inside the tent than out.

l.

--
You received this message because you are subscribed to the Google Groups "RISC-V ISA Dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to isa-dev+unsubscribe@groups.riscv.org.
To post to this group, send email to isa...@groups.riscv.org.
Visit this group at https://groups.google.com/a/groups.riscv.org/group/isa-dev/.

To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/CAPweEDzYgiu6FYHSHBAiGnyA2tKAizVAGxOG9EH1uXG09t8UJg%40mail.gmail.com.

[lkcl .]

On Mon, Mar 26, 2018 at 1:02 PM, Bruce Hoult <br...@hoult.org> wrote:

> So you're not at this moment sure whether members of a working group would
> be indemnified? Maybe they are, maybe they are not. Fair enough.
>
> I'm no expert, but would it not be the case that someone outside such a
> working group, trying to influence the direction of the working group via,
> say, public mailing lists posts, would have absolutely no prospect of being
> protected from lawsuits in the event that their advice appeared to have been
> influential?

huh. good point. i would hazard a guess that it would revolve
around who is formally assigned or agreed to the responsibility.
honestly though i don't know.

> I prefer to worry more about technical matters than hypothetical lawsuits,
> but I don't see how it's any more dangerous contributing from inside the
> tent than out.

... leaving that aside (despite really appreciating the insight you
raised), yes it would indeed be nice to be able to discuss technical
matters.... but krste's shut the conversation down before it could get
started. if it was anyone else, the conversation could potentially
continue, but krste (apologies for referring to you in the third
person, it's partly necessary: i'm aware you'll be reading this) is in
a particularly unique position of influence which i'll outline a bit
about, below.

i don't know if you're aware of it, krste, but people are scared of you.

from reading the book "invisible dynamics" [0] i'm keenly aware that
it's important to recognise and appreciate that you are both
technically extremely capable *and* also one of the earliest people
involved in RISC-V. that makes you an extremely valuable contributor,
and also it places you in a position of enormous influence and lends a
much higher significance to your words than anyone else who might wish
to speak and/or contribute to RISC-V.

thus, if you say something, *nobody* wants to contradict you.
absolutely nobody. why not? well, because (a) you're highly likely
(technically) to be right, having far more knowledge than them but (b)
just as importantly they will fear that they're overstepping somehow
(because you're a longer-standing contributor than them) and (c) the
consequences for them of contradicting or being *perceived* to
contradict you might be really quite disproportionately severe.

* for people in corporations, if they're seen to be pissing you off
in some way, that's their own job prospects they just pissed on.

* likewise for people in academia.

* for people in the open hardware and free software world it's
slightly different: their bread-and-butter depends on good-will and on
reputation... and if they ever find themselves in a pissing contest
with you, their reputation is *instantly* shot to shit and they'll be
completely ostracised... forever [the public memory of the internet's
a bitch... cf archive.org].

so *they* won't say anything to you *either*.

me? i'm known for speaking my mind, plain and simple. no bullshit,
no agenda. i don't *have* a "reputation" to "protect", and i don't
agree to enslave myself to pathological profit-maximising corporations
[1]. that makes me quite possibly literally the only person in the
world who's ever going give you some insights into how your words
affect the RISC-V Project, and i'm hearing from multiple sources, as
well as observing personally instances where, RISC-V's development is
[summarising / paraphrasing] heavily / unduly / overbearingly
influenced and controlled by UCB-BAR.

now, i have no control over you. you are your own person, as is
everyone else. you make your own decisions. what brings anyone
together and puts them in a situation where they might have to take
into account other people and other people's input and influence is
when a goal is shared between them. and within that context - sharing
of the goal of moving RISC-V forward - i'm seeing evidence that some
of the "Systemic Laws" (as they put it) outlined in "Invisible
Dynamics" [0] being violated. these issues are easy to fix... but
important to acknowledge, where acknowledging the situation is (as
opposed to "denial"), interestingly, one of the six Systemic Laws.

anyway, like i said: i have no control over you. you have absolutely
no reason to listen to a word i say. your decisions are entirely your
responsibility. the only thing that i am permitted to do is to bring
this to your attention, to make you (and others) aware. what you do -
where you go from here - is entirely your responsibility.

l.

[0] https://www.amazon.com/dp/3896704915
[1] cf the documentary "The Corporation" and Professor Yunus "Creating
a World Without Poverty".