Skip to contentSkip to conversation

Adjust NUMA imbalance for multiple LLCs

PATCH Superseded Mel Gorman 5 participants 16 messages Dec 1, 2021 – Dec 9, 2021 Scheduler

v3 of 6 Superseded Latest is v6 →

lore
Share & tools
lore

Mel Gorman

author
#0 lore raw

v3 cover Adjust NUMA imbalance for multiple LLCs

Commit 7d2b5dd0bcc4 ("sched/numa: Allow a floating imbalance between NUMA nodes") allowed an imbalance between NUMA nodes such that communicating tasks would not be pulled apart by the load balancer. This works fine when there is a 1:1 relationship between LLC and node but can be suboptimal for multiple LLCs if independent tasks prematurely use CPUs sharing cache.

The series addresses two problems -- inconsistent use of scheduler domain weights and sub-optimal performance when there are many LLCs per NUMA node.

Signature · 1 line
2.31.1
author
#1 lore raw

PATCH v3 1/2 sched/fair: Use weight of SD_NUMA domain in find_busiest_group

find_busiest_group uses the child domain's group weight instead of the sched_domain's weight that has SD_NUMA set when calculating the allowed imbalance between NUMA nodes. This is wrong and inconsistent with find_idlest_group.

This patch uses the SD_NUMA weight in both.

Fixes c4e8f691d926 ("sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCS")
---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
index 6e476f6d9435..0a969affca76 100644
@@ -9397,7 +9397,7 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 		/* Consider allowing a small imbalance between NUMA groups */
 		if (env->sd->flags & SD_NUMA) {
 			env->imbalance = adjust_numa_imbalance(env->imbalance,
-				busiest->sum_nr_running, busiest->group_weight);
+				busiest->sum_nr_running, env->sd->span_weight);
 		}
 
 		return;
Signature · 1 line
2.31.1
author
#5 lore raw

PATCH v3 2/2 sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

In reply to Mel Gorman

Commit 7d2b5dd0bcc4 ("sched/numa: Allow a floating imbalance between NUMA nodes") allowed an imbalance between NUMA nodes such that communicating tasks would not be pulled apart by the load balancer. This works fine when there is a 1:1 relationship between LLC and node but can be suboptimal for multiple LLCs if independent tasks prematurely use CPUs sharing cache.

Zen* has multiple LLCs per node with local memory channels and due to the allowed imbalance, it's far harder to tune some workloads to run optimally than it is on hardware that has 1 LLC per node. This patch adjusts the imbalance on multi-LLC machines to allow an imbalance up to the point where LLCs should be balanced between nodes.

On a Zen3 machine running STREAM parallelised with OMP to have on instance per LLC the results and without binding, the results are

                            5.16.0-rc1             5.16.0-rc1
                               vanilla     sched-numaimb-v3r1
MB/sec copy-16    166712.18 (   0.00%)   587662.60 ( 252.50%)
MB/sec scale-16   140109.66 (   0.00%)   393528.14 ( 180.87%)
MB/sec add-16     160791.18 (   0.00%)   618622.00 ( 284.74%)
MB/sec triad-16   160043.84 (   0.00%)   589188.40 ( 268.14%)

STREAM can use directives to force the spread if the OpenMP is new enough but that doesn't help if an application uses threads and it's not known in advance how many threads will be created.

Coremark is a CPU and cache intensive benchmark parallelised with threads. When running with 1 thread per instance, the vanilla kernel allows threads to contend on cache. With the patch;

                               5.16.0-rc1             5.16.0-rc1
                                  vanilla     sched-numaimb-v3r1
Min       Score-16   367816.09 (   0.00%)   403429.15 (   9.68%)
Hmean     Score-16   389627.78 (   0.00%)   451015.49 *  15.76%*
Max       Score-16   416178.96 (   0.00%)   480012.00 (  15.34%)
Stddev    Score-16    17361.82 (   0.00%)    32378.08 ( -86.49%)
CoeffVar  Score-16        4.45 (   0.00%)        7.14 ( -60.57%)

It can also make a big difference for semi-realistic workloads like specjbb which can execute arbitrary numbers of threads without advance knowledge of how they should be placed

                               5.16.0-rc1             5.16.0-rc1
                                  vanilla     sched-numaimb-v3r1
Hmean     tput-1      73743.05 (   0.00%)    70258.27 *  -4.73%*
Hmean     tput-8     563036.51 (   0.00%)   591187.39 (   5.00%)
Hmean     tput-16   1016590.61 (   0.00%)  1032311.78 (   1.55%)
Hmean     tput-24   1418558.41 (   0.00%)  1424005.80 (   0.38%)
Hmean     tput-32   1608794.22 (   0.00%)  1907855.80 *  18.59%*
Hmean     tput-40   1761338.13 (   0.00%)  2108162.23 *  19.69%*
Hmean     tput-48   2290646.54 (   0.00%)  2214383.47 (  -3.33%)
Hmean     tput-56   2463345.12 (   0.00%)  2780216.58 *  12.86%*
Hmean     tput-64   2650213.53 (   0.00%)  2598196.66 (  -1.96%)
Hmean     tput-72   2497253.28 (   0.00%)  2998882.47 *  20.09%*
Hmean     tput-80   2820786.72 (   0.00%)  2951655.27 (   4.64%)
Hmean     tput-88   2813541.68 (   0.00%)  3045450.86 *   8.24%*
Hmean     tput-96   2604158.67 (   0.00%)  3035311.91 *  16.56%*
Hmean     tput-104  2713810.62 (   0.00%)  2984270.04 (   9.97%)
Hmean     tput-112  2558425.37 (   0.00%)  2894737.46 *  13.15%*
Hmean     tput-120  2611434.93 (   0.00%)  2781661.01 (   6.52%)
Hmean     tput-128  2706103.22 (   0.00%)  2811447.85 (   3.89%)
---
 include/linux/sched/topology.h |  1 +
 kernel/sched/fair.c            | 26 +++++++++++++++-----------
 kernel/sched/topology.c        | 20 ++++++++++++++++++++
 3 files changed, 36 insertions(+), 11 deletions(-)
