RE: [RFC PATCH v2 02/23] sched/topology: Introduce a NUMA distance matrix with unique distance values

[Jianyong Wu]

Hi Tim,

Thanks for your suggestion.

> -----Original Message-----
> From: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
> Sent: Wednesday, September 23, 2026 2:39 AM
> To: Peter Zijlstra <peterz@xxxxxxxxxxxxx>; Jianyong Wu
> <wujianyong@xxxxxxxx>
> Cc: Ingo Molnar <mingo@xxxxxxxxxx>; Juri Lelli <juri.lelli@xxxxxxxxxx>;
> Vincent Guittot <vincent.guittot@xxxxxxxxxx>; Chen Yu
> <yu.c.chen@xxxxxxxxx>; Dietmar Eggemann
> <dietmar.eggemann@xxxxxxx>; Steven Rostedt <rostedt@xxxxxxxxxxx>;
> Ben Segall <bsegall@xxxxxxxxxx>; Mel Gorman <mgorman@xxxxxxx>;
> Valentin Schneider <vschneid@xxxxxxxxxx>; K Prateek Nayak
> <kprateek.nayak@xxxxxxx>; Shrikanth Hegde <sshegde@xxxxxxxxxxxxx>;
> Phil Auld <pauld@xxxxxxxxxx>; Andrew Morton
> <akpm@xxxxxxxxxxxxxxxxxxxx>; David Hildenbrand <david@xxxxxxxxxx>;
> linux-kernel@xxxxxxxxxxxxxxx; linux-mm@xxxxxxxxx;
> jianyong.wu@xxxxxxxxxxx; Yuan Zhong <zhongyuan@xxxxxxxx>; Huangsj
> <huangsj@xxxxxxxx>; Fengyu Wang <wangfengyu@xxxxxxxx>; Zhiwei Ying
> <yingzhiwei@xxxxxxxx>; justin.he@xxxxxxx
> Subject: Re: [RFC PATCH v2 02/23] sched/topology: Introduce a NUMA
> distance matrix with unique distance values
> 
> On Mon, 2026-08-31 at 13:50 +0200, Peter Zijlstra wrote:
> > On Thu, Aug 27, 2026 at 08:27:55PM +0800, Jianyong Wu wrote:
> > > Builds a refined node distance matrix based on the raw NUMA distance
> matrix
> > > provided by BIOS. The refined matrix preserves the relative ordering of
> > > NUMA distances, while assigning distinct distance values to node pairs
> that
> > > originally shared identical distances within each matrix row. This matrix
> > > is exclusively used for cache-aware scheduling and has no impact on
> existing
> > > NUMA topology logic such as sched domain construction.
> > >
> > > For example, consider a system with 4 NUMA nodes. The raw
> BIOS-provided
> > > distance matrix may look like this:
> > >
> > >         NODE0  NODE1  NODE2  NODE3
> > > NODE0   10     20     20     30
> > > NODE1   20     10     20     25
> > > NODE2   20     20     10     20
> > > NODE3   30     25     20     10
> > >
> > > Multiple duplicate distance values exist within each row. After the
> > > deduplication step, the refined distance matrix becomes:
> > >
> > >         NODE0  NODE1  NODE2  NODE3
> > > NODE0   10     15     20     30
> > > NODE1   15     10     12     25
> > > NODE2   20     12     10     15
> > > NODE3   30     25     15     10
> > >
> > > All entries in each row are now unique, while adhering to two core
> principles:
> > > 1. The relative distance ordering from the original matrix is preserved.
> > >    For instance, original distance(NODE0, NODE1) < distance(NODE0,
> NODE3),
> > >    and this relative relationship is retained in the refined matrix as
> well.
> > > 2. The matrix remains symmetric across its main diagonal. Maintaining
> > >    symmetry is critical to guarantee consistent pairwise node
> distances.
> >
> > This example uses Node only, but the code in question is specifically
> > aimed at Cache granularity; might it be better to use a cache example?
> >
> > A little something like so (I got tired of prompting Gemini to generate
> > more complicates / less broken examples)...
> >
> > Pre:
> >
> > Cache |  C0   C1 |  C2   C3 |  C4   C5 |  C6   C7
> > ------+----------+----------+----------+---------
> >   C0  |  10   10 |  20   20 |  20   20 |  20   20
> >   C1  |  10   10 |  20   20 |  20   20 |  20   20
> > ------+----------+----------+----------+---------
> >   C2  |  20   20 |  10   10 |  20   20 |  20   20
> >   C3  |  20   20 |  10   10 |  20   20 |  20   20
> > ------+----------+----------+----------+---------
> >   C4  |  20   20 |  20   20 |  10   10 |  20   20
> >   C5  |  20   20 |  20   20 |  10   10 |  20   20
> > ------+----------+----------+----------+---------
> >   C6  |  20   20 |  20   20 |  20   20 |  10   10
> >   C7  |  20   20 |  20   20 |  20   20 |  10   10
> 
> I think what we really want is an ordering of caches within
> the same NUMA node.  So when one cache is full, we can
> pick the next one down the list.  That is essentially the
> net effect of the distance de-duplication.

