On Sunday, January 23, 2022 at 4:09:03 AM UTC-6, Michael S wrote:
> On Sunday, January 23, 2022 at 1:31:58 AM UTC+2, Anton Ertl wrote:
> > Michael S <already...@yahoo.com> writes:
> > >I don't think that Spectre-V1 (bounds check bypass) can be solved in hardware without significant performance degradation on many important workloads.
> > We have described here in January 2018 (and repeated it later) how to
> > fix Spectre (all versions): Just treat microarchitectural state like
> > they treat architectural state: only make it visible to the outside on
> > commit, and throw it away on misprediction.
> >
> > I think this can be achieved with little performance degradation for
> > most workloads; it will cost hardware (not huge amounts, but still)
> > and some design effort.
> > - anton
> > --
> > 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> > Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>
<
> I read these discussions. Found all proposals unconvincing.
> They all appear to either underestimate performance cost of not doing load
> that is based on result of speculated load
<
This is not <directly> the problem. It is absolutely OK to perform a LD that
is under the shadow of a branch that reads data which is used as an operand
to another LD (or ST). What is NOT OK is to use the loaded value in a subsequent
AGEN when the LD does not get a hit in either tag or TLB or both. It is the use of
"bad data" that opens the sideband window, and it is the pre-retirement updates
of microarchitectural state (cache tags, cache lines, TLB PTEs, ...) that further
opens the sideband channel window so it can be exploited.
<
> or underestimate area cost of circuit
> that completly undo side-effects of such "twice-speculated" loads.
<
I submit that the overhead of closing this is nearly invisible in size and nearly
invisible in performance.

On Sunday, January 23, 2022 at 9:34:45 PM UTC+2, MitchAlsup wrote:
> On Sunday, January 23, 2022 at 4:09:03 AM UTC-6, Michael S wrote:
> > On Sunday, January 23, 2022 at 1:31:58 AM UTC+2, Anton Ertl wrote:
> > > Michael S <already...@yahoo.com> writes:
> > > >I don't think that Spectre-V1 (bounds check bypass) can be solved in hardware without significant performance degradation on many important workloads.
> > > We have described here in January 2018 (and repeated it later) how to
> > > fix Spectre (all versions): Just treat microarchitectural state like
> > > they treat architectural state: only make it visible to the outside on
> > > commit, and throw it away on misprediction.
> > >
> > > I think this can be achieved with little performance degradation for
> > > most workloads; it will cost hardware (not huge amounts, but still)
> > > and some design effort.
> > > - anton
> > > --
> > > 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> > > Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>
> <
> > I read these discussions. Found all proposals unconvincing.
> > They all appear to either underestimate performance cost of not doing load
> > that is based on result of speculated load
> <
> This is not <directly> the problem. It is absolutely OK to perform a LD that
> is under the shadow of a branch that reads data which is used as an operand
> to another LD (or ST). What is NOT OK is to use the loaded value in a subsequent
> AGEN when the LD does not get a hit in either tag or TLB or both. It is the use of
> "bad data" that opens the sideband window, and it is the pre-retirement updates
> of microarchitectural state (cache tags, cache lines, TLB PTEs, ...) that further
> opens the sideband channel window so it can be exploited.

But majority of the gain from speculation is exactly in situation when "twice-speculated" load misses L1D$

> <
> > or underestimate area cost of circuit
> > that completly undo side-effects of such "twice-speculated" loads.
> <
> I submit that the overhead of closing this is nearly invisible in size and nearly
> invisible in performance.

On Sunday, January 23, 2022 at 2:44:59 PM UTC-6, Michael S wrote:
> On Sunday, January 23, 2022 at 9:34:45 PM UTC+2, MitchAlsup wrote:
> > On Sunday, January 23, 2022 at 4:09:03 AM UTC-6, Michael S wrote:
> > > On Sunday, January 23, 2022 at 1:31:58 AM UTC+2, Anton Ertl wrote:
> > > > Michael S <already...@yahoo.com> writes:
> > > > >I don't think that Spectre-V1 (bounds check bypass) can be solved in hardware without significant performance degradation on many important workloads.
> > > > We have described here in January 2018 (and repeated it later) how to
> > > > fix Spectre (all versions): Just treat microarchitectural state like
> > > > they treat architectural state: only make it visible to the outside on
> > > > commit, and throw it away on misprediction.
> > > >
> > > > I think this can be achieved with little performance degradation for
> > > > most workloads; it will cost hardware (not huge amounts, but still)
> > > > and some design effort.
> > > > - anton
> > > > --
> > > > 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> > > > Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>
> > <
> > > I read these discussions. Found all proposals unconvincing.
> > > They all appear to either underestimate performance cost of not doing load
> > > that is based on result of speculated load
> > <
> > This is not <directly> the problem. It is absolutely OK to perform a LD that
> > is under the shadow of a branch that reads data which is used as an operand
> > to another LD (or ST). What is NOT OK is to use the loaded value in a subsequent
> > AGEN when the LD does not get a hit in either tag or TLB or both. It is the use of
> > "bad data" that opens the sideband window, and it is the pre-retirement updates
> > of microarchitectural state (cache tags, cache lines, TLB PTEs, ...) that further
> > opens the sideband channel window so it can be exploited.
<
> But majority of the gain from speculation is exactly in situation when "twice-speculated" load misses L1D$
<
No, it is not. What is important is that subsequent loads can be processed
the the point of retirement awaiting the missed load to finally resolve and
allow itself and subsequents to retire.
<
Spectré and Meltdown have a side channel means to observe the states of
the cache that is ONLY visible if instructions that will never retire are allowed
to modify cache state (Meltdown) or predictor state (Spectré_).
<
The elimination of a high precision clock also eliminates both of these exploits.
<
But so does deferring the microarchitectural state updates until retirement..
<
> > <
> > > or underestimate area cost of circuit
> > > that completly undo side-effects of such "twice-speculated" loads.
> > <
> > I submit that the overhead of closing this is nearly invisible in size and nearly
> > invisible in performance.

