A student asked me a question that essentially reduces to: How does
Intel allocate/replace cache lines in the L3? The L3 consists of a
number of slices; e.g., on the Raptor Lake a slice has 3MB, and there
is one slice per Raptor Cove core and one per 4 Gracemont cores,
resulting in, e.g., 12 slices for a 13900.

Now if each core allocated only in its own slice, many programs would
see an effect of only 3MB of L3 cache, but Intel processors are well
documented to access all the cache even from one thread running on
only one core.

Using some pseudo-LRU replacement across the whole L3 also seems
unlikely to me (too slow and too power-expensive).

The way I would do it if I don't want to be limited to a slice is to
select some slice (maybe with a per-core round-robin scheme), and
allocate the line there (with pseudo-LRU within the slice).

How does Intel do it?

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

Anton Ertl wrote:
> A student asked me a question that essentially reduces to: How does
> Intel allocate/replace cache lines in the L3? The L3 consists of a
> number of slices; e.g., on the Raptor Lake a slice has 3MB, and there
> is one slice per Raptor Cove core and one per 4 Gracemont cores,
> resulting in, e.g., 12 slices for a 13900.
>
> Now if each core allocated only in its own slice, many programs would
> see an effect of only 3MB of L3 cache, but Intel processors are well
> documented to access all the cache even from one thread running on
> only one core.
>
> Using some pseudo-LRU replacement across the whole L3 also seems
> unlikely to me (too slow and too power-expensive).
>
> The way I would do it if I don't want to be limited to a slice is to
> select some slice (maybe with a per-core round-robin scheme), and
> allocate the line there (with pseudo-LRU within the slice).
>
> How does Intel do it?
>
> - anton

This recent article talks some about Intel L3 and its connections:

https://chipsandcheese.com/2023/08/04/sandy-bridge-setting-intels-modern-foundation/

EricP wrote:
> Anton Ertl wrote:
>> A student asked me a question that essentially reduces to: How does
>> Intel allocate/replace cache lines in the L3? The L3 consists of a
>> number of slices; e.g., on the Raptor Lake a slice has 3MB, and there
>> is one slice per Raptor Cove core and one per 4 Gracemont cores,
>> resulting in, e.g., 12 slices for a 13900.
>>
>> Now if each core allocated only in its own slice, many programs would
>> see an effect of only 3MB of L3 cache, but Intel processors are well
>> documented to access all the cache even from one thread running on
>> only one core.
>>
>> Using some pseudo-LRU replacement across the whole L3 also seems
>> unlikely to me (too slow and too power-expensive).
>>
>> The way I would do it if I don't want to be limited to a slice is to
>> select some slice (maybe with a per-core round-robin scheme), and
>> allocate the line there (with pseudo-LRU within the slice).
>>
>> How does Intel do it?
>>
>> - anton
>
> This recent article talks some about Intel L3 and its connections:
>
> https://chipsandcheese.com/2023/08/04/sandy-bridge-setting-intels-modern-foundation/

This also talks about L3 slices

Sapphire Rapids: Golden Cove Hits Servers
https://chipsandcheese.com/2023/03/12/a-peek-at-sapphire-rapids/

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>A student asked me a question that essentially reduces to: How does
>Intel allocate/replace cache lines in the L3? The L3 consists of a
>number of slices; e.g., on the Raptor Lake a slice has 3MB, and there
>is one slice per Raptor Cove core and one per 4 Gracemont cores,
>resulting in, e.g., 12 slices for a 13900.
>
>Now if each core allocated only in its own slice, many programs would
>see an effect of only 3MB of L3 cache, but Intel processors are well
>documented to access all the cache even from one thread running on
>only one core.
>
>Using some pseudo-LRU replacement across the whole L3 also seems
>unlikely to me (too slow and too power-expensive).
>
>The way I would do it if I don't want to be limited to a slice is to
>select some slice (maybe with a per-core round-robin scheme), and
>allocate the line there (with pseudo-LRU within the slice).
>
>How does Intel do it?

The probably hash the linear/physical address to select which
L3 island to route to.

