scott@slp53.sl.home (Scott Lurndal) writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>scott@slp53.sl.home (Scott Lurndal) writes:
>>>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>>Also, if the prefetcher works with data in a shared cache (I don't
>>>>know whether the data-dependent prefetchers do that), it may not
>>>>matter on which core the code runs.
>>>
>>>Run it in non-cacheable memory. Slow but safe.
>>
>>To eliminate this particular vulnerability, it's sufficient to disable
>>the data-dependent prefetcher.
>
>That assumes that chicken bit(s) are available to do that.

The hardware designers have put in the chicken bit(s); it's highly
unlikely that they have unconditionally enabled the data-dependent
prefetcher on M1 and M2, and only added a chicken bit on M3. Now that
the hardware indeed turns out to be broken, they just need to activate
it/them.

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

On Sun, 24 Mar 2024 18:20:06 +0000
mitchalsup@aol.com (MitchAlsup1) wrote:

> Stephen Fuld wrote:
>
> > https://arstechnica.com/security/2024/03/hackers-can-extract-secret-encryption-keys-from-apples-mac-chips/
> >
>
> > So, is there a way to fix this while maintaining the feature's
> > performance advantage?
>
> They COULD start by not putting prefetched data into the cache
> until after the predicting instruction retires. {{I have a note
> from about 20 months ago where this feature was publicized and
> the note indicates a potential side-channel.}}
>
> An alternative is to notice that [*]cryption instructions are
> being processed and turn DMP off during those intervals of time.
> {Or both}.
>

Their PoC attacks public key crypto algorithms - RSA-2048, DHKE-2048 and
couple of exotic new algorithms that nobody uses.
I think, neither RSA-2048 nor DHKE-2048 use any special crypto
instructions.
On Intel/AMD it's likely that thise crypto routines use MULX
and ADX instruction much for often than non-crypto code, but that's not
guaranteed.
On ARM64 you don't even have that much, because equivalents of MULX and
of ADX are part of base instruction set.

> Principle:: an Architecturally visible unit of data can only become
> visible after the causing instruction retires. A high precision timer
> makes cache line [dis]placement visible; so either take away the HPT
> or don't alter cache visible state too early.
>
> And we are off to the races, again.....

On Mon, 25 Mar 2024 12:18:18 -0400
Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> > Principle:: an Architecturally visible unit of data can only become
> > visible after the causing instruction retires. A high precision
> > timer makes cache line [dis]placement visible; so either take away
> > the HPT or don't alter cache visible state too early.
>
> And parallelism (e.g. multicores) can be used to emulate HPT, so "take
> away the HPT" is not really an option.
>
>
> Stefan

That's exactly how they measured time in PoC.

Michael S <already5chosen@yahoo.com> schrieb:

> In case you missed it, the web page contains link to pdf:
> https://gofetch.fail/files/gofetch.pdf

Looking the paper, it seems that a separate "load value" instruction
(where it is guaranteed that no pointer prefetching will be done)
could fix this particular issue. Compilers know what type is being
loaded from memory, and could issue the corresponding instruction.
This would not impact performance.

Only works for new versions of an architecture, and supporting
compilers, but no code change would be required. And, of course,
it would eat up opcode space.

Thomas Koenig wrote:
> Michael S <already5chosen@yahoo.com> schrieb:
>
>> In case you missed it, the web page contains link to pdf:
>> https://gofetch.fail/files/gofetch.pdf
>
> Looking the paper, it seems that a separate "load value" instruction
> (where it is guaranteed that no pointer prefetching will be done)
> could fix this particular issue. Compilers know what type is being
> loaded from memory, and could issue the corresponding instruction.
> This would not impact performance.
>
> Only works for new versions of an architecture, and supporting
> compilers, but no code change would be required. And, of course,
> it would eat up opcode space.

It doesn't need to eat opcode space if you only support one data type,
64-bit ints, and one address mode, [register].
Other address modes can be calculated using LEA.
Since these are rare instructions to solve a particular problem,
they won't be used that often, so a few extra instructions shouldn't matter.

I used this approach for the Atomic Fetch-and-OP instructions.
They only need one or two data types and one address mode.

I also considered the same single [reg] address mode for privileged
Load & Store to Physical Address, though these would need to
support 1,2,4, and 8 byte ints, and need some cache control bits.

EricP <ThatWouldBeTelling@thevillage.com> schrieb:
> Thomas Koenig wrote:
>> Michael S <already5chosen@yahoo.com> schrieb:
>>
>>> In case you missed it, the web page contains link to pdf:
>>> https://gofetch.fail/files/gofetch.pdf
>>
>> Looking the paper, it seems that a separate "load value" instruction
>> (where it is guaranteed that no pointer prefetching will be done)
>> could fix this particular issue. Compilers know what type is being
>> loaded from memory, and could issue the corresponding instruction.
>> This would not impact performance.
>>
>> Only works for new versions of an architecture, and supporting
>> compilers, but no code change would be required. And, of course,
>> it would eat up opcode space.
>
> It doesn't need to eat opcode space if you only support one data type,
> 64-bit ints, and one address mode, [register].
> Other address modes can be calculated using LEA.
> Since these are rare instructions to solve a particular problem,
> they won't be used that often, so a few extra instructions shouldn't matter.