Ivan Godard <ivan@millcomputing.com> writes:
>On 1/23/2022 10:35 AM, Anton Ertl wrote:
>> You don't undo the side-effects. Instead, you don't do the side
>> effects. You just keep the load buffers around until commit, and then
>> you update the L1 cache. And if the line is already in the L1 cache,
>> you only need to keep the info around that the line has been accessed
>> (for LRU).
>
>Yes, but that's hard to get right - the LRU can leak the reference too.

That's why you don't update the LRU info until the load has been
commited.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 1/23/2022 4:16 PM, David W Schroth wrote:
> On Sat, 22 Jan 2022 13:42:35 GMT, anton@mips.complang.tuwien.ac.at
> (Anton Ertl) wrote:
>
>> MitchAlsup <MitchAlsup@aol.com> writes:
>>> I wonder if all of the viruses, Spctr=C3=A9, Meltdown, RoP attacks have red=
>>> uced
>>> PC sales by more than a total of 37 chips ?
>>
>> Probably not by much, thanks also to the competetive landscape. But I
>> think that if one of the manufacturers chose to close Spectre, and
>> then made this big in their marketing, it might win them quite a lot
>> of sales (and lose the other quite a lot).
>>
>> Given that Alder Lake came out still vulnerable to Spectre 54 months
>> after Intel was informed of Spectre in June 2017, it seems that they
>> don't want to take this opportunity to have a USP for a while. We
>> will see with Zen 4 towards the end of the year whether AMD is wiser.
>>
>> We have seen with Rowhammer that the DRAM industry seems to just want
>> to wait this out. They seem to think that Rowhammer-immune DRAM won't
>> sell. Does the CPU industry think the same about Spectre?
>>
>> - anton
>
> I would be interested in this forum's reaction to the article in the
> December 2021 issue of Communications of the ACM, "Speculative Taint
> Tracking (STT): A Comprehensive Protection for Speculatively Accessed
> Data".

Available without paywall at
https://www.cs.tau.ac.il/~mad/publications/micro2019-stt.pdf

On Sunday, January 23, 2022 at 6:14:26 PM UTC-6, David W Schroth wrote:
> On Sat, 22 Jan 2022 13:42:35 GMT, an...@mips.complang.tuwien.ac.at
> (Anton Ertl) wrote:
>
> >MitchAlsup <Mitch...@aol.com> writes:
> >>I wonder if all of the viruses, Spctr=C3=A9, Meltdown, RoP attacks have red=
> >>uced
> >>PC sales by more than a total of 37 chips ?
> >
> >Probably not by much, thanks also to the competetive landscape. But I
> >think that if one of the manufacturers chose to close Spectre, and
> >then made this big in their marketing, it might win them quite a lot
> >of sales (and lose the other quite a lot).
> >
> >Given that Alder Lake came out still vulnerable to Spectre 54 months
> >after Intel was informed of Spectre in June 2017, it seems that they
> >don't want to take this opportunity to have a USP for a while. We
> >will see with Zen 4 towards the end of the year whether AMD is wiser.
> >
> >We have seen with Rowhammer that the DRAM industry seems to just want
> >to wait this out. They seem to think that Rowhammer-immune DRAM won't
> >sell. Does the CPU industry think the same about Spectre?
> >
> >- anton
>
> I would be interested in this forum's reaction to the article in the
> December 2021 issue of Communications of the ACM, "Speculative Taint
> Tracking (STT): A Comprehensive Protection for Speculatively Accessed
> Data".
>
First thoughts: A bunch of new features added to various (already hard to design)
circuits that lose 7%-15% performance. This is to be compared with a HW cost
of a few-ish % that looses an invisible amount of performance by buffering state
updates until safe and forwarding from the buffers while still unsafe.
<
Academic quality.

MitchAlsup wrote:
> On Sunday, January 23, 2022 at 2:44:59 PM UTC-6, Michael S wrote:
>> On Sunday, January 23, 2022 at 9:34:45 PM UTC+2, MitchAlsup wrote:
>>> On Sunday, January 23, 2022 at 4:09:03 AM UTC-6, Michael S wrote:
>>>> On Sunday, January 23, 2022 at 1:31:58 AM UTC+2, Anton Ertl wrote:
>>>>> Michael S <already...@yahoo.com> writes:
>>>>>> I don't think that Spectre-V1 (bounds check bypass) can be solved in hardware without significant performance degradation on many important workloads.
>>>>> We have described here in January 2018 (and repeated it later) how to
>>>>> fix Spectre (all versions): Just treat microarchitectural state like
>>>>> they treat architectural state: only make it visible to the outside on
>>>>> commit, and throw it away on misprediction.
>>>>>
>>>>> I think this can be achieved with little performance degradation for
>>>>> most workloads; it will cost hardware (not huge amounts, but still)
>>>>> and some design effort.
>>>>> - anton
>>>>> --
>>>>> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
>>>>> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>
>>> <
>>>> I read these discussions. Found all proposals unconvincing.
>>>> They all appear to either underestimate performance cost of not doing load
>>>> that is based on result of speculated load
>>> <
>>> This is not <directly> the problem. It is absolutely OK to perform a LD that
>>> is under the shadow of a branch that reads data which is used as an operand
>>> to another LD (or ST). What is NOT OK is to use the loaded value in a subsequent
>>> AGEN when the LD does not get a hit in either tag or TLB or both. It is the use of
>>> "bad data" that opens the sideband window, and it is the pre-retirement updates
>>> of microarchitectural state (cache tags, cache lines, TLB PTEs, ...) that further
>>> opens the sideband channel window so it can be exploited.
> <
>> But majority of the gain from speculation is exactly in situation when "twice-speculated" load misses L1D$
> <
> No, it is not. What is important is that subsequent loads can be processed
> the the point of retirement awaiting the missed load to finally resolve and
> allow itself and subsequents to retire.
> <
> Spectré and Meltdown have a side channel means to observe the states of
> the cache that is ONLY visible if instructions that will never retire are allowed
> to modify cache state (Meltdown) or predictor state (Spectré_).
> <
> The elimination of a high precision clock also eliminates both of these exploits.
> <
> But so does deferring the microarchitectural state updates until retirement.

