The paper describing it is:

https://downfall.page/media/downfall.pdf

@inproceedings{moghimi2023downfall,
title={{Downfall}: Exploiting Speculative Data Gathering},
author={Moghimi, Daniel},
booktitle={32th USENIX Security Symposium (USENIX Security 2023)},
year={2023}
}

There is a lot of stuff in there, and I have not read it thoroughly,
but "Gather Data Sampling" (GDS) appears to be a Meltdown-class attack
that speculatively extracts data from SIMD-load buffers by using
speculatively-executed gather instructions (present since AVX2), and
then uses a side channel to get the data from the speculative to the
architectural state. Then the author explores various ways to further
exploit this vulnerability, and it proves pretty versatile (read for
yourself), including breaking SGX (secure enclaves in Intel).

The author tested Tiger Lake, Ice Lake Server, Cascade Lake (a Server
Skylake variant), and Kaby Lake (a client Skylake variant), and they
all are vulnerable. He does not describe that some CPUs are safe, so
every CPU with AVX2 (which includes the gather instructions) might be
affected.

Disabling HT (SMT) reduces the leakage speed by a lot, but data can
still be leaked across context switches; the instructions that flush
other microarchitecural state on context switches do not flush these
SIMD load buffers.

In the eternal discussion about RISC vs. non-RISC, the RISC advocates
can point to another case where the complexity of accessing multiple
memory locations (and the desire to optimize that, and deal with,
e.g., TLB misses without restarting everything from scratch) has led
to complexity, that resulted in a hardware bug.

The strange thing is that gather is ultra-slow on Skylake, so whatever
they optimized does not work very well (maybe it's better on Tiger
Lake).

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

On 8/9/2023 8:13 AM, Anton Ertl wrote:
> The paper describing it is:
>
> https://downfall.page/media/downfall.pdf
>
> @inproceedings{moghimi2023downfall,
> title={{Downfall}: Exploiting Speculative Data Gathering},
> author={Moghimi, Daniel},
> booktitle={32th USENIX Security Symposium (USENIX Security 2023)},
> year={2023}
> }
>
> There is a lot of stuff in there, and I have not read it thoroughly,
> but "Gather Data Sampling" (GDS) appears to be a Meltdown-class attack
> that speculatively extracts data from SIMD-load buffers by using
> speculatively-executed gather instructions (present since AVX2), and
> then uses a side channel to get the data from the speculative to the
> architectural state. Then the author explores various ways to further
> exploit this vulnerability, and it proves pretty versatile (read for
> yourself), including breaking SGX (secure enclaves in Intel).
>
> The author tested Tiger Lake, Ice Lake Server, Cascade Lake (a Server
> Skylake variant), and Kaby Lake (a client Skylake variant), and they
> all are vulnerable. He does not describe that some CPUs are safe, so
> every CPU with AVX2 (which includes the gather instructions) might be
> affected.

According to Wired,

https://www.wired.com/story/downfall-flaw-intel-chips/

> Intel's current generation chips—including those in the Alder Lake, Raptor Lake, and Sapphire Rapids families—are not affected, because attempts to exploit the vulnerability would be blocked by defenses Intel has added recently.

So did they know about this vulnerability for a long time, or did they
fix it inadvertently?

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

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:
>According to Wired,
>
>https://www.wired.com/story/downfall-flaw-intel-chips/
>
>> Intel's current generation chips—including those in the Alder Lake, Raptor Lake, and Sapphire Rapids families—are not affected, because attempts to exploit the vulnerability would be blocked by defenses Intel has added recently.
>
>So did they know about this vulnerability for a long time, or did they
>fix it inadvertently?

Good question. Intel also tells us that Haswell and Broadwell are not
vulnerable. Maybe they added the defenses in Haswell, removed it in
Skylake, and readded it in Golden Cove and Gracemont. And according
to the author, preliminary results indicate that Zen2 is not
vulnerable, so maybe AMD also knew about this vulnerability and added
a defense against it.