Hm, I'm not sure it would actually be used rarely, at least not
the way I thought about it.

I envisage a "ldp" (load pointer) instruction, which turns on
prefetaching, for everything that looks like

foo_t *p = some_expr;

which could also mean something like

*p = ptrarray[i];

with a scaled and indexed load (for example), where prefixing
is turned on, and a "ldd" (load double data) instruction where,
explicitly, for

long int n = some_other_expr;

where prefetching is explicitly disabled. (Apart from the security
implicatins, this could also save a tiny bit of power).

Thomas Koenig wrote:
> EricP <ThatWouldBeTelling@thevillage.com> schrieb:
>> Thomas Koenig wrote:
>>> Michael S <already5chosen@yahoo.com> schrieb:
>>>
>>>> In case you missed it, the web page contains link to pdf:
>>>> https://gofetch.fail/files/gofetch.pdf
>>> Looking the paper, it seems that a separate "load value" instruction
>>> (where it is guaranteed that no pointer prefetching will be done)
>>> could fix this particular issue. Compilers know what type is being
>>> loaded from memory, and could issue the corresponding instruction.
>>> This would not impact performance.
>>>
>>> Only works for new versions of an architecture, and supporting
>>> compilers, but no code change would be required. And, of course,
>>> it would eat up opcode space.
>> It doesn't need to eat opcode space if you only support one data type,
>> 64-bit ints, and one address mode, [register].
>> Other address modes can be calculated using LEA.
>> Since these are rare instructions to solve a particular problem,
>> they won't be used that often, so a few extra instructions shouldn't matter.
>
> Hm, I'm not sure it would actually be used rarely, at least not
> the way I thought about it.

I'm referring to your load with prefetch disable.
For these particular loads it's users could likely tolerate the
"overhead" of an extra LEA instruction to calculate the address,
and don't need all 7 integer data types.

> I envisage a "ldp" (load pointer) instruction, which turns on
> prefetaching, for everything that looks like
>
> foo_t *p = some_expr;
>
> which could also mean something like
>
> *p = ptrarray[i];

So this would be
LEA r0,[rBase+rIndex*8+offset]
LDAPQ r0,[r0] // load quad with auto pointer prefetch

though I'm not really sold on the need for this if you have an instruction
(below) that explicitly disables pointer auto-prefetch.
Plus all this does is eliminate an explicit PREFCHR Prefetch-for-Read.

> with a scaled and indexed load (for example), where prefixing
> is turned on, and a "ldd" (load double data) instruction where,
> explicitly, for
>
> long int n = some_other_expr;
>
> where prefetching is explicitly disabled. (Apart from the security
> implicatins, this could also save a tiny bit of power).

LEA r0,[rBase+offset]
LDNPQ r0,[r0] // load quad no-auto-prefetch

costs 1 opcode as it only supports int64 data type and
doesn't need a corresponding STNPQ store.

On 3/25/2024 5:27 PM, Lawrence D'Oliveiro wrote:
> On Mon, 25 Mar 2024 22:17:55 +0000, MitchAlsup1 wrote:
>
>> Lawrence D'Oliveiro wrote:
>>
>>> The basic problem is that building all this complex, bug-prone
>>> functionality into monolithic, nonupgradeable hardware is not really a
>>> good idea.
>>
>> Would you like to inform us of how it can be done otherwise ?
>
> Upgradeable firmware/software, of course.

But microcode is generally slower than dedicated hardware, and most
people seem to be unwilling to give up performance all the time to gain
an advantage in a situation that occurs infrequently and mostly never.

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

Thomas Koenig <tkoenig@netcologne.de> writes:
>Michael S <already5chosen@yahoo.com> schrieb:
>
>> In case you missed it, the web page contains link to pdf:
>> https://gofetch.fail/files/gofetch.pdf
>
>Looking the paper, it seems that a separate "load value" instruction
>(where it is guaranteed that no pointer prefetching will be done)
>could fix this particular issue. Compilers know what type is being
>loaded from memory, and could issue the corresponding instruction.
>This would not impact performance.
>
>Only works for new versions of an architecture, and supporting
>compilers, but no code change would be required. And, of course,
>it would eat up opcode space.

The other way 'round seems to be a better approach: mark those loads
that load addresses, and then prefetch at most based on the data
loaded by these instructions (of course, the data-dependent prefetcher
may choose to ignore the data based on history). That means that
existing programs are immune to GoFetch, but also don't benefit from
the data-dependent prefetcher (which is a minor issue IMO).