Nothing really bad happens if you delay such updates, we have seen
examples of this previously in the case of an x86 CPU (around the
Pentium era?) which could not update the branch predictor tables unless
you had a taken-branch-free cycle. I.e. a chain of Jcc where all were
taken including the one at the end that wrapped back up would never be
predicted correctly the first time you entered the loop:

or ecx,-1 ; Set to -1
add ecx,1000001h ; Will set carry

top:
jc carry_set
...
carry_set:
dec ecx ;; Don't touch carry
jnz top

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Michael S <already5chosen@yahoo.com> writes:
>But majority of the gain from speculation is exactly in situation when "twice-speculated" load misses L1D$

First of all, fixing Spectre the way we suggest will not slow the
execution down in that situation.

Second, I very much doubt that these situations provide the majority
of the gain from speculation. You gain from speculative execution
every time the branch predictor predicts correctly. You gain so much
that even in-order cores like the A53 and Bonnell have it. They would
all suffer heavily without branch prediction, including on code that
does not miss the D-cache. I actually expect that such code would
suffer more from leaving away branch predictions, because such code
performs more branches/cycle, so making branches more expensive causes
a bigger slowdown.

There have also been claims that OoO execution gains are mainly due to
being better able to deal with cache misses. That's not the case.
Workloads with few cache misses also benefit greatly from OoO
execution:

E.g., for our LaTeX benchmark:
<http://www.complang.tuwien.ac.at/franz/latex-bench>

Here's the D-cache misses measured on a CPU with 32KB D-cache
(Cortex-A72 on a RK3399 on a Rockpro64 with Debian 9):

LC_NUMERIC=en_US.utf8 taskset -c 5 perf stat -B -e cycles -e L1-dcache-loads -e L1-dcache-load-misses -e L1-dcache-stores -e L1-dcache-store-misses latex bench >/dev/null

Performance counter stats for 'latex bench':

Performance counter stats for 'latex bench':

2,406,381,871 cycles
1,072,495,674 L1-dcache-loads
15,797,929 L1-dcache-load-misses #1.47% of all L1-dcache hits
639,859,039 L1-dcache-stores
1,824,796 L1-dcache-store-misses

And measurements on a Skylake (also 32KB D-cache) with Debian 11:

LC_NUMERIC=en_US.utf8 perf stat -B -e cycles -e L1-dcache-loads -e L1-dcache-load-misses -e L1-dcache-stores -e L1-dcache-store-misses -e LLC-loads -e LLC-load-misses latex bench >/dev/null

Performance counter stats for 'latex bench':

1,567,716,026 cycles
887,037,687 L1-dcache-loads
15,595,603 L1-dcache-load-misses #1.76% of all L1-dcache accesses
554,281,424 L1-dcache-stores
<not supported> L1-dcache-store-misses
2,988,275 LLC-loads
252,212 LLC-load-misses #8.44% of all LL-cache accesses

We see a similar number of D-cache load misses on both CPUs, and a
relatively low D-cache miss rate overall. The L2 cache on the Skylake
reduces the miss rate by another factor of ~5, and the L3 cache by
another factor of 10 (unfortunately, I have no event counters for
these things on the Cortex-A72). If we assume 10 cycles extra for a
L1 miss/L2 hit, 40 cycles extra for a L1/L2 miss/L3 hit, and 200
cycles extra for an l1/l2/l3 miss (and 0 extra cycles for store
misses), the cache misses result in
10*15595603+(40-10)*2988275+(200-40)*252212=285,958,200 cycles on the
Skylake, i.e., less than 20% of the execution time.

Yet when we look at the performance of 2-wide in-order vs. 2-wide OoO
machines, we see that the OoO machines are roughly twice as fast; Only
a small part of this can be explained with OoO papering over cache
misses:

- Intel Atom 330, 1.6GHz, 512K L2 Zotac ION A, Debian 9 64bit 2.368
- AMD E-450 1650MHz (Lenovo Thinkpad X121e), Ubuntu 11.10 64-bit 1.216
- Celeron J1900 (Silvermont) 2416MHz (Shuttle XS35V4) Ubuntu16.10 1.052

- Odroid N2 (1896MHz Cortex A53) Ubuntu 18.04 2.488
- Odroid N2 (1800MHz Cortex A73) Ubuntu 18.04 1.224

The Atom 330 and Cortex-A53 are in-order, while the AMD E-450,
Silvermont, and Cortex-A73 are OoO.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> We have described here in January 2018 (and repeated it later) how to
>> fix Spectre (all versions): Just treat microarchitectural state like
>> they treat architectural state: only make it visible to the outside on
>> commit, and throw it away on misprediction.
>
>While I do believe it can be done I don't think it's as easy as
>it sounds. More specifically it requires:
>- A clear definition of "microarchitectural state".

That's pretty easy: All state that's not architectural. Given that
architectural state also has to be made visible to the outside only on
commit, the end result is that no speculative state must become
visible to the outside.

>- A clear definition of "the outside".

Anything that survives a branch misprediction recovery is outside.

>I think there is a lack of experience with such a viewpoint which makes
>it hard to have a clear understanding of the real costs.

Actually there has been a lot of experience with the same viewpoint
for architectural state since the mid-1990s, we only need to extend it
to all state.