The goal of this series is to provide a system-wide LLC affinity
ordering, rather than only an ordering of the LLCs within one NUMA node.

Maintaining one large system-wide LLC ordering would be expensive, so
the ordering is represented hierarchically: a NUMA-node-level affinity
ordering, followed by an LLC-level ordering within each node.  This
patch only deals with the NUMA-node-level part.

> 
> So how about introduce a llc_next array.  We will initialize
> the array such that it will return the next LLC in
> the NUMA node.  So for the example that Peter has above,
> assuming C0 maps to LLC id 0, C1 maps to 1, etc.
> then llc_next is
> 
> 	    c0 c1 c2 c3 c4 c5 c6 c7
> llc_next = [1  0  3  2  5  4  7  6]
> 
> When we come back to the orginal LLC we start off with,
> we know that it is time to move on to a LLC in next closest
> NUMA node.
>
How should the next closest NUMA node be selected when multiple nodes
have the same distance from the current node?

That is the ambiguity this patch is intended to resolve. For each
source node, it disambiguates equal NUMA distances and produces a
unique node-level affinity ordering. An llc_next array can describe
the traversal of LLCs within a node, but it does not determine which
equidistant NUMA node should be visited next.

> This will be storage efficient and more straight forward
> to use than maintaining an artificial cache distance matrix.
> 
> I dislike the artificial distance matrix also for the
> reason that there is no guarantee that there are enough
> available distance slots between two nodes.  Say if I
> start with
> 
>         NODE0  NODE1  NODE2  NODE3
> NODE0   10     20     20     30
> NODE1   20     10     20     25
> NODE2   20     20     10     20
> NODE3   30     25     20     10
> 
> and there are 16 LLCs in NODE 1, I will run
> out of slots when I try to deduplicate as
> only 10 slots are available to fit 16 LLCs.
>

There is no system-wide LLC distance matrix in this series. The
de-duplication is applied only to the NUMA-node distance matrix.
Consequently, the number of LLCs in NODE1 does not affect the number
of distance values required by this patch.

The algorithm also takes the available distance space into account
when assigning the refined node distances. It does not simply insert
one value for each duplicate into the existing gap between two
original distance levels. The distance values are adjusted as
necessary to reserve enough space before the duplicates are assigned.
Therefore, the algorithm cannot run out of available distance values,
regardless of the number of nodes sharing the same original distance.

In addition to providing the node-level component of the LLC affinity
ordering, the refined node distances are used to calculate the
affinity improvement score when selecting a source scheduling group
or runqueue during load balancing. Please see patch 12 for that usage.

Thanks
Jianyong

> Tim
> 
> >
> > Post:
> >
> > Cache |  C0   C1 |  C2   C3 |  C4   C5 |  C6   C7
> > ------+----------+----------+----------+---------
> >   C0  |  10   11 |  20   21 |  22   23 |  24   25
> >   C1  |  11   10 |  21   20 |  23   22 |  25   24
> > ------+----------+----------+----------+---------
> >   C2  |  20   21 |  10   11 |  24   25 |  22   23
> >   C3  |  21   20 |  11   10 |  25   24 |  23   22
> > ------+----------+----------+----------+---------
> >   C4  |  22   23 |  24   25 |  10   11 |  20   21
> >   C5  |  23   22 |  25   24 |  11   10 |  21   20
> > ------+----------+----------+----------+---------
> >   C6  |  24   25 |  22   23 |  20   21 |  10   11
> >   C7  |  25   24 |  23   22 |  21   20 |  11   10
> >
> >
> > > Each row of this refined NUMA distance matrix is sorted in ascending
> order to
> > > generate a unique per-node affinity sequence. This sequence will guide
> > > thread migration logic introduced in subsequent patches.
> >
> > IIRC greedy has significant worse bounds than many other schemes. This
> > would result in more unique distances than strictly needed here, right?
> >
> > Since this is all on slow paths anyway, does it make sense to pick a
> > slightly better algorithm in order to reduce this bound and get better
> > results?
> >
> > Anyway, let me continue trying to dig through all this.