As for opcode space, we already have prefetch instructions, so one
could implement this by letting every load that actually loads an
address be followed by a prefetch instruction. But of course that
would consume more code space and decoding bandwidth than just adding
a load-address instruction.

In any case, passing the prefetch hints to hardware that may ignore
the hint based on history may help reduce the performance
disadvantages that have been seen when using prefetch hint
instructions.

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

EricP <ThatWouldBeTelling@thevillage.com> writes:
>It doesn't need to eat opcode space if you only support one data type,
>64-bit ints, and one address mode, [register].
>Other address modes can be calculated using LEA.
>Since these are rare instructions to solve a particular problem,
>they won't be used that often, so a few extra instructions shouldn't matter.

You lost me here. Do you mean that a load with address mode
[register] is considered to be a non-address load and not followed by
the data-dependent prefetcher? So how would an address load be
encoded if the natural expression would be [register]?

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

Anton Ertl wrote:
> EricP <ThatWouldBeTelling@thevillage.com> writes:
>> It doesn't need to eat opcode space if you only support one data type,
>> 64-bit ints, and one address mode, [register].
>> Other address modes can be calculated using LEA.
>> Since these are rare instructions to solve a particular problem,
>> they won't be used that often, so a few extra instructions shouldn't matter.
>
> You lost me here. Do you mean that a load with address mode
> [register] is considered to be a non-address load and not followed by
> the data-dependent prefetcher? So how would an address load be
> encoded if the natural expression would be [register]?
>
> - anton

I'm pointing out that not all instructions need to be orthogonal.
There can be savings in opcode space by tempering that based on
expected frequency of occurrence.

The normal LD and ST have all their address modes and data types
because these functions occur frequently enough that we deem it
worthwhile to support these all in one instruction,
such as supporting both sign and zero extended loads
or scaled index addressing.

I note there is this class of relatively rarely used special purpose
memory access instructions that don't need to have all singing and all
dancing address modes and/or data types like the regular LD and ST.

Since I need a LEA Load Effective Address instruction anyway
which does rBase+rIndex*scale+offset calculation
(plus I have others, like where rBase is RIP or an absolute address),
then I can drop all but the [reg] address mode for these rare instructions
and in many cases drop some sign or zero extend types for loads.

For example, I use just two opcodes for Atomic Fetch Add int64 and int32
AFADD8 rDst,rSrc,[rAddr]
AFADD4 rDst,rSrc,[rAddr]

EricP <ThatWouldBeTelling@thevillage.com> schrieb:
> Thomas Koenig wrote:
>> EricP <ThatWouldBeTelling@thevillage.com> schrieb:
>>> Thomas Koenig wrote:
>>>> Michael S <already5chosen@yahoo.com> schrieb:
>>>>
>>>>> In case you missed it, the web page contains link to pdf:
>>>>> https://gofetch.fail/files/gofetch.pdf
>>>> Looking the paper, it seems that a separate "load value" instruction
>>>> (where it is guaranteed that no pointer prefetching will be done)
>>>> could fix this particular issue. Compilers know what type is being
>>>> loaded from memory, and could issue the corresponding instruction.
>>>> This would not impact performance.
>>>>
>>>> Only works for new versions of an architecture, and supporting
>>>> compilers, but no code change would be required. And, of course,
>>>> it would eat up opcode space.
>>> It doesn't need to eat opcode space if you only support one data type,
>>> 64-bit ints, and one address mode, [register].
>>> Other address modes can be calculated using LEA.
>>> Since these are rare instructions to solve a particular problem,
>>> they won't be used that often, so a few extra instructions shouldn't matter.
>>
>> Hm, I'm not sure it would actually be used rarely, at least not
>> the way I thought about it.
>
> I'm referring to your load with prefetch disable.
> For these particular loads it's users could likely tolerate the
> "overhead" of an extra LEA instruction to calculate the address,
> and don't need all 7 integer data types.

If it was LEA-only, it would need some kind of pragma in the code
which said "use this more cumbersome and slower, but more
safe version".

For that reason, I would probably prefer a separate version
which is implicitly safe and does not have any other drawbacks
for performance, with no code changes.

If it's worth the opcode space...

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Thomas Koenig <tkoenig@netcologne.de> writes:
>>Michael S <already5chosen@yahoo.com> schrieb:
>>
>>> In case you missed it, the web page contains link to pdf:
>>> https://gofetch.fail/files/gofetch.pdf
>>
>>Looking the paper, it seems that a separate "load value" instruction
>>(where it is guaranteed that no pointer prefetching will be done)
>>could fix this particular issue. Compilers know what type is being
>>loaded from memory, and could issue the corresponding instruction.
>>This would not impact performance.