include/linux/sched/topology.h +1 -0
index c07bfa2d80f2..54f5207154d3 100644
@@ -93,6 +93,7 @@ struct sched_domain {
 	unsigned int busy_factor;	/* less balancing by factor if busy */
 	unsigned int imbalance_pct;	/* No balance until over watermark */
 	unsigned int cache_nice_tries;	/* Leave cache hot tasks for # tries */
+	unsigned int imb_numa_nr;	/* Nr imbalanced tasks allowed between nodes */
 
 	int nohz_idle;			/* NOHZ IDLE status */
 	int flags;			/* See SD_* */
kernel/sched/fair.c +15 -11
index 0a969affca76..64f211879e43 100644
@@ -1489,6 +1489,7 @@ struct task_numa_env {
 
 	int src_cpu, src_nid;
 	int dst_cpu, dst_nid;
+	int imb_numa_nr;
 
 	struct numa_stats src_stats, dst_stats;
 
@@ -1885,7 +1886,7 @@ static void task_numa_find_cpu(struct task_numa_env *env,
 		dst_running = env->dst_stats.nr_running + 1;
 		imbalance = max(0, dst_running - src_running);
 		imbalance = adjust_numa_imbalance(imbalance, dst_running,
-							env->dst_stats.weight);
+						  env->imb_numa_nr);
 
 		/* Use idle CPU if there is no imbalance */
 		if (!imbalance) {
@@ -1950,8 +1951,10 @@ static int task_numa_migrate(struct task_struct *p)
 	 */
 	rcu_read_lock();
 	sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
-	if (sd)
+	if (sd) {
 		env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
+		env.imb_numa_nr = sd->imb_numa_nr;
+	}
 	rcu_read_unlock();
 
 	/*
@@ -9046,13 +9049,14 @@ static bool update_pick_idlest(struct sched_group *idlest,
 }
 
 /*
- * Allow a NUMA imbalance if busy CPUs is less than 25% of the domain.
- * This is an approximation as the number of running tasks may not be
- * related to the number of busy CPUs due to sched_setaffinity.
+ * Allow a NUMA imbalance if busy CPUs is less than the allowed
+ * imbalance. This is an approximation as the number of running
+ * tasks may not be related to the number of busy CPUs due to
+ * sched_setaffinity.
  */
-static inline bool allow_numa_imbalance(int dst_running, int dst_weight)
+static inline bool allow_numa_imbalance(int dst_running, int imb_numa_nr)
 {
-	return (dst_running < (dst_weight >> 2));
+	return dst_running < imb_numa_nr;
 }
 
 /*
@@ -9191,7 +9195,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)
 			 * a real need of migration, periodic load balance will
 			 * take care of it.
 			 */
-			if (allow_numa_imbalance(local_sgs.sum_nr_running, sd->span_weight))
+			if (allow_numa_imbalance(local_sgs.sum_nr_running, sd->imb_numa_nr))
 				return NULL;
 		}
 
@@ -9283,9 +9287,9 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 #define NUMA_IMBALANCE_MIN 2
 
 static inline long adjust_numa_imbalance(int imbalance,
-				int dst_running, int dst_weight)
+				int dst_running, int imb_numa_nr)
 {
-	if (!allow_numa_imbalance(dst_running, dst_weight))
+	if (!allow_numa_imbalance(dst_running, imb_numa_nr))
 		return imbalance;
 
 	/*
@@ -9397,7 +9401,7 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 		/* Consider allowing a small imbalance between NUMA groups */
 		if (env->sd->flags & SD_NUMA) {
 			env->imbalance = adjust_numa_imbalance(env->imbalance,
-				busiest->sum_nr_running, env->sd->span_weight);
+				busiest->sum_nr_running, env->sd->imb_numa_nr);
 		}
 
 		return;
kernel/sched/topology.c +20 -0
index d201a7052a29..fee2930745ab 100644
@@ -2242,6 +2242,26 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
 		}
 	}
 
