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

[Peter Zijlstra]

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.

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

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