anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>EricP <ThatWouldBeTelling@thevillage.com> writes:
>>Systematic reverse engineering of cache slice selection
>>in Intel processors, 2015
>>https://eprint.iacr.org/2015/690.pdf
>
>This paper shows in Figure 2 that the set is determined without going
>through the hash function. It also shows that the set is determined
>from the lowest bits beyond the 6 bits used for addressing the byte
>within the cache line. And, as mentioned above, the has value is
>determined by higher bits. So if there is an aligned block of 128KB
>consecutive physical addresses (say, in a huge page), it will be
>allocated in the same slice. Is this good, bad, or don't care? My
>feeling is that I would prefer to distribute consecutive cache lines
>across slices.

It may be useful to consider the access pattern to the huge
page - will accesse orignate from a single thread or from mutiple threads.

In the former case, keeping them in the same slice seems reasonable.

In the latter case, distributing them amongst slices may provide
some additional concurrency.

Note that huge pages are usually used to reduce TLB pressure, not
for caching purposes. The access patterns for a huge page may
not differ significantly from those to an similarly sized region
of 4k/16k/64k pages.

I wonder if the replacement algorithms anticipate access
pattern(s) over time, i.e. prefetch ahead when the accesses
have been sequential?

On Friday, October 20, 2023 at 6:35:26 PM UTC+3, Anton Ertl wrote:
> Michael S <already...@yahoo.com> writes:
> >On Friday, October 20, 2023 at 12:09:36=E2=80=AFPM UTC+3, Anton Ertl wrote:
> >> Preliminaries: We have n sets in an
> >> L3 slice and s slices, with t=ceil(ld(s)).
> >>
> >> To compute the slice and set, n+t bits from the physical address.
> >> Multiply this number with s, giving x. The target slice then is
> >> x/2^(n+t) (which is in the range [0,n)). The target set is the bits
> >> n+t-1..t of x.
> >>
> >> This requires an (n+t)*t-bit multiplier with an n+2t-bit result, and
> >> for, e.g., Sapphire Rapids, t=6 and n=11 (assuming that each way has
> >> 128KB; with smaller ways and more associativity, n would be smaller; n
> >> cannot be larger, because 128KB is the largest power-of-2 that divides
> >> the size of an L3 slice). This multiplier size (17*6->23 bits) seems
> >> downright cheap compared to the integer (64*64->128) or FP
> >> multipliers, and, as you point out, also cheap compared to the rest of
> >> the L3 access (both in latency and in energy).
> >> - anton
> >> --
> >> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> >> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>
> >
> >When you say "physical address" do you mean PA[16:6] a.k.a. Line Index in
> >classic Nehalem-to-SkylakeClient Intel LLC? Or something else?
> I wrote "n+t bits from the physical address", which would be 17 bits
> in the example above. So yes, maybe PA[22:6].
>

I don't understand how PA[22:17] could be of help.
More so, I don't understand how they could be non-harmful.
I mean, before Skylake Server/Cascade Lake.