I think a more useful POV is that Intel reimplemented Gather in
Skylake with a bug, and reimplemented it in Golden Cove without the
bug; whether they noticed the bug in the previous implementation when
they reimplemented it in Golden Cove is the question.

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

On Thursday, August 10, 2023 at 11:20:30 AM UTC-5, Anton Ertl wrote:
> Stephen Fuld <sf...@alumni.cmu.edu.invalid> writes:
> >According to Wired,
> >
> >https://www.wired.com/story/downfall-flaw-intel-chips/
> >
> >> Intel's current generation chips—including those in the Alder Lake, Raptor Lake, and Sapphire Rapids families—are not affected, because attempts to exploit the vulnerability would be blocked by defenses Intel has added recently.
> >
> >So did they know about this vulnerability for a long time, or did they
> >fix it inadvertently?
<
> Good question. Intel also tells us that Haswell and Broadwell are not
> vulnerable. Maybe they added the defenses in Haswell, removed it in
> Skylake, and readded it in Golden Cove and Gracemont. And according
> to the author, preliminary results indicate that Zen2 is not
> vulnerable, so maybe AMD also knew about this vulnerability and added
> a defense against it.
<
Either they knew
OR
AMD has to have better verification in order to maintain complete bug-for-bug
compatibility.
>
> I think a more useful POV is that Intel reimplemented Gather in
> Skylake with a bug, and reimplemented it in Golden Cove without the
> bug; whether they noticed the bug in the previous implementation when
> they reimplemented it in Golden Cove is the question.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Wednesday, August 9, 2023 at 10:44:33 AM UTC-5, Anton Ertl wrote:
> The paper describing it is:
>
> https://downfall.page/media/downfall.pdf
>
> @inproceedings{moghimi2023downfall,
> title={{Downfall}: Exploiting Speculative Data Gathering},
> author={Moghimi, Daniel},
> booktitle={32th USENIX Security Symposium (USENIX Security 2023)},
> year={2023}
> }
>
> There is a lot of stuff in there, and I have not read it thoroughly,
> but "Gather Data Sampling" (GDS) appears to be a Meltdown-class attack
> that speculatively extracts data from SIMD-load buffers by using
> speculatively-executed gather instructions (present since AVX2), and
> then uses a side channel to get the data from the speculative to the
> architectural state. Then the author explores various ways to further
> exploit this vulnerability, and it proves pretty versatile (read for
> yourself), including breaking SGX (secure enclaves in Intel).
>
> The author tested Tiger Lake, Ice Lake Server, Cascade Lake (a Server
> Skylake variant), and Kaby Lake (a client Skylake variant), and they
> all are vulnerable. He does not describe that some CPUs are safe, so
> every CPU with AVX2 (which includes the gather instructions) might be
> affected.
>
> Disabling HT (SMT) reduces the leakage speed by a lot, but data can
> still be leaked across context switches; the instructions that flush
> other microarchitecural state on context switches do not flush these
> SIMD load buffers.
>
> In the eternal discussion about RISC vs. non-RISC, the RISC advocates
> can point to another case where the complexity of accessing multiple
> memory locations (and the desire to optimize that, and deal with,
> e.g., TLB misses without restarting everything from scratch) has led
> to complexity, that resulted in a hardware bug.
<
The gather bug is an example of not-obeying the rule:
"If you change 1 bit in an architectural register, you change them all"
<
RISC-people in 1980 already knew the x86 byte stuff was problematic
{along with a host of other mis-features}
<
But I guess, every µArchitecture generation gets to figure it out for
themselves.
>
> The strange thing is that gather is ultra-slow on Skylake, so whatever
> they optimized does not work very well (maybe it's better on Tiger
> Lake).
>
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

MitchAlsup <MitchAlsup@aol.com> writes:
>Either they knew
>OR
>AMD has to have better verification in order to maintain complete bug-for-b=
>ug
>compatibility.

Zenbleed (an architectural bug) shows that AMD's verification has holes.

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