On Wednesday, October 18, 2023 at 2:33:52 PM UTC-5, Scott Lurndal wrote:
> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> >A student asked me a question that essentially reduces to: How does
> >Intel allocate/replace cache lines in the L3? The L3 consists of a
> >number of slices; e.g., on the Raptor Lake a slice has 3MB, and there
> >is one slice per Raptor Cove core and one per 4 Gracemont cores,
> >resulting in, e.g., 12 slices for a 13900.
> >
> >Now if each core allocated only in its own slice, many programs would
> >see an effect of only 3MB of L3 cache, but Intel processors are well
> >documented to access all the cache even from one thread running on
> >only one core.
> >
> >Using some pseudo-LRU replacement across the whole L3 also seems
> >unlikely to me (too slow and too power-expensive).
> >
> >The way I would do it if I don't want to be limited to a slice is to
> >select some slice (maybe with a per-core round-robin scheme), and
> >allocate the line there (with pseudo-LRU within the slice).
> >
> >How does Intel do it?
> The probably hash the linear/physical address to select which
> L3 island to route to.
<
This recent article talks some about Intel L3 and its connections:
<
https://chipsandcheese.com/2023/08/04/sandy-bridge-setting-intels-modern-foundation/
<
One of the drawings shows that all the L3s are on a ring bus.

MitchAlsup wrote:
> On Wednesday, October 18, 2023 at 2:33:52 PM UTC-5, Scott Lurndal wrote:
>> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> A student asked me a question that essentially reduces to: How does
>>> Intel allocate/replace cache lines in the L3? The L3 consists of a
>>> number of slices; e.g., on the Raptor Lake a slice has 3MB, and there
>>> is one slice per Raptor Cove core and one per 4 Gracemont cores,
>>> resulting in, e.g., 12 slices for a 13900.
>>>
>>> Now if each core allocated only in its own slice, many programs would
>>> see an effect of only 3MB of L3 cache, but Intel processors are well
>>> documented to access all the cache even from one thread running on
>>> only one core.
>>>
>>> Using some pseudo-LRU replacement across the whole L3 also seems
>>> unlikely to me (too slow and too power-expensive).
>>>
>>> The way I would do it if I don't want to be limited to a slice is to
>>> select some slice (maybe with a per-core round-robin scheme), and
>>> allocate the line there (with pseudo-LRU within the slice).
>>>
>>> How does Intel do it?
>> The probably hash the linear/physical address to select which
>> L3 island to route to.
> <
> This recent article talks some about Intel L3 and its connections:
> <
> https://chipsandcheese.com/2023/08/04/sandy-bridge-setting-intels-modern-foundation/
> <
> One of the drawings shows that all the L3s are on a ring bus.

I _think_ that Intel introduced the dual counter-rotating ring bus
structure for Larrabee, to allow 60+ cores to communicate efficiently
(low latency & power)?

Terje

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

On Thursday, October 19, 2023 at 1:23:13 AM UTC-5, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Wednesday, October 18, 2023 at 2:33:52 PM UTC-5, Scott Lurndal wrote:
> >> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> >>> A student asked me a question that essentially reduces to: How does
> >>> Intel allocate/replace cache lines in the L3? The L3 consists of a
> >>> number of slices; e.g., on the Raptor Lake a slice has 3MB, and there
> >>> is one slice per Raptor Cove core and one per 4 Gracemont cores,
> >>> resulting in, e.g., 12 slices for a 13900.
> >>>
> >>> Now if each core allocated only in its own slice, many programs would
> >>> see an effect of only 3MB of L3 cache, but Intel processors are well
> >>> documented to access all the cache even from one thread running on
> >>> only one core.
> >>>
> >>> Using some pseudo-LRU replacement across the whole L3 also seems
> >>> unlikely to me (too slow and too power-expensive).
> >>>
> >>> The way I would do it if I don't want to be limited to a slice is to
> >>> select some slice (maybe with a per-core round-robin scheme), and
> >>> allocate the line there (with pseudo-LRU within the slice).
> >>>
> >>> How does Intel do it?
> >> The probably hash the linear/physical address to select which
> >> L3 island to route to.
> > <
> > This recent article talks some about Intel L3 and its connections:
> > <
> > https://chipsandcheese.com/2023/08/04/sandy-bridge-setting-intels-modern-foundation/
> > <
> > One of the drawings shows that all the L3s are on a ring bus.
> I _think_ that Intel introduced the dual counter-rotating ring bus
> structure for Larrabee, to allow 60+ cores to communicate efficiently
> (low latency & power)?
<
Larry-the-bee certainly had a ring bus.
>
> Terje
>
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

