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 11:46 PM
> 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 Thu, 2026-09-24 at 05:41 +0000, Jianyong Wu wrote:
> > >
> > > On Wed, 2026-09-23 at 03:14 +0000, Jianyong Wu wrote:
> > >
> > > [snip]
> > >
> > > > > >
> > > > >
> > > > 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.
> 

OK, So, What about using a triple (distance, abs(node_id_i - node_id_j), min(i, j))
to rank node-affinity sequences? The third component is what makes it a total
order - given the distance, the gap and the smaller node id, the pair is
determined - so it guarantees deduplication and symmetry without inventing any
new distance value.

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

Makes sense. So, what about the following solution? 
Given a node affinity sequence, a move from src to dst improves the
affinity of every task whose preferred node i ranks dst better than src. The score
is then

Di = raw_dist(src, i) - raw_dist(dst, i)
affinity_bias_i = position of src minus position of dst in node i's affinity
             sequence, counted among the nodes at the same distance from
             i (zero when Di is not zero)
p = sum_i {numa_counts[i] * (Di + affinity_bias_i)}, kept only if (Di + affinity_bias_i) > 0

When raw_dist(src, i) equals raw_dist(dst, i), Di is zero and the candidate is
selected purely by the affinity bias.

I would rather keep it fixed than let load decide. Load changes between passes,
so the choice can flip and the same tasks can be pulled back - not every time, but
it is the direction the aggregation is fighting against. At the node level,
equidistant nodes are indistinguishable to the metric, so the order between them is
a convention in any case; I would just rather it be a fixed one.

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

OK, let me try to remove this artificial node distance.

Thanks
Jianyong