MitchAlsup <MitchAlsup@aol.com> writes:
>The gather bug is an example of not-obeying the rule:
>"If you change 1 bit in an architectural register, you change them all"
><
>RISC-people in 1980 already knew the x86 byte stuff was problematic
>{along with a host of other mis-features}

Where can I read about this knowledge of the RISC people? Did they
even waste one thought to the 8086, which was an insignificant
microprocessor in 1980?

As for the gather bug, the gather instructions were added with AVX2,
first implemented in Haswell (released 2013), and with AVX-512 F
(Knights Landing, 2013). Intel had problems with partial register
updates since they introduced OoO with the Pentium Pro (released
1995), so they were aware of the problems of implementing such
instructions. And yet they chose to do so, in addition to choosing to
add an instruction that may perform 16 memory accesses.

Interestingly, the definition of, e.g., VGATHERPS says:

|* Faults are delivered in a right-to-left manner. That is, if a fault
| is triggered by an element and delivered, all elements closer to the
| LSB of the destination will be completed (and
| non-faulting). Individual elements closer to the MSB may or may not
| be completed. If a given element triggers multiple faults, they are
| delivered in the conventional order.
| |* Elements may be gathered in any order, but faults must be delivered
| in a right-to-left order; thus, elements to the left of a faulting
| one may be gathered before the fault is delivered. A given
| implementation of this instruction is repeatable - given the same
| input values and architectural state, the same set of elements to
| the left of the faulting one will be gathered.

It's not clear to me what this "completed" and "gathered" is about.
Is it about changing the destination register in case of a fault? Is
it about order of memory accesses for concurrent processing?

There is a good reason why multi-access instructions are shunned by
most architects.

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

On Friday, August 11, 2023 at 9:13:29 AM UTC+3, Anton Ertl wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >Either they knew
> >OR
> >AMD has to have better verification in order to maintain complete bug-for-b=
> >ug
> >compatibility.
>
> Zenbleed (an architectural bug) shows that AMD's verification has holes.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

Also, zenbleed is sort of bug that can be relatively easily discovered with
automatic black-box testing.
Downfall, on the other hand, looks impossible to find unless you know
what you are looking for.

On Friday, August 11, 2023 at 9:39:09 AM UTC+3, Anton Ertl wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >The gather bug is an example of not-obeying the rule:
> >"If you change 1 bit in an architectural register, you change them all"
> ><
> >RISC-people in 1980 already knew the x86 byte stuff was problematic
> >{along with a host of other mis-features}
> Where can I read about this knowledge of the RISC people? Did they
> even waste one thought to the 8086, which was an insignificant
> microprocessor in 1980?
>

MIPS solution for unaligned loads relies on partial register update.
IIRCC, they tought it's so cool that they even patented the idea.
So, obviously, MIPS was not designed by RISC-people in 1980s.
Or was it?

> As for the gather bug, the gather instructions were added with AVX2,
> first implemented in Haswell (released 2013), and with AVX-512 F
> (Knights Landing, 2013). Intel had problems with partial register
> updates since they introduced OoO with the Pentium Pro (released
> 1995), so they were aware of the problems of implementing such
> instructions. And yet they chose to do so, in addition to choosing to
> add an instruction that may perform 16 memory accesses.
>
> Interestingly, the definition of, e.g., VGATHERPS says:
>
> |* Faults are delivered in a right-to-left manner. That is, if a fault
> | is triggered by an element and delivered, all elements closer to the
> | LSB of the destination will be completed (and
> | non-faulting). Individual elements closer to the MSB may or may not
> | be completed. If a given element triggers multiple faults, they are
> | delivered in the conventional order.
> |
> |* Elements may be gathered in any order, but faults must be delivered
> | in a right-to-left order; thus, elements to the left of a faulting
> | one may be gathered before the fault is delivered. A given
> | implementation of this instruction is repeatable - given the same
> | input values and architectural state, the same set of elements to
> | the left of the faulting one will be gathered.
>
> It's not clear to me what this "completed" and "gathered" is about.
> Is it about changing the destination register in case of a fault? Is
> it about order of memory accesses for concurrent processing?
>
> There is a good reason why multi-access instructions are shunned by
> most architects.