+	/* Calculate allowed NUMA imbalance */
+	for_each_cpu(i, cpu_map) {
+		int imb_numa_nr = 0;
+
+		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+			struct sched_domain *child = sd->child;
+
+			if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&
+			    (child->flags & SD_SHARE_PKG_RESOURCES)) {
+				int nr_groups;
+
+				nr_groups = sd->span_weight / child->span_weight;
+				imb_numa_nr = max(1U, ((child->span_weight) >> 1) /
+						(nr_groups * num_online_nodes()));
+			}
+
+			sd->imb_numa_nr = imb_numa_nr;
+		}
+	}
+
 	/* Calculate CPU capacity for physical packages and nodes */
 	for (i = nr_cpumask_bits-1; i >= 0; i--) {
 		if (!cpumask_test_cpu(i, cpu_map))
Signature · 1 line
2.31.1
#6 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

Quoted 177 lines · Mel Gorman

Commit 7d2b5dd0bcc4 ("sched/numa: Allow a floating imbalance between NUMA nodes") allowed an imbalance between NUMA nodes such that communicating tasks would not be pulled apart by the load balancer. This works fine when there is a 1:1 relationship between LLC and node but can be suboptimal for multiple LLCs if independent tasks prematurely use CPUs sharing cache.

Zen* has multiple LLCs per node with local memory channels and due to the allowed imbalance, it's far harder to tune some workloads to run optimally than it is on hardware that has 1 LLC per node. This patch adjusts the imbalance on multi-LLC machines to allow an imbalance up to the point where LLCs should be balanced between nodes.

On a Zen3 machine running STREAM parallelised with OMP to have on instance per LLC the results and without binding, the results are

                            5.16.0-rc1             5.16.0-rc1
                               vanilla     sched-numaimb-v3r1
MB/sec copy-16    166712.18 (   0.00%)   587662.60 ( 252.50%)
MB/sec scale-16   140109.66 (   0.00%)   393528.14 ( 180.87%)
MB/sec add-16     160791.18 (   0.00%)   618622.00 ( 284.74%)
MB/sec triad-16   160043.84 (   0.00%)   589188.40 ( 268.14%)

STREAM can use directives to force the spread if the OpenMP is new enough but that doesn't help if an application uses threads and it's not known in advance how many threads will be created.

Coremark is a CPU and cache intensive benchmark parallelised with threads. When running with 1 thread per instance, the vanilla kernel allows threads to contend on cache. With the patch;

                               5.16.0-rc1             5.16.0-rc1
                                  vanilla     sched-numaimb-v3r1
Min       Score-16   367816.09 (   0.00%)   403429.15 (   9.68%)
Hmean     Score-16   389627.78 (   0.00%)   451015.49 *  15.76%*
Max       Score-16   416178.96 (   0.00%)   480012.00 (  15.34%)
Stddev    Score-16    17361.82 (   0.00%)    32378.08 ( -86.49%)
CoeffVar  Score-16        4.45 (   0.00%)        7.14 ( -60.57%)

It can also make a big difference for semi-realistic workloads like specjbb which can execute arbitrary numbers of threads without advance knowledge of how they should be placed

                               5.16.0-rc1             5.16.0-rc1
                                  vanilla     sched-numaimb-v3r1
Hmean     tput-1      73743.05 (   0.00%)    70258.27 *  -4.73%*
Hmean     tput-8     563036.51 (   0.00%)   591187.39 (   5.00%)
Hmean     tput-16   1016590.61 (   0.00%)  1032311.78 (   1.55%)
Hmean     tput-24   1418558.41 (   0.00%)  1424005.80 (   0.38%)
Hmean     tput-32   1608794.22 (   0.00%)  1907855.80 *  18.59%*
Hmean     tput-40   1761338.13 (   0.00%)  2108162.23 *  19.69%*
Hmean     tput-48   2290646.54 (   0.00%)  2214383.47 (  -3.33%)
Hmean     tput-56   2463345.12 (   0.00%)  2780216.58 *  12.86%*
Hmean     tput-64   2650213.53 (   0.00%)  2598196.66 (  -1.96%)
Hmean     tput-72   2497253.28 (   0.00%)  2998882.47 *  20.09%*
Hmean     tput-80   2820786.72 (   0.00%)  2951655.27 (   4.64%)
Hmean     tput-88   2813541.68 (   0.00%)  3045450.86 *   8.24%*
Hmean     tput-96   2604158.67 (   0.00%)  3035311.91 *  16.56%*
Hmean     tput-104  2713810.62 (   0.00%)  2984270.04 (   9.97%)
Hmean     tput-112  2558425.37 (   0.00%)  2894737.46 *  13.15%*
Hmean     tput-120  2611434.93 (   0.00%)  2781661.01 (   6.52%)
Hmean     tput-128  2706103.22 (   0.00%)  2811447.85 (   3.89%)
---
 include/linux/sched/topology.h |  1 +
 kernel/sched/fair.c            | 26 +++++++++++++++-----------
 kernel/sched/topology.c        | 20 ++++++++++++++++++++
 3 files changed, 36 insertions(+), 11 deletions(-)
include/linux/sched/topology.h +1 -0
index c07bfa2d80f2..54f5207154d3 100644
@@ -93,6 +93,7 @@ struct sched_domain {
        unsigned int busy_factor;       /* less balancing by factor if busy */
        unsigned int imbalance_pct;     /* No balance until over watermark */
        unsigned int cache_nice_tries;  /* Leave cache hot tasks for # tries */
+       unsigned int imb_numa_nr;       /* Nr imbalanced tasks allowed between nodes */
 
        int nohz_idle;                  /* NOHZ IDLE status */
        int flags;                      /* See SD_* */
kernel/sched/fair.c +15 -11
index 0a969affca76..64f211879e43 100644
@@ -1489,6 +1489,7 @@ struct task_numa_env {
 
        int src_cpu, src_nid;
        int dst_cpu, dst_nid;
+       int imb_numa_nr;
 
        struct numa_stats src_stats, dst_stats;
 
@@ -1885,7 +1886,7 @@ static void task_numa_find_cpu(struct task_numa_env *env,
                dst_running = env->dst_stats.nr_running + 1;
                imbalance = max(0, dst_running - src_running);
                imbalance = adjust_numa_imbalance(imbalance, dst_running,
-                                                       env->dst_stats.weight);
+                                                 env->imb_numa_nr);
 
                /* Use idle CPU if there is no imbalance */
                if (!imbalance) {
@@ -1950,8 +1951,10 @@ static int task_numa_migrate(struct task_struct *p)
         */
        rcu_read_lock();
        sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
-       if (sd)
+       if (sd) {
                env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
+               env.imb_numa_nr = sd->imb_numa_nr;
+       }
        rcu_read_unlock();
 
        /*
@@ -9046,13 +9049,14 @@ static bool update_pick_idlest(struct sched_group *idlest,
 }
 
 /*
- * Allow a NUMA imbalance if busy CPUs is less than 25% of the domain.
- * This is an approximation as the number of running tasks may not be
- * related to the number of busy CPUs due to sched_setaffinity.
+ * Allow a NUMA imbalance if busy CPUs is less than the allowed
+ * imbalance. This is an approximation as the number of running
+ * tasks may not be related to the number of busy CPUs due to
+ * sched_setaffinity.
  */
-static inline bool allow_numa_imbalance(int dst_running, int dst_weight)
+static inline bool allow_numa_imbalance(int dst_running, int imb_numa_nr)
 {
-       return (dst_running < (dst_weight >> 2));
+       return dst_running < imb_numa_nr;
 }
 
 /*
@@ -9191,7 +9195,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)
                         * a real need of migration, periodic load balance will
                         * take care of it.
                         */
-                       if (allow_numa_imbalance(local_sgs.sum_nr_running, sd->span_weight))
+                       if (allow_numa_imbalance(local_sgs.sum_nr_running, sd->imb_numa_nr))
                                return NULL;
                }
 
@@ -9283,9 +9287,9 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 #define NUMA_IMBALANCE_MIN 2
 
 static inline long adjust_numa_imbalance(int imbalance,
-                               int dst_running, int dst_weight)
+                               int dst_running, int imb_numa_nr)
 {
-       if (!allow_numa_imbalance(dst_running, dst_weight))
+       if (!allow_numa_imbalance(dst_running, imb_numa_nr))
                return imbalance;
 
        /*
@@ -9397,7 +9401,7 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
                /* Consider allowing a small imbalance between NUMA groups */
                if (env->sd->flags & SD_NUMA) {
                        env->imbalance = adjust_numa_imbalance(env->imbalance,
-                               busiest->sum_nr_running, env->sd->span_weight);
+                               busiest->sum_nr_running, env->sd->imb_numa_nr);
                }
 
                return;
kernel/sched/topology.c +4 -0
index d201a7052a29..fee2930745ab 100644
@@ -2242,6 +2242,26 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
                }
        }
 
+       /* Calculate allowed NUMA imbalance */
+       for_each_cpu(i, cpu_map) {
+               int imb_numa_nr = 0;
+

kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2258

Quoted 10 lines
kernel/sched/topology.c +10 -0
+               for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+                       struct sched_domain *child = sd->child;
+
+                       if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&
+                           (child->flags & SD_SHARE_PKG_RESOURCES)) {
+                               int nr_groups;
+
+                               nr_groups = sd->span_weight / child->span_weight;
+                               imb_numa_nr = max(1U, ((child->span_weight) >> 1) /
+                                               (nr_groups * num_online_nodes()));

Hi Mel, you used to have 25% * numa_weight if node has only one LLC. for a system with 4 numa, In case sd has 2 nodes, child is 1 numa node, then nr_groups=2, num_online_nodes()=4, imb_numa_nr will be child->span_weight/2/2/4?

Does this patch change the behaviour for machines whose numa equals LLC?

Quoted 10 lines
kernel/sched/topology.c +6 -1
+                       }
+
+                       sd->imb_numa_nr = imb_numa_nr;
+               }
+       }
+
        /* Calculate CPU capacity for physical packages and nodes */
        for (i = nr_cpumask_bits-1; i >= 0; i--) {
                if (!cpumask_test_cpu(i, cpu_map))
--
Quoted 2 lines

2.31.1

Thanks
Barry

#2 lore raw

Re: [PATCH 1/2] sched/fair: Use weight of SD_NUMA domain in find_busiest_group

In reply to Mel Gorman
Quoted 9 lines · Mel Gorman

find_busiest_group uses the child domain's group weight instead of the sched_domain's weight that has SD_NUMA set when calculating the allowed imbalance between NUMA nodes. This is wrong and inconsistent with find_idlest_group.

This patch uses the SD_NUMA weight in both.

Fixes c4e8f691d926 ("sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCS")

Hi Mel,

sorry I might be missing something. but I have failed to figure out where this commit is.

Quoted 19 lines
---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -2
index 6e476f6d9435..0a969affca76 100644
@@ -9397,7 +9397,7 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
                /* Consider allowing a small imbalance between NUMA groups */
                if (env->sd->flags & SD_NUMA) {
                        env->imbalance = adjust_numa_imbalance(env->imbalance,
-                               busiest->sum_nr_running, busiest->group_weight);
+                               busiest->sum_nr_running, env->sd->span_weight);
                }
 
                return;
