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

[Jianyong Wu]

Hi Peter,

> -----Original Message-----
> From: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
> Sent: Monday, August 31, 2026 7:50 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 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
> 
> 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
> 
> 

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.

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

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

Thanks
Jianyong

> Anyway, let me continue trying to dig through all this.