Is there wider than 128-bit SIMD ISA that does *not* have that or
another variant of gather?

Personally I am of low opinion about gather. IMHO, if one's algorithm
needs gather for vectorization then it's a sign that vectorization gain
will be low and that you better not bother.
But it seems to me that most architect are enamored but this sort of crap.

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

Michael S <already5chosen@yahoo.com> writes:
>On Friday, August 11, 2023 at 9:39:09=E2=80=AFAM UTC+3, Anton Ertl wrote:

>> There is a good reason why multi-access instructions are shunned by=20
>> most architects.
>
>Is there wider than 128-bit SIMD ISA that does *not* have that or
>another variant of gather?
>
>Personally I am of low opinion about gather. IMHO, if one's algorithm
>needs gather for vectorization then it's a sign that vectorization gain
>will be low and that you better not bother.
>But it seems to me that most architect are enamored but this sort of crap.

It has been my experience that architects are interested in generally improving
performance. They don't just willy-nilly add features for the sake
of adding features, but rather spend a great deal of time analyzing workloads
and modeling performance improvements before they are adopted into a
instruction set architecture.

On Friday, August 11, 2023 at 4:25:21 PM UTC+3, Scott Lurndal wrote:
> Michael S <already...@yahoo.com> writes:
> >On Friday, August 11, 2023 at 9:39:09=E2=80=AFAM UTC+3, Anton Ertl wrote:
>
> >> There is a good reason why multi-access instructions are shunned by=20
> >> most architects.
> >
> >Is there wider than 128-bit SIMD ISA that does *not* have that or
> >another variant of gather?
> >
> >Personally I am of low opinion about gather. IMHO, if one's algorithm
> >needs gather for vectorization then it's a sign that vectorization gain
> >will be low and that you better not bother.
> >But it seems to me that most architect are enamored but this sort of crap.
> It has been my experience that architects are interested in generally improving
> performance. They don't just willy-nilly add features for the sake
> of adding features, but rather spend a great deal of time analyzing workloads
> and modeling performance improvements before they are adopted into a
> instruction set architecture.

Gather is in SVE not because of some deep analysis of its advantages and
disadvantages on today's huge cores with relatively narrow 128-bit or 256-bit
SIMD. It's there because it made sense for Fujitsu A64Fx - relatively spartan
4-wide core with smallish OoO structures? long load pipliine and wide 512-bit
SIMD. Another big reason - it was present in Fujitsu's previous SPRAC64 VIIIFx.

Gather is in AVX-512 for similar reasons - legacy of LRBNI and of KNC/KNL.

Why they have gather in AVX2? I don't know. IMHO, by mistake.

Scott Lurndal wrote:
> Michael S <already5chosen@yahoo.com> writes:
>> On Friday, August 11, 2023 at 9:39:09=E2=80=AFAM UTC+3, Anton Ertl wrote:
>
>>> There is a good reason why multi-access instructions are shunned by=20
>>> most architects.
>>
>> Is there wider than 128-bit SIMD ISA that does *not* have that or
>> another variant of gather?
>>
>> Personally I am of low opinion about gather. IMHO, if one's algorithm
>> needs gather for vectorization then it's a sign that vectorization gain
>> will be low and that you better not bother.
>> But it seems to me that most architect are enamored but this sort of crap.
>
> It has been my experience that architects are interested in generally improving
> performance. They don't just willy-nilly add features for the sake
> of adding features, but rather spend a great deal of time analyzing workloads
> and modeling performance improvements before they are adopted into a
> instruction set architecture.

gather is one of (if not) the most obvious missing link(s) if you want
to allow a compiler to vectorize arbitrary scalar looping code,
particularly when any form of sparse matrix storage is involved.

