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

[Tim Chen]

On Thu, 2026-09-24 at 05:41 +0000, Jianyong Wu wrote:
> 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. 
> 

Ordering symmetry can be resolved by looking at (distance, abs(node_id_i - node_id_j)).

> For instance, node_affinity_distance(A, B) is not guaranteed to equal
> node_affinity_distance(B, A).

node distance is symmetric if you don't modify it.

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

I think you should get true affinity metric based on real distance. Bias based on node
property can be applied separately and a easily controlled manner.  That has the advantage
of setting the bias based on factors like load or others.

It is a bad design to have to tune a hacked up
distance to change the bias.  It is hard to control
the magnitude of the bias and use a similar and consistent
bias with the current approach. The distance you inject to
disambiguate is not the same from node to node.

>  
> 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 think the design can be much simplified if you don't have to invent a new
distance matrix.

Thanks.

Tim

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