In Skylake Server they use Sub-NUMA Clustering (SNC) that according
to manual "can improve the average LLC/memory latency by splitting
the LLC into disjoint clusters based on address range, with each cluster
bound to a subset of memory controllers in the system."
So with SNC, assuming that selection of memory controller takes into
account higher address bits than PA[16] (but is it? I don't know) these
higher address bits necessarily influence selection of LLC slice.

> One disadvantage of this scheme AFAICS is that we need to store
> essentially the whole physical address (apart from the bottom 6 bits)
> as tag, whereas in a normal un"hashed" cache access scheme you do not
> need to store the n bits that identify the set.
>
> I can think of ways of varying the scheme to use the physical address
> rather than the "hashed" address for accessing the set, and thus
> reduce the tags by n bits (per cache line) and also reduces the
> multiplier to a t*t->2t bit multiplier. But I am not sure if this
> results in a significantly skewed distribution, which would be worse
> than expending a few more hardware resources.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Saturday, October 21, 2023 at 6:59:49 AM UTC-5, Terje Mathisen wrote:
> MitchAlsup wrote:
> > It seems to me that all the L3 chunks are on a ring bus.
> > And that getting to RingBus[mod-t] requires a trip around the ring.
> > <
> > So, why not just snoop that L3 of the ring node you are on while
> > passing from where you are to where the data is.
> > <
> > That is, no special hashing needed, get data if you run into it,
> > use snoop statistics to decide where to put it if no snoops succeed.
> > <
> > So, why are we using a hash again ??
> >
> Each node/L3 slice needs a way to determine if it should cache a
> particular line?
<
L3 closest to the originator should end up with the line.
<
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

On Saturday, October 21, 2023 at 11:06:02 AM UTC-5, Scott Lurndal wrote:
> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> >EricP <ThatWould...@thevillage.com> writes:
> >>Systematic reverse engineering of cache slice selection
> >>in Intel processors, 2015
> >>https://eprint.iacr.org/2015/690.pdf
> >
> >This paper shows in Figure 2 that the set is determined without going
> >through the hash function. It also shows that the set is determined
> >from the lowest bits beyond the 6 bits used for addressing the byte
> >within the cache line. And, as mentioned above, the has value is
> >determined by higher bits. So if there is an aligned block of 128KB
> >consecutive physical addresses (say, in a huge page), it will be
> >allocated in the same slice. Is this good, bad, or don't care? My
> >feeling is that I would prefer to distribute consecutive cache lines
> >across slices.
> It may be useful to consider the access pattern to the huge
> page - will accesse orignate from a single thread or from mutiple threads..
>
> In the former case, keeping them in the same slice seems reasonable.
>
> In the latter case, distributing them amongst slices may provide
> some additional concurrency.
<
Most huge page users (>1GB) are data bases where they use the huge page
to minimize TLB misses. But these applications have hundreds to thousands
of threads all using the same (index set) data. So, one would expect many
TLBs to contain the huge page translations, and the those pages would
be accessed fairly often but randomly across any LLC structurizing.
>
> Note that huge pages are usually used to reduce TLB pressure, not
> for caching purposes. The access patterns for a huge page may
> not differ significantly from those to an similarly sized region
> of 4k/16k/64k pages.
>
> I wonder if the replacement algorithms anticipate access
> pattern(s) over time, i.e. prefetch ahead when the accesses
> have been sequential?

MitchAlsup wrote:
> On Saturday, October 21, 2023 at 6:59:49 AM UTC-5, Terje Mathisen wrote:
>> MitchAlsup wrote:
>>> It seems to me that all the L3 chunks are on a ring bus.
>>> And that getting to RingBus[mod-t] requires a trip around the ring.
>>> <
>>> So, why not just snoop that L3 of the ring node you are on while
>>> passing from where you are to where the data is.
>>> <
>>> That is, no special hashing needed, get data if you run into it,
>>> use snoop statistics to decide where to put it if no snoops succeed.
>>> <
>>> So, why are we using a hash again ??
>>>
>> Each node/L3 slice needs a way to determine if it should cache a
>> particular line?
> <
> L3 closest to the originator should end up with the line.

I agree that this seems like the logical way to do it, but it does
require some kind of dictionary/broadcast process to allow other
cores/slices to discover that this line is already cached somewhere
else, right?

OTOH, this is already the case for all other cache levels on a
multi-core cpu, so nothing new needs to be invented, except the latency
might be too high, so making it faster (more energy-effienciet?) to
allow each core/slice to determine when to cache something?

Terje

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

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>MitchAlsup wrote:
>> L3 closest to the originator should end up with the line.
>
>I agree that this seems like the logical way to do it, but it does
>require some kind of dictionary/broadcast process to allow other
>cores/slices to discover that this line is already cached somewhere
>else, right?

Not just that. It means that a process running on one core can cache
only in the slice of that core (i.e., in 3MB on Raptor Lake), and not
make use of the other slices.

AMD does it that way with it's core complexes (CCXs): e.g., a Ryzen
1800X has two CCXs (on one die), each with 4 cores and 8MB of L3. So
despite it having 16MB of L3, measurements of pointer chasing latency
show a step-up increase in latency after 8MB. See Column 18 of
<http://www.complang.tuwien.ac.at/anton/bplat/Results>; Column 19
(Ryzen 3900X with 64GB L3, but split into 4 CCXs with 16MB L3 each)
also shows this behaviour.

- 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:
>On Friday, October 20, 2023 at 6:35:26=E2=80=AFPM UTC+3, Anton Ertl wrote:
>> Michael S <already...@yahoo.com> writes:
>> >On Friday, October 20, 2023 at 12:09:36=3DE2=3D80=3DAFPM UTC+3, Anton Er=
>tl wrote:=20
>> >> Preliminaries: We have n sets in an=20
>> >> L3 slice and s slices, with t=3Dceil(ld(s)).=20
>> >>=20
>> >> To compute the slice and set, n+t bits from the physical address.=20
>> >> Multiply this number with s, giving x. The target slice then is=20
>> >> x/2^(n+t) (which is in the range [0,n)). The target set is the bits=20
>> >> n+t-1..t of x.=20
>> >>=20
>> >> This requires an (n+t)*t-bit multiplier with an n+2t-bit result, and=
>=20
>> >> for, e.g., Sapphire Rapids, t=3D6 and n=3D11 (assuming that each way h=
>as=20
>> >> 128KB; with smaller ways and more associativity, n would be smaller; n=
>=20
>> >> cannot be larger, because 128KB is the largest power-of-2 that divides=
>=20
>> >> the size of an L3 slice). This multiplier size (17*6->23 bits) seems=
>=20
>> >> downright cheap compared to the integer (64*64->128) or FP=20
>> >> multipliers, and, as you point out, also cheap compared to the rest of=
>=20
>> >> the L3 access (both in latency and in energy).=20
....
>> >When you say "physical address" do you mean PA[16:6] a.k.a. Line Index i=
>n=20
>> >classic Nehalem-to-SkylakeClient Intel LLC? Or something else?
>> I wrote "n+t bits from the physical address", which would be 17 bits=20
>> in the example above. So yes, maybe PA[22:6].=20
>>=20
>
>I don't understand how PA[22:17] could be of help.

The idea here is that the output of the "hash function" contains n
bits for the set and (almost) t bits for the slice number. Then you
need at least n+t bits as input in order to produce all possible
output patterns. If you don't produce all possible output patterns,
only a part of the L3 cache will be utilized.

>More so, I don't understand how they could be non-harmful.

Why should they be harmful? As we found out, Intel uses PA[37:20] on
a number of processors.

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

scott@slp53.sl.home (Scott Lurndal) writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>EricP <ThatWouldBeTelling@thevillage.com> writes:
>>>Systematic reverse engineering of cache slice selection
>>>in Intel processors, 2015
>>>https://eprint.iacr.org/2015/690.pdf
>>
>>This paper shows in Figure 2 that the set is determined without going
>>through the hash function. It also shows that the set is determined
>>from the lowest bits beyond the 6 bits used for addressing the byte
>>within the cache line. And, as mentioned above, the has value is
>>determined by higher bits. So if there is an aligned block of 128KB
>>consecutive physical addresses (say, in a huge page), it will be
>>allocated in the same slice. Is this good, bad, or don't care? My
>>feeling is that I would prefer to distribute consecutive cache lines
>>across slices.
>
>It may be useful to consider the access pattern to the huge
>page - will accesse orignate from a single thread or from mutiple threads.

Often from a single thread.

>In the former case, keeping them in the same slice seems reasonable.

Why? My feeling is that by distributing the accesses of a thread
walking through memory across different slices, there would be better
load distribution. But given that Intel is keeping them clustered,
maybe there is some batching mechanism for the L3 slice accesses that
benefits from the clustering.

>Note that huge pages are usually used to reduce TLB pressure, not
>for caching purposes. The access patterns for a huge page may
>not differ significantly from those to an similarly sized region
>of 4k/16k/64k pages.

I expect that in the physical addresses, they differ significantly,
because, unless the OS does something special, there is no reason for
virtually adjacent pages to be physically adjacent.

>I wonder if the replacement algorithms anticipate access
>pattern(s) over time, i.e. prefetch ahead when the accesses
>have been sequential?

Intel and AMD (and, I expect, others) have had hardware prefetchers
for many years. It has not been discussed much in recent years, so I
guess that they are just working ok.

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

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>scott@slp53.sl.home (Scott Lurndal) writes:

>>I wonder if the replacement algorithms anticipate access
>>pattern(s) over time, i.e. prefetch ahead when the accesses
>>have been sequential?
>
>Intel and AMD (and, I expect, others) have had hardware prefetchers
>for many years. It has not been discussed much in recent years, so I
>guess that they are just working ok.

Yes, but those prefetchers work out of the per-core L2, not the LLC.

On 10/20/23 3:45 PM, MitchAlsup wrote:
> It seems to me that all the L3 chunks are on a ring bus.
> And that getting to RingBus[mod-t] requires a trip around the ring.
> <
> So, why not just snoop that L3 of the ring node you are on while
> passing from where you are to where the data is.
> <
> That is, no special hashing needed, get data if you run into it,
> use snoop statistics to decide where to put it if no snoops succeed.
> <
> So, why are we using a hash again ??

It was my understanding that the hash-based distribution
was intended to avoid snooping and support home-based
coherence (perhaps in part because (later) Itanium
implementations were directory/home-based).

This obviously provides more flexibility in network
topology (Intel moved from single ring quite some time
ago, IIRC, and I think now uses a mesh/grid topology).

While bandwidth is presumably the main constraint for
snooping (and a ring topology wastes less bandwidth
for all-to-all communication than a grid), I would
guess that the cache probing is not entirely free, so
energy costs might also bias the design choices.

Biasing placement to be closer to a "memory-side"
cache (where data sourced from adjacent memory
controllers is cached) might also have some energy
benefits with a miss having fewer network hops to
reach the memory controller and possibly having
higher bandwidth).