Terje

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

Michael S <already5chosen@yahoo.com> writes:
>Is there wider than 128-bit SIMD ISA that does *not* have that or
>another variant of gather?

AVX. However, Intel added gather instructions with AVX2 two years
later.

>Personally I am of low opinion about gather. IMHO, if one's algorithm
>needs gather for vectorization then it's a sign that vectorization gain
>will be low and that you better not bother.
>But it seems to me that most architect are enamored but this sort of crap.

Yes, it's better to arrange your data or your computations so you
don't need gather.

However, if the programmer does not do that (either because he does
not think about vectorization, or just does not find such an
arrangement), gather and scatter instructions may be useful for
avoiding to have to switch from SIMD to scalar code and back.

AFAIK the Cray-1 had gather and scatter instructions. I wonder how
much the speed difference between stride-1 loads and stores and gather
and scatter was on the Cray-1.

Maybe gather and scatter were added in the Cray-1 (for which people
thought about how to vectorize) because they could be implemented
efficiently, and nowadays SIMD designers add them, because the Cray-1
had them, and code designed with that background has them, even though
nowadays the performance advantages of stride-1 accesses are much
bigger.

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

Michael S <already5chosen@yahoo.com> writes:
>Downfall, on the other hand, looks impossible to find unless you know
>what you are looking for.

So how do you think did Daniel Moghimi know what to look for?

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

Anton Ertl wrote:
> Michael S <already5chosen@yahoo.com> writes:
>> Is there wider than 128-bit SIMD ISA that does *not* have that or
>> another variant of gather?
>
> AVX. However, Intel added gather instructions with AVX2 two years
> later.
>
>> Personally I am of low opinion about gather. IMHO, if one's algorithm
>> needs gather for vectorization then it's a sign that vectorization gain
>> will be low and that you better not bother.
>> But it seems to me that most architect are enamored but this sort of crap.
>
> Yes, it's better to arrange your data or your computations so you
> don't need gather.
>
> However, if the programmer does not do that (either because he does
> not think about vectorization, or just does not find such an
> arrangement), gather and scatter instructions may be useful for
> avoiding to have to switch from SIMD to scalar code and back.

I think this is exactly right.
>
> AFAIK the Cray-1 had gather and scatter instructions. I wonder how
> much the speed difference between stride-1 loads and stores and gather
> and scatter was on the Cray-1.
>
> Maybe gather and scatter were added in the Cray-1 (for which people
> thought about how to vectorize) because they could be implemented
> efficiently, and nowadays SIMD designers add them, because the Cray-1
> had them, and code designed with that background has them, even though
> nowadays the performance advantages of stride-1 accesses are much
> bigger.

I view gather as a form of caching, in that it can be much more
efficient when the source data is mostly sequential, or at least
spatially nearby:

On the original Larrabee the intention/target was for gather to use one
cycle per source cache line, i.e. it would process source addresses from
the left, then while looking at the corresponding cache line, it would
also pick up any subsequent words that happened to lie in the same cache
line.

This meant that for purely sequential data you got maximal speed, while
a gather from 16 random addresses would take the same 16 cycles as a
scalar implementation.

(This all assumes sourc data in $L1 cache of course, adding wait cycles
for more remote source data.)

Terje

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

On 8/11/2023 11:38 PM, Anton Ertl wrote:
> Michael S <already5chosen@yahoo.com> writes:
>> Is there wider than 128-bit SIMD ISA that does *not* have that or
>> another variant of gather?
>
> AVX. However, Intel added gather instructions with AVX2 two years
> later.
>
>> Personally I am of low opinion about gather. IMHO, if one's algorithm
>> needs gather for vectorization then it's a sign that vectorization gain
>> will be low and that you better not bother.
>> But it seems to me that most architect are enamored but this sort of crap.
>
> Yes, it's better to arrange your data or your computations so you
> don't need gather.
>
> However, if the programmer does not do that (either because he does
> not think about vectorization, or just does not find such an
> arrangement), gather and scatter instructions may be useful for
> avoiding to have to switch from SIMD to scalar code and back.
>
> AFAIK the Cray-1 had gather and scatter instructions. I wonder how
> much the speed difference between stride-1 loads and stores and gather
> and scatter was on the Cray-1.