There is one other potential side channel that needs to be taken care
of: resource limitations. This has been used for non-speculative
exploits, but AFAIK not for speculative ones yet. But while we are at
it, we should be thinking about that, too. E.g., if the attacker can
cause the attacked program to perform a speculative access to some
secret, and then perform a data-dependent action that can be watched
by measuring resource contention (e.g., functional unit usage in a
competing SMT thread, or cache access contention on another core).
Not sure if that can really be used for a realistic attack, but if
that side channel can be closed, there's one less worry.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>MitchAlsup wrote:
>> But so does deferring the microarchitectural state updates until retirement.
>
>Nothing really bad happens if you delay such updates, we have seen
>examples of this previously in the case of an x86 CPU (around the
>Pentium era?) which could not update the branch predictor tables unless
>you had a taken-branch-free cycle. I.e. a chain of Jcc where all were
>taken including the one at the end that wrapped back up would never be
>predicted correctly the first time you entered the loop:

If you delay the update until retirement (and at that time you
actually know the outcome of the branch, so update the predictor with
correct data) rather than forever, the branch will be updated after
the first mispreduction, and all subsequent instances of that branch
will be predicted correctly (until the loop is exited).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl [2022-01-24 13:46:12] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>> We have described here in January 2018 (and repeated it later) how to
>>> fix Spectre (all versions): Just treat microarchitectural state like
>>> they treat architectural state: only make it visible to the outside on
>>> commit, and throw it away on misprediction.
>>
>>While I do believe it can be done I don't think it's as easy as
>>it sounds. More specifically it requires:
>>- A clear definition of "microarchitectural state".
>
> That's pretty easy: All state that's not architectural.

AFAIK that includes all the latches & flip-flops, right?

> Given that architectural state also has to be made visible to the
> outside only on commit, the end result is that no speculative state
> must become visible to the outside.

But all the buffers we may add to delay exposing the microarchitectural
state are themselves part of the microarchitectural state. I think this
recursion is well-founded, but it does make thinking about it a bit
harder for me.

>>I think there is a lack of experience with such a viewpoint which makes
>>it hard to have a clear understanding of the real costs.
>
> Actually there has been a lot of experience with the same viewpoint
> for architectural state since the mid-1990s, we only need to extend it
> to all state.

But there is not the same kind of recursion for the non-micro
architectural state.

> There is one other potential side channel that needs to be taken care
> of: resource limitations.

Hmm... I didn't realize this was considered as a different category.
Maybe that's why you think it's easy and I think it's hard: to me side
channels via resource limitations is included in the general
Spectre problem.

Stefan

On Monday, January 24, 2022 at 8:06:39 AM UTC-6, Anton Ertl wrote:
> Terje Mathisen <terje.m...@tmsw.no> writes:
> >MitchAlsup wrote:
> >> But so does deferring the microarchitectural state updates until retirement.
> >
> >Nothing really bad happens if you delay such updates, we have seen
> >examples of this previously in the case of an x86 CPU (around the
> >Pentium era?) which could not update the branch predictor tables unless
> >you had a taken-branch-free cycle. I.e. a chain of Jcc where all were
> >taken including the one at the end that wrapped back up would never be
> >predicted correctly the first time you entered the loop:
<
> If you delay the update until retirement (and at that time you
> actually know the outcome of the branch, so update the predictor with
> correct data) rather than forever, the branch will be updated after
> the first mispreduction, and all subsequent instances of that branch
> will be predicted correctly (until the loop is exited).
<
You must have missed my statement about forwarding. You have to snoop
these deferral buffers and get the most up to date prediction--just like you
have to snoop the miss buffers for data that has not made its way into the
cache.
<
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Monday, January 24, 2022 at 8:02:35 AM UTC-6, Anton Ertl wrote:
> Stefan Monnier <mon...@iro.umontreal.ca> writes:
> >> We have described here in January 2018 (and repeated it later) how to
> >> fix Spectre (all versions): Just treat microarchitectural state like
> >> they treat architectural state: only make it visible to the outside on
> >> commit, and throw it away on misprediction.
> >
> >While I do believe it can be done I don't think it's as easy as
> >it sounds. More specifically it requires:
> >- A clear definition of "microarchitectural state".
<
> That's pretty easy: All state that's not architectural. Given that
> architectural state also has to be made visible to the outside only on
> commit, the end result is that no speculative state must become
> visible to the outside.
<
> >- A clear definition of "the outside".
<
> Anything that survives a branch misprediction recovery is outside.
<
And any 3rd party observer (another CPU or DMA device, but these have
already been restricted to memory).
<
> >I think there is a lack of experience with such a viewpoint which makes
> >it hard to have a clear understanding of the real costs.
<
> Actually there has been a lot of experience with the same viewpoint
> for architectural state since the mid-1990s, we only need to extend it
> to all state.
<
All state that eventually becomes visible.
>
> There is one other potential side channel that needs to be taken care
> of: resource limitations. This has been used for non-speculative
> exploits, but AFAIK not for speculative ones yet. But while we are at
> it, we should be thinking about that, too. E.g., if the attacker can
> cause the attacked program to perform a speculative access to some
> secret, and then perform a data-dependent action that can be watched
> by measuring resource contention (e.g., functional unit usage in a
> competing SMT thread, or cache access contention on another core).
> Not sure if that can really be used for a realistic attack, but if
> that side channel can be closed, there's one less worry.
<
It likely can.
>
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Monday, January 24, 2022 at 9:06:38 AM UTC-6, Stefan Monnier wrote:
> Anton Ertl [2022-01-24 13:46:12] wrote:
> > Stefan Monnier <mon...@iro.umontreal.ca> writes:
> >>> We have described here in January 2018 (and repeated it later) how to
> >>> fix Spectre (all versions): Just treat microarchitectural state like
> >>> they treat architectural state: only make it visible to the outside on
> >>> commit, and throw it away on misprediction.
> >>
> >>While I do believe it can be done I don't think it's as easy as
> >>it sounds. More specifically it requires:
> >>- A clear definition of "microarchitectural state".
> >
> > That's pretty easy: All state that's not architectural.
> AFAIK that includes all the latches & flip-flops, right?
<
Not if these never become "visible"--for example, the pipeline flip-flops
do not become visible, but many times the state they carry does. Here
it is the state not the container holding the state the is important.
<
Notice again: it is the state not the container that matters.
<
> > Given that architectural state also has to be made visible to the
> > outside only on commit, the end result is that no speculative state
> > must become visible to the outside.
<
> But all the buffers we may add to delay exposing the microarchitectural
> state are themselves part of the microarchitectural state. I think this
> recursion is well-founded, but it does make thinking about it a bit
> harder for me.
<
No, they are like the pipeline flip-flops holding state.
<
> >>I think there is a lack of experience with such a viewpoint which makes
> >>it hard to have a clear understanding of the real costs.
> >
> > Actually there has been a lot of experience with the same viewpoint
> > for architectural state since the mid-1990s, we only need to extend it
> > to all state.
<
> But there is not the same kind of recursion for the non-micro
> architectural state.
<
MIcrocoded state would have to be included, pipeline nd sequencing
state is mainly what we have been talking about.
<
> > There is one other potential side channel that needs to be taken care
> > of: resource limitations.
<
> Hmm... I didn't realize this was considered as a different category.
> Maybe that's why you think it's easy and I think it's hard: to me side
> channels via resource limitations is included in the general
> Spectre problem.
>
>
> Stefan