--
Quoted 2 lines

2.31.1

Thanks
Barry

#3 lore raw

Re: [PATCH 1/2] sched/fair: Use weight of SD_NUMA domain in find_busiest_group

Hello Barry,

Quoted 9 lines · Barry Song
Quoted 8 lines · Mel Gorman

find_busiest_group uses the child domain's group weight instead of the sched_domain's weight that has SD_NUMA set when calculating the allowed imbalance between NUMA nodes. This is wrong and inconsistent with find_idlest_group.

This patch uses the SD_NUMA weight in both.

Quoted 7 lines
Quoted 1 line
Fixes c4e8f691d926 ("sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCS")

Hi Mel,

sorry I might be missing something. but I have failed to figure out where this commit is.

I think it is supposed to be

Fixes 7d2b5dd0bcc4 ("sched/numa: Allow a floating imbalance between NUMA nodes")

since it was the commit which introduced the "busiest->group_weight" change.

Quoted 21 lines
Quoted 21 lines
---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
index 6e476f6d9435..0a969affca76 100644
@@ -9397,7 +9397,7 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
                /* Consider allowing a small imbalance between NUMA groups */
                if (env->sd->flags & SD_NUMA) {
                        env->imbalance = adjust_numa_imbalance(env->imbalance,
-                               busiest->sum_nr_running, busiest->group_weight);
+                               busiest->sum_nr_running, env->sd->span_weight);
 
 
 
                }
Quoted 7 lines
Quoted 4 lines
                return;

--
2.31.1

Thanks
Barry

--
Thanks and Regards
gautham.

author
#7 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

In reply to Barry Song
Quoted 28 lines · Barry Song
Quoted 12 lines
kernel/sched/topology.c +4 -0
index d201a7052a29..fee2930745ab 100644
@@ -2242,6 +2242,26 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
                }
        }
 
+       /* Calculate allowed NUMA imbalance */
+       for_each_cpu(i, cpu_map) {
+               int imb_numa_nr = 0;
+

kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2258

Quoted 10 lines
kernel/sched/topology.c +10 -0
+               for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+                       struct sched_domain *child = sd->child;
+
+                       if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&
+                           (child->flags & SD_SHARE_PKG_RESOURCES)) {
+                               int nr_groups;
+
+                               nr_groups = sd->span_weight / child->span_weight;
+                               imb_numa_nr = max(1U, ((child->span_weight) >> 1) /
+                                               (nr_groups * num_online_nodes()));

Hi Mel, you used to have 25% * numa_weight if node has only one LLC. for a system with 4 numa, In case sd has 2 nodes, child is 1 numa node, then nr_groups=2, num_online_nodes()=4, imb_numa_nr will be child->span_weight/2/2/4?

Quoted 2 lines

Does this patch change the behaviour for machines whose numa equals LLC?

Yes, it changes behaviour. Instead of a flat 25%, it takes into account the number of LLCs per node and the number of nodes overall.

Signature · 2 lines
Mel Gorman
SUSE Labs
author
#4 lore raw

Re: [PATCH 1/2] sched/fair: Use weight of SD_NUMA domain in find_busiest_group

In reply to Barry Song
Quoted 7 lines · Barry Song
Quoted 6 lines · Mel Gorman

find_busiest_group uses the child domain's group weight instead of the sched_domain's weight that has SD_NUMA set when calculating the allowed imbalance between NUMA nodes. This is wrong and inconsistent with find_idlest_group.

Quoted 9 lines
Quoted 3 lines

This patch uses the SD_NUMA weight in both.

Fixes c4e8f691d926 ("sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCS")

Hi Mel,

sorry I might be missing something. but I have failed to figure out where this commit is.

Stupid cut&paste error and failing to check it properly

7d2b5dd0bcc4 ("sched/numa: Allow a floating imbalance between NUMA nodes")

Signature · 2 lines
Mel Gorman
SUSE Labs
#8 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

In reply to Mel Gorman
Quoted 30 lines · Mel Gorman
Quoted 28 lines · Barry Song
Quoted 12 lines
kernel/sched/topology.c +4 -0
index d201a7052a29..fee2930745ab 100644
@@ -2242,6 +2242,26 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
                }
        }
 