Probably not much at all, perhaps none. Remember, Cray-1 had no cache,
used static RAM for main memory (i.e. no page mode, etc.), and had
highly interleaved memory.

> Maybe gather and scatter were added in the Cray-1 (for which people
> thought about how to vectorize) because they could be implemented
> efficiently, and nowadays SIMD designers add them, because the Cray-1
> had them, and code designed with that background has them, even though
> nowadays the performance advantages of stride-1 accesses are much
> bigger.

Could be.

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

On Saturday, August 12, 2023 at 1:49:58 AM UTC-5, Anton Ertl wrote:
> Michael S <already...@yahoo.com> writes:
> >Is there wider than 128-bit SIMD ISA that does *not* have that or
> >another variant of gather?
> AVX. However, Intel added gather instructions with AVX2 two years
> later.
> >Personally I am of low opinion about gather. IMHO, if one's algorithm
> >needs gather for vectorization then it's a sign that vectorization gain
> >will be low and that you better not bother.
> >But it seems to me that most architect are enamored but this sort of crap.
> Yes, it's better to arrange your data or your computations so you
> don't need gather.
>
> However, if the programmer does not do that (either because he does
> not think about vectorization, or just does not find such an
> arrangement), gather and scatter instructions may be useful for
> avoiding to have to switch from SIMD to scalar code and back.
>
> AFAIK the Cray-1 had gather and scatter instructions. I wonder how
> much the speed difference between stride-1 loads and stores and gather
> and scatter was on the Cray-1.
<
Cray-1 and CRAY 1-S did NOT have gather/Scatter
Cray-XMP and YMP did
>
> Maybe gather and scatter were added in the Cray-1 (for which people
> thought about how to vectorize) because they could be implemented
> efficiently, and nowadays SIMD designers add them, because the Cray-1
> had them, and code designed with that background has them, even though
> nowadays the performance advantages of stride-1 accesses are much
> bigger.
<
Efficiently in CRAY XMP was AGENnig 1 new address per cycle per gather and
sending it out into the heavily interleaved memory system.
<
Efficiently in CRAYY YMP was AGENing 3 addresses per cycle and sending these
out into the even heavier interleaved memory system.
<
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Saturday, August 12, 2023 at 10:52:09 AM UTC-5, Stephen Fuld wrote:
> On 8/11/2023 11:38 PM, Anton Ertl wrote:
> > Michael S <already...@yahoo.com> writes:
> >> Is there wider than 128-bit SIMD ISA that does *not* have that or
> >> another variant of gather?
> >
> > AVX. However, Intel added gather instructions with AVX2 two years
> > later.
> >
> >> Personally I am of low opinion about gather. IMHO, if one's algorithm
> >> needs gather for vectorization then it's a sign that vectorization gain
> >> will be low and that you better not bother.
> >> But it seems to me that most architect are enamored but this sort of crap.
> >
> > Yes, it's better to arrange your data or your computations so you
> > don't need gather.
> >
> > However, if the programmer does not do that (either because he does
> > not think about vectorization, or just does not find such an
> > arrangement), gather and scatter instructions may be useful for
> > avoiding to have to switch from SIMD to scalar code and back.
> >
> > AFAIK the Cray-1 had gather and scatter instructions. I wonder how
> > much the speed difference between stride-1 loads and stores and gather
> > and scatter was on the Cray-1.
> Probably not much at all, perhaps none. Remember, Cray-1 had no cache,
<
Yes,, CRAY-1
<
> used static RAM for main memory
<
CRAY-1S
<
> (i.e. no page mode, etc.), and had
> highly interleaved memory.
<
64-to-256 banks
<
> > Maybe gather and scatter were added in the Cray-1 (for which people
> > thought about how to vectorize) because they could be implemented
> > efficiently, and nowadays SIMD designers add them, because the Cray-1
> > had them, and code designed with that background has them, even though
> > nowadays the performance advantages of stride-1 accesses are much
> > bigger.
> Could be.
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

