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

[Jianyong Wu]

> -----Original Message-----
> From: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
> Sent: Tuesday, September 1, 2026 3:13 PM
> To: 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>; Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>; 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 Tue, Sep 01, 2026 at 06:57:43AM +0000, Jianyong Wu wrote:
> 
> > > 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)...
> 
> > Originally I tried to use a single big LLC distance matrix. But once I
> > realized how much memory and computation time it would cost, e.g.
> when
> > calculating affinity scores in later patches. I dropped it in favor of
> > a two-level scheme: the first is a NUMA node distance matrix, and the
> > second is an intra-node LLC matrix that only encodes the LLC distances
> > inside a single node, so it is very small. This way, both memory and
> > time are greatly reduced.
> 
> See, that would've made good Changelog material :-) But yeah, fair
> enough, the matrix will get rather big I suppose. And going to
> triangular matrix storage will only save half, while you still scale by
> n^2, so that's not going to help.

Right, I'll fold this into the commit message. And agreed on the triangular layout - it halves
the storage but stays O(n^2), so it doesn't really change the picture.

> 
> > > > 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?
> > >
> > Yes, Greedy edge-coloring is simple but can't guarantee to get the
> > optimal result in theory.
> 
> Right, so the theoretical count is :delta: or :delta:+1, but the greedy
> bound is 2:delta:+1. But IIRC (and I really am not well versed in this
> particular area) there are algorithms that are still relatively easy to
> implement and get better bounds.
> 
> I just asked Gemini (so take with a big pinch of salt and consult your
> algorithm book) there are simple algorithms such as Eulerian paths, that
> exploit topological constraints, such as hypercubes or 2d meshes, to
> still reach :delta:.
> 
Thanks for the pointer. I'll look into Eulerian path based coloring and check
whether the per-tier subgraphs in our topology are regular enough (hypercube/mesh-like)
for it to reach delta. If so, that should let me tighten the bound without much extra complexity.

> > > 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?
> > >
> > This matrix currently has two consumers:
> > 1. it is sorted to build a unique per-node affinity sequence;
> > 2. its values are used to calculate the affinity gain in patch 12.
> >
> > Therefore, when changing the de-duplication algorithm, I need to
> > consider the requirements of both Consumers, For the first use, any
> > symmetric matrix with no duplicate entries in a row is sufficient. For
> > the second use, however, the actual values and their differences may
> > affect the affinity score.
> >
> > It is not yet clear whether using a more optimal algorithm would
> > provide any real benefit for these consumers. I will investigate
> > whether a tighter matrix can be generated without introducing too much
> > complexity, and then decide which algorithm is more appropriate.
> 
> Right, fair enough. I'll continue trying to digest the series.

Thanks, appreciate the thorough review.

Thanks
Jianyong