On 1/22/2022 3:42 AM, Terje Mathisen wrote:
> Stephen Fuld wrote:

>> Anyway, if one had this instruction, the main loop in the code above
>> could be something like
>>
>>
>> loop:
>>      LDUB        R10,[R1+R9]
>>      CARRY         R6,IO
>>      LBF        R12,R10,R2     ;I am not sure about R2,  It should be
>> the start of the packed buffer.
>>      STD        R12,[R3+R9<<3]
>>      ADD        R9,R9,#1
>>       CMP        R11,R9,R4
>>       BLT        R11,loop
>
> That is really quite nice.

Thank you!

>>
>> For a savings of about 10 instructions in the I cache, but fewer in
>> execution (but still significant) depending upon how often the
>> instructions under the predicate are executed.
>>
>>
>> Anyway, Of course, I invite comments, criticisms, etc.  One obvious
>> drawback is that this only addresses the "decompression" side.  While
>> I briefly considered a "Store Bit Field", I discarded it as it seemed
>> too complex, and presumably would used less frequently, as
>> compression/coding happens less frequently than decompression/decoding.
>
> Encoding is almost always far easier than decoding, since there are zero
> surprises when encoding. Yes, for codecs/compression it can be a _lot_
> of work to figure out a near-optimal encoding, but the actual conversion
> of the selected option into a bit stream is easy.

Good point, that I hadn't thought of. More reason why the hypothetical
"Store Bit Field" isn't needed.

> I.e. just like writing JSON or XML is trivial, while decoding is
> somewhere between "some work" and "very hard".

:-)

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Monday, January 24, 2022 at 4:08:52 PM UTC-6, Stephen Fuld wrote:
> On 1/22/2022 3:42 AM, Terje Mathisen wrote:
> > Stephen Fuld wrote:
>
> >> Anyway, if one had this instruction, the main loop in the code above
> >> could be something like
> >>
> >>
> >> loop:
> >> LDUB R10,[R1+R9]
> >> CARRY R6,IO
> >> LBF R12,R10,R2 ;I am not sure about R2, It should be
> >> the start of the packed buffer.
> >> STD R12,[R3+R9<<3]
> >> ADD R9,R9,#1
> >> CMP R11,R9,R4
> >> BLT R11,loop
> >
> > That is really quite nice.
>
> Thank you!
>
>
> >>
> >> For a savings of about 10 instructions in the I cache, but fewer in
> >> execution (but still significant) depending upon how often the
> >> instructions under the predicate are executed.
> >>
> >>
> >> Anyway, Of course, I invite comments, criticisms, etc. One obvious
> >> drawback is that this only addresses the "decompression" side. While
> >> I briefly considered a "Store Bit Field", I discarded it as it seemed
> >> too complex, and presumably would used less frequently, as
> >> compression/coding happens less frequently than decompression/decoding.
> >
> > Encoding is almost always far easier than decoding,
<
Encoding of bit-strings is easier than decoding of bit strings.
<
Encoding of instructions sets is a lot harder than decoding of instructions sets
because the encoding directly influences how hard it is (how many gates) it
takes; and if you don't take decoding (now and in future implementations) into
consideration you have already shot yourself in the foot. Witness x86. Q.E.D
<
> since there are zero
> > surprises when encoding. Yes, for codecs/compression it can be a _lot_
> > of work to figure out a near-optimal encoding, but the actual conversion
> > of the selected option into a bit stream is easy.
>
> Good point, that I hadn't thought of. More reason why the hypothetical
> "Store Bit Field" isn't needed.
>
> > I.e. just like writing JSON or XML is trivial, while decoding is
> > somewhere between "some work" and "very hard".
>
> :-)
>
>
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

Stephen Fuld wrote:
> On 1/22/2022 3:42 AM, Terje Mathisen wrote:
>> Stephen Fuld wrote:
>
>>> Anyway, if one had this instruction, the main loop in the code above
>>> could be something like
>>>
>>>
>>> loop:
>>> LDUB R10,[R1+R9]
>>> CARRY R6,IO
>>> LBF R12,R10,R2 ;I am not sure about R2, It should be
>>> the start of the packed buffer.
>>> STD R12,[R3+R9<<3]
>>> ADD R9,R9,#1
>>> CMP R11,R9,R4
>>> BLT R11,loop
>>
>> That is really quite nice.
>
> Thank you!
>
>
>>>
>>> For a savings of about 10 instructions in the I cache, but fewer in
>>> execution (but still significant) depending upon how often the
>>> instructions under the predicate are executed.
>>>
>>>
>>> Anyway, Of course, I invite comments, criticisms, etc. One obvious
>>> drawback is that this only addresses the "decompression" side. While
>>> I briefly considered a "Store Bit Field", I discarded it as it seemed
>>> too complex, and presumably would used less frequently, as
>>> compression/coding happens less frequently than decompression/decoding.
>>
>> Encoding is almost always far easier than decoding, since there are
>> zero surprises when encoding. Yes, for codecs/compression it can be a
>> _lot_ of work to figure out a near-optimal encoding, but the actual
>> conversion of the selected option into a bit stream is easy.
>
> Good point, that I hadn't thought of. More reason why the hypothetical
> "Store Bit Field" isn't needed.

