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

[Jianyong Wu]

Hi Tim,

> -----Original Message-----
> From: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
> Sent: Thursday, September 24, 2026 2:29 AM
> To: Jianyong Wu <wujianyong@xxxxxxxx>; Peter Zijlstra
> <peterz@xxxxxxxxxxxxx>
> 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 Wed, 2026-09-23 at 03:14 +0000, Jianyong Wu wrote:
> 
> [snip]
> 
> > > >
> > >
> > > 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?
> 
> You could use some other means like node id or load in the node
> if there's a tie in distance.
> 
> >
> > 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.
> >
> 
> Agreed that llc_next only covers intra-node traversal and that you still
> need an inter-node order for the equidistant case. But I think
> sorting each source node's row by (distance, node_id)
> already gives a stable total order; the node id breaks the tie. You can
> also break it by node load if you'd rather balance than pin. Either way
> no new distance value has to be invented.
> 

Yes, using (distance, node_id) pairs is a straightforward way to order nodes,
similar to the memory zonelist fallback node sequence. I once considered
adopting this approach, but dropped the idea after realizing it lacks
symmetry. For instance, node_affinity_distance(A, B) is not guaranteed to equal
node_affinity_distance(B, A).

The dedup algorithm can enforce this symmetry property for the resulting
node‑distance matrix.

> > > 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.
> >
> 
> Fair - you're right that the dedup is node-granularity, so my 16-LLC
> example doesn't apply as I stated it, and I'll drop that objection. It's
> moot anyway under the argument below: if the ordering uses raw distance
> plus a tie-break, and the score uses raw distance, then there's no matrix
> to pack in the first place and the "enough slots" question disappears.
> 
> > 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.
> 
> This affinity computation is where I think the dedup actually hurts rather
> than
> helps. The score in patch 12 is
> 
>     Di = dist(src_node, i) - dist(dst_node, i)   (kept only if Di > 0)
>     p  = sum_i  numa_counts[i] * clamp(Di, 4, 1024)
> 
> so it reads the distance *magnitude*, not just the order. Feeding it the
> refined values manufactures gains on exactly the node pairs the dedup
> perturbed - the equidistant ones. Using your node matrices:
> 
>     raw:                          refined:
>           N0  N1  N2  N3                 N0  N1  N2  N3
>     N0    10  20  20  30           N0    10  15  20  30
>     N1    20  10  20  25           N1    15  10  12  25
>     N2    20  20  10  20           N2    20  12  10  15
>     N3    30  25  20  10           N3    30  25  15  10
> 
> Scenario A - a locality-neutral pull gets a fabricated gain.
> Dest CPU on N1, source rq on N0, 5 tasks preferring N2:
> 
>                   dist(N0,N2)  dist(N1,N2)  Di   contribution
>     raw           20           20            0   5 * 0 =  0
>     refined       20           12            8   5 * 8 = 40
> 
> N0 and N1 are physically equidistant from N2 (both 20), so pulling those
> tasks to N1 buys zero locality - raw correctly gives 0. Refined scores it
> 40 and the balancer may drag all 5 over chasing a gain that isn't there.
> 
> Scenario B - two physically identical options get fake-ranked. Dest on
> N1; candidate sources N0 and N3, each holding only N2-preferring tasks:
> 
>                   raw Di   refined Di   after clamp(.,4,1024)
>     X (N0)        20-20=0  20-12=8      8
>     Y (N3)        20-20=0  15-12=3      4
> 
> Raw Di says both are 0, i.e. locality-equivalent, and load should decide.
> Refined ranks X over Y purely from invented deltas - and the clamp floor
> even promotes Y's fabricated 3 up to 4.
> 
> Note the dedup only ever perturbs ties, so the skew is confined to
> equidistant pairs - which is exactly the case where there is no real
> locality difference and load should have been the tiebreaker.
> 

My intention is to distinguish equal node distances and give a definitely
task move direction. 
What we want to do is aggregate task to as small area as possible. If N2 is
Preferred node, and N2 is saturate, N1 is the next node of N2 in the
affinity node order, it's natural that prefer N1 than N0 for task aggregation,
right? Thus, we should give weight for task in N0. So N0 is more likely to be
chosen and migrate task to N1. Consequently, the task can more likely
aggregate to N1 and not evenly spread in the two nodes.
 
Also, give a preference between N0 and N1 can limit the task migration from
N1 to N0. By this way, we can achieve the goal that keep tasks inside N1.

> Stepping back, the matrix is being asked to do two jobs at once:
> 
>     - ordering: only needs a deterministic total order, which
>       raw distance + node-id tie-break already provides;
>     - scoring: wants true magnitudes, which raw distance also provides
>       (equidistant => Di = 0).
> 
> The dedup is only necessary if one matrix has to serve both - and that
> coupling is precisely what injects the fake Di. So if you need a node
> ordering, I'd use the unaltered distance and break ties by some other
> means (node id, or load), and feed the score the raw distance too.
> 

Yes, the refined node distance serves both purposes mentioned above. Hence,
dedup is necessary for this patch series.

Both affinity‑score calculation and migration control rely on a consistent
refined node distance matrix. To keep this consistent, we should avoid using
the default node distance for one objective while adopting a different
variant for another purpose.

The only open design question is whether symmetric node distances are
strictly required. Symmetry is preferable but adds implementation
complexity, so this represents a trade‑off. If symmetry is unnecessary,
I can construct the node order following your approach using the
(node_distance, node_id) pair, which is significantly simpler than my
current implementation.

Your question touches on the trickiest part of this patch series. I'm
not sure I've answered your question clearly, though this discussion
has prompted further thinking from me. Thanks Tim.

Jianyong

> Tim
> 
> >
> > Thanks
> > Jianyong
> 
>