EricP <ThatWouldBeTelling@thevillage.com> writes:
>EricP wrote:
>> This recent article talks some about Intel L3 and its connections:
>>
>> https://chipsandcheese.com/2023/08/04/sandy-bridge-setting-intels-modern-foundation/
>
>This also talks about L3 slices
>
>Sapphire Rapids: Golden Cove Hits Servers
>https://chipsandcheese.com/2023/03/12/a-peek-at-sapphire-rapids/

Good stuff, yes, and I looked at it again now, but if it says anything
about L3 replacement policies, I missed it again.

- 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:
>The probably hash the linear/physical address to select which
>L3 island to route to.

The number of slices (islands) depends on the enabled cores (not sure
if that is also true of BIOS-enabled cores, but it certainly is true
of cores enabled/disabled after testing and binning), so such a hash
function would be more complex (and slower) than I would be
comfortable with.

An advantage of such an approach would be that only one slice needs to
make the actual lookup on a later access, which saves power and
increases total bandwidth.

So overall, this looks more plausible to me than my round-robin
concept.

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

Anton Ertl wrote:
> scott@slp53.sl.home (Scott Lurndal) writes:
>> The probably hash the linear/physical address to select which
>> L3 island to route to.
>
> The number of slices (islands) depends on the enabled cores (not sure
> if that is also true of BIOS-enabled cores, but it certainly is true
> of cores enabled/disabled after testing and binning), so such a hash
> function would be more complex (and slower) than I would be
> comfortable with.
>
> An advantage of such an approach would be that only one slice needs to
> make the actual lookup on a later access, which saves power and
> increases total bandwidth.
>
> So overall, this looks more plausible to me than my round-robin
> concept.

If I had to implement a fixed for the CPU but variable between bins
modulo operator for sharding, then it could be feasible to do this via a
reciprocal MUL selected during the binning process.

MUL is expensive, yeah, but L3 accesses are about 5 X more
power-intensive than a double precision FMAC, so a custom, slightly
reduced unsigned MUL must be even cheaper, right?

Terje

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

Terje Mathisen <terje.mathisen@tmsw.no> writes:
>If I had to implement a fixed for the CPU but variable between bins
>modulo operator for sharding, then it could be feasible to do this via a
>reciprocal MUL selected during the binning process.

Modulo would require division (reciprocal multiplication) followed by
a multiply and a subtraction.

The following is more effective: 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-a594-88a85ac10d20o@googlegroups.com>

On Friday, October 20, 2023 at 12:09:36 PM UTC+3, Anton Ertl wrote:
> Terje Mathisen <terje.m...@tmsw.no> writes:
> >If I had to implement a fixed for the CPU but variable between bins
> >modulo operator for sharding, then it could be feasible to do this via a
> >reciprocal MUL selected during the binning process.
> Modulo would require division (reciprocal multiplication) followed by
> a multiply and a subtraction.
>
> The following is more effective: 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?

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>scott@slp53.sl.home (Scott Lurndal) writes:
>>They probably hash the linear/physical address to select which
>>L3 island to route to.
>
>The number of slices (islands) depends on the enabled cores (not sure
>if that is also true of BIOS-enabled cores, but it certainly is true
>of cores enabled/disabled after testing and binning), so such a hash
>function would be more complex (and slower) than I would be
>comfortable with.

For binning, yes, the hash function needs to accommodate fused out islands/slices.
So does the core identifier (core number) space, such that the logical
core number is dense with no gaps.

If the hardware allows "renaming" of the remaining islands such that
they have a monotonically increasing identifier space, then the hash
function will automatically accomodate the reduced island count without
needing to handle missing islands.

Michael S <already5chosen@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].

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-a594-88a85ac10d20o@googlegroups.com>

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Michael S <already5chosen@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].

To quote one of my colleagues:

"It is well understood that the bits of a key (such as an address)
should not be used as-is to index into a cache or similar table".

One needs to give some thought to how the islands/slices themselves
are identified for routing purposes. For rings, each island has an
unique address (small integer log2(island-count)). For a mesh, each
island has an X and Y coordinate.