On Friday, August 11, 2023 at 1:39:09 AM UTC-5, Anton Ertl wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >The gather bug is an example of not-obeying the rule:
> >"If you change 1 bit in an architectural register, you change them all"
> ><
> >RISC-people in 1980 already knew the x86 byte stuff was problematic
> >{along with a host of other mis-features}
<
> Where can I read about this knowledge of the RISC people? Did they
> even waste one thought to the 8086, which was an insignificant
> microprocessor in 1980?
<
It was well known that early x86 compilers had a hard time treating
the separate containers of the registers sometimes as a pair and
sometimes as a byte.
<
It was very well known that setting some condition codes without setting
all of them was already problematic--not just on the HW but for the
compilers, too.
<
It was well known that dedicated registers for MUL and DIV were
a different kind of problem for the compilers of that era.
<
And It was seen and a significant problem how IBM 360 has insert
character but not LDB (especially with the K&R C rules for integer
upward casting)
<
I don't know/remember where any of this was actually written down.
<
I certainly knew this stuff in 1983 after having built the DENELCOR
C compiler from PCC base in 1981-2. {This is also where I discovered
my dislike of condition codes, and separate register files.}
>
> As for the gather bug, the gather instructions were added with AVX2,
> first implemented in Haswell (released 2013), and with AVX-512 F
> (Knights Landing, 2013). Intel had problems with partial register
<
AMD had long and significant talks on partial register updates when
designing Opteron (x86-64). There were essentially 2 camps--a) get
rid of them, and b) backwards compatibility is a requirement. The
rest (as they say) is history.
<
> updates since they introduced OoO with the Pentium Pro (released
> 1995), so they were aware of the problems of implementing such
> instructions. And yet they chose to do so, in addition to choosing to
> add an instruction that may perform 16 memory accesses.
<
I think they would feel they were forced into it, and it was not a "free" choice.
>
> Interestingly, the definition of, e.g., VGATHERPS says:
>
> |* Faults are delivered in a right-to-left manner. That is, if a fault
> | is triggered by an element and delivered, all elements closer to the
> | LSB of the destination will be completed (and
> | non-faulting). Individual elements closer to the MSB may or may not
> | be completed. If a given element triggers multiple faults, they are
> | delivered in the conventional order.
> |
> |* Elements may be gathered in any order, but faults must be delivered
> | in a right-to-left order; thus, elements to the left of a faulting
> | one may be gathered before the fault is delivered. A given
> | implementation of this instruction is repeatable - given the same
> | input values and architectural state, the same set of elements to
> | the left of the faulting one will be gathered.
>
> It's not clear to me what this "completed" and "gathered" is about.
> Is it about changing the destination register in case of a fault? Is
> it about order of memory accesses for concurrent processing?
<
When you define gather as above:: and you have a OoO µArchitecture,
you are tempted to stream operands through AGEN and out through
the memory system, the odd accesses that miss the TLB are not serviced
in the order of occurrence in the AGENing and not serviced in the order
of occurrence in filling of the register. This can lead to all sorts of
"interesting stuff happening" not much of which is good for the
implementation.
>
> There is a good reason why multi-access instructions are shunned by
> most architects.
<
Especially when 1 address cannot define the memory access pattern.
<
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Saturday, August 12, 2023 at 9:53:33 AM UTC+3, Anton Ertl wrote:
> Michael S <already...@yahoo.com> writes:
> >Downfall, on the other hand, looks impossible to find unless you know
> >what you are looking for.
> So how do you think did Daniel Moghimi know what to look for?
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

I don't know. But his article leaves a feeling that somehow he suspected that
there is something of this sort.