+       /* Calculate allowed NUMA imbalance */
+       for_each_cpu(i, cpu_map) {
+               int imb_numa_nr = 0;
+

kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2258

Quoted 10 lines
kernel/sched/topology.c +10 -0
+               for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+                       struct sched_domain *child = sd->child;
+
+                       if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&
+                           (child->flags & SD_SHARE_PKG_RESOURCES)) {
+                               int nr_groups;
+
+                               nr_groups = sd->span_weight / child->span_weight;
+                               imb_numa_nr = max(1U, ((child->span_weight) >> 1) /
+                                               (nr_groups * num_online_nodes()));

Hi Mel, you used to have 25% * numa_weight if node has only one LLC. for a system with 4 numa, In case sd has 2 nodes, child is 1 numa node, then nr_groups=2, num_online_nodes()=4, imb_numa_nr will be child->span_weight/2/2/4?

Quoted 5 lines
Quoted 2 lines

Does this patch change the behaviour for machines whose numa equals LLC?

Yes, it changes behaviour. Instead of a flat 25%, it takes into account the number of LLCs per node and the number of nodes overall.

Considering the number of nodes overall seems to be quite weird to me. for example, for the below machines

1P * 2DIE = 2NUMA:    node1 - node0
2P * 2DIE = 4NUMA:    node1 - node0  ------ node2 - node3
4P * 2DIE = 8NUMA:    node1 - node0  ------ node2 - node3
                                      node5 - node4  ------ node6 - node7

if one service pins node1 and node0 in all above configurations, it seems in all different machines, the app will result in different behavior.

the other example is:
in a 2P machine, if one app pins the first two NUMAs, the other app pins the last two NUMAs, why would the num_online_nodes() matter to them? there is no balance requirement between the two P.

Quoted 4 lines

--
Mel Gorman
SUSE Labs

Thanks
Barry

author
#9 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

Quoted 14 lines · Barry Song
Quoted 10 lines
Quoted 7 lines

Hi Mel, you used to have 25% * numa_weight if node has only one LLC. for a system with 4 numa, In case sd has 2 nodes, child is 1 numa node, then nr_groups=2, num_online_nodes()=4, imb_numa_nr will be child->span_weight/2/2/4?

Does this patch change the behaviour for machines whose numa equals LLC?

Yes, it changes behaviour. Instead of a flat 25%, it takes into account the number of LLCs per node and the number of nodes overall.

Considering the number of nodes overall seems to be quite weird to me. for example, for the below machines

Quoted 8 lines
1P * 2DIE = 2NUMA:    node1 - node0
2P * 2DIE = 4NUMA:    node1 - node0  ------ node2 - node3
4P * 2DIE = 8NUMA:    node1 - node0  ------ node2 - node3
                                      node5 - node4  ------ node6 - node7

if one service pins node1 and node0 in all above configurations, it seems in all different machines, the app will result in different behavior.

The intent is to balance between LLCs across the whole machine, hence accounting for the number of online nodes.

Quoted 5 lines

the other example is:
in a 2P machine, if one app pins the first two NUMAs, the other app pins the last two NUMAs, why would the num_online_nodes() matter to them? there is no balance requirement between the two P.

The previous 25% imbalance also did not take pinning into account and the choice was somewhat arbitrary.

Signature · 2 lines
Mel Gorman
SUSE Labs
maintainer
#10 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

In reply to Mel Gorman
Quoted 8 lines · Mel Gorman
kernel/sched/topology.c +8 -0
+	/* Calculate allowed NUMA imbalance */
+	for_each_cpu(i, cpu_map) {
+		int imb_numa_nr = 0;
+
+		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+			struct sched_domain *child = sd->child;
+
+			if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&

kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2262

Quoted 10 lines
kernel/sched/topology.c +10 -0
+			    (child->flags & SD_SHARE_PKG_RESOURCES)) {
+				int nr_groups;
+
+				nr_groups = sd->span_weight / child->span_weight;
+				imb_numa_nr = max(1U, ((child->span_weight) >> 1) /
+						(nr_groups * num_online_nodes()));
+			}
+
+			sd->imb_numa_nr = imb_numa_nr;
+		}

OK, so let's see. All domains with SHARE_PKG_RESOURCES set will have imb_numa_nr = 0, all domains above it will have the same value calculated here.

So far so good I suppose :-)

Then nr_groups is what it says on the tin; we could've equally well iterated sd->groups and gotten the same number, but this is simpler.

Now, imb_numa_nr is where the magic happens, the way it's written doesn't help, but it's something like:

	(child->span_weight / 2) / (nr_groups * num_online_nodes())

With a minimum value of 1. So the larger the system is, or the smaller the LLCs, the smaller this number gets, right?

So my ivb-ep that has 20 cpus in a LLC and 2 nodes, will get: (20 / 2) / (1 * 2) = 10, while the ivb-ex will get: (20/2) / (1*4) = 5.

But a Zen box that has only like 4 CPUs per LLC will have 1, regardless of how many nodes it has.

Now, I'm thinking this assumes (fairly reasonable) that the level above LLC is a node, but I don't think we need to assume this, while also not assuming the balance domain spans the whole machine (yay paritions!).

	for (top = sd; top->parent; top = top->parent)
		;

	nr_llcs = top->span_weight / child->span_weight;
	imb_numa_nr = max(1, child->span_weight / nr_llcs);
which for my ivb-ep gets me:  20 / (40 / 20) = 10
and the Zen system will have:  4 / (huge number) = 1

Now, the exp: a / (b / a) is equivalent to a * (a / b) or a^2/b, so we can also write the above as:

	(child->span_weight * child->span_weight) / top->span_weight;

Hmm?

Quoted 8 lines
kernel/sched/topology.c +2 -0
+	}
+
 	/* Calculate CPU capacity for physical packages and nodes */
 	for (i = nr_cpumask_bits-1; i >= 0; i--) {
 		if (!cpumask_test_cpu(i, cpu_map))
Signature · 1 line
2.31.1
#11 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

Hello Peter, Mel,

Quoted 24 lines · Peter Zijlstra
Quoted 8 lines · Mel Gorman
kernel/sched/topology.c +8 -0
+	/* Calculate allowed NUMA imbalance */
+	for_each_cpu(i, cpu_map) {
+		int imb_numa_nr = 0;
+
+		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+			struct sched_domain *child = sd->child;
+
+			if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&

kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2262

Quoted 10 lines
kernel/sched/topology.c +10 -0
+			    (child->flags & SD_SHARE_PKG_RESOURCES)) {
+				int nr_groups;
+
+				nr_groups = sd->span_weight / child->span_weight;
+				imb_numa_nr = max(1U, ((child->span_weight) >> 1) /
+						(nr_groups * num_online_nodes()));
+			}
+
+			sd->imb_numa_nr = imb_numa_nr;
+		}

OK, so let's see. All domains with SHARE_PKG_RESOURCES set will have imb_numa_nr = 0, all domains above it will have the same value calculated here.

Quoted 1 line

So far so good I suppose :-)

Well, we will still have the same imb_numa_nr set for different NUMA domains which have different distances!

Quoted 9 lines

Then nr_groups is what it says on the tin; we could've equally well iterated sd->groups and gotten the same number, but this is simpler.

Now, imb_numa_nr is where the magic happens, the way it's written doesn't help, but it's something like:

	(child->span_weight / 2) / (nr_groups * num_online_nodes())
Quoted 8 lines

With a minimum value of 1. So the larger the system is, or the smaller the LLCs, the smaller this number gets, right?

So my ivb-ep that has 20 cpus in a LLC and 2 nodes, will get: (20 / 2) / (1 * 2) = 10, while the ivb-ex will get: (20/2) / (1*4) = 5.

But a Zen box that has only like 4 CPUs per LLC will have 1, regardless of how many nodes it has.

That's correct. On a Zen3 box with 2 sockets with 64 cores per sockets, we can configure it with either 1/2/4 Nodes Per Socket (NPS). The imb_numa_nr value for each of the NPS configurations is as follows:

NPS1 :
~~~~~~~~
SMT [span_wt=2]
--> MC [span_wt=16, LLC]

     --> DIE[span_wt=128]
         --> NUMA [span_wt=256, SD_NUMA]

sd->span = 128, child->span = 16, nr_groups = 8, num_online_nodes() = 2 imb_numa_nr = max(1, (16 >> 1)/(8*2)) = max(1, 0.5) = 1.

