Messages in this thread Patch in this message | | | Date | Wed, 18 Dec 2019 15:44:02 +0000 | From | Mel Gorman <> | Subject | [PATCH] sched, fair: Allow a small degree of load imbalance between SD_NUMA domains |
| |
The CPU load balancer balances between different domains to spread load and strives to have equal balance everywhere. Communicating tasks can migrate so they are topologically close to each other but these decisions are independent. On a lightly loaded NUMA machine, two communicating tasks pulled together at wakeup time can be pushed apart by the load balancer. In isolation, the load balancer decision is fine but it ignores the tasks data locality and the wakeup/LB paths continually conflict. NUMA balancing is also a factor but it also simply conflicts with the load balancer.
This patch allows a degree of imbalance to exist between NUMA domains based on the imbalance_pct defined by the scheduler domain to take into account that data locality is also important. This slight imbalance is allowed until the scheduler domain reaches almost 50% utilisation at which point other factors like HT utilisation and memory bandwidth come into play. While not commented upon in the code, the cutoff is important for memory-bound parallelised non-communicating workloads that do not fully utilise the entire machine. This is not necessarily the best universal cut-off point but it appeared appropriate for a variety of workloads and machines.
The most obvious impact is on netperf TCP_STREAM -- two simple communicating tasks with some softirq offloaded depending on the transmission rate.
2-socket Haswell machine 48 core, HT enabled netperf-tcp -- mmtests config config-network-netperf-unbound baseline lbnuma-v1 Hmean 64 666.68 ( 0.00%) 669.00 ( 0.35%) Hmean 128 1276.18 ( 0.00%) 1285.59 * 0.74%* Hmean 256 2366.78 ( 0.00%) 2419.42 * 2.22%* Hmean 1024 8123.94 ( 0.00%) 8494.92 * 4.57%* Hmean 2048 12962.45 ( 0.00%) 13430.37 * 3.61%* Hmean 3312 17709.24 ( 0.00%) 17317.23 * -2.21%* Hmean 4096 19756.01 ( 0.00%) 19480.56 ( -1.39%) Hmean 8192 27469.59 ( 0.00%) 27208.17 ( -0.95%) Hmean 16384 30062.82 ( 0.00%) 31135.21 * 3.57%* Stddev 64 2.64 ( 0.00%) 1.19 ( 54.86%) Stddev 128 6.22 ( 0.00%) 0.65 ( 89.51%) Stddev 256 9.75 ( 0.00%) 11.81 ( -21.07%) Stddev 1024 69.62 ( 0.00%) 38.48 ( 44.74%) Stddev 2048 72.73 ( 0.00%) 58.22 ( 19.94%) Stddev 3312 412.35 ( 0.00%) 67.77 ( 83.57%) Stddev 4096 345.02 ( 0.00%) 81.07 ( 76.50%) Stddev 8192 280.09 ( 0.00%) 250.19 ( 10.68%) Stddev 16384 452.99 ( 0.00%) 222.97 ( 50.78%)
Fairly small impact on average performance but note how much the standard deviation is reduced showing much more stable results. A clearer story is visible from the NUMA Balancing stats
Ops NUMA base-page range updates 21596.00 282.00 Ops NUMA PTE updates 21596.00 282.00 Ops NUMA PMD updates 0.00 0.00 Ops NUMA hint faults 17786.00 134.00 Ops NUMA hint local faults % 9916.00 134.00 Ops NUMA hint local percent 55.75 100.00 Ops NUMA pages migrated 4231.00 0.00
Without the patch, only 55.75% of sampled accesses are local. With the patch, 100% of sampled accesses are local. A 2-socket Broadwell showed better results on average but are not presented for brevity. The patch holds up for 4-socket boxes as well
4-socket Haswell machine, 144 core, HT enabled netperf-tcp
baseline lbnuma-v1 Hmean 64 953.51 ( 0.00%) 986.63 * 3.47%* Hmean 128 1826.48 ( 0.00%) 1887.48 * 3.34%* Hmean 256 3295.19 ( 0.00%) 3402.08 * 3.24%* Hmean 1024 10915.40 ( 0.00%) 11482.92 * 5.20%* Hmean 2048 17833.82 ( 0.00%) 19033.89 * 6.73%* Hmean 3312 22690.72 ( 0.00%) 24101.77 * 6.22%* Hmean 4096 24422.23 ( 0.00%) 26665.46 * 9.19%* Hmean 8192 31250.11 ( 0.00%) 33514.74 * 7.25%* Hmean 16384 37033.70 ( 0.00%) 38732.22 * 4.59%*
On this machine, the baseline measured 58.11% locality for sampled accesses and 100% local accesses with the patch. Similarly, the patch holds up for 2-socket machines with multiple L3 caches such as the AMD Epyc 2
2-socket EPYC-2 machine, 256 cores netperf-tcp Hmean 64 1564.63 ( 0.00%) 1550.59 ( -0.90%) Hmean 128 3028.83 ( 0.00%) 3030.48 ( 0.05%) Hmean 256 5733.47 ( 0.00%) 5769.51 ( 0.63%) Hmean 1024 18936.04 ( 0.00%) 19216.15 * 1.48%* Hmean 2048 27589.77 ( 0.00%) 28200.45 * 2.21%* Hmean 3312 35361.97 ( 0.00%) 35881.94 * 1.47%* Hmean 4096 37965.59 ( 0.00%) 38702.01 * 1.94%* Hmean 8192 48499.92 ( 0.00%) 49530.62 * 2.13%* Hmean 16384 54249.96 ( 0.00%) 55937.24 * 3.11%*
For amusement purposes, here are two graphs showing CPU utilisation on the 2-socket Haswell machine over time based on mpstat with the ordering of the CPUs based on topology.
http://www.skynet.ie/~mel/postings/lbnuma-20191218/netperf-tcp-mpstat-baseline.png http://www.skynet.ie/~mel/postings/lbnuma-20191218/netperf-tcp-mpstat-lbnuma-v1r1.png
The lines on the left match up CPUs that are HT siblings or on the same node. The machine has only one L3 cache per NUMA node or that would also be shown. It should be very clear from the images that the baseline kernel spread the load with lighter utilisation across nodes while the patched kernel had heavy utilisation of fewer CPUs on one node.
Hackbench generally shows good results across machines with some differences depending on whether threads or sockets are used as well as pipes or sockets. This is the *worst* result from the 2-socket Haswell machine
2-socket Haswell machine 48 core, HT enabled hackbench-process-pipes -- mmtests config config-scheduler-unbound 5.5.0-rc1 5.5.0-rc1 baseline lbnuma-v1 Amean 1 1.2580 ( 0.00%) 1.2393 ( 1.48%) Amean 4 5.3293 ( 0.00%) 5.2683 * 1.14%* Amean 7 8.9067 ( 0.00%) 8.7130 * 2.17%* Amean 12 14.9577 ( 0.00%) 14.5773 * 2.54%* Amean 21 25.9570 ( 0.00%) 25.6657 * 1.12%* Amean 30 37.7287 ( 0.00%) 37.1277 * 1.59%* Amean 48 61.6757 ( 0.00%) 60.0433 * 2.65%* Amean 79 100.4740 ( 0.00%) 98.4507 ( 2.01%) Amean 110 141.2450 ( 0.00%) 136.8900 * 3.08%* Amean 141 179.7747 ( 0.00%) 174.5110 * 2.93%* Amean 172 221.0700 ( 0.00%) 214.7857 * 2.84%* Amean 192 245.2007 ( 0.00%) 238.3680 * 2.79%*
An earlier prototype of the patch showed major regressions for NAS C-class when running with only half of the available CPUs -- 20-30% performance hits were measured at the time. With this version of the patch, the impact is marginal
NAS-C class OMP -- mmtests config hpc-nas-c-class-omp-half baseline lbnuma-v1 Amean bt.C 64.29 ( 0.00%) 70.31 * -9.36%* Amean cg.C 26.33 ( 0.00%) 25.73 ( 2.31%) Amean ep.C 10.26 ( 0.00%) 10.27 ( -0.10%) Amean ft.C 17.98 ( 0.00%) 19.03 ( -5.84%) Amean is.C 0.99 ( 0.00%) 0.99 ( 0.40%) Amean lu.C 51.72 ( 0.00%) 49.11 ( 5.04%) Amean mg.C 8.12 ( 0.00%) 8.13 ( -0.15%) Amean sp.C 82.76 ( 0.00%) 84.52 ( -2.13%) Amean ua.C 58.64 ( 0.00%) 57.57 ( 1.82%)
There is some impact but there is a degree of variability and the ones showing impact are mainly workloads that are mostly parallelised and communicate infrequently between tests. It's a corner case where the workload benefits heavily from spreading wide and early which is not common. This is intended to illustrate the worst case measured.
In general, the patch simply seeks to avoid unnecessarily cross-node migrations when a machine is lightly loaded but shows benefits for other workloads. While tests are still running, so far it seems to benefit light-utilisation smaller workloads on large machines and does not appear to do any harm to larger or parallelised workloads.
Signed-off-by: Mel Gorman <mgorman@techsingularity.net> --- kernel/sched/fair.c | 38 +++++++++++++++++++++++++++++++++----- 1 file changed, 33 insertions(+), 5 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 08a233e97a01..1dc8c7800fc0 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -8637,10 +8637,6 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s /* * Try to use spare capacity of local group without overloading it or * emptying busiest. - * XXX Spreading tasks across NUMA nodes is not always the best policy - * and special care should be taken for SD_NUMA domain level before - * spreading the tasks. For now, load_balance() fully relies on - * NUMA_BALANCING and fbq_classify_group/rq to override the decision. */ if (local->group_type == group_has_spare) { if (busiest->group_type > group_fully_busy) { @@ -8680,7 +8676,7 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s env->migration_type = migrate_task; lsub_positive(&nr_diff, local->sum_nr_running); env->imbalance = nr_diff >> 1; - return; + goto out_spare; } /* @@ -8690,6 +8686,38 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s env->migration_type = migrate_task; env->imbalance = max_t(long, 0, (local->idle_cpus - busiest->idle_cpus) >> 1); + +out_spare: + /* + * Whether balancing the number of running tasks or the number + * of idle CPUs, consider allowing some degree of imbalance if + * migrating between NUMA domains. + */ + if (env->sd->flags & SD_NUMA) { + unsigned int imbalance_adj, imbalance_max; + + /* + * imbalance_adj is the allowable degree of imbalance + * to exist between two NUMA domains. It's calculated + * relative to imbalance_pct with a minimum of two + * tasks or idle CPUs. + */ + imbalance_adj = (busiest->group_weight * + (env->sd->imbalance_pct - 100) / 100) >> 1; + imbalance_adj = max(imbalance_adj, 2U); + + /* + * Ignore imbalance unless busiest sd is close to 50% + * utilisation. At that point balancing for memory + * bandwidth and potentially avoiding unnecessary use + * of HT siblings is as relevant as memory locality. + */ + imbalance_max = (busiest->group_weight >> 1) - imbalance_adj; + if (env->imbalance <= imbalance_adj && + busiest->sum_nr_running < imbalance_max) { + env->imbalance = 0; + } + } return; } -- Mel Gorman SUSE Labs
| |