On Saturday, August 12, 2023 at 9:49:58 AM UTC+3, Anton Ertl wrote:
> Michael S <already...@yahoo.com> writes:
> >Is there wider than 128-bit SIMD ISA that does *not* have that or
> >another variant of gather?
> AVX. However, Intel added gather instructions with AVX2 two years
> later.
> >Personally I am of low opinion about gather. IMHO, if one's algorithm
> >needs gather for vectorization then it's a sign that vectorization gain
> >will be low and that you better not bother.
> >But it seems to me that most architect are enamored but this sort of crap.
> Yes, it's better to arrange your data or your computations so you
> don't need gather.
>
> However, if the programmer does not do that (either because he does
> not think about vectorization, or just does not find such an
> arrangement), gather and scatter instructions may be useful for
> avoiding to have to switch from SIMD to scalar code and back.
>

I wanted to write that the problem of current form of AVX/AVX2 is that
mixing SIMD ALUs with scalar load is expensive. But during writing I
realized that it is not necessarily true. One can use a series of broadcast
loads followed by VBLENDPx. Both a cheap.
I didn't think about this simple technique until now.

> AFAIK the Cray-1 had gather and scatter instructions. I wonder how
> much the speed difference between stride-1 loads and stores and gather
> and scatter was on the Cray-1.
>
> Maybe gather and scatter were added in the Cray-1 (for which people
> thought about how to vectorize) because they could be implemented
> efficiently, and nowadays SIMD designers add them, because the Cray-1
> had them, and code designed with that background has them, even though
> nowadays the performance advantages of stride-1 accesses are much
> bigger.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

Anton Ertl wrote:
> Michael S <already5chosen@yahoo.com> writes:
>> Downfall, on the other hand, looks impossible to find unless you know
>> what you are looking for.
>
> So how do you think did Daniel Moghimi know what to look for?
>
> - anton

The paper references two patents

US8972697B2 - Gather using index array and finite state machine
https://patents.google.com/patent/US8972697B2/

US9189236B2 - Speculative non-faulting loads and gathers
https://patents.google.com/patent/US9189236/

If he was reading Intel or AMD patents (I do that myself sometimes)
he might have noticed US8972697B2 includes the following paragraph
which has a very Meltdown-y smell to it if an SMT task switch happens
at just the wrong moment.

He'd still have to be a pretty smart cookie to figure that out.

"In one embodiment, the uops schedulers 202, 204, 206, dispatch dependent
operations before the parent load has finished executing. As uops are
speculatively scheduled and executed in processor 200, the processor 200
also includes logic to handle memory misses. If a data load misses in the
data cache, there can be dependent operations in flight in the pipeline
that have left the scheduler with temporarily incorrect data. In some
embodiments, a replay mechanism may track and re-execute instructions
that use incorrect data. Only the dependent operations need to be
replayed and the independent ones are allowed to complete.
The schedulers and replay mechanism of one embodiment of a processor
are also designed to catch instructions that provide vector scatter
and/or gather functionality. In some alternative embodiments without
a replay mechanism, speculative execution of uops may be prevented and
dependent uops may reside in the schedulers 202, 204, 206 until they are
canceled, or until they cannot be canceled."

EricP <ThatWouldBeTelling@thevillage.com> schrieb:

> If he was reading Intel or AMD patents (I do that myself sometimes)

You're quite brave, reading and understanding patents is a hard work.

This has not gotten easier in more recent years, when patent offices
demand more and more detail in dislosure in patent texts - this
makes them harder to read, because it is hard to be sure if you are
currently reading about the core of the patent, or some arbitrary
description that the author thought the patent office would require,
just to be on the safe side.

And yes, I have been very much guilty in that respect - several
people have told me that they did not understand what I had written,
although they were active in the field. My standard reply was that
these patents are meant to be exact, not necessarily easy to read.

I recently read a patent from the late 1960s/early 1970s. It had
a total of three pages - a title page, a text page, a page with
two drawings. It was a thing of beauty.