High bandwith compression happens more these days with video conferencing.
Maybe its a chicken & egg thing - we do more because we can do more.

Unless Bit Field Insert requires significantly more hardware than
BF Extract I don't see why one would leave it out.

BFEXT requires a data and BF specifier source regs + 1 dest reg,
so fits in the standard RISC 2R 1W port model.

BFINS requires a struct source, data source, BF specifier regs, + dest reg,
so 3R 1W ports. Also instruction would require 4 register specifiers
unless you allow the struct source and dest reg to be the same specifier.
That bothers some, but if you have FMA then you probably have already
crossed that Rubicon. I would rather have the functionality than stick
to a somewhat arbitrary design philosophy.

There are a bunch of bit field manipulation instructions beyond those
useful for multimedia codec encode/decode, signal processing, crypto.
butterfly, reverse butterfly, permute, mix.

Then there is the whole area of double-wide shifts and bit fields
to facilitate bit stream processing.

> Unless Bit Field Insert requires significantly more hardware than
> BF Extract I don't see why one would leave it out.

I think we know better nowadays than to use this kind of reasoning when
decided what to put in an ISA ;-)

Stefan

On 1/25/2022 7:48 AM, EricP wrote:
> Stephen Fuld wrote:
>> On 1/22/2022 3:42 AM, Terje Mathisen wrote:
>>> Stephen Fuld wrote:
>>
>>>> Anyway, if one had this instruction, the main loop in the code above
>>>> could be something like
>>>>
>>>>
>>>> loop:
>>>>      LDUB        R10,[R1+R9]
>>>>      CARRY         R6,IO
>>>>      LBF        R12,R10,R2     ;I am not sure about R2,  It should
>>>> be the start of the packed buffer.
>>>>      STD        R12,[R3+R9<<3]
>>>>      ADD        R9,R9,#1
>>>>       CMP        R11,R9,R4
>>>>       BLT        R11,loop
>>>
>>> That is really quite nice.
>>
>> Thank you!
>>
>>
>>>>
>>>> For a savings of about 10 instructions in the I cache, but fewer in
>>>> execution (but still significant) depending upon how often the
>>>> instructions under the predicate are executed.
>>>>
>>>>
>>>> Anyway, Of course, I invite comments, criticisms, etc.  One obvious
>>>> drawback is that this only addresses the "decompression" side.
>>>> While I briefly considered a "Store Bit Field", I discarded it as it
>>>> seemed too complex, and presumably would used less frequently, as
>>>> compression/coding happens less frequently than decompression/decoding.
>>>
>>> Encoding is almost always far easier than decoding, since there are
>>> zero surprises when encoding. Yes, for codecs/compression it can be a
>>> _lot_ of work to figure out a near-optimal encoding, but the actual
>>> conversion of the selected option into a bit stream is easy.
>>
>> Good point, that I hadn't thought of.  More reason why the
>> hypothetical "Store Bit Field" isn't needed.
>
> High bandwith compression happens more these days with video conferencing.
> Maybe its a chicken & egg thing - we do more because we can do more.

Interesting. I think a valid counter argument. But see below.

>
> Unless Bit Field Insert requires significantly more hardware than
> BF Extract I don't see why one would leave it out.

The MY 66000 ISA already includes "simple" bit field insert and extract.
The main advantage of my proposed instruction is to eliminate all the
instructions needed for bookkeeping and testing for and handling when
the extracted field crosses double word boundaries.

> There are a bunch of bit field manipulation instructions beyond those
> useful for multimedia codec encode/decode, signal processing, crypto.
> butterfly, reverse butterfly, permute, mix.

Can you tell us what they are?

> Then there is the whole area of double-wide shifts and bit fields
> to facilitate bit stream processing.

Again, already included in the MY 66000 ISA via the use of the CARRY
meta instruction.

As shown in Mitch's example code, the problem posed could already be
solved with the existing ISA. My proposed additional instruction simply
made the solution more efficient.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Tuesday, January 25, 2022 at 9:48:39 AM UTC-6, EricP wrote:
> Stephen Fuld wrote:

> > Good point, that I hadn't thought of. More reason why the hypothetical
> > "Store Bit Field" isn't needed.
<
> High bandwith compression happens more these days with video conferencing.
> Maybe its a chicken & egg thing - we do more because we can do more.
>
> Unless Bit Field Insert requires significantly more hardware than
> BF Extract I don't see why one would leave it out.
>
> BFEXT requires a data and BF specifier source regs + 1 dest reg,
> so fits in the standard RISC 2R 1W port model.
>
> BFINS requires a struct source, data source, BF specifier regs, + dest reg,
> so 3R 1W ports. Also instruction would require 4 register specifiers
> unless you allow the struct source and dest reg to be the same specifier.
<
Register INS does require what you state
<
Memory INS does not as the memory container is updated in situ.
Thus, memory based EXT and INS are more like LDs and STs than
register EXT and INS.
<
> That bothers some, but if you have FMA then you probably have already
> crossed that Rubicon. I would rather have the functionality than stick
> to a somewhat arbitrary design philosophy.
>
> There are a bunch of bit field manipulation instructions beyond those
> useful for multimedia codec encode/decode, signal processing, crypto.
> butterfly, reverse butterfly, permute, mix.
>
> Then there is the whole area of double-wide shifts and bit fields
> to facilitate bit stream processing.