Biasing placement to reduce travel time and energy
to the most likely next user would make sense and
biasing might also be able to help snoop filters
work more effectively.

The tradeoffs seem complex, interacting with workload,
capacity, network topology, memory latency, memory
bandwidth, and other factors (e.g., consistency model?).

One could also bias associativity such that some
snoops would have to check fewer ways. With overlaid
skewed associativity, one could have lower associativity
yet still allow utilization of the entire capacity. One
might also be able to bias physical placement of tags
to reduce average energy use and/or average latency for
expected/common use patterns. (With cuckoo/elbow caching
limiting some addresses to fewer ways may not have that
much effect on miss rate.)

On Sunday, October 22, 2023 at 6:17:32 PM UTC+3, Anton Ertl wrote:
> Michael S <already...@yahoo.com> writes:
> >On Friday, October 20, 2023 at 6:35:26=E2=80=AFPM UTC+3, Anton Ertl wrote:
> >> Michael S <already...@yahoo.com> writes:
> >> >On Friday, October 20, 2023 at 12:09:36=3DE2=3D80=3DAFPM UTC+3, Anton Er=
> >tl wrote:=20
> >> >> Preliminaries: We have n sets in an=20
> >> >> L3 slice and s slices, with t=3Dceil(ld(s)).=20
> >> >>=20
> >> >> To compute the slice and set, n+t bits from the physical address.=20
> >> >> Multiply this number with s, giving x. The target slice then is=20
> >> >> x/2^(n+t) (which is in the range [0,n)). The target set is the bits=20
> >> >> n+t-1..t of x.=20
> >> >>=20
> >> >> This requires an (n+t)*t-bit multiplier with an n+2t-bit result, and=
> >=20
> >> >> for, e.g., Sapphire Rapids, t=3D6 and n=3D11 (assuming that each way h=
> >as=20
> >> >> 128KB; with smaller ways and more associativity, n would be smaller; n=
> >=20
> >> >> cannot be larger, because 128KB is the largest power-of-2 that divides=
> >=20
> >> >> the size of an L3 slice). This multiplier size (17*6->23 bits) seems=
> >=20
> >> >> downright cheap compared to the integer (64*64->128) or FP=20
> >> >> multipliers, and, as you point out, also cheap compared to the rest of=
> >=20
> >> >> the L3 access (both in latency and in energy).=20
> ...
> >> >When you say "physical address" do you mean PA[16:6] a.k.a. Line Index i=
> >n=20
> >> >classic Nehalem-to-SkylakeClient Intel LLC? Or something else?
> >> I wrote "n+t bits from the physical address", which would be 17 bits=20
> >> in the example above. So yes, maybe PA[22:6].=20
> >>=20
> >
> >I don't understand how PA[22:17] could be of help.
> The idea here is that the output of the "hash function" contains n
> bits for the set and (almost) t bits for the slice number. Then you
> need at least n+t bits as input in order to produce all possible
> output patterns. If you don't produce all possible output patterns,
> only a part of the L3 cache will be utilized.
> >More so, I don't understand how they could be non-harmful.
> Why should they be harmful? As we found out, Intel uses PA[37:20] on
> a number of processors.
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