NPS2 :
~~~~~~~~
SMT [span_wt=2]
--> MC [span_wt=16,LLC]

     --> NODE[span_wt=64]
         --> NUMA [span_wt=128, SD_NUMA]
             --> NUMA [span_wt=256, SD_NUMA]

sd->span = 64, child->span = 16, nr_groups = 4, num_online_nodes() = 4 imb_numa_nr = max(1, (16 >> 1)/(4*4)) = max(1, 0.5) = 1.

NPS 4:
~~~~~~~
SMT [span_wt=2]
--> MC [span_wt=16, LLC]

       --> NODE [span_wt=32]
           --> NUMA [span_wt=128, SD_NUMA]
	       --> NUMA [span_wt=256, SD_NUMA]

sd->span = 32, child->span = 16, nr_groups = 2, num_online_nodes() = 8 imb_numa_nr = max(1, (16 >> 1)/(2*8)) = max(1, 0.5) = 1.

While the imb_numa_nr = 1 is good for the NUMA domain within a socket (the lower NUMA domains in in NPS2 and NPS4 modes), it appears to be a little bit aggressive for the NUMA domain spanning the two sockets. If we have only a pair of communicating tasks in a socket, we will end up spreading them across the two sockets with this patch.

Quoted 11 lines

Now, I'm thinking this assumes (fairly reasonable) that the level above LLC is a node, but I don't think we need to assume this, while also not assuming the balance domain spans the whole machine (yay paritions!).

	for (top = sd; top->parent; top = top->parent)
		;

	nr_llcs = top->span_weight / child->span_weight;
	imb_numa_nr = max(1, child->span_weight / nr_llcs);
Quoted 7 lines
which for my ivb-ep gets me:  20 / (40 / 20) = 10
and the Zen system will have:  4 / (huge number) = 1

Now, the exp: a / (b / a) is equivalent to a * (a / b) or a^2/b, so we can also write the above as:

	(child->span_weight * child->span_weight) / top->span_weight;

Assuming that "child" here refers to the LLC domain, on Zen3 we would have
(a) child->span_weight = 16. (b) top->span_weight = 256.

So we get a^2/b = 1.

Quoted 2 lines

Hmm?

Last week, I tried a modification on top of Mel's current patch where we spread tasks between the LLCs of the groups within each NUMA domain and compute the value of imb_numa_nr per NUMA domain. The idea is to set

sd->imb_numa_nr = min(1U,
(Number of LLCs in each sd group / Number of sd groups))

This won't work for processors which have a single LLC in a socket, since the sd->imb_numa_nr will be 1 which is probably too low. FWIW, with this heuristic, the imb_numa_nr across the different NPS configurations of a Zen3 server is as follows

NPS1:
NUMA domain: nr_llcs_per_group = 8. nr_groups = 2. imb_numa_nr = 4

NPS2:
1st NUMA domain: nr_llcs_per_group = 4. nr_groups = 2. imb_numa_nr = 2. 2nd NUMA domain: nr_llcs_per_group = 8. nr_groups = 2. imb_numa_nr = 4.

NPS4:
1st NUMA domain: nr_llcs_per_group = 2. nr_groups = 4. imb_numa_nr = min(1, 2/4) = 1. 2nd NUMA domain: nr_llcs_per_group = 8. nr_groups = 2. imb_numa_nr = 4.

Thus, at the highest NUMA level (socket), we don't spread across the two sockets until there are 4 tasks within the socket. If there is only a pair of communicating tasks in the socket, they will be left alone within that socket. The stream numbers (average of 10 runs. The following are Triad numbers. The Copy, Scale and Add numbers have the same trend) are presented in the table below. We do see some degradation for the 4 thread case in NPS2 and NPS4 modes with the aforementioned approach, but there are gains as well for 16 and 32 thread case on NPS4 mode.

NPS1:

==========+===========+================+=================