On Tuesday, January 25, 2022 at 11:30:50 AM UTC-6, Stephen Fuld wrote:
> On 1/25/2022 7:48 AM, EricP wrote:
> > Stephen Fuld wrote:
> >> On 1/22/2022 3:42 AM, Terje Mathisen wrote:
> >>> Stephen Fuld wrote:
> >>
> >>>> Anyway, if one had this instruction, the main loop in the code above
> >>>> could be something like
> >>>>
> >>>>
> >>>> loop:
> >>>> LDUB R10,[R1+R9]
> >>>> CARRY R6,IO
> >>>> LBF R12,R10,R2 ;I am not sure about R2, It should
> >>>> be the start of the packed buffer.
> >>>> STD R12,[R3+R9<<3]
> >>>> ADD R9,R9,#1
> >>>> CMP R11,R9,R4
> >>>> BLT R11,loop
> >>>
> >>> That is really quite nice.
> >>
> >> Thank you!
> >>
> >>
> >>>>
> >>>> For a savings of about 10 instructions in the I cache, but fewer in
> >>>> execution (but still significant) depending upon how often the
> >>>> instructions under the predicate are executed.
> >>>>
> >>>>
> >>>> Anyway, Of course, I invite comments, criticisms, etc. One obvious
> >>>> drawback is that this only addresses the "decompression" side.
> >>>> While I briefly considered a "Store Bit Field", I discarded it as it
> >>>> seemed too complex, and presumably would used less frequently, as
> >>>> compression/coding happens less frequently than decompression/decoding.
> >>>
> >>> Encoding is almost always far easier than decoding, since there are
> >>> zero surprises when encoding. Yes, for codecs/compression it can be a
> >>> _lot_ of work to figure out a near-optimal encoding, but the actual
> >>> conversion of the selected option into a bit stream is easy.
> >>
> >> Good point, that I hadn't thought of. More reason why the
> >> hypothetical "Store Bit Field" isn't needed.
> >
> > High bandwith compression happens more these days with video conferencing.
> > Maybe its a chicken & egg thing - we do more because we can do more.
> Interesting. I think a valid counter argument. But see below.
> >
> > Unless Bit Field Insert requires significantly more hardware than
> > BF Extract I don't see why one would leave it out.
> The MY 66000 ISA already includes "simple" bit field insert and extract.
> The main advantage of my proposed instruction is to eliminate all the
> instructions needed for bookkeeping and testing for and handling when
> the extracted field crosses double word boundaries.
> > There are a bunch of bit field manipulation instructions beyond those
> > useful for multimedia codec encode/decode, signal processing, crypto.
> > butterfly, reverse butterfly, permute, mix.
> Can you tell us what they are?
> > Then there is the whole area of double-wide shifts and bit fields
> > to facilitate bit stream processing.
<
> Again, already included in the MY 66000 ISA via the use of the CARRY
> meta instruction.
<
Instruction-modifier
>
> As shown in Mitch's example code, the problem posed could already be
> solved with the existing ISA. My proposed additional instruction simply
> made the solution more efficient.
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

Stephen Fuld wrote:
> On 1/25/2022 7:48 AM, EricP wrote:
>
>> There are a bunch of bit field manipulation instructions beyond those
>> useful for multimedia codec encode/decode, signal processing, crypto.
>> butterfly, reverse butterfly, permute, mix.
>
> Can you tell us what they are?

I don't personally need such instructions as I rarely operate on
bit fields and when I do it is not performance critical,
but I note that others feel they do need them. One example paper:

A New Basis for Shifters in General-Purpose Processors for
Existing and Advanced Bit Manipulations, 2008
https://www.researchgate.net/publication/220332176_A_New_Basis_for_Shifters_in_General-Purpose_Processors_for_Existing_and_Advanced_Bit_Manipulations

describes the following bit field operations:
- rotate right & left
- shift right & left with zero or sign fill
- bit field extract & insert
- mix select right or left subwords
- butterfly and inverse butterfly
- parallel extract and insert (scatter, gather)
- popcount
- bit dot product
- bit matrix multiply

I would add:
- find first/last bit set/clear

potential usage in:

- dna sequencing and sequence compression, alignment
- crypto
- error correction
- bit stream signal processing, multiplexing

On Tuesday, January 25, 2022 at 1:07:11 PM UTC-6, EricP wrote:
> Stephen Fuld wrote:
> > On 1/25/2022 7:48 AM, EricP wrote:
> >
> >> There are a bunch of bit field manipulation instructions beyond those
> >> useful for multimedia codec encode/decode, signal processing, crypto.
> >> butterfly, reverse butterfly, permute, mix.
> >
> > Can you tell us what they are?
> I don't personally need such instructions as I rarely operate on
> bit fields and when I do it is not performance critical,
> but I note that others feel they do need them. One example paper:
>
> A New Basis for Shifters in General-Purpose Processors for
> Existing and Advanced Bit Manipulations, 2008
> https://www.researchgate.net/publication/220332176_A_New_Basis_for_Shifters_in_General-Purpose_Processors_for_Existing_and_Advanced_Bit_Manipulations
>
<
My 66000 ISA encodings:
<
> describes the following bit field operations:
> - rotate right & left
CARRY Rs,{I}
SL/SR Rd,Rs,off
> - shift right & left with zero or sign fill
SL/SR Rd,Rs,off
> - bit field extract & insert
SL Rd,Rs,<len,off>
INS Rd,Rb,<len,off>
> - mix select right or left subwords
MUX Rd,Rs1,Rs2,mask // but level multiplex between s1 and s2 based on S3
> - butterfly and inverse butterfly
BITR Rd,Rs,<len,off>
> - parallel extract and insert (scatter, gather)
> - popcount
POP Rd,Rs
> - bit dot product
???
> - bit matrix multiply
BMM Rd,Rb,[Rbm]
>
> I would add:
> - find first/last bit set/clear
FF1 Rd,Rs // can be from the left or from the right.
FF1 Rd,~Rs
SET = INS Rd,#~0,<len,off>
CLR = IINS Rd,#0,<len,off>
>
<
Looks like I got most of them.
<
> potential usage in:
>
> - dna sequencing and sequence compression, alignment
> - crypto
> - error correction
> - bit stream signal processing, multiplexing