To support binning, there needs to be a function to map the output
of the address hash function into a destination address (ring or mesh);
which could be a simple hardware lookup table (flops or ram) programmed
by firmware or on-board microcontroller early in the boot process
before caching is enabled on the CPU.

A useful characteristic of a hash function is invertibility.

Note that the destination for an access to a physical address may
not necessarily be an L3 island, but rather to an I/O host bridge.

Anton Ertl wrote:
> EricP <ThatWouldBeTelling@thevillage.com> writes:
>> EricP wrote:
>>> This recent article talks some about Intel L3 and its connections:
>>>
>>> https://chipsandcheese.com/2023/08/04/sandy-bridge-setting-intels-modern-foundation/
>> This also talks about L3 slices
>>
>> Sapphire Rapids: Golden Cove Hits Servers
>> https://chipsandcheese.com/2023/03/12/a-peek-at-sapphire-rapids/
>
> Good stuff, yes, and I looked at it again now, but if it says anything
> about L3 replacement policies, I missed it again.
>
> - anton

Sorry, I didn't read your msg close enough.

I put 'intel "L3" cache slice' into Google Scholar and got a few hits:

https://scholar.google.com/scholar?hl=en&as_sdt=0%2C5&q=intel+%22L3%22+cache+slice&btnG=

with titles that sound like what you are looking for, such as:

Systematic reverse engineering of cache slice selection
in Intel processors, 2015
https://eprint.iacr.org/2015/690.pdf

Mapping addresses to l3/cha slices in intel processors, JD McCalpin, 2021
https://repositories.lib.utexas.edu/handle/2152/87595
https://repositories.lib.utexas.edu/bitstream/handle/2152/87595/TR-2021-03_IntelAddressHashing.pdf?sequence=45&isAllowed=y

Mapping core and L3 slice numbering to die location in
Intel Xeon Scalable processors, JD McCalpin, 2021
https://repositories.lib.utexas.edu/handle/2152/86168
https://repositories.lib.utexas.edu/bitstream/handle/2152/86168/TR-2021-01b_SKX_CLX_Die_Layout.pdf?sequence=3

scott@slp53.sl.home (Scott Lurndal) writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>To quote one of my colleagues:
>
> "It is well understood that the bits of a key (such as an address)
> should not be used as-is to index into a cache or similar table".

It's not well understood by most cache designers who have used bits of
the address to select the set. And I don't see any reason why they
should not be used. Maybe your collegue can provide a justification
for the claim rather than just a claim of well-understood-ness.

>A useful characteristic of a hash function is invertibility.

Why? Given that the result is intended to be a non-power-of-2 slice
number, and the actual physical addresses are a very small and
possibly distributed subset of the huge address space, I don't see
that you can get that characteristic even if it is useful.

>Note that the destination for an access to a physical address may
>not necessarily be an L3 island, but rather to an I/O host bridge.

Non-cacheable accesses are identified during translation, and then you
don't need to worry about which L3 slice to access.

- 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:
>>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>To quote one of my colleagues:
>>
>> "It is well understood that the bits of a key (such as an address)
>> should not be used as-is to index into a cache or similar table".
>
>It's not well understood by most cache designers who have used bits of
>the address to select the set. And I don't see any reason why they
>should not be used. Maybe your collegue can provide a justification
>for the claim rather than just a claim of well-understood-ness.

"This is due to possible imbalances in the bit statistics
and correlation between bits."

physical addresess aren't random enough to ensure balance.

Anton Ertl wrote:
> EricP <ThatWouldBeTelling@thevillage.com> writes:
>> EricP wrote:
>>> This recent article talks some about Intel L3 and its connections:
>>>
>>> https://chipsandcheese.com/2023/08/04/sandy-bridge-setting-intels-modern-foundation/
>> This also talks about L3 slices
>>
>> Sapphire Rapids: Golden Cove Hits Servers
>> https://chipsandcheese.com/2023/03/12/a-peek-at-sapphire-rapids/
>
> Good stuff, yes, and I looked at it again now, but if it says anything
> about L3 replacement policies, I missed it again.
>
> - anton

I notice that Intel has Resource Director Technology (RDT)
which also might interact with L3 allocation and access time:
- Cache Allocation Technology (CAT) can control
which cache *ways* are allocated to which cores
- Memory Bandwidth Allocation (MBA) can throttle the bandwidth
between per-core L2 cache and L3 interconnect.