| Nr      |  Mel v3   | tip/sched/core |   Spread across|
| Stream  |           |                |   LLCs of NUMA |
| Threads |           |                |   groups       |
==========+===========+================+=================
|       4 | 111106.14 |       94849.77 |  111820.02     |
|         |           |      (-14.63%) |  (+0.64%)      | 
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|       8 | 175633.00 |      128268.22 |  189705.48     |
|         |           |      (-26.97%) |  (+8.01%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      16 | 252812.87 |      136745.98 |  255577.34     |
|         |           |      (-45.91%) |  (+1.09%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      32 | 248198.43 |      130120.30 |  253266.86     |
|         |           |      (-47.57%) |  (+2.04%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      64 | 244202.33 |      133773.03 |  249449.53     |
|         |           |      (-45.22%) |  (+2.15%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|     128 | 248459.85 |      249450.61 |  250346.09     |
|         |           |      (+0.40%)  |  (+0.76%)      |

~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+

NPS2:
==========+===========+================+=================

| Nr      |  Mel v3   | tip/sched/core |   Spread across|
| Stream  |           |                |   LLCs of NUMA |
| Threads |           |                |   groups       |
==========+===========+================+=================
|       4 | 110888.35 |       63067.26 |  104971.36     |
|         |           |      (-43.12%) |   (-5.34%)     |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|       8 | 174983.85 |       96226.39 |  177558.65     |
|         |           |      (-45.01%) |   (+1.47%)     |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      16 | 252943.21 |       106474.3 |  260749.60     |
|         |           |      (-57.90%) |  (+1.47%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      32 | 248540.52 |      113864.09 |  254141.33     |
|         |           |      (-54.19%) |  (+2.25%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      64 | 248383.17 |      137101.85 |  255018.52     |
|         |           |      (-44.80%) |  (+2.67%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|     128 | 250123.31 |      257031.29 |  254457.13     |
|         |           |      (+2.76%)  |  (+1.73%)      |

~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+

NPS4:
==========+===========+================+=================

| Nr      |  Mel v3   | tip/sched/core |   Spread across|
| Stream  |           |                |   LLCs of NUMA |
| Threads |           |                |   groups       |
==========+===========+================+=================
|       4 | 108580.91 |       31746.06 |   97585.53	|
|         |           |      (-70.76%) |  (-10.12%)     |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|       8 | 150259.94 |       64841.89 |  154954.75     |
|         |           |      (-56.84%) |  (+3.12%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      16 | 234137.41 |      106780.26 |  261005.27     |
|         |           |      (-54.39%) |  (+11.48%)     |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      32 | 241583.06 |      147572.50 |  257004.22     |
|         |           |      (-38.91%) |  (+6.38%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|      64 | 248511.64 |      166183.06 |  259599.32     |
|         |           |      (-33.12%) |  (+4.46%)      |
~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~+
|     128 | 252227.34 |      239270.85 |  259117.18     |
|         |           |      (-5.13%)  |  (2.73%)       | 

~~~~~~~~~~+~~~~~~~~~~~~~~~~+~~~~~~~~~~~+~~~~~~~~~~~~~~~~+

--
Thanks and Regards
gautham.

maintainer
#12 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

Quoted 25 lines · Gautham R. Shenoy
Quoted 24 lines · Peter Zijlstra
Quoted 8 lines · Mel Gorman
kernel/sched/topology.c +8 -0
+	/* Calculate allowed NUMA imbalance */
+	for_each_cpu(i, cpu_map) {
+		int imb_numa_nr = 0;
+
+		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+			struct sched_domain *child = sd->child;
+
+			if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&

kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2262

Quoted 10 lines
kernel/sched/topology.c +10 -0
+			    (child->flags & SD_SHARE_PKG_RESOURCES)) {
+				int nr_groups;
+
+				nr_groups = sd->span_weight / child->span_weight;
+				imb_numa_nr = max(1U, ((child->span_weight) >> 1) /
+						(nr_groups * num_online_nodes()));
+			}
+
+			sd->imb_numa_nr = imb_numa_nr;
+		}

OK, so let's see. All domains with SHARE_PKG_RESOURCES set will have imb_numa_nr = 0, all domains above it will have the same value calculated here.

Quoted 4 lines
Quoted 1 line

So far so good I suppose :-)

Well, we will still have the same imb_numa_nr set for different NUMA domains which have different distances!

Fair enough; that would need making the computation depends on more thing, but that shouldn't be too hard.

Quoted 14 lines
Quoted 14 lines

Then nr_groups is what it says on the tin; we could've equally well iterated sd->groups and gotten the same number, but this is simpler.

Now, imb_numa_nr is where the magic happens, the way it's written doesn't help, but it's something like:

	(child->span_weight / 2) / (nr_groups * num_online_nodes())

With a minimum value of 1. So the larger the system is, or the smaller the LLCs, the smaller this number gets, right?

So my ivb-ep that has 20 cpus in a LLC and 2 nodes, will get: (20 / 2) / (1 * 2) = 10, while the ivb-ex will get: (20/2) / (1*4) = 5.

Quoted 7 lines
Quoted 2 lines

But a Zen box that has only like 4 CPUs per LLC will have 1, regardless of how many nodes it has.

That's correct. On a Zen3 box with 2 sockets with 64 cores per sockets, we can configure it with either 1/2/4 Nodes Per Socket (NPS). The imb_numa_nr value for each of the NPS configurations is as follows:

Cute; that's similar to the whole Intel sub-numa-cluster stuff then; perhaps update the comment that goes with x86_has_numa_in_package ? Currently that only mentions AMD Magny-Cours which is a few generations ago.

Quoted 7 lines

NPS 4:
~~~~~~~
SMT [span_wt=2]
--> MC [span_wt=16, LLC]

       --> NODE [span_wt=32]
           --> NUMA [span_wt=128, SD_NUMA]
	       --> NUMA [span_wt=256, SD_NUMA]

OK, so at max nodes you still have at least 2 LLCs per node.

Quoted 23 lines

While the imb_numa_nr = 1 is good for the NUMA domain within a socket (the lower NUMA domains in in NPS2 and NPS4 modes), it appears to be a little bit aggressive for the NUMA domain spanning the two sockets. If we have only a pair of communicating tasks in a socket, we will end up spreading them across the two sockets with this patch.

Quoted 17 lines

Now, I'm thinking this assumes (fairly reasonable) that the level above LLC is a node, but I don't think we need to assume this, while also not assuming the balance domain spans the whole machine (yay paritions!).

	for (top = sd; top->parent; top = top->parent)
		;

	nr_llcs = top->span_weight / child->span_weight;
	imb_numa_nr = max(1, child->span_weight / nr_llcs);
which for my ivb-ep gets me:  20 / (40 / 20) = 10
and the Zen system will have:  4 / (huge number) = 1

Now, the exp: a / (b / a) is equivalent to a * (a / b) or a^2/b, so we can also write the above as:

Quoted 7 lines
Quoted 1 line
	(child->span_weight * child->span_weight) / top->span_weight;

Assuming that "child" here refers to the LLC domain, on Zen3 we would have
(a) child->span_weight = 16. (b) top->span_weight = 256.

So we get a^2/b = 1.

Yes, it would be in the same place as the current imb_numa_nr calculation, so child would be the largest domain having SHARE_PKG_RESOURCES, aka. LLC.

Quoted 6 lines

Last week, I tried a modification on top of Mel's current patch where we spread tasks between the LLCs of the groups within each NUMA domain and compute the value of imb_numa_nr per NUMA domain. The idea is to set

sd->imb_numa_nr = min(1U,
(Number of LLCs in each sd group / Number of sd groups))

s/min/max/

Which is basically something like:

for_each (sd in NUMA):
llc_per_group = child->span / llc->span;
nr_group = sd->span / child->span;
imb = max(1, llc_per_group / nr_group);

Quoted 2 lines

This won't work for processors which have a single LLC in a socket, since the sd->imb_numa_nr will be 1 which is probably too low.

Right.

Quoted 11 lines

FWIW,
with this heuristic, the imb_numa_nr across the different NPS configurations of a Zen3 server is as follows

NPS1:
NUMA domain: nr_llcs_per_group = 8. nr_groups = 2. imb_numa_nr = 4

NPS2:
1st NUMA domain: nr_llcs_per_group = 4. nr_groups = 2. imb_numa_nr = 2. 2nd NUMA domain: nr_llcs_per_group = 8. nr_groups = 2. imb_numa_nr = 4.

Quoted 8 lines

NPS4:
1st NUMA domain: nr_llcs_per_group = 2. nr_groups = 4. imb_numa_nr = min(1, 2/4) = 1. 2nd NUMA domain: nr_llcs_per_group = 8. nr_groups = 2. imb_numa_nr = 4.

Thus, at the highest NUMA level (socket), we don't spread across the two sockets until there are 4 tasks within the socket. If there is only a pair of communicating tasks in the socket, they will be left alone within that socket.

Something that might work:

imb = 0;
imb_span = 1;

for_each_sd(sd) {
	child = sd->child;

	if (!(sd->flags & SD_SPR) && child && (child->flags & SD_SPR)) {

		imb = /* initial magic */
		imb_span = sd->span;
		sd->imb = imb;

	} else if (imb) {
		sd->imb = imb * (sd->span / imb_span);
	}
}

Where we calculate the initial imbalance for the LLC boundary, and then increase that for subsequent domains based on how often that boundary sd fits in it. That gives the same progression you have, but also works for NODE==LLC I think.

author
#13 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

In reply to Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
Quoted 8 lines · Mel Gorman
kernel/sched/topology.c +8 -0
+	/* Calculate allowed NUMA imbalance */
+	for_each_cpu(i, cpu_map) {
+		int imb_numa_nr = 0;
+
+		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+			struct sched_domain *child = sd->child;
+
+			if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&

kernel/sched/topology.c build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att · line 2262

Quoted 10 lines
kernel/sched/topology.c +10 -0
+			    (child->flags & SD_SHARE_PKG_RESOURCES)) {
+				int nr_groups;
+
+				nr_groups = sd->span_weight / child->span_weight;
+				imb_numa_nr = max(1U, ((child->span_weight) >> 1) /
+						(nr_groups * num_online_nodes()));
+			}
+
+			sd->imb_numa_nr = imb_numa_nr;
+		}

OK, so let's see. All domains with SHARE_PKG_RESOURCES set will have imb_numa_nr = 0, all domains above it will have the same value calculated here.

Quoted 2 lines

So far so good I suppose :-)

Good start :)

Quoted 3 lines

Then nr_groups is what it says on the tin; we could've equally well iterated sd->groups and gotten the same number, but this is simpler.

I also thought it would be clearer.

Quoted 8 lines

Now, imb_numa_nr is where the magic happens, the way it's written doesn't help, but it's something like:

	(child->span_weight / 2) / (nr_groups * num_online_nodes())

With a minimum value of 1. So the larger the system is, or the smaller the LLCs, the smaller this number gets, right?

Correct.

Quoted 6 lines

So my ivb-ep that has 20 cpus in a LLC and 2 nodes, will get: (20 / 2) / (1 * 2) = 10, while the ivb-ex will get: (20/2) / (1*4) = 5.

But a Zen box that has only like 4 CPUs per LLC will have 1, regardless of how many nodes it has.

The minimum of one was to allow a pair of communicating tasks to remain on one node even if it's imbalacnced.

Quoted 10 lines

Now, I'm thinking this assumes (fairly reasonable) that the level above LLC is a node, but I don't think we need to assume this, while also not assuming the balance domain spans the whole machine (yay paritions!).

	for (top = sd; top->parent; top = top->parent)
		;

	nr_llcs = top->span_weight / child->span_weight;
	imb_numa_nr = max(1, child->span_weight / nr_llcs);
Quoted 8 lines
which for my ivb-ep gets me:  20 / (40 / 20) = 10
and the Zen system will have:  4 / (huge number) = 1

Now, the exp: a / (b / a) is equivalent to a * (a / b) or a^2/b, so we can also write the above as:

	(child->span_weight * child->span_weight) / top->span_weight;

Gautham had similar reasoning to calculate the imbalance at each higher-level domain instead of using a static value throughout and it does make sense. For each level and splitting the imbalance between two domains, this works out as

	/*
	 * Calculate an allowed NUMA imbalance such that LLCs do not get
	 * imbalanced.
	 */
	for_each_cpu(i, cpu_map) {
		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
			struct sched_domain *child = sd->child;

			if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&
			    (child->flags & SD_SHARE_PKG_RESOURCES)) {
				struct sched_domain *top = sd;
				unsigned int llc_sq;

				/*
				 * nr_llcs = (top->span_weight / llc_weight);
				 * imb = (child_weight / nr_llcs) >> 1
				 *
				 * is equivalent to
				 *
				 * imb = (llc_weight^2 / top->span_weight) >> 1
				 *
				 */
				llc_sq = child->span_weight * child->span_weight;
				while (top) {
					top->imb_numa_nr = max(1U,
						(llc_sq / top->span_weight) >> 1);
					top = top->parent;
				}

				break;
			}
		}
	}

I'll test this and should have results tomorrow.

Signature · 2 lines
Mel Gorman
SUSE Labs
#14 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

Quoted 31 lines · Mel Gorman

Gautham had similar reasoning to calculate the imbalance at each higher-level domain instead of using a static value throughout and it does make sense. For each level and splitting the imbalance between two domains, this works out as

      /*
       * Calculate an allowed NUMA imbalance such that LLCs do not get
       * imbalanced.
       */
      for_each_cpu(i, cpu_map) {
              for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
                      struct sched_domain *child = sd->child;

                      if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&
                          (child->flags & SD_SHARE_PKG_RESOURCES)) {
                              struct sched_domain *top = sd;
                              unsigned int llc_sq;

                              /*
                               * nr_llcs = (top->span_weight / llc_weight);
                               * imb = (child_weight / nr_llcs) >> 1
                               *
                               * is equivalent to
                               *
                               * imb = (llc_weight^2 / top->span_weight) >> 1
                               *
                               */
                              llc_sq = child->span_weight * child->span_weight;
                              while (top) {
                                      top->imb_numa_nr = max(1U,
Quoted 9 lines
                                              (llc_sq / top->span_weight) >> 1);
                                      top = top->parent;
                              }

                              break;
                      }
              }
      }