On Tuesday, January 25, 2022 at 1:23:35 PM UTC-6, MitchAlsup wrote:
> On Tuesday, January 25, 2022 at 1:07:11 PM UTC-6, EricP wrote:
> > Stephen Fuld wrote:
> > > On 1/25/2022 7:48 AM, EricP wrote:
> > >
> > >> There are a bunch of bit field manipulation instructions beyond those
> > >> useful for multimedia codec encode/decode, signal processing, crypto.
> > >> butterfly, reverse butterfly, permute, mix.
> > >
> > > Can you tell us what they are?
> > I don't personally need such instructions as I rarely operate on
> > bit fields and when I do it is not performance critical,
> > but I note that others feel they do need them. One example paper:
> >
> > A New Basis for Shifters in General-Purpose Processors for
> > Existing and Advanced Bit Manipulations, 2008
> > https://www.researchgate.net/publication/220332176_A_New_Basis_for_Shifters_in_General-Purpose_Processors_for_Existing_and_Advanced_Bit_Manipulations
> >
> <
> My 66000 ISA encodings:
> <
> > describes the following bit field operations:
> > - rotate right & left
> CARRY Rs,{I}
> SL/SR Rd,Rs,off
> > - shift right & left with zero or sign fill
> SL/SR Rd,Rs,off
> > - bit field extract & insert
> SL Rd,Rs,<len,off>
> INS Rd,Rb,<len,off>
> > - mix select right or left subwords
> MUX Rd,Rs1,Rs2,mask // but level multiplex between s1 and s2 based on S3
> > - butterfly and inverse butterfly
> BITR Rd,Rs,<len,off>
> > - parallel extract and insert (scatter, gather)
> > - popcount
> POP Rd,Rs
> > - bit dot product
> ???
> > - bit matrix multiply
> BMM Rd,Rb,[Rbm]
> >
> > I would add:
> > - find first/last bit set/clear
> FF1 Rd,Rs // can be from the left or from the right.
> FF1 Rd,~Rs
> SET = INS Rd,#~0,<len,off>
> CLR = IINS Rd,#0,<len,off>
> >
> <
> Looks like I got most of them.
<
I should also point out that many of these were available in Mc 88100
circa 1985............
<
> <
> > potential usage in:
> >
> > - dna sequencing and sequence compression, alignment
> > - crypto
> > - error correction
> > - bit stream signal processing, multiplexing

On 1/25/2022 7:48 AM, EricP wrote:
> Stephen Fuld wrote:
>> On 1/22/2022 3:42 AM, Terje Mathisen wrote:
>>> Stephen Fuld wrote:
>>
>>>> Anyway, if one had this instruction, the main loop in the code above
>>>> could be something like
>>>>
>>>>
>>>> loop:
>>>>      LDUB        R10,[R1+R9]
>>>>      CARRY         R6,IO
>>>>      LBF        R12,R10,R2     ;I am not sure about R2,  It should
>>>> be the start of the packed buffer.
>>>>      STD        R12,[R3+R9<<3]
>>>>      ADD        R9,R9,#1
>>>>       CMP        R11,R9,R4
>>>>       BLT        R11,loop
>>>
>>> That is really quite nice.
>>
>> Thank you!
>>
>>
>>>>
>>>> For a savings of about 10 instructions in the I cache, but fewer in
>>>> execution (but still significant) depending upon how often the
>>>> instructions under the predicate are executed.
>>>>
>>>>
>>>> Anyway, Of course, I invite comments, criticisms, etc.  One obvious
>>>> drawback is that this only addresses the "decompression" side.
>>>> While I briefly considered a "Store Bit Field", I discarded it as it
>>>> seemed too complex, and presumably would used less frequently, as
>>>> compression/coding happens less frequently than decompression/decoding.
>>>
>>> Encoding is almost always far easier than decoding, since there are
>>> zero surprises when encoding. Yes, for codecs/compression it can be a
>>> _lot_ of work to figure out a near-optimal encoding, but the actual
>>> conversion of the selected option into a bit stream is easy.
>>
>> Good point, that I hadn't thought of.  More reason why the
>> hypothetical "Store Bit Field" isn't needed.
>
> High bandwith compression happens more these days with video conferencing.
> Maybe its a chicken & egg thing - we do more because we can do more.
>
> Unless Bit Field Insert requires significantly more hardware than
> BF Extract I don't see why one would leave it out.
>
> BFEXT requires a data and BF specifier source regs + 1 dest reg,
> so fits in the standard RISC 2R 1W port model.
>
> BFINS requires a struct source, data source, BF specifier regs, + dest reg,
> so 3R 1W ports. Also instruction would require 4 register specifiers
> unless you allow the struct source and dest reg to be the same specifier.
> That bothers some, but if you have FMA then you probably have already
> crossed that Rubicon. I would rather have the functionality than stick
> to a somewhat arbitrary design philosophy.
>
> There are a bunch of bit field manipulation instructions beyond those
> useful for multimedia codec encode/decode, signal processing, crypto.
> butterfly, reverse butterfly, permute, mix.
>
> Then there is the whole area of double-wide shifts and bit fields
> to facilitate bit stream processing.
>
>

You don't offer dynamic BFINS/EXT? Dynamc needs two more registers,
unless you separately buid a descriptor like Mitch.