After re-reading David Kantor's Sandy Bridge article
(https://www.realworldtech.com/sandy-bridge/8/) I realized that
"classic" Intel cache works very differently from what I imagined.
Somehow I was thinking that there were 2048 sets with 64 ways
in each set. Now I am starting to understand that there are only
16 ways. I still didn't get it completely.
So please ignore everything that I said in couple of previous posts.

MitchAlsup wrote:
> It seems to me that all the L3 chunks are on a ring bus.
> And that getting to RingBus[mod-t] requires a trip around the ring.
> <
> So, why not just snoop that L3 of the ring node you are on while
> passing from where you are to where the data is.
> <
> That is, no special hashing needed, get data if you run into it,
> use snoop statistics to decide where to put it if no snoops succeed.
> <
> So, why are we using a hash again ??

Just guessing... because it is the easiest way to evenly distribute a
variable number and size of shared L3 caches to a variable amount of DRAM.
It allows the logical topology to adapt to different physical topologies.

Each tile has a core, private L1 and L2 cache, and shared L3.
The size of L3 is model dependent and not necessarily a round binary power.
(Also prior L3 was non-inclusive for L1,L2.
Newer L3 is exclusive, L2 victim cache only.)

The number of tiles per chip is model dependent
and not necessarily a round binary power.

The chip tiles are in a 2D grid connected by
vertical and horizontal ring buses.

There are two Memory Controllers each with 3 channels.
There is a variable amount of DRAM connected to each channel.
One MC is physically located on the left chip side, one on the right size.

So it needs to take that #tiles * size L3 cache and distribute it across
the amount of dram discovered at boot, in such a manner that contention
on the ring bus grid is minimized. And do so for a range of applications
with various vectors, matrices, strides and/or sparse accesses.

A strict physical range assignment of dram to tile could bottleneck on
particular tiles for certain applications. And there would still be the
problem of how to evenly allocate the L3 lines to cover the assigned
physical dram range.

A hash fits the bill. The difficulty is coming up with a hash function
that does this cheaply.