It is worth noting (from the paper's Introduction):

In particular, Augury reported that the [Apple M-series ed.] DMP only activates
in the presence of a rather idiosyncratic program memory
access pattern (where the program streams through an array
of pointers and architecturally dereferences those pointers).
This access pattern is not typically found in security critical
software such as side-channel hardened constant-time code--
hence making that code impervious to leakage through the
DMP.

scott@slp53.sl.home (Scott Lurndal) writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>Thomas Koenig <tkoenig@netcologne.de> writes:
>>>Michael S <already5chosen@yahoo.com> schrieb:
>>>
>>>> In case you missed it, the web page contains link to pdf:
>>>> https://gofetch.fail/files/gofetch.pdf
>>>
>>>Looking the paper, it seems that a separate "load value" instruction
>>>(where it is guaranteed that no pointer prefetching will be done)
>>>could fix this particular issue. Compilers know what type is being
>>>loaded from memory, and could issue the corresponding instruction.
>>>This would not impact performance.
>
>It is worth noting (from the paper's Introduction):
>
> In particular, Augury reported that the [Apple M-series ed.] DMP only activates
> in the presence of a rather idiosyncratic program memory
> access pattern (where the program streams through an array
> of pointers and architecturally dereferences those pointers).
> This access pattern is not typically found in security critical
> software such as side-channel hardened constant-time code--
> hence making that code impervious to leakage through the
> DMP.

Reminder to self, read rest of article before commenting.

Never mind.

EricP wrote:

> Anton Ertl wrote:
>> EricP <ThatWouldBeTelling@thevillage.com> writes:
>>> It doesn't need to eat opcode space if you only support one data type,
>>> 64-bit ints, and one address mode, [register].
>>> Other address modes can be calculated using LEA.
>>> Since these are rare instructions to solve a particular problem,
>>> they won't be used that often, so a few extra instructions shouldn't matter.
>>
>> You lost me here. Do you mean that a load with address mode
>> [register] is considered to be a non-address load and not followed by
>> the data-dependent prefetcher? So how would an address load be
>> encoded if the natural expression would be [register]?
>>
>> - anton

> I'm pointing out that not all instructions need to be orthogonal.
> There can be savings in opcode space by tempering that based on
> expected frequency of occurrence.

> The normal LD and ST have all their address modes and data types
> because these functions occur frequently enough that we deem it
> worthwhile to support these all in one instruction,
> such as supporting both sign and zero extended loads
> or scaled index addressing.

> I note there is this class of relatively rarely used special purpose
> memory access instructions that don't need to have all singing and all
> dancing address modes and/or data types like the regular LD and ST.

> Since I need a LEA Load Effective Address instruction anyway
> which does rBase+rIndex*scale+offset calculation
> (plus I have others, like where rBase is RIP or an absolute address),
> then I can drop all but the [reg] address mode for these rare instructions
> and in many cases drop some sign or zero extend types for loads.

It seems to me that once the core has identified an address and an offset
from that address contains another address (foo->next, foo->prev) that
only those are prefetched. So this depends on placing next as the first
container in a structure and remains dependent on chasing next a lot more
often than chasing prev.

Otherwise, knowing a loaded value contains a pointer to a structure (or array)
one cannot predict what to prefetch unless one can assume the offset into the
struct (or array).

Now Note:: If there were an instruction that loaded the value known to be
a pointer and prefetched based on the received pointer, then the prefetch
is now architectural not µArchitectural and you are allowed to damage the
cache or TLB when/after the instruction retires.

> For example, I use just two opcodes for Atomic Fetch Add int64 and int32
> AFADD8 rDst,rSrc,[rAddr]
> AFADD4 rDst,rSrc,[rAddr]

On Wed, 27 Mar 2024 09:22:12 -0700, Stephen Fuld wrote:

> On 3/25/2024 5:27 PM, Lawrence D'Oliveiro wrote:
>
>> On Mon, 25 Mar 2024 22:17:55 +0000, MitchAlsup1 wrote:
>>
>>> Lawrence D'Oliveiro wrote:
>>>
>>>> The basic problem is that building all this complex, bug-prone
>>>> functionality into monolithic, nonupgradeable hardware is not really
>>>> a good idea.
>>>
>>> Would you like to inform us of how it can be done otherwise ?
>>
>> Upgradeable firmware/software, of course.
>
> But microcode is generally slower than dedicated hardware, and most
> people seem to be unwilling to give up performance all the time to gain
> an advantage in a situation that occurs infrequently and mostly never.

Bruce Schneier has a saying: “attacks never get worse, they can only get
better”.

Lawrence D'Oliveiro wrote:

> On Wed, 27 Mar 2024 09:22:12 -0700, Stephen Fuld wrote:

>> On 3/25/2024 5:27 PM, Lawrence D'Oliveiro wrote:
>>
>>> On Mon, 25 Mar 2024 22:17:55 +0000, MitchAlsup1 wrote:
>>>
>>>> Lawrence D'Oliveiro wrote:
>>>>
>>>>> The basic problem is that building all this complex, bug-prone
>>>>> functionality into monolithic, nonupgradeable hardware is not really
>>>>> a good idea.
>>>>
>>>> Would you like to inform us of how it can be done otherwise ?
>>>
>>> Upgradeable firmware/software, of course.
>>
>> But microcode is generally slower than dedicated hardware, and most
>> people seem to be unwilling to give up performance all the time to gain
>> an advantage in a situation that occurs infrequently and mostly never.

S.E.L 32/65, 32/67, 32/87 were all microcoded. 95% of the instructions*
ran down the pipeline without using the microcode (which was only there
to pick up the pieces after HW logic sequencers got tooo complicated.

(*) closer to 97% of the dynamic instruction stream.

Microcode IS generally slower, but not always. PDP-11 or VAX microcode
is too much, IBM, S.E.L. is not too much.

> Bruce Schneier has a saying: “attacks never get worse, they can only get
> better”.

Which is why to have to design for attackers (to be thwarted}.

Observing the last 4-odd years, it appears to me that CPU designers will
not be in a position to "give a rat's ass" until there is performance
competitive, cost competitive, alternatives. Given Apple, AMD, ARM, and
Intel not giving a rat's ass, it's going to have to come from somewhere
else.

MitchAlsup1 wrote:
> EricP wrote:
>
>> Anton Ertl wrote:
>>> EricP <ThatWouldBeTelling@thevillage.com> writes:
>>>> It doesn't need to eat opcode space if you only support one data type,
>>>> 64-bit ints, and one address mode, [register].
>>>> Other address modes can be calculated using LEA.
>>>> Since these are rare instructions to solve a particular problem,
>>>> they won't be used that often, so a few extra instructions shouldn't
>>>> matter.
>>>
>>> You lost me here. Do you mean that a load with address mode
>>> [register] is considered to be a non-address load and not followed by
>>> the data-dependent prefetcher? So how would an address load be
>>> encoded if the natural expression would be [register]?
>>>
>>> - anton
>
>> I'm pointing out that not all instructions need to be orthogonal.
>> There can be savings in opcode space by tempering that based on
>> expected frequency of occurrence.
>
>> The normal LD and ST have all their address modes and data types
>> because these functions occur frequently enough that we deem it
>> worthwhile to support these all in one instruction,
>> such as supporting both sign and zero extended loads
>> or scaled index addressing.
>
>> I note there is this class of relatively rarely used special purpose
>> memory access instructions that don't need to have all singing and all
>> dancing address modes and/or data types like the regular LD and ST.
>
>> Since I need a LEA Load Effective Address instruction anyway
>> which does rBase+rIndex*scale+offset calculation
>> (plus I have others, like where rBase is RIP or an absolute address),
>> then I can drop all but the [reg] address mode for these rare
>> instructions
>> and in many cases drop some sign or zero extend types for loads.
>
> It seems to me that once the core has identified an address and an offset
> from that address contains another address (foo->next, foo->prev) that
> only those are prefetched. So this depends on placing next as the first
> container in a structure and remains dependent on chasing next a lot more
> often than chasing prev.
>
> Otherwise, knowing a loaded value contains a pointer to a structure (or
> array)
> one cannot predict what to prefetch unless one can assume the offset
> into the
> struct (or array).

Right, this is the problem that these "data memory-dependent" prefetchers
like described in that Intel Programmable and Integrated Unified Memory
Architecture (PIUMA)" paper referenced by Paul Clayton are trying to solve.

The pointer field to chase can be
(a) at an +- offset from the current pointer virtual address
(b) at a different offset for each iteration
(c) conditional on some other field at some other offset

and most important:

(d) any new pointers are virtual address that have to start back at
the Load Store Queue for VA translation and forwarding testing
after applying (a),(b) and (c) above.

Since each chased pointer starts back at LSQ, the cost is no different
than an explicit Prefetch instruction, except without (a),(b) and (c)
having been applied first.

So I find the simplistic, blithe data-dependent auto prefetching
described as questionable.

> Now Note:: If there were an instruction that loaded the value known to be
> a pointer and prefetched based on the received pointer, then the prefetch
> is now architectural not µArchitectural and you are allowed to damage the
> cache or TLB when/after the instruction retires.

In the PIUMA case those pointers were to sparse data sets
so part of the problem was rolling over the cache, as well as
(and the PIUMA paper didn't mention this) the TLB.

After reading the PIUMA paper I had an idea for a small modification
to the PTE cache control bits to handle sparse data. The PTE's 3 CC bits
can specify the upper page table levels are cached in the TLB but
lower levels are not because they would always roll over the TLB.
However the non-TLB cached PTE's may optionally still be cached
in L1 or L2, or not at all.

This allows one to hold the top page table levels in the TLB,
the upper middle levels in L1, lower middle levels in L2,
and leaf PTE's and sparse code/data not cached at all.
BUT, as PIUMA proposes, we also allow the memory subsystem to read and write
individual aligned 8-byte values from DRAM, rather than whole cache lines,
so we only move that actual 8 bytes values we need.

Also note that page table walks are also graph structure walks
but chasing physical addresses at some simple calculated offsets.
These physical addresses might be cached in L1 or L2 so we can't
just chase these pointers in the memory controller but,
if one wants to do this, have to do so in the cache controller.

EricP wrote:

> MitchAlsup1 wrote:
>>
>> It seems to me that once the core has identified an address and an offset
>> from that address contains another address (foo->next, foo->prev) that
>> only those are prefetched. So this depends on placing next as the first
>> container in a structure and remains dependent on chasing next a lot more
>> often than chasing prev.
>>
>> Otherwise, knowing a loaded value contains a pointer to a structure (or
>> array)
>> one cannot predict what to prefetch unless one can assume the offset
>> into the
>> struct (or array).

> Right, this is the problem that these "data memory-dependent" prefetchers
> like described in that Intel Programmable and Integrated Unified Memory
> Architecture (PIUMA)" paper referenced by Paul Clayton are trying to solve.

> The pointer field to chase can be
> (a) at an +- offset from the current pointer virtual address
> (b) at a different offset for each iteration
> (c) conditional on some other field at some other offset

> and most important:

> (d) any new pointers are virtual address that have to start back at
> the Load Store Queue for VA translation and forwarding testing
> after applying (a),(b) and (c) above.

This is the tidbit that prevents doing prefetches at/in the DRAM controller.
The address so fetched needs translation !! And this requires dragging
stuff over to DRC that is not normally done.

> Since each chased pointer starts back at LSQ, the cost is no different
> than an explicit Prefetch instruction, except without (a),(b) and (c)
> having been applied first.

Latency cost is identical, instruction issue/retire costs are lower.

> So I find the simplistic, blithe data-dependent auto prefetching
> described as questionable.

K9 built a SW model of such a prefetcher. For the first 1B cycles of a
SPEC benchmark from ~2004 it performed quite well. {{We later figured out
that this was initialization that built a GB data structure.}} Late on
in the benchmark the pointers got scrambled and the performance from the
prefetched fell on its face.

Moral, you need close to 1T cycle of simulation to qualify a prefetcher.

>> Now Note:: If there were an instruction that loaded the value known to be
>> a pointer and prefetched based on the received pointer, then the prefetch
>> is now architectural not µArchitectural and you are allowed to damage the
>> cache or TLB when/after the instruction retires.

> In the PIUMA case those pointers were to sparse data sets
> so part of the problem was rolling over the cache, as well as
> (and the PIUMA paper didn't mention this) the TLB.

> After reading the PIUMA paper I had an idea for a small modification
> to the PTE cache control bits to handle sparse data. The PTE's 3 CC bits
> can specify the upper page table levels are cached in the TLB but
> lower levels are not because they would always roll over the TLB.
> However the non-TLB cached PTE's may optionally still be cached
> in L1 or L2, or not at all.

> This allows one to hold the top page table levels in the TLB,
> the upper middle levels in L1, lower middle levels in L2,
> and leaf PTE's and sparse code/data not cached at all.

Given the 2-level TLBs currently in vogue, the fist level might
have 32-64 PTEs, while the second might have 2048 PTEs. With this
number of PTEs available, does you scheme still give benefit ??

> BUT, as PIUMA proposes, we also allow the memory subsystem to read and write
> individual aligned 8-byte values from DRAM, rather than whole cache lines,
> so we only move that actual 8 bytes values we need.

Busses on cores are reaching the stage where an entire cache line
is transferred in 1-cycle. With such busses, why define anything
smaller than a cache line ?? {other than uncacheable accesses}

> Also note that page table walks are also graph structure walks
> but chasing physical addresses at some simple calculated offsets.
> These physical addresses might be cached in L1 or L2 so we can't
> just chase these pointers in the memory controller but,
> if one wants to do this, have to do so in the cache controller.

Yes, this is why the K9 prefetcher was in the L2 where it had access
to the L2 TLB.

On 3/28/24 3:59 PM, MitchAlsup1 wrote:
> EricP wrote:
[snip]
>> (d) any new pointers are virtual address that have to start back at
>>      the Load Store Queue for VA translation and forwarding testing
>>      after applying (a),(b) and (c) above.
>
> This is the tidbit that prevents doing prefetches at/in the DRAM controller.
> The address so fetched needs translation !! And this requires dragging
> stuff over to DRC that is not normally done.

With multiple memory channels having independent memory
controllers (a reasonable design I suspect), a memory controller
may have to send the prefetch request to another memory controller
anyway. If the prefetch has to take a trip on the on-chip network,
a "minor side trip" for translation might not be horrible (though
it seems distasteful to me).

With the Mill having translation at last level cache miss, such
prefetching may be more natural *but* distributing the virtual
address translations and the memory controllers seems challenging
when one wants to minimize hops.

[snip]
>> BUT, as PIUMA proposes, we also allow the memory subsystem to
>> read and write
>> individual aligned 8-byte values from DRAM, rather than whole
>> cache lines,
>> so we only move that actual 8 bytes values we need.
>
> Busses on cores are reaching the stage where an entire cache line
> is transferred in 1-cycle. With such busses, why define anything
> smaller than a cache line ?? {other than uncacheable accesses}

The Intel research chip was special-purpose targeting
cache-unfriendly code. Reading 64 bytes when 99% of the time 56
bytes would be unused is rather wasteful (and having more memory
channels helps under high thread count).

However, even for a "general purpose" processor, "word"-granular
atomic operations could justify not having all data transfers be
cache line size. (Such are rare compared with cache line loads
from memory or other caches, but a design might have narrower
connections for coherence, interrupts, etc. that could be used for
small data communication.)

In-cache compression might also nudge the tradeoffs. Being able to
have higher effective bandwidth when data is transmitted in a
compressed form might be useful. "Lossy compression", where the
recipient does not care about much of the data, would allow
compression even when the data itself is not compressible. For
contiguous useful data, this is comparable to a smaller cache
line.

"Paul A. Clayton" <paaronclayton@gmail.com> writes:
>On 3/28/24 3:59 PM, MitchAlsup1 wrote:
>> EricP wrote:
>[snip]
>>> (d) any new pointers are virtual address that have to start back at
>>>      the Load Store Queue for VA translation and forwarding testing
>>>      after applying (a),(b) and (c) above.
>>
>> This is the tidbit that prevents doing prefetches at/in the DRAM controller.
>> The address so fetched needs translation !! And this requires dragging
>> stuff over to DRC that is not normally done.
>
>With multiple memory channels having independent memory
>controllers (a reasonable design I suspect), a memory controller
>may have to send the prefetch request to another memory controller
>anyway.

Which is usually handled by the LLC when the address space is
striped across multiple memory controllers.

>> Busses on cores are reaching the stage where an entire cache line
>> is transferred in 1-cycle. With such busses, why define anything
>> smaller than a cache line ?? {other than uncacheable accesses}
>
>The Intel research chip was special-purpose targeting
>cache-unfriendly code. Reading 64 bytes when 99% of the time 56
>bytes would be unused is rather wasteful (and having more memory
>channels helps under high thread count).

Given the lack of both spatial and temporal locality in that
workload, one wonders if the data should be cached at all.

>
>However, even for a "general purpose" processor, "word"-granular
>atomic operations could justify not having all data transfers be
>cache line size. (Such are rare compared with cache line loads
>from memory or other caches, but a design might have narrower
>connections for coherence, interrupts, etc. that could be used for
>small data communication.)

So long as the data transfer is cachable, the atomics can be handled
at the LLC, rather than the memory controller.

On 3/29/24 10:15 AM, Scott Lurndal wrote:
> "Paul A. Clayton" <paaronclayton@gmail.com> writes:
>> On 3/28/24 3:59 PM, MitchAlsup1 wrote:
[snip]
>>> This is the tidbit that prevents doing prefetches at/in the DRAM controller.
>>> The address so fetched needs translation !! And this requires dragging
>>> stuff over to DRC that is not normally done.
>>
>> With multiple memory channels having independent memory
>> controllers (a reasonable design I suspect), a memory controller
>> may have to send the prefetch request to another memory controller
>> anyway.
>
> Which is usually handled by the LLC when the address space is
> striped across multiple memory controllers.

For data-dependent (pointer chasing) prefetching, one would like
for the prefetch to start as soon as the data was available. For a
cache miss that would be in the memory controller. Having to do
address translation can be inconvenient even for LLC.
>
>
>
>>> Busses on cores are reaching the stage where an entire cache line
>>> is transferred in 1-cycle. With such busses, why define anything
>>> smaller than a cache line ?? {other than uncacheable accesses}
>>
>> The Intel research chip was special-purpose targeting
>> cache-unfriendly code. Reading 64 bytes when 99% of the time 56
>> bytes would be unused is rather wasteful (and having more memory
>> channels helps under high thread count).
>
> Given the lack of both spatial and temporal locality in that
> workload, one wonders if the data should be cached at all.

Most of the data was intended not to be cached. Instructions and
stack would still have spatial locality and some temporal
locality.

>> However, even for a "general purpose" processor, "word"-granular
>> atomic operations could justify not having all data transfers be
>> cache line size. (Such are rare compared with cache line loads
>>from memory or other caches, but a design might have narrower
>> connections for coherence, interrupts, etc. that could be used for
>> small data communication.)
>
> So long as the data transfer is cachable, the atomics can be handled
> at the LLC, rather than the memory controller.

Yes, but if the width of the on-chip network — which is what Mitch
was referring to in transferring a cache line in one cycle — is
c.72 bytes (64 bytes for the data and 8 bytes for control
information) it seems that short messages would either have to be
grouped (increasing latency) or waste a significant fraction of
the potential bandwidth for that transfer. Compressed cache lines
would also not save bandwidth. These may not be significant
considerations, but this is an answer to "why define anything
smaller than a cache line?", i.e., seemingly reasonable
motivations may exist.

"Paul A. Clayton" <paaronclayton@gmail.com> writes:
>On 3/29/24 10:15 AM, Scott Lurndal wrote:
>> "Paul A. Clayton" <paaronclayton@gmail.com> writes:
>>> On 3/28/24 3:59 PM, MitchAlsup1 wrote:
>[snip]

>>> However, even for a "general purpose" processor, "word"-granular
>>> atomic operations could justify not having all data transfers be
>>> cache line size. (Such are rare compared with cache line loads
>>>from memory or other caches, but a design might have narrower
>>> connections for coherence, interrupts, etc. that could be used for
>>> small data communication.)
>>
>> So long as the data transfer is cachable, the atomics can be handled
>> at the LLC, rather than the memory controller.
>
>Yes, but if the width of the on-chip network — which is what Mitch
>was referring to in transferring a cache line in one cycle — is
>c.72 bytes (64 bytes for the data and 8 bytes for control
>information) it seems that short messages would either have to be
>grouped (increasing latency) or waste a significant fraction of
>the potential bandwidth for that transfer. Compressed cache lines
>would also not save bandwidth. These may not be significant
>considerations, but this is an answer to "why define anything
>smaller than a cache line?", i.e., seemingly reasonable
>motivations may exist.
>

It's not uncommon for the bus/switch/mesh -structure- to be 512-bits wide,
which indeed will support a full cache line transfer in a single transaction;
it also supports high-volume DMA operations (either memory to memory or
device to memory).

Most of the interconnect (bus, switched or point-to-point) implementations
have an overlaying protocol (including the cache coherency
protocol) and are effectively message based, with agents posting requests
that don't need a reply and expecting a reply for the rest.

That doesn't require that every transaction over that bus to
utilize the full width of the bus.

Scott Lurndal wrote:

> "Paul A. Clayton" <paaronclayton@gmail.com> writes:
>>On 3/29/24 10:15 AM, Scott Lurndal wrote:
>>> "Paul A. Clayton" <paaronclayton@gmail.com> writes:
>>>> On 3/28/24 3:59 PM, MitchAlsup1 wrote:
>>[snip]

>>>> However, even for a "general purpose" processor, "word"-granular
>>>> atomic operations could justify not having all data transfers be
>>>> cache line size. (Such are rare compared with cache line loads
>>>>from memory or other caches, but a design might have narrower
>>>> connections for coherence, interrupts, etc. that could be used for
>>>> small data communication.)
>>>
>>> So long as the data transfer is cachable, the atomics can be handled
>>> at the LLC, rather than the memory controller.
>>
>>Yes, but if the width of the on-chip network — which is what Mitch
>>was referring to in transferring a cache line in one cycle — is
>>c.72 bytes (64 bytes for the data and 8 bytes for control
>>information) it seems that short messages would either have to be
>>grouped (increasing latency) or waste a significant fraction of
>>the potential bandwidth for that transfer. Compressed cache lines
>>would also not save bandwidth. These may not be significant
>>considerations, but this is an answer to "why define anything
>>smaller than a cache line?", i.e., seemingly reasonable
>>motivations may exist.
>>

> It's not uncommon for the bus/switch/mesh -structure- to be 512-bits wide,
> which indeed will support a full cache line transfer in a single transaction;

It is not the transaction it is a single beat of the clock. One can have
narrower bus widths and simply divide the cache line size by the bus width
to get the number of required beats.

> it also supports high-volume DMA operations (either memory to memory or
> device to memory).

> Most of the interconnect (bus, switched or point-to-point) implementations
> have an

or more than one

> overlaying protocol (including the cache coherency
> protocol) and are effectively message based, with agents posting requests
> that don't need a reply and expecting a reply for the rest.

Many older busses read PTP and PTEs from memory sizeof( PTE ) at a time,
some of them requesting write permission so that used and modified bits
can be written back immediately.{{Which skirts the distinction between
cacheable and uncacheable in several ways.}}

> That doesn't require that every transaction over that bus to
> utilize the full width of the bus.

In my wide bus situation, the line width is used to gang up multiple
responses (from different end-points) into a single beat==message.
For example the chip-to-chip transport can carry multiple independent
SNOOP responses in a single beat (saving cycles and lowering latency).

> Since each chased pointer starts back at LSQ, the cost is no different
> than an explicit Prefetch instruction, except without (a),(b) and (c)
> having been applied first.

I thought the important difference is that the decision to prefetch or
not can be done dynamically based on past history.

Stefan