IIRC Peter suggested punting that logic to before domains get degenerated, but I don't see how that helps here. If you just want to grab the LLC domain (aka highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES)) and compare its span with that of its parents, that can happen after the degeneration, no?

Quoted 5 lines

I'll test this and should have results tomorrow.

--
Mel Gorman
SUSE Labs

author
#15 lore raw

Re: [PATCH 2/2] sched/fair: Adjust the allowed NUMA imbalance when SD_NUMA spans multiple LLCs

Quoted 42 lines · Valentin Schneider
Quoted 31 lines · Mel Gorman

Gautham had similar reasoning to calculate the imbalance at each higher-level domain instead of using a static value throughout and it does make sense. For each level and splitting the imbalance between two domains, this works out as

      /*
       * Calculate an allowed NUMA imbalance such that LLCs do not get
       * imbalanced.
       */
      for_each_cpu(i, cpu_map) {
              for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
                      struct sched_domain *child = sd->child;

                      if (!(sd->flags & SD_SHARE_PKG_RESOURCES) && child &&
                          (child->flags & SD_SHARE_PKG_RESOURCES)) {
                              struct sched_domain *top = sd;
                              unsigned int llc_sq;

                              /*
                               * nr_llcs = (top->span_weight / llc_weight);
                               * imb = (child_weight / nr_llcs) >> 1
                               *
                               * is equivalent to
                               *
                               * imb = (llc_weight^2 / top->span_weight) >> 1
                               *
                               */
                              llc_sq = child->span_weight * child->span_weight;
                              while (top) {
                                      top->imb_numa_nr = max(1U,
Quoted 9 lines
                                              (llc_sq / top->span_weight) >> 1);
                                      top = top->parent;
                              }

                              break;
                      }
              }
      }
Quoted 6 lines

IIRC Peter suggested punting that logic to before domains get degenerated, but I don't see how that helps here. If you just want to grab the LLC domain (aka highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES)) and compare its span with that of its parents, that can happen after the degeneration, no?

I guess we could but I don't see any specific advantage to doing that.

Quoted 2 lines
Quoted 2 lines

I'll test this and should have results tomorrow.

The test results indicated that there was still a problem with communicating tasks being pulled apart so am testing a new version.

Signature · 2 lines
Mel Gorman
SUSE Labs