A Closer Look at Intel Resource Director Technology (RDT), 2022
https://par.nsf.gov/biblio/10332455
https://par.nsf.gov/servlets/purl/10332455

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 ??

Anton Ertl wrote:
> A student asked me a question that essentially reduces to: How does
> Intel allocate/replace cache lines in the L3? The L3 consists of a
> number of slices; e.g., on the Raptor Lake a slice has 3MB, and there
> is one slice per Raptor Cove core and one per 4 Gracemont cores,
> resulting in, e.g., 12 slices for a 13900.
>
> Now if each core allocated only in its own slice, many programs would
> see an effect of only 3MB of L3 cache, but Intel processors are well
> documented to access all the cache even from one thread running on
> only one core.
>
> Using some pseudo-LRU replacement across the whole L3 also seems
> unlikely to me (too slow and too power-expensive).
>
> The way I would do it if I don't want to be limited to a slice is to
> select some slice (maybe with a per-core round-robin scheme), and
> allocate the line there (with pseudo-LRU within the slice).
>
> How does Intel do it?
>
> - anton

According to this which has two sections on Intel replacement policy:

Understanding HPC Benchmark Performance on Intel Broadwell
and Cascade Lake Processors, 2020
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7295341/pdf/978-3-030-50743-5_Chapter_21.pdf

"L3 Cache Replacement Policy
....
new Intel microarchitectures have implemented dynamic replacement policies
....
Instead of applying the same pseudo-LRU policy to all workloads,
post-SNB processors make use of a small amount of dedicated leader sets,
each of which implements a different replacement policy. During execution,
the processor constantly monitors which of the leader sets delivers the
highest hit rate, and instructs all remaining sets (also called follower
sets) to use the best-performing leader set’s replacement strategy"

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 ??

One source said it was to minimize contention.
Presumably they didn't want consecutive lines from
the same page to all come from the same source.

On Friday, October 20, 2023 at 4:13:02 PM UTC-5, EricP 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 ??
> One source said it was to minimize contention.
> Presumably they didn't want consecutive lines from
> the same page to all come from the same source.
<
Back in 2000:: optimal large-data-set memory movement minimized
page crossing (linear address sequence) and a single ACT to DRAM
could satisfy at least 4096 bytes of data, thus being faster than
spreading the ACTs across the available DRAM DIMMs; lower power,
too.
<
What has changed ??

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?

Terje

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

EricP <ThatWouldBeTelling@thevillage.com> writes:
>Systematic reverse engineering of cache slice selection
>in Intel processors, 2015
>https://eprint.iacr.org/2015/690.pdf

According to this, Intel selects the slice using a hash function that
uses PA[32:17] for Ivy Bridge and Haswell. Only power-of-two number
of slices occur in this paper. This paper discusses how to reverse
engineer this knowledge.

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.

>Mapping addresses to l3/cha slices in intel processors, JD McCalpin, 2021
>https://repositories.lib.utexas.edu/handle/2152/87595
>https://repositories.lib.utexas.edu/bitstream/handle/2152/87595/TR-2021-03_IntelAddressHashing.pdf?sequence=45&isAllowed=y

This one discusses mainly Skylake-X/Cascade Lake CPUs with various
core counts, plus an IceLake-X and a Knight's Landing. The hash
functions used here use PA[37:10]..PA[37:20] (depending on the number
of slices).

The hash function is used for determining the slice. If I understand
table 9 correctly, it is not particularly good at uniform distribution
if the number of slices is not a power of 2, with factors >1.25
between the popularity of slices for some CPUs (or, for a less
dramatic number, the most heavily allocated lines receive 1.6% to 3.7%
(KNL 7.6%) more cache lines than with a uniform distribution (the
least allocated receive significantly less than with a uniform
distribution).

I have not read through the paper completely, but it seems that the
set number is permuted based on the hash. So while in the cases of
using PA[37:20], an aligned 1MB block of physical addresses will be
allocated to the same L3 slice, the set number depends not only on the
low bits, but also on the higher bits. This may be helpful in case
where you have a lot of huge pages around of which you don't use the
end: then the parmutation helps distributing these addresses more
evenly among sets.

Thanks for finding these papers.

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