Revisit NUMA imbalance tolerance and fork balancing
PATCH v2 2/4 sched: Avoid unnecessary calculation of load imbalance at clone time
In reply to Mel GormanIn find_idlest_group(), the load imbalance is only relevant when the group is either overloaded or fully busy but it is calculated unconditionally. This patch moves the imbalance calculation to the context it is required. Technically, it is a micro-optimisation but really the benefit is avoiding confusing one type of imbalance with another depending on the group_type in the next patch.
No functional change.
--- kernel/sched/fair.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
kernel/sched/fair.c +5 -3
@@ -8777,9 +8777,6 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu) .group_type = group_overloaded, }; - imbalance =scale_load_down (NICE_0_LOAD ) * - (sd->imbalance_pct-100 ) /100 ; - do { int local_group;
@@ -8833,6 +8830,11 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)switch (local_sgs.group_type) {case group_overloaded:case group_fully_busy: + +/* Calculate allowed imbalance based on load */ + imbalance =scale_load_down (NICE_0_LOAD ) * + (sd->imbalance_pct-100 ) /100 ; +/* * When comparing groups across NUMA domains, it's possible for * the local domain to be very lightly loaded relative to the
Signature · 1 line
2.26.2
v2 cover Revisit NUMA imbalance tolerance and fork balancing
Changelog since v1
o Split out patch that moves imbalance calculation
o Strongly connect fork imbalance considerations with adjust_numa_imbalance
When NUMA and CPU balancing were reconciled, there was an attempt to allow a degree of imbalance but it caused more problems than it solved. Instead, imbalance was only allowed with an almost idle NUMA domain. A lot of the problems have since been addressed so it's time for a revisit. There is also an issue with how fork is balanced across threads. It's mentioned in this context as patch 3 and 4 should share similar behaviour in terms of a nodes utilisation.
Patch 1 is just a cosmetic rename
Patch 2 moves an imbalance calculation. It is both a micro-optimisation
and avoids confusing what imbalance means for different group types.
Patch 3 allows a "floating" imbalance to exist so communicating tasks can
remain on the same domain until utilisation is higher. It aims to balance compute availability with memory bandwidth.
Patch 4 is the interesting one. Currently fork can allow a NUMA node
to be completely utilised as long as there are idle CPUs until the load balancer gets involved. This caused serious problems with a real workload that unfortunately I cannot share many details about but there is a proxy reproducer.
Signature · 1 line
2.26.2
PATCH v2 1/4 sched/numa: Rename nr_running and break out the magic number
This is simply a preparation patch to make the following patches easier to read. No functional change.
--- kernel/sched/fair.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-)
kernel/sched/fair.c +6 -4
@@ -1550,7 +1550,7 @@ struct task_numa_env {static unsigned long cpu_load (struct rq *rq);static unsigned long cpu_runnable (struct rq *rq);static unsigned long cpu_util (int cpu); -static inline long adjust_numa_imbalance (int imbalance,int nr_running); +static inline long adjust_numa_imbalance (int imbalance,int dst_running); static inline enum numa_type numa_classify(unsigned int imbalance_pct,
@@ -8991,7 +8991,9 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd } } -static inline long adjust_numa_imbalance (int imbalance,int nr_running) +#define NUMA_IMBALANCE_MIN 2 + +static inline long adjust_numa_imbalance (int imbalance,int dst_running) {unsigned int imbalance_min;
@@ -8999,8 +9001,8 @@ static inline long adjust_numa_imbalance(int imbalance, int nr_running)* Allow a small imbalance based on a simple pair of communicating * tasks that remain local when the source domain is almost idle. */ - imbalance_min =2 ; -if (nr_running <= imbalance_min) + imbalance_min =NUMA_IMBALANCE_MIN ; +if (dst_running <= imbalance_min)return 0 ;return imbalance;
Signature · 1 line
2.26.2
PATCH v2 3/4 sched/numa: Allow a floating imbalance between NUMA nodes
In reply to Mel GormanCurrently, an imbalance is only allowed when a destination node is almost completely idle. This solved one basic class of problems and was the cautious approach.
This patch revisits the possibility that NUMA nodes can be imbalanced until 25% of the CPUs are occupied. The reasoning behind 25% is somewhat superficial -- it's half the cores when HT is enabled. At higher utilisations, balancing should continue as normal and keep things even until scheduler domains are fully busy or over utilised.
Note that this is not expected to be a universal win. Any benchmark that prefers spreading as wide as possible with limited communication will favour the old behaviour as there is more memory bandwidth. Workloads that communicate heavily in pairs such as netperf or tbench benefit. For the tests I ran, the vast majority of workloads saw a benefit so it seems to be a worthwhile trade-off.
--- kernel/sched/fair.c | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-)
kernel/sched/fair.c +11 -10
@@ -1550,7 +1550,8 @@ struct task_numa_env {static unsigned long cpu_load (struct rq *rq);static unsigned long cpu_runnable (struct rq *rq);static unsigned long cpu_util (int cpu); -static inline long adjust_numa_imbalance (int imbalance,int dst_running); +static inline long adjust_numa_imbalance (int imbalance, +int dst_running,int dst_weight); static inline enum numa_type numa_classify(unsigned int imbalance_pct,
@@ -1930,7 +1931,8 @@ static void task_numa_find_cpu(struct task_numa_env *env, src_running = env->src_stats.nr_running -1 ; dst_running = env->dst_stats.nr_running +1 ; imbalance =max (0 , dst_running - src_running); - imbalance =adjust_numa_imbalance (imbalance, dst_running); + imbalance =adjust_numa_imbalance (imbalance, dst_running, + env->dst_stats.weight);/* Use idle CPU if there is no imbalance */ if (!imbalance) {
@@ -8995,16 +8997,14 @@ 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) +static inline long adjust_numa_imbalance (int imbalance, +int dst_running,int dst_weight) { -unsigned int imbalance_min; -/* * Allow a small imbalance based on a simple pair of communicating -* tasks that remain local when the source domain is almost idle. +* tasks that remain local when the destination is lightly loaded. */ - imbalance_min =NUMA_IMBALANCE_MIN ; -if (dst_running <= imbalance_min) +if (dst_running < (dst_weight >>2 ) && imbalance <=NUMA_IMBALANCE_MIN )return 0 ;return imbalance;
@@ -9107,9 +9107,10 @@ 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 ) +if (env->sd->flags &SD_NUMA ) { env->imbalance =adjust_numa_imbalance (env->imbalance, - busiest->sum_nr_running); + busiest->sum_nr_running, busiest->group_weight); + }return ; }
Signature · 1 line
2.26.2
PATCH v2 4/4 sched: Limit the amount of NUMA imbalance that can exist at fork time
In reply to Mel GormanAt fork time currently, a local node can be allowed to fill completely and allow the periodic load balancer to fix the problem. This can be problematic in cases where a task creates lots of threads that idle until woken as part of a worker poll causing a memory bandwidth problem.
However, a "real" workload suffers badly from this behaviour. The workload in question is mostly NUMA aware but spawns large numbers of threads that act as a worker pool that can be called from anywhere. These need to spread early to get reasonable behaviour.
This patch limits how much a local node can fill before spilling over to another node and it will not be a universal win. Specifically, very short-lived workloads that fit within a NUMA node would prefer the memory bandwidth.
As I cannot describe the "real" workload, the best proxy measure I found for illustration was a page fault microbenchmark. It's not representative of the workload but demonstrates the hazard of the current behaviour.
pft timings
5.10.0-rc2 5.10.0-rc2
imbalancefloat-v2 forkspread-v2
Amean elapsed-1 46.37 ( 0.00%) 46.05 * 0.69%*
Amean elapsed-4 12.43 ( 0.00%) 12.49 * -0.47%*
Amean elapsed-7 7.61 ( 0.00%) 7.55 * 0.81%*
Amean elapsed-12 4.79 ( 0.00%) 4.80 ( -0.17%)
Amean elapsed-21 3.13 ( 0.00%) 2.89 * 7.74%*
Amean elapsed-30 3.65 ( 0.00%) 2.27 * 37.62%*
Amean elapsed-48 3.08 ( 0.00%) 2.13 * 30.69%*
Amean elapsed-79 2.00 ( 0.00%) 1.90 * 4.95%*
Amean elapsed-80 2.00 ( 0.00%) 1.90 * 4.70%*This is showing the time to fault regions belonging to threads. The target machine has 80 logical CPUs and two nodes. Note the ~30% gain when the machine is approximately the point where one node becomes fully utilised. The slower results are borderline noise.
Kernel building shows similar benefits around the same balance point. Generally performance was either neutral or better in the tests conducted. The main consideration with this patch is the point where fork stops spreading a task so some workloads may benefit from different balance points but it would be a risky tuning parameter.
--- kernel/sched/fair.c | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-)
kernel/sched/fair.c +16 -2
@@ -1550,6 +1550,7 @@ struct task_numa_env {static unsigned long cpu_load (struct rq *rq);static unsigned long cpu_runnable (struct rq *rq);static unsigned long cpu_util (int cpu); +static inline bool allow_numa_imbalance (int dst_running,int dst_weight);static inline long adjust_numa_imbalance (int imbalance,int dst_running,int dst_weight);
@@ -8893,7 +8894,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 (local_sgs.idle_cpus) +if (allow_numa_imbalance (local_sgs.sum_nr_running, sd->span_weight))return NULL ; }
@@ -8997,14 +8998,27 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd#define NUMA_IMBALANCE_MIN 2 +/* +* 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. +*/ +static inline bool allow_numa_imbalance (int dst_running,int dst_weight) +{ +return (dst_running < (dst_weight >>2 )); +} +static inline long adjust_numa_imbalance (int imbalance,int dst_running,int dst_weight) { +if (!allow_numa_imbalance (dst_running, dst_weight)) +return imbalance; +/* * Allow a small imbalance based on a simple pair of communicating * tasks that remain local when the destination is lightly loaded. */ -if (dst_running < (dst_weight >>2 ) && imbalance <=NUMA_IMBALANCE_MIN ) +if (imbalance <=NUMA_IMBALANCE_MIN )return 0 ;return imbalance;
Signature · 1 line
2.26.2