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

[Tim Chen]

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.  

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

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. 

Tim

> 
> Thanks
> Jianyong