sched/fair: Change SIS_PROP to search idle CPU based on sum of util_avg
RFC PATCH v2 1/1 sched/fair: Change SIS_PROP to search idle CPU based on sum of util_avg
[Problem Statement]
Currently select_idle_cpu() uses the percpu average idle time to estimate the total LLC domain idle time, and calculate the number of CPUs to be scanned. This might be inconsistent because idle time of a CPU does not necessarily correlate with idle time of a domain. As a result, the load could be underestimated and causes over searching when the system is very busy.
The following histogram is the time spent in select_idle_cpu(), when running 224 instance of netperf on a system with 112 CPUs per LLC domain:
@usecs:
[0] 533 | | [1] 5495 | | [2, 4) 12008 | | [4, 8) 239252 | | [8, 16) 4041924 |@@@@@@@@@@@@@@ | [16, 32) 12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [32, 64) 14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [64, 128) 13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [128, 256) 8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [256, 512) 4507667 |@@@@@@@@@@@@@@@ | [512, 1K) 2600472 |@@@@@@@@@ | [1K, 2K) 927912 |@@@ | [2K, 4K) 218720 | | [4K, 8K) 98161 | | [8K, 16K) 37722 | | [16K, 32K) 6715 | | [32K, 64K) 477 | | [64K, 128K) 7 | |
netperf latency:
=======
case load Lat_99th std% TCP_RR thread-224 257.39 ( 0.21) UDP_RR thread-224 242.83 ( 6.29)
The netperf 99th latency(usec) above is comparable with the time spent in select_idle_cpu(). That is to say, when the system is overloaded, searching for idle CPU could be a bottleneck.
[Proposal]
The main idea is to replace percpu average idle time with the domain based metric. Choose average CPU utilization(util_avg) as the candidate. In general, the number of CPUs to be scanned should be inversely proportional to the sum of util_avg in this domain. That is, the lower the util_avg is, the more select_idle_cpu() should scan for idle CPU, and vice versa. The benefit of choosing util_avg is that, it is a metric of accumulated historic activity, which seems to be more accurate than instantaneous metrics(such as rq->nr_running).
Furthermore, borrow the util_avg from periodic load balance, which could offload the overhead of select_idle_cpu().
According to last discussion[1], introduced the linear function for experimental purpose:
f(x) = a - bx
llc_size
x = \Sum util_avg[cpu] / llc_cpu_capacity
1
f(x) is the number of CPUs to be scanned, x is the sum util_avg. To decide a and b, the following condition should be met:
[1] f(0) = llc_size
[2] f(x) = 4, x >= 50%
That is to say, when the util_avg is 0, we should search for the whole LLC domain. And if util_avg ratio reaches 50% or higher, it should search at most 4 CPUs.
Yes, there would be questions like:
Why using this linear function to calculate the number of CPUs to be scanned? Why choosing 50% as the threshold? These questions will be discussed in the [Limitations] section.
[Benchmark]
netperf, hackbench, schbench, tbench
were tested with 25% 50% 75% 100% 125% 150% 175% 200% instance of CPU number (these ratios are not CPU utilization). Each test lasts for 100 seconds, and repeats 3 times. The system would reboot into a fresh environment for each benchmark.
The following is the benchmark result comparison between baseline:vanilla and compare:patched kernel. Positive compare% indicates better performance.
netperf
=======
case load baseline(std%) compare%( std%) TCP_RR 28 threads 1.00 ( 0.30) -1.26 ( 0.32) TCP_RR 56 threads 1.00 ( 0.35) -1.26 ( 0.41) TCP_RR 84 threads 1.00 ( 0.46) -0.15 ( 0.60) TCP_RR 112 threads 1.00 ( 0.36) +0.44 ( 0.41) TCP_RR 140 threads 1.00 ( 0.23) +0.95 ( 0.21) TCP_RR 168 threads 1.00 ( 0.20) +177.77 ( 3.78) TCP_RR 196 threads 1.00 ( 0.18) +185.43 ( 10.08) TCP_RR 224 threads 1.00 ( 0.16) +187.86 ( 7.32) UDP_RR 28 threads 1.00 ( 0.43) -0.93 ( 0.27) UDP_RR 56 threads 1.00 ( 0.17) -0.39 ( 10.91) UDP_RR 84 threads 1.00 ( 6.36) +1.03 ( 0.92) UDP_RR 112 threads 1.00 ( 5.55) +1.47 ( 17.67) UDP_RR 140 threads 1.00 ( 18.17) +0.31 ( 15.48) UDP_RR 168 threads 1.00 ( 15.00) +153.87 ( 13.20) UDP_RR 196 threads 1.00 ( 16.26) +169.19 ( 13.78) UDP_RR 224 threads 1.00 ( 51.81) +76.72 ( 10.95)
hackbench
=========
(each group has 1/4 * 112 tasks)
case load baseline(std%) compare%( std%) process-pipe 1 group 1.00 ( 0.47) -0.46 ( 0.16) process-pipe 2 groups 1.00 ( 0.42) -0.61 ( 0.74) process-pipe 3 groups 1.00 ( 0.42) +0.38 ( 0.20) process-pipe 4 groups 1.00 ( 0.15) -0.36 ( 0.56) process-pipe 5 groups 1.00 ( 0.20) -5.08 ( 0.01) process-pipe 6 groups 1.00 ( 0.28) -2.98 ( 0.29) process-pipe 7 groups 1.00 ( 0.08) -1.18 ( 0.28) process-pipe 8 groups 1.00 ( 0.11) -0.40 ( 0.07) process-sockets 1 group 1.00 ( 0.43) -1.93 ( 0.58) process-sockets 2 groups 1.00 ( 0.23) -1.10 ( 0.49) process-sockets 3 groups 1.00 ( 1.10) -0.96 ( 1.12) process-sockets 4 groups 1.00 ( 0.59) -0.08 ( 0.88) process-sockets 5 groups 1.00 ( 0.45) +0.31 ( 0.34) process-sockets 6 groups 1.00 ( 0.23) +0.06 ( 0.66) process-sockets 7 groups 1.00 ( 0.12) +1.72 ( 0.20) process-sockets 8 groups 1.00 ( 0.11) +1.98 ( 0.02) threads-pipe 1 group 1.00 ( 1.07) +0.03 ( 0.40) threads-pipe 2 groups 1.00 ( 1.05) +0.19 ( 1.27) threads-pipe 3 groups 1.00 ( 0.32) -0.42 ( 0.48) threads-pipe 4 groups 1.00 ( 0.42) -0.76 ( 0.79) threads-pipe 5 groups 1.00 ( 0.19) -4.97 ( 0.07) threads-pipe 6 groups 1.00 ( 0.05) -4.11 ( 0.04) threads-pipe 7 groups 1.00 ( 0.10) -1.13 ( 0.16) threads-pipe 8 groups 1.00 ( 0.03) -0.08 ( 0.05) threads-sockets 1 group 1.00 ( 0.33) -1.93 ( 0.69) threads-sockets 2 groups 1.00 ( 0.20) -1.55 ( 0.30) threads-sockets 3 groups 1.00 ( 0.37) -1.29 ( 0.59) threads-sockets 4 groups 1.00 ( 1.83) +0.31 ( 1.17) threads-sockets 5 groups 1.00 ( 0.28) +15.73 ( 0.24) threads-sockets 6 groups 1.00 ( 0.15) +5.02 ( 0.34) threads-sockets 7 groups 1.00 ( 0.10) +2.29 ( 0.14) threads-sockets 8 groups 1.00 ( 0.17) +2.22 ( 0.12)
tbench
======
case load baseline(std%) compare%( std%) loopback 28 threads 1.00 ( 0.05) -1.39 ( 0.04) loopback 56 threads 1.00 ( 0.08) -0.37 ( 0.04) loopback 84 threads 1.00 ( 0.03) +0.20 ( 0.13) loopback 112 threads 1.00 ( 0.04) +0.69 ( 0.04) loopback 140 threads 1.00 ( 0.13) +1.15 ( 0.21) loopback 168 threads 1.00 ( 0.03) +1.62 ( 0.08) loopback 196 threads 1.00 ( 0.08) +1.50 ( 0.30) loopback 224 threads 1.00 ( 0.05) +1.62 ( 0.05)
schbench
========
(each mthread group has 1/4 * 112 tasks)
case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67) normal 2 mthread groups 1.00 ( 21.10) +8.32 ( 16.92) normal 3 mthread groups 1.00 ( 10.80) +10.03 ( 9.21) normal 4 mthread groups 1.00 ( 2.67) +0.11 ( 3.00) normal 5 mthread groups 1.00 ( 0.08) +0.00 ( 0.13) normal 6 mthread groups 1.00 ( 2.99) -2.66 ( 3.87) normal 7 mthread groups 1.00 ( 2.16) -0.83 ( 2.24) normal 8 mthread groups 1.00 ( 1.75) +0.18 ( 3.18)
According to the results above, when the workloads is heavy, the throughput of netperf improves a lot. It might be interesting to look into the reason why this patch benefits netperf significantly. Further investigation has shown that, this might be a 'side effect' of this patch. It is found that, the CPU utilization is around 90% on vanilla kernel, while it is nearly 100% on patched kernel. According to the perf profile, with the patch applied, the scheduler would likely to choose previous running CPU for the waking task, thus reduces runqueue lock contention, so the CPU utilization is higher and get better performance.
[Limitations]
Q:Why using 50% as the util_avg/capacity threshold to search at most 4 CPUs?
A: 50% is chosen as that corresponds to almost full CPU utilization, when
the CPU is fixed to run at its base frequency, with turbo enabled. 4 is the minimal number of CPUs to be scanned in current select_idle_cpu().
A synthetic workload was used to simulate different level of load. This workload takes every 10ms as the sample period, and in each sample period:
while (!timeout_10ms) {
loop(busy_pct_ms);
sleep(10ms-busy_pct_ms)
} to simulate busy_pct% of CPU utilization. When the workload is running, the percpu runqueue util_avg was monitored. The following is the result from turbostat's Busy% on CPU2 and cfs_rq[2].util_avg from /sys/kernel/debug/sched/debug:
Busy% util_avg util_avg/cpu_capacity% 10.06 35 3.42 19.97 99 9.67 29.93 154 15.04 39.86 213 20.80 49.79 256 25.00 59.73 325 31.74 69.77 437 42.68 79.69 458 44.73 89.62 519 50.68 99.54 598 58.39
The reason why util_avg ratio is not consistent with Busy% might be due to CPU frequency invariance. The CPU is running at fixed lower frequency than the turbo frequency, then the util_avg scales lower than SCHED_CAPACITY_SCALE. In our test platform, the base frequency is 1.9GHz, and the max turbo frequency is 3.7GHz, so 1.9/3.7 is around 50%. In the future maybe we could use arch_scale_freq_capacity() instead of sds->total_capacity, so as to remove the impact from frequency. Then the 50% could be adjusted higher. For now, 50% is an aggressive threshold to restric the idle CPU searching and shows benchmark improvement.
Q: Why using nr_scan = a - b * sum_util_avg to do linear search?
A: Ideally the nr_scan could be:
nr_scan = sum_util_avg / pelt_avg_scan_cost
However consider the overhead of calculating pelt on avg_scan_cost in each wake up, choosing heuristic search for evaluation seems to be an acceptable trade-off.
The f(sum_util_avg) could be of any form, as long as it is a monotonically decreasing function. At first f(x) = a - 2^(bx) was chosen. Because when the sum_util_avg is low, the system should try very hard to find an idle CPU. And if sum_util_avg goes higher, the system dramatically lose its interest to search for the idle CPU. But exponential function does have its drawback:
Consider a system with 112 CPUs, let f(x) = 112 when x = 0, f(x) = 4 when x = 50, x belongs to [0, 100], then we have:
f1(x) = 113 - 2^(x / 7.35)
and
f2(x) = 112 - 2.16 * x
Since kernel does not support floating point, above functions are converted into:
nr_scan1(x) = 113 - 2^(x / 7)
and
nr_scan2(x) = 112 - 2 * x
util_avg% 0 1 2 ... 8 9 ... 47 48 49 nr_scan1 112 112 112 111 111 49 49 4 nr_scan2 112 110 108 96 94 18 16 14
According to above result, the granularity of exponential function is coarse-grained, while the linear function is fine-grained.
So finally choose linear function. After all, it has shown benchmark benefit without noticeable regression so far.
Q: How to deal with the following corner case:
It is possible that there is unbalanced tasks among CPUs due to CPU affinity. For example, suppose the LLC domain is composed of 6 CPUs, and 5 tasks are bound to CPU0~CPU4, while CPU5 is idle:
CPU0 CPU1 CPU2 CPU3 CPU4 CPU5
util_avg 1024 1024 1024 1024 1024 0
Since the util_avg ratio is 83%( = 5/6 ), which is higher than 50%, select_idle_cpu() only searches 4 CPUs starting from CPU0, thus leaves idle CPU5 undetected.
A possible workaround to mitigate this problem is that, the nr_scan should be increased by the number of idle CPUs found during periodic load balance in update_sd_lb_stats(). In above example, the nr_scan will be adjusted to 4 + 1 = 5. Currently I don't have better solution in mind to deal with it gracefully.
Any comment is appreciated.
--- include/linux/sched/topology.h | 1 + kernel/sched/fair.c | 107 +++++++++++++++++++-------------- 2 files changed, 63 insertions(+), 45 deletions(-)
include/linux/sched/topology.h +1 -0
@@ -81,6 +81,7 @@ struct sched_domain_shared {atomic_t ref;atomic_t nr_busy_cpus;int has_idle_cores; +int nr_idle_scan; };struct sched_domain {
kernel/sched/fair.c +62 -45
147 lines not on this page · raw message
Signature · 1 line
2.25.1
Hi Chen,
Quoted 52 lines · Chen Yu
[Problem Statement]
Currentlyselect_idle_cpu()uses the percpu average idle time to estimate the total LLC domain idle time, and calculate the number of CPUs to be scanned. This might be inconsistent because idle time of a CPU does not necessarily correlate with idle time of a domain. As a result, the load could be underestimated and causes over searching when the system is very busy.The following histogram is the time spent in
select_idle_cpu(), when running 224 instance of netperf on a system with 112 CPUs per LLC domain:@usecs:
[0] 533 | | [1] 5495 | | [2, 4) 12008 | | [4, 8) 239252 | | [8, 16) 4041924 |@@@@@@@@@@@@@@ | [16, 32) 12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [32, 64) 14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [64, 128) 13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [128, 256) 8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [256, 512) 4507667 |@@@@@@@@@@@@@@@ | [512, 1K) 2600472 |@@@@@@@@@ | [1K, 2K) 927912 |@@@ | [2K, 4K) 218720 | | [4K, 8K) 98161 | | [8K, 16K) 37722 | | [16K, 32K) 6715 | | [32K, 64K) 477 | | [64K, 128K) 7 | |netperf latency:
=======case load Lat_99th std% TCP_RR thread-224 257.39 ( 0.21) UDP_RR thread-224 242.83 ( 6.29)The netperf 99th latency(usec) above is comparable with the time spent in
select_idle_cpu(). That is to say, when the system is overloaded, searching for idle CPU could be a bottleneck.[Proposal]
The main idea is to replace percpu average idle time with the domain based metric. Choose average CPUutilization(util_avg)as the candidate. In general, the number of CPUs to be scanned should be inversely proportional to the sum ofutil_avgin this domain. That is, the lower theutil_avgis, the moreselect_idle_cpu()should scan for idle CPU, and vice versa. The benefit of choosingutil_avgis that, it is a metric of accumulated historic activity, which seems to be more accurate than instantaneousmetrics(such as rq->nr_running).
Quoted 5 lines
Furthermore, borrow the
util_avgfrom periodic load balance, which could offload the overhead ofselect_idle_cpu().According to last discussion[1], introduced the linear function for experimental purpose:
It would be better if you can prove it's a linear model by the SIS efficiency statistics :)
Quoted 326 lines
f(x) = a - bx
llc_size
x = \Sum util_avg[cpu] /llc_cpu_capacity1f(x) is the number of CPUs to be scanned, x is the sum
util_avg. To decide a and b, the following condition should be met:[1] f(0) =
llc_size
[2] f(x) = 4, x >= 50%That is to say, when the
util_avgis 0, we should search for the whole LLC domain. And ifutil_avgratio reaches 50% or higher, it should search at most 4 CPUs.Yes, there would be questions like:
Why using this linear function to calculate the number of CPUs to be scanned? Why choosing 50% as the threshold? These questions will be discussed in the [Limitations] section.[Benchmark]
netperf, hackbench, schbench, tbench
were tested with 25% 50% 75% 100% 125% 150% 175% 200% instance of CPU number (these ratios are not CPU utilization). Each test lasts for 100 seconds, and repeats 3 times. The system would reboot into a fresh environment for each benchmark.The following is the benchmark result comparison between baseline:vanilla and compare:patched kernel. Positive compare% indicates better performance.
netperf
=======case load baseline(std%) compare%( std%) TCP_RR 28 threads 1.00 ( 0.30) -1.26 ( 0.32) TCP_RR 56 threads 1.00 ( 0.35) -1.26 ( 0.41) TCP_RR 84 threads 1.00 ( 0.46) -0.15 ( 0.60) TCP_RR 112 threads 1.00 ( 0.36) +0.44 ( 0.41) TCP_RR 140 threads 1.00 ( 0.23) +0.95 ( 0.21) TCP_RR 168 threads 1.00 ( 0.20) +177.77 ( 3.78) TCP_RR 196 threads 1.00 ( 0.18) +185.43 ( 10.08) TCP_RR 224 threads 1.00 ( 0.16) +187.86 ( 7.32) UDP_RR 28 threads 1.00 ( 0.43) -0.93 ( 0.27) UDP_RR 56 threads 1.00 ( 0.17) -0.39 ( 10.91) UDP_RR 84 threads 1.00 ( 6.36) +1.03 ( 0.92) UDP_RR 112 threads 1.00 ( 5.55) +1.47 ( 17.67) UDP_RR 140 threads 1.00 ( 18.17) +0.31 ( 15.48) UDP_RR 168 threads 1.00 ( 15.00) +153.87 ( 13.20) UDP_RR 196 threads 1.00 ( 16.26) +169.19 ( 13.78) UDP_RR 224 threads 1.00 ( 51.81) +76.72 ( 10.95)hackbench
=========
(each group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) process-pipe 1 group 1.00 ( 0.47) -0.46 ( 0.16) process-pipe 2 groups 1.00 ( 0.42) -0.61 ( 0.74) process-pipe 3 groups 1.00 ( 0.42) +0.38 ( 0.20) process-pipe 4 groups 1.00 ( 0.15) -0.36 ( 0.56) process-pipe 5 groups 1.00 ( 0.20) -5.08 ( 0.01) process-pipe 6 groups 1.00 ( 0.28) -2.98 ( 0.29) process-pipe 7 groups 1.00 ( 0.08) -1.18 ( 0.28) process-pipe 8 groups 1.00 ( 0.11) -0.40 ( 0.07) process-sockets 1 group 1.00 ( 0.43) -1.93 ( 0.58) process-sockets 2 groups 1.00 ( 0.23) -1.10 ( 0.49) process-sockets 3 groups 1.00 ( 1.10) -0.96 ( 1.12) process-sockets 4 groups 1.00 ( 0.59) -0.08 ( 0.88) process-sockets 5 groups 1.00 ( 0.45) +0.31 ( 0.34) process-sockets 6 groups 1.00 ( 0.23) +0.06 ( 0.66) process-sockets 7 groups 1.00 ( 0.12) +1.72 ( 0.20) process-sockets 8 groups 1.00 ( 0.11) +1.98 ( 0.02) threads-pipe 1 group 1.00 ( 1.07) +0.03 ( 0.40) threads-pipe 2 groups 1.00 ( 1.05) +0.19 ( 1.27) threads-pipe 3 groups 1.00 ( 0.32) -0.42 ( 0.48) threads-pipe 4 groups 1.00 ( 0.42) -0.76 ( 0.79) threads-pipe 5 groups 1.00 ( 0.19) -4.97 ( 0.07) threads-pipe 6 groups 1.00 ( 0.05) -4.11 ( 0.04) threads-pipe 7 groups 1.00 ( 0.10) -1.13 ( 0.16) threads-pipe 8 groups 1.00 ( 0.03) -0.08 ( 0.05) threads-sockets 1 group 1.00 ( 0.33) -1.93 ( 0.69) threads-sockets 2 groups 1.00 ( 0.20) -1.55 ( 0.30) threads-sockets 3 groups 1.00 ( 0.37) -1.29 ( 0.59) threads-sockets 4 groups 1.00 ( 1.83) +0.31 ( 1.17) threads-sockets 5 groups 1.00 ( 0.28) +15.73 ( 0.24) threads-sockets 6 groups 1.00 ( 0.15) +5.02 ( 0.34) threads-sockets 7 groups 1.00 ( 0.10) +2.29 ( 0.14) threads-sockets 8 groups 1.00 ( 0.17) +2.22 ( 0.12)tbench
======case load baseline(std%) compare%( std%) loopback 28 threads 1.00 ( 0.05) -1.39 ( 0.04) loopback 56 threads 1.00 ( 0.08) -0.37 ( 0.04) loopback 84 threads 1.00 ( 0.03) +0.20 ( 0.13) loopback 112 threads 1.00 ( 0.04) +0.69 ( 0.04) loopback 140 threads 1.00 ( 0.13) +1.15 ( 0.21) loopback 168 threads 1.00 ( 0.03) +1.62 ( 0.08) loopback 196 threads 1.00 ( 0.08) +1.50 ( 0.30) loopback 224 threads 1.00 ( 0.05) +1.62 ( 0.05)schbench
========
(each mthread group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67) normal 2 mthread groups 1.00 ( 21.10) +8.32 ( 16.92) normal 3 mthread groups 1.00 ( 10.80) +10.03 ( 9.21) normal 4 mthread groups 1.00 ( 2.67) +0.11 ( 3.00) normal 5 mthread groups 1.00 ( 0.08) +0.00 ( 0.13) normal 6 mthread groups 1.00 ( 2.99) -2.66 ( 3.87) normal 7 mthread groups 1.00 ( 2.16) -0.83 ( 2.24) normal 8 mthread groups 1.00 ( 1.75) +0.18 ( 3.18)According to the results above, when the workloads is heavy, the throughput of netperf improves a lot. It might be interesting to look into the reason why this patch benefits netperf significantly. Further investigation has shown that, this might be a 'side effect' of this patch. It is found that, the CPU utilization is around 90% on vanilla kernel, while it is nearly 100% on patched kernel. According to the perf profile, with the patch applied, the scheduler would likely to choose previous running CPU for the waking task, thus reduces runqueue lock contention, so the CPU utilization is higher and get better performance.
[Limitations]
Q:Why using 50% as the util_avg/capacity threshold to search at most 4 CPUs?A: 50% is chosen as that corresponds to almost full CPU utilization, when
the CPU is fixed to run at its base frequency, with turbo enabled. 4 is the minimal number of CPUs to be scanned in currentselect_idle_cpu().A synthetic workload was used to simulate different level of load. This workload takes every 10ms as the sample period, and in each sample period:
while (!timeout_10ms) {
loop(busy_pct_ms);
sleep(10ms-busy_pct_ms)
}to simulate busy_pct% of CPU utilization. When the workload is running, the percpu runqueue
util_avgwas monitored. The following is the result from turbostat's Busy% on CPU2 and cfs_rq[2].util_avg from/sys/kernel/debug/sched/debug:Busy%
util_avgutil_avg/cpu_capacity%
10.06 35 3.42
19.97 99 9.67
29.93 154 15.04
39.86 213 20.80
49.79 256 25.00
59.73 325 31.74
69.77 437 42.68
79.69 458 44.73
89.62 519 50.68
99.54 598 58.39The reason why
util_avgratio is not consistent with Busy% might be due to CPU frequency invariance. The CPU is running at fixed lower frequency than the turbo frequency, then theutil_avgscales lower thanSCHED_CAPACITY_SCALE. In our test platform, the base frequency is 1.9GHz, and the max turbo frequency is 3.7GHz, so 1.9/3.7 is around 50%. In the future maybe we could usearch_scale_freq_capacity()instead ofsds->total_capacity, so as to remove the impact from frequency. Then the 50% could be adjusted higher. For now, 50% is an aggressive threshold to restric the idle CPU searching and shows benchmark improvement.Q: Why using
nr_scan= a - b *sum_util_avgto do linear search?A: Ideally the
nr_scancould be:
nr_scan=sum_util_avg/pelt_avg_scan_costHowever consider the overhead of calculating pelt on
avg_scan_costin each wake up, choosing heuristic search for evaluation seems to be an acceptable trade-off.The
f(sum_util_avg)could be of any form, as long as it is a monotonically decreasing function. At first f(x) = a - 2^(bx) was chosen. Because when thesum_util_avgis low, the system should try very hard to find an idle CPU. And ifsum_util_avggoes higher, the system dramatically lose its interest to search for the idle CPU. But exponential function does have its drawback:Consider a system with 112 CPUs, let f(x) = 112 when x = 0, f(x) = 4 when x = 50, x belongs to [0, 100], then we have:
f1(x) = 113 - 2^(x / 7.35)
and
f2(x) = 112 - 2.16 * xSince kernel does not support floating point, above functions are converted into:
nr_scan1(x)= 113 - 2^(x / 7)
and
nr_scan2(x)= 112 - 2 * xutil_avg% 0 1 2 ... 8 9 ... 47 48 49
nr_scan1112 112 112 111 111 49 49 4
nr_scan2112 110 108 96 94 18 16 14According to above result, the granularity of exponential function is coarse-grained, while the linear function is fine-grained.
So finally choose linear function. After all, it has shown benchmark benefit without noticeable regression so far.
Q: How to deal with the following corner case:
It is possible that there is unbalanced tasks among CPUs due to CPU affinity. For example, suppose the LLC domain is composed of 6 CPUs, and 5 tasks are bound to CPU0~CPU4, while CPU5 is idle:
CPU0 CPU1 CPU2 CPU3 CPU4 CPU5
util_avg1024 1024 1024 1024 1024 0Since the
util_avgratio is 83%( = 5/6 ), which is higher than 50%,select_idle_cpu()only searches 4 CPUs starting from CPU0, thus leaves idle CPU5 undetected.A possible workaround to mitigate this problem is that, the
nr_scanshould be increased by the number of idle CPUs found during periodic load balance inupdate_sd_lb_stats(). In above example, thenr_scanwill be adjusted to 4 + 1 = 5. Currently I don't have better solution in mind to deal with it gracefully.Any comment is appreciated.
Suggested-by Tim Chen <[email protected]>Suggested-by Peter Zijlstra <[email protected]>Signed-off-by Chen Yu <[email protected]>--- include/linux/sched/topology.h | 1 + kernel/sched/fair.c | 107 +++++++++++++++++++-------------- 2 files changed, 63 insertions(+), 45 deletions(-)include/linux/sched/topology.h +1
-0@@ -81,6 +81,7 @@ struct sched_domain_shared {atomic_t ref;atomic_t nr_busy_cpus;int has_idle_cores; +int nr_idle_scan; };struct sched_domain {kernel/sched/fair.c +8
-45@@ -6271,43 +6271,14 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool {struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask);int i, cpu, idle_cpu =-1 , nr =INT_MAX ; -struct rq *this_rq =this_rq (); -int this =smp_processor_id (); -struct sched_domain *this_sd; -u64 time =0 ; - - this_sd =rcu_dereference (*this_cpu_ptr (&sd_llc)); -if (!this_sd) -return -1 ; +struct sched_domain_shared *sd_share;cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr);if (sched_feat (SIS_PROP ) && !has_idle_core) { -u64 avg_cost, avg_idle, span_avg; -unsigned long now = jiffies; - -/* -* If we're busy, the assumption that the last idle period -* predicts the future is flawed; age away the remaining -* predicted idle time. -*/ -if (unlikely (this_rq->wake_stamp < now)) { -while (this_rq->wake_stamp < now && this_rq->wake_avg_idle) { - this_rq->wake_stamp++; - this_rq->wake_avg_idle >>=1 ; - } - } - - avg_idle = this_rq->wake_avg_idle; - avg_cost = this_sd->avg_scan_cost +1 ; - - span_avg = sd->span_weight * avg_idle; -if (span_avg >4 *avg_cost) - nr =div_u64 (span_avg, avg_cost); -else - nr =4 ; - - time =cpu_clock (this); + sd_share =rcu_dereference (per_cpu (sd_llc_shared, target)); +if (sd_share) + nr =READ_ONCE (sd_share->nr_idle_scan); }for_each_cpu_wrap (cpu, cpus, target +1 ) {@@ -6328,18 +6299,6 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, boolif (has_idle_core)set_idle_cores (target, false); -if (sched_feat (SIS_PROP ) && !has_idle_core) { - time =cpu_clock (this) - time; - -/* -* Account for the scan cost of wakeups against the average -* idle time. -*/ - this_rq->wake_avg_idle -=min (this_rq->wake_avg_idle, time); - -update_avg (&this_sd->avg_scan_cost, time); - } -return idle_cpu; }@@ -9199,6 +9158,60 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)return idlest; } +static inline void update_nr_idle_scan (struct lb_env *env,struct sd_lb_stats *sds, +unsigned long sum_util) +{ +struct sched_domain_shared *sd_share;
kernel/sched/fair.c find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu) · line 9174
Quoted 10 lines
kernel/sched/fair.c +10
-0+int llc_size =per_cpu (sd_llc_size, env->dst_cpu); +int nr_scan; + +/* +* Update the number of CPUs to scan in LLC domain, which could +* be used as a hint in select_idle_cpu(). The update of this hint +* occurs during periodic load balancing, rather than frequent +* newidle balance. +*/ +if (env->idle ==CPU_NEWLY_IDLE || env->sd->span_weight != llc_size)
So nr_scan will probably be updated at llc-domain-lb-interval, which is llc_size milliseconds. Since load can be varied a lot during such a period, would this brought accuracy issues?
Best regards
Abel
Quoted 68 lines
kernel/sched/fair.c +44
-0+return ; + + sd_share =rcu_dereference (per_cpu (sd_llc_shared, env->dst_cpu)); +if (!sd_share) +return ; + +/* +* In general, the number of cpus to be scanned should be +* inversely proportional to the sum_util. That is, the lower +* the sum_util is, the harder select_idle_cpu() should scan +* for idle CPU, and vice versa. Let x be the sum_util ratio +* [0-100] of the LLC domain, f(x) be the number of CPUs scanned: +* +* f(x) = a - bx [1] +* +* Consider that f(x) = nr_llc when x = 0, and f(x) = 4 when +* x >= threshold('h' below) then: +* +* a = llc_size; +* b = (nr_llc - 4) / h [2] +* +* then [2] becomes: +* +* f(x) = llc_size - (llc_size -4)x/h [3] +* +* Choose 50 (50%) for h as the threshold from experiment result. +* And since x = 100 * sum_util / total_cap, [3] becomes: +* +* f(sum_util) +* = llc_size - (llc_size - 4) * 100 * sum_util / total_cap * 50 +* = llc_size - (llc_size - 4) * 2 * sum_util / total_cap +* +*/ + nr_scan = llc_size - (llc_size -4 ) *2 * sum_util / sds->total_capacity; +if (nr_scan <4 ) + nr_scan =4 ; + +WRITE_ONCE (sd_share->nr_idle_scan, nr_scan); +} +/** * update_sd_lb_stats - Update sched_domain's statistics for load balancing. * @env: The load balancing environment. @@ -9212,6 +9225,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdstruct sg_lb_stats *local = &sds->local_stat;struct sg_lb_stats tmp_sgs;int sg_status =0 ; +unsigned long sum_util =0 ; do { struct sg_lb_stats *sgs = &tmp_sgs;@@ -9242,6 +9256,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd/* Now, start updating sd_lb_stats */ sds->total_load += sgs->group_load; sds->total_capacity += sgs->group_capacity; + sum_util += sgs->group_util; sg = sg->next; }while (sg != env->sd->groups);@@ -9268,6 +9283,8 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdWRITE_ONCE (rd->overutilized,SG_OVERUTILIZED );trace_sched_overutilized_tp (rd,SG_OVERUTILIZED ); } + +update_nr_idle_scan (env, sds, sum_util); }#define NUMA_IMBALANCE_MIN 2
Hi Abel,
Quoted 55 lines · Abel Wu
Hi Chen,
Quoted 52 lines · Chen Yu
[Problem Statement]
Currentlyselect_idle_cpu()uses the percpu average idle time to estimate the total LLC domain idle time, and calculate the number of CPUs to be scanned. This might be inconsistent because idle time of a CPU does not necessarily correlate with idle time of a domain. As a result, the load could be underestimated and causes over searching when the system is very busy.The following histogram is the time spent in
select_idle_cpu(), when running 224 instance of netperf on a system with 112 CPUs per LLC domain:@usecs:
[0] 533 | | [1] 5495 | | [2, 4) 12008 | | [4, 8) 239252 | | [8, 16) 4041924 |@@@@@@@@@@@@@@ | [16, 32) 12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [32, 64) 14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [64, 128) 13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [128, 256) 8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [256, 512) 4507667 |@@@@@@@@@@@@@@@ | [512, 1K) 2600472 |@@@@@@@@@ | [1K, 2K) 927912 |@@@ | [2K, 4K) 218720 | | [4K, 8K) 98161 | | [8K, 16K) 37722 | | [16K, 32K) 6715 | | [32K, 64K) 477 | | [64K, 128K) 7 | |netperf latency:
=======case load Lat_99th std% TCP_RR thread-224 257.39 ( 0.21) UDP_RR thread-224 242.83 ( 6.29)The netperf 99th latency(usec) above is comparable with the time spent in
select_idle_cpu(). That is to say, when the system is overloaded, searching for idle CPU could be a bottleneck.[Proposal]
The main idea is to replace percpu average idle time with the domain based metric. Choose average CPUutilization(util_avg)as the candidate. In general, the number of CPUs to be scanned should be inversely proportional to the sum ofutil_avgin this domain. That is, the lower theutil_avgis, the moreselect_idle_cpu()should scan for idle CPU, and vice versa. The benefit of choosingutil_avgis that, it is a metric of accumulated historic activity, which seems to be more accurate than instantaneousmetrics(such as rq->nr_running).
Quoted 9 lines
Quoted 5 lines
Furthermore, borrow the
util_avgfrom periodic load balance, which could offload the overhead ofselect_idle_cpu().According to last discussion[1], introduced the linear function for experimental purpose:
It would be better if you can prove it's a linear model by the SIS efficiency statistics :)
Thanks for your comments!
Good point, the SIS efficiency could be used to verify if the real search number fitting this linear mode well, I'll collect this statistics. But TBH I'm not sure whether there is a convergent/accurate mapping between the sum of util_avg and the number of CPUs to be scanned(unless we use sum_util/pelt_scan_cost to approach it). Choosing a model seems to always be a heuristic search policy.
Quoted 12 lines
Quoted 12 lines
f(x) = a - bx
llc_size
x = \Sum util_avg[cpu] /llc_cpu_capacity1f(x) is the number of CPUs to be scanned, x is the sum
util_avg. To decide a and b, the following condition should be met:[1] f(0) =
llc_size
[2] f(x) = 4, x >= 50%
Quoted 8 lines
kernel/sched/fair.c find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu) · line 9174
Quoted 3 lines
kernel/sched/fair.c +3
-0+* newidle balance. +*/ +if (env->idle ==CPU_NEWLY_IDLE || env->sd->span_weight != llc_size)So
nr_scanwill probably be updated at llc-domain-lb-interval, which isllc_sizemilliseconds. Since load can be varied a lot during such a period, would this brought accuracy issues?
I agree there might be delay in reflecting the latest utilization. The sum_util calculated by periodic load balance after 112ms would be decay to about 0.5 * 0.5 * 0.5 * 0.7 = 8.75%.
But consider that this is a server platform, I have an impression that the CPU utilization jitter during a small period of time is not a regular scenario? It seems to be a trade-off. Checking the util_avg in newidle load balance path would be more frequent, but it also brings overhead - multiple CPUs write/read the per-LLC shared variable and introduces cache false sharing. But to make this more robust, maybe we can add time interval control in newidle load balance too.
thanks,
Chenyu
Quoted 2 lines
Best regards
Abel
Quoted 6 lines · Chen Yu
Quoted 6 lines
So
nr_scanwill probably be updated at llc-domain-lb-interval, which isllc_sizemilliseconds. Since load can be varied a lot during such a period, would this brought accuracy issues?
Quoted 12 lines
I agree there might be delay in reflecting the latest utilization. The
sum_utilcalculated by periodic load balance after 112ms would be decay to about 0.5 * 0.5 * 0.5 * 0.7 = 8.75%.
But consider that this is a server platform, I have an impression that the CPU utilization jitter during a small period of time is not a regular scenario? It seems to be a trade-off. Checking theutil_avgin newidle load balance path would be more frequent, but it also brings overhead - multiple CPUs write/read the per-LLC shared variable and introduces cache false sharing. But to make this more robust, maybe we can add time interval control in newidle load balance too.
Also the idea is we allow ourselves to be non-optimal in terms of scheduling for the short term variations. But we want to make sure that if there's a long term trend in the load behavior, the scheduler should adjust for that. I think if you see high utilization and CPUs are all close to fully busy for quite a while, that is a long term trend that overwhelms any short load jitters.
Tim
Quoted 20 lines · Tim Chen
Quoted 6 lines · Chen Yu
Quoted 6 lines
So
nr_scanwill probably be updated at llc-domain-lb-interval, which isllc_sizemilliseconds. Since load can be varied a lot during such a period, would this brought accuracy issues?Quoted 12 lines
I agree there might be delay in reflecting the latest utilization. The
sum_utilcalculated by periodic load balance after 112ms would be decay to about 0.5 * 0.5 * 0.5 * 0.7 = 8.75%.
But consider that this is a server platform, I have an impression that the CPU utilization jitter during a small period of time is not a regular scenario? It seems to be a trade-off. Checking theutil_avgin newidle load balance path would be more frequent, but it also brings overhead - multiple CPUs write/read the per-LLC shared variable and introduces cache false sharing. But to make this more robust, maybe we can add time interval control in newidle load balance too.
Quoted 7 lines
Also the idea is we allow ourselves to be non-optimal in terms of scheduling for the short term variations. But we want to make sure that if there's a long term trend in the load behavior, the scheduler should adjust for that. I think if you see high utilization and CPUs are all close to fully busy for quite a while, that is a long term trend that overwhelms any short load jitters.
Agree. From long term trend, the scheduler should approach an optimization status.
thanks,
Chenyu
Quoted 2 lines
Tim
K Prateek Nayak
reviewerHello Chenyu,
Quoted 161 lines · Chen Yu
[Problem Statement]
Currentlyselect_idle_cpu()uses the percpu average idle time to estimate the total LLC domain idle time, and calculate the number of CPUs to be scanned. This might be inconsistent because idle time of a CPU does not necessarily correlate with idle time of a domain. As a result, the load could be underestimated and causes over searching when the system is very busy.The following histogram is the time spent in
select_idle_cpu(), when running 224 instance of netperf on a system with 112 CPUs per LLC domain:@usecs:
[0] 533 | | [1] 5495 | | [2, 4) 12008 | | [4, 8) 239252 | | [8, 16) 4041924 |@@@@@@@@@@@@@@ | [16, 32) 12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [32, 64) 14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [64, 128) 13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [128, 256) 8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [256, 512) 4507667 |@@@@@@@@@@@@@@@ | [512, 1K) 2600472 |@@@@@@@@@ | [1K, 2K) 927912 |@@@ | [2K, 4K) 218720 | | [4K, 8K) 98161 | | [8K, 16K) 37722 | | [16K, 32K) 6715 | | [32K, 64K) 477 | | [64K, 128K) 7 | |netperf latency:
=======case load Lat_99th std% TCP_RR thread-224 257.39 ( 0.21) UDP_RR thread-224 242.83 ( 6.29)The netperf 99th latency(usec) above is comparable with the time spent in
select_idle_cpu(). That is to say, when the system is overloaded, searching for idle CPU could be a bottleneck.[Proposal]
The main idea is to replace percpu average idle time with the domain based metric. Choose average CPUutilization(util_avg)as the candidate. In general, the number of CPUs to be scanned should be inversely proportional to the sum ofutil_avgin this domain. That is, the lower theutil_avgis, the moreselect_idle_cpu()should scan for idle CPU, and vice versa. The benefit of choosingutil_avgis that, it is a metric of accumulated historic activity, which seems to be more accurate than instantaneousmetrics(such as rq->nr_running).Furthermore, borrow the
util_avgfrom periodic load balance, which could offload the overhead ofselect_idle_cpu().According to last discussion[1], introduced the linear function for experimental purpose:
f(x) = a - bx
llc_size
x = \Sum util_avg[cpu] /llc_cpu_capacity1f(x) is the number of CPUs to be scanned, x is the sum
util_avg. To decide a and b, the following condition should be met:[1] f(0) =
llc_size
[2] f(x) = 4, x >= 50%That is to say, when the
util_avgis 0, we should search for the whole LLC domain. And ifutil_avgratio reaches 50% or higher, it should search at most 4 CPUs.Yes, there would be questions like:
Why using this linear function to calculate the number of CPUs to be scanned? Why choosing 50% as the threshold? These questions will be discussed in the [Limitations] section.[Benchmark]
netperf, hackbench, schbench, tbench
were tested with 25% 50% 75% 100% 125% 150% 175% 200% instance of CPU number (these ratios are not CPU utilization). Each test lasts for 100 seconds, and repeats 3 times. The system would reboot into a fresh environment for each benchmark.The following is the benchmark result comparison between baseline:vanilla and compare:patched kernel. Positive compare% indicates better performance.
netperf
=======case load baseline(std%) compare%( std%) TCP_RR 28 threads 1.00 ( 0.30) -1.26 ( 0.32) TCP_RR 56 threads 1.00 ( 0.35) -1.26 ( 0.41) TCP_RR 84 threads 1.00 ( 0.46) -0.15 ( 0.60) TCP_RR 112 threads 1.00 ( 0.36) +0.44 ( 0.41) TCP_RR 140 threads 1.00 ( 0.23) +0.95 ( 0.21) TCP_RR 168 threads 1.00 ( 0.20) +177.77 ( 3.78) TCP_RR 196 threads 1.00 ( 0.18) +185.43 ( 10.08) TCP_RR 224 threads 1.00 ( 0.16) +187.86 ( 7.32) UDP_RR 28 threads 1.00 ( 0.43) -0.93 ( 0.27) UDP_RR 56 threads 1.00 ( 0.17) -0.39 ( 10.91) UDP_RR 84 threads 1.00 ( 6.36) +1.03 ( 0.92) UDP_RR 112 threads 1.00 ( 5.55) +1.47 ( 17.67) UDP_RR 140 threads 1.00 ( 18.17) +0.31 ( 15.48) UDP_RR 168 threads 1.00 ( 15.00) +153.87 ( 13.20) UDP_RR 196 threads 1.00 ( 16.26) +169.19 ( 13.78) UDP_RR 224 threads 1.00 ( 51.81) +76.72 ( 10.95)hackbench
=========
(each group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) process-pipe 1 group 1.00 ( 0.47) -0.46 ( 0.16) process-pipe 2 groups 1.00 ( 0.42) -0.61 ( 0.74) process-pipe 3 groups 1.00 ( 0.42) +0.38 ( 0.20) process-pipe 4 groups 1.00 ( 0.15) -0.36 ( 0.56) process-pipe 5 groups 1.00 ( 0.20) -5.08 ( 0.01) process-pipe 6 groups 1.00 ( 0.28) -2.98 ( 0.29) process-pipe 7 groups 1.00 ( 0.08) -1.18 ( 0.28) process-pipe 8 groups 1.00 ( 0.11) -0.40 ( 0.07) process-sockets 1 group 1.00 ( 0.43) -1.93 ( 0.58) process-sockets 2 groups 1.00 ( 0.23) -1.10 ( 0.49) process-sockets 3 groups 1.00 ( 1.10) -0.96 ( 1.12) process-sockets 4 groups 1.00 ( 0.59) -0.08 ( 0.88) process-sockets 5 groups 1.00 ( 0.45) +0.31 ( 0.34) process-sockets 6 groups 1.00 ( 0.23) +0.06 ( 0.66) process-sockets 7 groups 1.00 ( 0.12) +1.72 ( 0.20) process-sockets 8 groups 1.00 ( 0.11) +1.98 ( 0.02) threads-pipe 1 group 1.00 ( 1.07) +0.03 ( 0.40) threads-pipe 2 groups 1.00 ( 1.05) +0.19 ( 1.27) threads-pipe 3 groups 1.00 ( 0.32) -0.42 ( 0.48) threads-pipe 4 groups 1.00 ( 0.42) -0.76 ( 0.79) threads-pipe 5 groups 1.00 ( 0.19) -4.97 ( 0.07) threads-pipe 6 groups 1.00 ( 0.05) -4.11 ( 0.04) threads-pipe 7 groups 1.00 ( 0.10) -1.13 ( 0.16) threads-pipe 8 groups 1.00 ( 0.03) -0.08 ( 0.05) threads-sockets 1 group 1.00 ( 0.33) -1.93 ( 0.69) threads-sockets 2 groups 1.00 ( 0.20) -1.55 ( 0.30) threads-sockets 3 groups 1.00 ( 0.37) -1.29 ( 0.59) threads-sockets 4 groups 1.00 ( 1.83) +0.31 ( 1.17) threads-sockets 5 groups 1.00 ( 0.28) +15.73 ( 0.24) threads-sockets 6 groups 1.00 ( 0.15) +5.02 ( 0.34) threads-sockets 7 groups 1.00 ( 0.10) +2.29 ( 0.14) threads-sockets 8 groups 1.00 ( 0.17) +2.22 ( 0.12)tbench
======case load baseline(std%) compare%( std%) loopback 28 threads 1.00 ( 0.05) -1.39 ( 0.04) loopback 56 threads 1.00 ( 0.08) -0.37 ( 0.04) loopback 84 threads 1.00 ( 0.03) +0.20 ( 0.13) loopback 112 threads 1.00 ( 0.04) +0.69 ( 0.04) loopback 140 threads 1.00 ( 0.13) +1.15 ( 0.21) loopback 168 threads 1.00 ( 0.03) +1.62 ( 0.08) loopback 196 threads 1.00 ( 0.08) +1.50 ( 0.30) loopback 224 threads 1.00 ( 0.05) +1.62 ( 0.05)schbench
========
(each mthread group has 1/4 * 112 tasks)
Quoted 9 lines
case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67) normal 2 mthread groups 1.00 ( 21.10) +8.32 ( 16.92) normal 3 mthread groups 1.00 ( 10.80) +10.03 ( 9.21) normal 4 mthread groups 1.00 ( 2.67) +0.11 ( 3.00) normal 5 mthread groups 1.00 ( 0.08) +0.00 ( 0.13) normal 6 mthread groups 1.00 ( 2.99) -2.66 ( 3.87) normal 7 mthread groups 1.00 ( 2.16) -0.83 ( 2.24) normal 8 mthread groups 1.00 ( 1.75) +0.18 ( 3.18)
Following are the results on benchmarks from Zen3 system (2 x 64C/128T) on different NPS modes.
NPS Configurations:
NPS Modes are used to logically divide single socket into multiple NUMA region.
Following is the NUMA configuration for each NPS mode on the system:
NPS1: Each socket is a NUMA node.
Total 2 NUMA nodes in the dual socket machine.
Node 0: 0-63, 128-191
Node 1: 64-127, 192-255
NPS2: Each socket is further logically divided into 2 NUMA regions. Total 4 NUMA nodes exist over 2 socket.
Node 0: 0-31, 128-159
Node 1: 32-63, 160-191
Node 2: 64-95, 192-223
Node 3: 96-127, 223-255
NPS4: Each socket is logically divided into 4 NUMA regions. Total 8 NUMA nodes exist over 2 socket.
Node 0: 0-15, 128-143
Node 1: 16-31, 144-159
Node 2: 32-47, 160-175
Node 3: 48-63, 176-191
Node 4: 64-79, 192-207
Node 5: 80-95, 208-223
Node 6: 96-111, 223-231
Node 7: 112-127, 232-255
Benchmark Results:
Kernel versions:
- sched-tip: 5.17-rc5 tip sched/core
- v2_sis_prop: 5.17-rc5 tip sched/core + this patch
~~~~~~~~~
hackbench
~~~~~~~~~
NPS1
Test: sched-tip v2_sis_prop 1-groups: 5.05 (0.00 pct) 5.00 (0.99 pct) 2-groups: 5.72 (0.00 pct) 5.63 (1.57 pct) 4-groups: 6.34 (0.00 pct) 6.21 (2.05 pct) 8-groups: 7.89 (0.00 pct) 7.80 (1.14 pct) 16-groups: 11.80 (0.00 pct) 11.62 (1.52 pct)
NPS2
Test: sched-tip v2_sis_prop 1-groups: 4.94 (0.00 pct) 4.93 (0.20 pct) 2-groups: 5.64 (0.00 pct) 5.55 (1.59 pct) 4-groups: 6.23 (0.00 pct) 6.07 (2.56 pct) 8-groups: 7.70 (0.00 pct) 7.46 (3.11 pct) 16-groups: 10.49 (0.00 pct) 10.12 (3.52 pct)
NPS4
Test: sched-tip v2_sis_prop 1-groups: 4.89 (0.00 pct) 4.97 (-1.63 pct) 2-groups: 5.43 (0.00 pct) 5.48 (-0.92 pct) 4-groups: 6.15 (0.00 pct) 6.21 (-0.97 pct) 8-groups: 7.54 (0.00 pct) 8.07 (-7.02 pct) 16-groups: 10.20 (0.00 pct) 10.13 ( 0.68 pct)
~~~~~~~~
schbench
~~~~~~~~
NPS 1
#workers: sched-tip v2_sis_prop 1: 13.00 (0.00 pct) 14.50 (-11.53 pct) 2: 31.50 (0.00 pct) 35.00 (-11.11 pct) 4: 43.00 (0.00 pct) 44.50 (-3.48 pct) 8: 52.50 (0.00 pct) 52.00 (0.95 pct) 16: 69.00 (0.00 pct) 68.00 (1.44 pct) 32: 108.50 (0.00 pct) 108.50 (0.00 pct) 64: 195.00 (0.00 pct) 192.50 (1.28 pct) 128: 395.50 (0.00 pct) 399.00 (-0.88 pct) 256: 950.00 (0.00 pct) 944.00 (0.63 pct) 512: 60352.00 (0.00 pct) 60608.00 (-0.42 pct)
NPS2
#workers: sched-tip v2_sis_prop 1: 10.00 (0.00 pct) 10.00 (0.00 pct) 2: 25.00 (0.00 pct) 28.00 (-12.00 pct) 4: 37.00 (0.00 pct) 37.50 (-1.35 pct) 8: 50.50 (0.00 pct) 52.50 (-3.96 pct) 16: 65.50 (0.00 pct) 67.50 (-3.05 pct) 32: 104.00 (0.00 pct) 104.50 (-0.48 pct) 64: 190.00 (0.00 pct) 186.50 (1.84 pct) 128: 394.50 (0.00 pct) 398.50 (-1.01 pct) 256: 959.00 (0.00 pct) 979.00 (-2.08 pct) 512: 60352.00 (0.00 pct) 60480.00 (-0.21 pct)
NPS4
#workers: sched-tip v2_sis_prop 1: 9.50 (0.00 pct) 10.00 (-5.26 pct) 2: 28.00 (0.00 pct) 30.00 (-7.14 pct) 4: 32.00 (0.00 pct) 36.50 (-14.06 pct) 8: 42.00 (0.00 pct) 43.00 (-2.38 pct) 16: 68.00 (0.00 pct) 75.50 (-11.02 pct) 32: 104.50 (0.00 pct) 106.50 (-1.91 pct) 64: 186.00 (0.00 pct) 191.50 (-2.95 pct) 128: 382.50 (0.00 pct) 392.50 (-2.61 pct) 256: 966.00 (0.00 pct) 963.00 (0.31 pct) 512: 60480.00 (0.00 pct) 60416.00 (0.10 pct)
~~~~~~
tbench
~~~~~~
NPS 1
Clients: sched-tip v2_sis_prop 1 477.85 (0.00 pct) 470.68 (-1.50 pct) 2 924.07 (0.00 pct) 910.82 (-1.43 pct) 4 1778.95 (0.00 pct) 1743.64 (-1.98 pct) 8 3244.81 (0.00 pct) 3200.35 (-1.37 pct) 16 5837.06 (0.00 pct) 5808.36 (-0.49 pct) 32 9339.33 (0.00 pct) 8648.03 (-7.40 pct) 64 14761.19 (0.00 pct) 15803.13 (7.05 pct) 128 27806.11 (0.00 pct) 27510.69 (-1.06 pct) 256 35262.03 (0.00 pct) 34135.78 (-3.19 pct) 512 52459.78 (0.00 pct) 51630.53 (-1.58 pct) 1024 52480.67 (0.00 pct) 52439.37 (-0.07 pct)
NPS 2
Clients: sched-tip v2_sis_prop 1 478.98 (0.00 pct) 472.98 (-1.25 pct) 2 930.52 (0.00 pct) 914.48 (-1.72 pct) 4 1743.26 (0.00 pct) 1711.16 (-1.84 pct) 8 3297.07 (0.00 pct) 3161.12 (-4.12 pct) 16 5779.10 (0.00 pct) 5738.38 (-0.70 pct) 32 10708.42 (0.00 pct) 10748.26 (0.37 pct) 64 16965.21 (0.00 pct) 16894.42 (-0.41 pct) 128 29152.49 (0.00 pct) 28287.31 (-2.96 pct) 256 27408.75 (0.00 pct) 33680.59 (22.88 pct) 512 51453.64 (0.00 pct) 47546.87 (-7.59 pct) 1024 52156.85 (0.00 pct) 51233.28 (-1.77 pct)
NPS 4
Clients: sched-tip v2_sis_prop 1 480.29 (0.00 pct) 473.75 (-1.36 pct) 2 940.23 (0.00 pct) 915.60 (-2.61 pct) 4 1760.21 (0.00 pct) 1687.99 (-4.10 pct) 8 3269.75 (0.00 pct) 3154.02 (-3.53 pct) 16 5503.71 (0.00 pct) 5485.01 (-0.33 pct) 32 10633.93 (0.00 pct) 10276.21 (-3.36 pct) 64 16304.44 (0.00 pct) 15351.17 (-5.84 pct) 128 26893.95 (0.00 pct) 25337.08 (-5.78 pct) 256 24469.94 (0.00 pct) 32178.33 (31.50 pct) 512 46343.65 (0.00 pct) 49607.28 (7.04 pct) 1024 51496.80 (0.00 pct) 51791.27 (0.57 pct)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Stream with 16 threads.
built with -DSTREAM_ARRAY_SIZE=128000000, -DNTIMES=10
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
NPS1
Test: sched-tip v2_sis_prop Copy: 204020.95 (0.00 pct) 211802.20 (3.81 pct) Scale: 208261.03 (0.00 pct) 210809.40 (1.22 pct) Add: 243944.45 (0.00 pct) 249801.81 (2.40 pct) Triad: 237033.90 (0.00 pct) 242273.45 (2.21 pct)
NPS2
Test: sched-tip v2_sis_prop Copy: 171679.21 (0.00 pct) 153853.24 (-10.38 pct) Scale: 191362.43 (0.00 pct) 188219.32 (-1.64 pct) Add: 218986.47 (0.00 pct) 204766.66 (-6.49 pct) Triad: 215118.01 (0.00 pct) 202370.69 (-5.92 pct)
NPS4
Test: sched-tip v2_sis_prop Copy: 133829.00 (0.00 pct) 125722.97 (-6.05 pct) Scale: 192074.89 (0.00 pct) 187164.95 (-2.55 pct) Add: 186288.73 (0.00 pct) 175316.23 (-5.89 pct) Triad: 185469.53 (0.00 pct) 175985.74 (-5.11 pct)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Stream with 16 threads.
built with -DSTREAM_ARRAY_SIZE=128000000, -DNTIMES=100
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
NPS1
Test: sched-tip v2_sis_prop Copy: 217592.30 (0.00 pct) 231684.51 (6.47 pct) Scale: 217269.78 (0.00 pct) 218632.93 (0.62 pct) Add: 265842.95 (0.00 pct) 266692.50 (0.31 pct) Triad: 252647.10 (0.00 pct) 253462.69 (0.32 pct)
NPS2
Test: sched-tip v2_sis_prop Copy: 226948.55 (0.00 pct) 242576.78 (6.88 pct) Scale: 217968.87 (0.00 pct) 220613.96 (1.21 pct) Add: 274839.22 (0.00 pct) 277389.36 (0.92 pct) Triad: 261920.73 (0.00 pct) 263849.95 (0.73 pct)
NPS4
Test: sched-tip v2_sis_prop Copy: 256162.84 (0.00 pct) 238881.35 (-6.74 pct) Scale: 228251.12 (0.00 pct) 228669.16 (0.18 pct) Add: 292794.77 (0.00 pct) 293700.42 (0.30 pct) Triad: 274152.69 (0.00 pct) 274900.77 (0.27 pct)
~~~~~~~~~~~~
ycsb-mongodb
~~~~~~~~~~~~
NPS1
sched-tip: 304934.67 (var: 0.88)
v2_sis_prop: 301560.0 (var: 2.0) (-1.1%)
NPS2
sched-tip: 303757.0 (var: 1.0)
v2_sis_prop: 302283.0 (var: 0.58) (-0.48%)
NPS4
sched-tip: 308106.67 (var: 2.88)
v2_sis_prop: 302302.67 (var: 1.12) (-1.88%)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
schbench, tbench - System 50% loaded to fully loaded
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~
schbench
~~~~~~~~
NPS1
#workers: sched-tip v2_sis_prop 128: 395.50 (0.00 pct) 399.00 (-0.88 pct) 144: 441.50 (0.00 pct) 450.00 (-1.92 pct) 160: 488.00 (0.00 pct) 513.00 (-5.12 pct) 176: 549.00 (0.00 pct) 547.00 (0.36 pct) 192: 601.00 (0.00 pct) 589.00 (1.99 pct) 208: 653.00 (0.00 pct) 736.00 (-12.71 pct) 224: 740.00 (0.00 pct) 757.00 (-2.29 pct) 240: 835.00 (0.00 pct) 808.00 (3.23 pct) 256: 950.00 (0.00 pct) 944.00 (0.63 pct)
NPS2:
#workers: sched-tip v2_sis_prop 128: 394.50 (0.00 pct) 398.50 (-1.01 pct) 144: 454.50 (0.00 pct) 443.50 (2.42 pct) 160: 500.00 (0.00 pct) 494.00 (1.20 pct) 176: 547.00 (0.00 pct) 530.00 (3.10 pct) 192: 595.00 (0.00 pct) 609.00 (-2.35 pct) 208: 739.00 (0.00 pct) 738.00 (0.13 pct) 224: 781.00 (0.00 pct) 794.00 (-1.66 pct) 240: 894.00 (0.00 pct) 890.00 (0.44 pct) 256: 959.00 (0.00 pct) 979.00 (-2.08 pct)
NPS4
#workers: sched-tip v2_sis_prop 128: 382.50 (0.00 pct) 392.50 (-2.61 pct) 144: 451.50 (0.00 pct) 459.00 (-1.66 pct) 160: 491.00 (0.00 pct) 497.00 (-1.22 pct) 176: 578.00 (0.00 pct) 564.00 (2.42 pct) 192: 593.00 (0.00 pct) 612.00 (-3.20 pct) 208: 737.00 (0.00 pct) 720.00 (2.30 pct) 224: 786.00 (0.00 pct) 796.00 (-1.27 pct) 240: 893.00 (0.00 pct) 890.00 (0.33 pct) 256: 966.00 (0.00 pct) 963.00 (0.31 pct)
~~~~~~
tbench
~~~~~~
NPS1
Clients: sched-tip v2_sis_prop 128 28369.07 (0.00 pct) 25649.26 (-9.58 pct) 144 25794.95 (0.00 pct) 25464.33 (-1.28 pct) 160 23905.48 (0.00 pct) 23507.18 (-1.66 pct) 176 24219.13 (0.00 pct) 22664.99 (-6.41 pct) 192 23978.71 (0.00 pct) 22506.50 (-6.13 pct) 208 24045.91 (0.00 pct) 22592.62 (-6.04 pct) 224 21961.21 (0.00 pct) 22154.28 (0.87 pct) 240 22001.05 (0.00 pct) 26245.06 (19.29 pct) 256 26866.60 (0.00 pct) 33064.10 (23.06 pct)
NPS2
Clients: sched-tip v2_sis_prop 128 25229.75 (0.00 pct) 26396.32 (4.62 pct) 144 27488.16 (0.00 pct) 24596.76 (-10.51 pct) 160 23765.03 (0.00 pct) 23945.55 (0.75 pct) 176 22230.05 (0.00 pct) 22207.84 (-0.09 pct) 192 21383.39 (0.00 pct) 22385.72 (4.68 pct) 208 23920.96 (0.00 pct) 22323.24 (-6.67 pct) 224 22212.38 (0.00 pct) 24108.90 (8.53 pct) 240 22143.36 (0.00 pct) 25655.54 (15.86 pct) 256 29923.16 (0.00 pct) 32570.60 (8.84 pct)
NPS4
Clients: sched-tip v2_sis_prop 128 26336.35 (0.00 pct) 24604.90 (-6.57 pct) 144 24469.64 (0.00 pct) 24685.57 (0.88 pct) 160 23742.98 (0.00 pct) 23381.86 (-1.52 pct) 176 22512.46 (0.00 pct) 22602.49 (0.39 pct) 192 21141.71 (0.00 pct) 22752.25 (7.61 pct) 208 21803.07 (0.00 pct) 22280.24 (2.18 pct) 224 21174.10 (0.00 pct) 23582.49 (11.37 pct) 240 21510.36 (0.00 pct) 26295.92 (22.24 pct) 256 25170.50 (0.00 pct) 34215.08 (35.93 pct)
Hackbench shows improvements in NPS1 and NPS2 modes. tbench sees good improvement when system is close to fully loaded. Stream values are very close to the baseline. YCSB MongoDB shows slight regression and schbench is a mixed bag.
This strategy would probably work better on systems with large number of CPUs per LLC but from our observations, I believe it is worthwhile to search for an idle CPUs in the entire LLC on Zen3 systems as we have 16 CPUs per LLC.
Only when the system is close to fully loaded, we see a good uplift by not searching the entire LLC in tbench which is what we saw with the v1 too. --
Thanks and Regards,
Prateek
Hi Prateek,
Quoted 173 lines · K Prateek Nayak
Hello Chenyu,
Quoted 161 lines · Chen Yu
[Problem Statement]
Currentlyselect_idle_cpu()uses the percpu average idle time to estimate the total LLC domain idle time, and calculate the number of CPUs to be scanned. This might be inconsistent because idle time of a CPU does not necessarily correlate with idle time of a domain. As a result, the load could be underestimated and causes over searching when the system is very busy.The following histogram is the time spent in
select_idle_cpu(), when running 224 instance of netperf on a system with 112 CPUs per LLC domain:@usecs:
[0] 533 | | [1] 5495 | | [2, 4) 12008 | | [4, 8) 239252 | | [8, 16) 4041924 |@@@@@@@@@@@@@@ | [16, 32) 12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [32, 64) 14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [64, 128) 13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [128, 256) 8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [256, 512) 4507667 |@@@@@@@@@@@@@@@ | [512, 1K) 2600472 |@@@@@@@@@ | [1K, 2K) 927912 |@@@ | [2K, 4K) 218720 | | [4K, 8K) 98161 | | [8K, 16K) 37722 | | [16K, 32K) 6715 | | [32K, 64K) 477 | | [64K, 128K) 7 | |netperf latency:
=======case load Lat_99th std% TCP_RR thread-224 257.39 ( 0.21) UDP_RR thread-224 242.83 ( 6.29)The netperf 99th latency(usec) above is comparable with the time spent in
select_idle_cpu(). That is to say, when the system is overloaded, searching for idle CPU could be a bottleneck.[Proposal]
The main idea is to replace percpu average idle time with the domain based metric. Choose average CPUutilization(util_avg)as the candidate. In general, the number of CPUs to be scanned should be inversely proportional to the sum ofutil_avgin this domain. That is, the lower theutil_avgis, the moreselect_idle_cpu()should scan for idle CPU, and vice versa. The benefit of choosingutil_avgis that, it is a metric of accumulated historic activity, which seems to be more accurate than instantaneousmetrics(such as rq->nr_running).Furthermore, borrow the
util_avgfrom periodic load balance, which could offload the overhead ofselect_idle_cpu().According to last discussion[1], introduced the linear function for experimental purpose:
f(x) = a - bx
llc_size
x = \Sum util_avg[cpu] /llc_cpu_capacity1f(x) is the number of CPUs to be scanned, x is the sum
util_avg. To decide a and b, the following condition should be met:[1] f(0) =
llc_size
[2] f(x) = 4, x >= 50%That is to say, when the
util_avgis 0, we should search for the whole LLC domain. And ifutil_avgratio reaches 50% or higher, it should search at most 4 CPUs.Yes, there would be questions like:
Why using this linear function to calculate the number of CPUs to be scanned? Why choosing 50% as the threshold? These questions will be discussed in the [Limitations] section.[Benchmark]
netperf, hackbench, schbench, tbench
were tested with 25% 50% 75% 100% 125% 150% 175% 200% instance of CPU number (these ratios are not CPU utilization). Each test lasts for 100 seconds, and repeats 3 times. The system would reboot into a fresh environment for each benchmark.The following is the benchmark result comparison between baseline:vanilla and compare:patched kernel. Positive compare% indicates better performance.
netperf
=======case load baseline(std%) compare%( std%) TCP_RR 28 threads 1.00 ( 0.30) -1.26 ( 0.32) TCP_RR 56 threads 1.00 ( 0.35) -1.26 ( 0.41) TCP_RR 84 threads 1.00 ( 0.46) -0.15 ( 0.60) TCP_RR 112 threads 1.00 ( 0.36) +0.44 ( 0.41) TCP_RR 140 threads 1.00 ( 0.23) +0.95 ( 0.21) TCP_RR 168 threads 1.00 ( 0.20) +177.77 ( 3.78) TCP_RR 196 threads 1.00 ( 0.18) +185.43 ( 10.08) TCP_RR 224 threads 1.00 ( 0.16) +187.86 ( 7.32) UDP_RR 28 threads 1.00 ( 0.43) -0.93 ( 0.27) UDP_RR 56 threads 1.00 ( 0.17) -0.39 ( 10.91) UDP_RR 84 threads 1.00 ( 6.36) +1.03 ( 0.92) UDP_RR 112 threads 1.00 ( 5.55) +1.47 ( 17.67) UDP_RR 140 threads 1.00 ( 18.17) +0.31 ( 15.48) UDP_RR 168 threads 1.00 ( 15.00) +153.87 ( 13.20) UDP_RR 196 threads 1.00 ( 16.26) +169.19 ( 13.78) UDP_RR 224 threads 1.00 ( 51.81) +76.72 ( 10.95)hackbench
=========
(each group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) process-pipe 1 group 1.00 ( 0.47) -0.46 ( 0.16) process-pipe 2 groups 1.00 ( 0.42) -0.61 ( 0.74) process-pipe 3 groups 1.00 ( 0.42) +0.38 ( 0.20) process-pipe 4 groups 1.00 ( 0.15) -0.36 ( 0.56) process-pipe 5 groups 1.00 ( 0.20) -5.08 ( 0.01) process-pipe 6 groups 1.00 ( 0.28) -2.98 ( 0.29) process-pipe 7 groups 1.00 ( 0.08) -1.18 ( 0.28) process-pipe 8 groups 1.00 ( 0.11) -0.40 ( 0.07) process-sockets 1 group 1.00 ( 0.43) -1.93 ( 0.58) process-sockets 2 groups 1.00 ( 0.23) -1.10 ( 0.49) process-sockets 3 groups 1.00 ( 1.10) -0.96 ( 1.12) process-sockets 4 groups 1.00 ( 0.59) -0.08 ( 0.88) process-sockets 5 groups 1.00 ( 0.45) +0.31 ( 0.34) process-sockets 6 groups 1.00 ( 0.23) +0.06 ( 0.66) process-sockets 7 groups 1.00 ( 0.12) +1.72 ( 0.20) process-sockets 8 groups 1.00 ( 0.11) +1.98 ( 0.02) threads-pipe 1 group 1.00 ( 1.07) +0.03 ( 0.40) threads-pipe 2 groups 1.00 ( 1.05) +0.19 ( 1.27) threads-pipe 3 groups 1.00 ( 0.32) -0.42 ( 0.48) threads-pipe 4 groups 1.00 ( 0.42) -0.76 ( 0.79) threads-pipe 5 groups 1.00 ( 0.19) -4.97 ( 0.07) threads-pipe 6 groups 1.00 ( 0.05) -4.11 ( 0.04) threads-pipe 7 groups 1.00 ( 0.10) -1.13 ( 0.16) threads-pipe 8 groups 1.00 ( 0.03) -0.08 ( 0.05) threads-sockets 1 group 1.00 ( 0.33) -1.93 ( 0.69) threads-sockets 2 groups 1.00 ( 0.20) -1.55 ( 0.30) threads-sockets 3 groups 1.00 ( 0.37) -1.29 ( 0.59) threads-sockets 4 groups 1.00 ( 1.83) +0.31 ( 1.17) threads-sockets 5 groups 1.00 ( 0.28) +15.73 ( 0.24) threads-sockets 6 groups 1.00 ( 0.15) +5.02 ( 0.34) threads-sockets 7 groups 1.00 ( 0.10) +2.29 ( 0.14) threads-sockets 8 groups 1.00 ( 0.17) +2.22 ( 0.12)tbench
======case load baseline(std%) compare%( std%) loopback 28 threads 1.00 ( 0.05) -1.39 ( 0.04) loopback 56 threads 1.00 ( 0.08) -0.37 ( 0.04) loopback 84 threads 1.00 ( 0.03) +0.20 ( 0.13) loopback 112 threads 1.00 ( 0.04) +0.69 ( 0.04) loopback 140 threads 1.00 ( 0.13) +1.15 ( 0.21) loopback 168 threads 1.00 ( 0.03) +1.62 ( 0.08) loopback 196 threads 1.00 ( 0.08) +1.50 ( 0.30) loopback 224 threads 1.00 ( 0.05) +1.62 ( 0.05)schbench
========
(each mthread group has 1/4 * 112 tasks)Quoted 9 lines
case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67) normal 2 mthread groups 1.00 ( 21.10) +8.32 ( 16.92) normal 3 mthread groups 1.00 ( 10.80) +10.03 ( 9.21) normal 4 mthread groups 1.00 ( 2.67) +0.11 ( 3.00) normal 5 mthread groups 1.00 ( 0.08) +0.00 ( 0.13) normal 6 mthread groups 1.00 ( 2.99) -2.66 ( 3.87) normal 7 mthread groups 1.00 ( 2.16) -0.83 ( 2.24) normal 8 mthread groups 1.00 ( 1.75) +0.18 ( 3.18)
Quoted 3 lines
Following are the results on benchmarks from Zen3 system (2 x 64C/128T) on different NPS modes.
Thanks for the testing.
Quoted 32 lines
NPS Configurations:
NPS Modes are used to logically divide single socket into multiple NUMA region.
Following is the NUMA configuration for each NPS mode on the system:NPS1: Each socket is a NUMA node.
Total 2 NUMA nodes in the dual socket machine.Node 0: 0-63, 128-191
Node 1: 64-127, 192-255NPS2: Each socket is further logically divided into 2 NUMA regions. Total 4 NUMA nodes exist over 2 socket.
Node 0: 0-31, 128-159
Node 1: 32-63, 160-191
Node 2: 64-95, 192-223
Node 3: 96-127, 223-255NPS4: Each socket is logically divided into 4 NUMA regions. Total 8 NUMA nodes exist over 2 socket.
Node 0: 0-15, 128-143
Node 1: 16-31, 144-159
Node 2: 32-47, 160-175
Node 3: 48-63, 176-191
Node 4: 64-79, 192-207
Node 5: 80-95, 208-223
Node 6: 96-111, 223-231
Node 7: 112-127, 232-255
Quoted 6 lines
Benchmark Results:
Kernel versions:
- sched-tip: 5.17-rc5 tip sched/core
-v2_sis_prop: 5.17-rc5 tip sched/core + this patch
Just wonder what the kernel version was when you tested v1?
https://lore.kernel.org/lkml/[email protected]/
It seems that there is slight performance difference between the old baseline and current 5.17-rc5 tip sched/core.
Quoted 35 lines
~~~~~~~~~
hackbench
~~~~~~~~~NPS1
Test: sched-tip
v2_sis_prop1-groups: 5.05 (0.00 pct) 5.00 (0.99 pct) 2-groups: 5.72 (0.00 pct) 5.63 (1.57 pct) 4-groups: 6.34 (0.00 pct) 6.21 (2.05 pct) 8-groups: 7.89 (0.00 pct) 7.80 (1.14 pct) 16-groups: 11.80 (0.00 pct) 11.62 (1.52 pct)NPS2
Test: sched-tip
v2_sis_prop1-groups: 4.94 (0.00 pct) 4.93 (0.20 pct) 2-groups: 5.64 (0.00 pct) 5.55 (1.59 pct) 4-groups: 6.23 (0.00 pct) 6.07 (2.56 pct) 8-groups: 7.70 (0.00 pct) 7.46 (3.11 pct) 16-groups: 10.49 (0.00 pct) 10.12 (3.52 pct)NPS4
Test: sched-tip
v2_sis_prop1-groups: 4.89 (0.00 pct) 4.97 (-1.63 pct) 2-groups: 5.43 (0.00 pct) 5.48 (-0.92 pct) 4-groups: 6.15 (0.00 pct) 6.21 (-0.97 pct) 8-groups: 7.54 (0.00 pct) 8.07 (-7.02 pct) 16-groups: 10.20 (0.00 pct) 10.13 ( 0.68 pct)~~~~~~~~
schbench
~~~~~~~~
Quoted 5 lines
NPS 1
#workers: sched-tip
v2_sis_prop1: 13.00 (0.00 pct) 14.50 (-11.53 pct) 2: 31.50 (0.00 pct) 35.00 (-11.11 pct)
It seems that in the old result:
NPS Mode - NPS1
#workers: sched-tip util-avg
1: 13.00 (0.00 pct) 14.50 (-11.53 pct) 2: 31.50 (0.00 pct) 34.00 (-7.93 pct)
we still saw some downgradings. Although in the v1 patch, there is no logic change when the utilization is below 85%. I'm thinking of this might be deviation when the load is low. For example in v2 test of schbench, 3 cycles of testings were launched:
case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67)
The standard deviation ratio is 23%, which seams to be relatively large. But consider that v2 patch has changed the logic of how aggressive we searching for a idle CPU, even in low utilization, this result needs to be evaluated.
Quoted 44 lines
4: 43.00 (0.00 pct) 44.50 (-3.48 pct) 8: 52.50 (0.00 pct) 52.00 (0.95 pct) 16: 69.00 (0.00 pct) 68.00 (1.44 pct) 32: 108.50 (0.00 pct) 108.50 (0.00 pct) 64: 195.00 (0.00 pct) 192.50 (1.28 pct) 128: 395.50 (0.00 pct) 399.00 (-0.88 pct) 256: 950.00 (0.00 pct) 944.00 (0.63 pct) 512: 60352.00 (0.00 pct) 60608.00 (-0.42 pct)
NPS2
#workers: sched-tip
v2_sis_prop1: 10.00 (0.00 pct) 10.00 (0.00 pct) 2: 25.00 (0.00 pct) 28.00 (-12.00 pct) 4: 37.00 (0.00 pct) 37.50 (-1.35 pct) 8: 50.50 (0.00 pct) 52.50 (-3.96 pct) 16: 65.50 (0.00 pct) 67.50 (-3.05 pct) 32: 104.00 (0.00 pct) 104.50 (-0.48 pct) 64: 190.00 (0.00 pct) 186.50 (1.84 pct) 128: 394.50 (0.00 pct) 398.50 (-1.01 pct) 256: 959.00 (0.00 pct) 979.00 (-2.08 pct) 512: 60352.00 (0.00 pct) 60480.00 (-0.21 pct)NPS4
#workers: sched-tip
v2_sis_prop1: 9.50 (0.00 pct) 10.00 (-5.26 pct) 2: 28.00 (0.00 pct) 30.00 (-7.14 pct) 4: 32.00 (0.00 pct) 36.50 (-14.06 pct) 8: 42.00 (0.00 pct) 43.00 (-2.38 pct) 16: 68.00 (0.00 pct) 75.50 (-11.02 pct)32: 104.50 (0.00 pct) 106.50 (-1.91 pct) 64: 186.00 (0.00 pct) 191.50 (-2.95 pct) 128: 382.50 (0.00 pct) 392.50 (-2.61 pct) 256: 966.00 (0.00 pct) 963.00 (0.31 pct) 512: 60480.00 (0.00 pct) 60416.00 (0.10 pct)
~~~~~~
tbench
~~~~~~NPS 1
Quoted 10 lines
Clients: sched-tip
v2_sis_prop1 477.85 (0.00 pct) 470.68 (-1.50 pct) 2 924.07 (0.00 pct) 910.82 (-1.43 pct) 4 1778.95 (0.00 pct) 1743.64 (-1.98 pct) 8 3244.81 (0.00 pct) 3200.35 (-1.37 pct) 16 5837.06 (0.00 pct) 5808.36 (-0.49 pct) 32 9339.33 (0.00 pct) 8648.03 (-7.40 pct) 64 14761.19 (0.00 pct) 15803.13 (7.05 pct) 128 27806.11 (0.00 pct) 27510.69 (-1.06 pct) 256 35262.03 (0.00 pct) 34135.78 (-3.19 pct)
The result from v1 patch:
NPS Mode - NPS1
Clients: sched-tip util-avg
256 26726.29 (0.00 pct) 52502.83 (96.44 pct)
Quoted 5 lines
512 52459.78 (0.00 pct) 51630.53 (-1.58 pct) 1024 52480.67 (0.00 pct) 52439.37 (-0.07 pct)
NPS 2
Quoted 10 lines
Clients: sched-tip
v2_sis_prop1 478.98 (0.00 pct) 472.98 (-1.25 pct) 2 930.52 (0.00 pct) 914.48 (-1.72 pct) 4 1743.26 (0.00 pct) 1711.16 (-1.84 pct) 8 3297.07 (0.00 pct) 3161.12 (-4.12 pct) 16 5779.10 (0.00 pct) 5738.38 (-0.70 pct) 32 10708.42 (0.00 pct) 10748.26 (0.37 pct) 64 16965.21 (0.00 pct) 16894.42 (-0.41 pct) 128 29152.49 (0.00 pct) 28287.31 (-2.96 pct) 256 27408.75 (0.00 pct) 33680.59 (22.88 pct)
The result from v1 patch:
256 27654.49 (0.00 pct) 47126.18 (70.41 pct)
Quoted 5 lines
512 51453.64 (0.00 pct) 47546.87 (-7.59 pct) 1024 52156.85 (0.00 pct) 51233.28 (-1.77 pct)
NPS 4
Quoted 10 lines
Clients: sched-tip
v2_sis_prop1 480.29 (0.00 pct) 473.75 (-1.36 pct) 2 940.23 (0.00 pct) 915.60 (-2.61 pct) 4 1760.21 (0.00 pct) 1687.99 (-4.10 pct) 8 3269.75 (0.00 pct) 3154.02 (-3.53 pct) 16 5503.71 (0.00 pct) 5485.01 (-0.33 pct) 32 10633.93 (0.00 pct) 10276.21 (-3.36 pct) 64 16304.44 (0.00 pct) 15351.17 (-5.84 pct) 128 26893.95 (0.00 pct) 25337.08 (-5.78 pct) 256 24469.94 (0.00 pct) 32178.33 (31.50 pct)
The result from v1 patch:
256 25997.38 (0.00 pct) 47735.83 (83.61 pct)
In above three cases, v2 has smaller improvement compared to v1. In both v1 and v2, the improvement mainly comes from choosing previous running CPU as the target, when the system is busy. But v2 is more likely to choose a previous CPU than v1, because its threshold 50% is lower than 85% from v2. Then why v2 has less improvement than v1? It seems that v2 patch only changes the logic of SIS_PRO for single idle CPU searching, but not touches the idle Core searching. Meanwhile v1 limits both idle CPU and idle Core searching, and this might explain the extra benefit from v1 patch IMO.
Quoted 72 lines
512 46343.65 (0.00 pct) 49607.28 (7.04 pct) 1024 51496.80 (0.00 pct) 51791.27 (0.57 pct)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Stream with 16 threads.
built with -DSTREAM_ARRAY_SIZE=128000000, -DNTIMES=10
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~NPS1
Test: sched-tip
v2_sis_propCopy: 204020.95 (0.00 pct) 211802.20 (3.81 pct) Scale: 208261.03 (0.00 pct) 210809.40 (1.22 pct) Add: 243944.45 (0.00 pct) 249801.81 (2.40 pct) Triad: 237033.90 (0.00 pct) 242273.45 (2.21 pct)NPS2
Test: sched-tip
v2_sis_propCopy: 171679.21 (0.00 pct) 153853.24 (-10.38 pct) Scale: 191362.43 (0.00 pct) 188219.32 (-1.64 pct) Add: 218986.47 (0.00 pct) 204766.66 (-6.49 pct) Triad: 215118.01 (0.00 pct) 202370.69 (-5.92 pct)NPS4
Test: sched-tip
v2_sis_propCopy: 133829.00 (0.00 pct) 125722.97 (-6.05 pct) Scale: 192074.89 (0.00 pct) 187164.95 (-2.55 pct) Add: 186288.73 (0.00 pct) 175316.23 (-5.89 pct) Triad: 185469.53 (0.00 pct) 175985.74 (-5.11 pct)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Stream with 16 threads.
built with -DSTREAM_ARRAY_SIZE=128000000, -DNTIMES=100
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~NPS1
Test: sched-tip
v2_sis_propCopy: 217592.30 (0.00 pct) 231684.51 (6.47 pct) Scale: 217269.78 (0.00 pct) 218632.93 (0.62 pct) Add: 265842.95 (0.00 pct) 266692.50 (0.31 pct) Triad: 252647.10 (0.00 pct) 253462.69 (0.32 pct)NPS2
Test: sched-tip
v2_sis_propCopy: 226948.55 (0.00 pct) 242576.78 (6.88 pct) Scale: 217968.87 (0.00 pct) 220613.96 (1.21 pct) Add: 274839.22 (0.00 pct) 277389.36 (0.92 pct) Triad: 261920.73 (0.00 pct) 263849.95 (0.73 pct)NPS4
Test: sched-tip
v2_sis_propCopy: 256162.84 (0.00 pct) 238881.35 (-6.74 pct) Scale: 228251.12 (0.00 pct) 228669.16 (0.18 pct) Add: 292794.77 (0.00 pct) 293700.42 (0.30 pct) Triad: 274152.69 (0.00 pct) 274900.77 (0.27 pct)~~~~~~~~~~~~
ycsb-mongodb
~~~~~~~~~~~~NPS1
sched-tip: 304934.67 (var: 0.88)
v2_sis_prop: 301560.0 (var: 2.0) (-1.1%)NPS2
Quoted 8 lines
sched-tip: 303757.0 (var: 1.0)
v2_sis_prop: 302283.0 (var: 0.58) (-0.48%)NPS4
sched-tip: 308106.67 (var: 2.88)
v2_sis_prop: 302302.67 (var: 1.12) (-1.88%)
May I know the average CPU utilization of this benchmark?
Quoted 94 lines
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
schbench, tbench - System 50% loaded to fully loaded
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
schbench
~~~~~~~~NPS1
#workers: sched-tip
v2_sis_prop128: 395.50 (0.00 pct) 399.00 (-0.88 pct) 144: 441.50 (0.00 pct) 450.00 (-1.92 pct) 160: 488.00 (0.00 pct) 513.00 (-5.12 pct) 176: 549.00 (0.00 pct) 547.00 (0.36 pct) 192: 601.00 (0.00 pct) 589.00 (1.99 pct) 208: 653.00 (0.00 pct) 736.00 (-12.71 pct) 224: 740.00 (0.00 pct) 757.00 (-2.29 pct) 240: 835.00 (0.00 pct) 808.00 (3.23 pct) 256: 950.00 (0.00 pct) 944.00 (0.63 pct)NPS2:
#workers: sched-tipv2_sis_prop128: 394.50 (0.00 pct) 398.50 (-1.01 pct) 144: 454.50 (0.00 pct) 443.50 (2.42 pct) 160: 500.00 (0.00 pct) 494.00 (1.20 pct) 176: 547.00 (0.00 pct) 530.00 (3.10 pct) 192: 595.00 (0.00 pct) 609.00 (-2.35 pct) 208: 739.00 (0.00 pct) 738.00 (0.13 pct) 224: 781.00 (0.00 pct) 794.00 (-1.66 pct) 240: 894.00 (0.00 pct) 890.00 (0.44 pct) 256: 959.00 (0.00 pct) 979.00 (-2.08 pct)NPS4
#workers: sched-tip
v2_sis_prop128: 382.50 (0.00 pct) 392.50 (-2.61 pct) 144: 451.50 (0.00 pct) 459.00 (-1.66 pct) 160: 491.00 (0.00 pct) 497.00 (-1.22 pct) 176: 578.00 (0.00 pct) 564.00 (2.42 pct) 192: 593.00 (0.00 pct) 612.00 (-3.20 pct) 208: 737.00 (0.00 pct) 720.00 (2.30 pct) 224: 786.00 (0.00 pct) 796.00 (-1.27 pct) 240: 893.00 (0.00 pct) 890.00 (0.33 pct) 256: 966.00 (0.00 pct) 963.00 (0.31 pct)~~~~~~
tbench
~~~~~~NPS1
Clients: sched-tip
v2_sis_prop128 28369.07 (0.00 pct) 25649.26 (-9.58 pct) 144 25794.95 (0.00 pct) 25464.33 (-1.28 pct) 160 23905.48 (0.00 pct) 23507.18 (-1.66 pct) 176 24219.13 (0.00 pct) 22664.99 (-6.41 pct) 192 23978.71 (0.00 pct) 22506.50 (-6.13 pct) 208 24045.91 (0.00 pct) 22592.62 (-6.04 pct) 224 21961.21 (0.00 pct) 22154.28 (0.87 pct) 240 22001.05 (0.00 pct) 26245.06 (19.29 pct) 256 26866.60 (0.00 pct) 33064.10 (23.06 pct)NPS2
Clients: sched-tip
v2_sis_prop128 25229.75 (0.00 pct) 26396.32 (4.62 pct) 144 27488.16 (0.00 pct) 24596.76 (-10.51 pct) 160 23765.03 (0.00 pct) 23945.55 (0.75 pct) 176 22230.05 (0.00 pct) 22207.84 (-0.09 pct) 192 21383.39 (0.00 pct) 22385.72 (4.68 pct) 208 23920.96 (0.00 pct) 22323.24 (-6.67 pct) 224 22212.38 (0.00 pct) 24108.90 (8.53 pct) 240 22143.36 (0.00 pct) 25655.54 (15.86 pct) 256 29923.16 (0.00 pct) 32570.60 (8.84 pct)NPS4
Clients: sched-tip
v2_sis_prop128 26336.35 (0.00 pct) 24604.90 (-6.57 pct) 144 24469.64 (0.00 pct) 24685.57 (0.88 pct) 160 23742.98 (0.00 pct) 23381.86 (-1.52 pct) 176 22512.46 (0.00 pct) 22602.49 (0.39 pct) 192 21141.71 (0.00 pct) 22752.25 (7.61 pct) 208 21803.07 (0.00 pct) 22280.24 (2.18 pct) 224 21174.10 (0.00 pct) 23582.49 (11.37 pct) 240 21510.36 (0.00 pct) 26295.92 (22.24 pct) 256 25170.50 (0.00 pct) 34215.08 (35.93 pct)Hackbench shows improvements in NPS1 and NPS2 modes. tbench sees good improvement when system is close to fully loaded. Stream values are very close to the baseline. YCSB MongoDB shows slight regression and schbench is a mixed bag.
Quoted 6 lines
This strategy would probably work better on systems with large number of CPUs per LLC but from our observations, I believe it is worthwhile to search for an idle CPUs in the entire LLC on Zen3 systems as we have 16 CPUs per LLC.
Only when the system is close to fully loaded, we see a good uplift by not searching the entire LLC in tbench which is what we saw with the v1 too.
I see. But we might have to make this per-LLC search generic, both for smaller size and bigger size. Current using exponential descent function could increase the number of CPUs to be searched when the system is not busy. I'll think about it and do some investigation.
thanks,
Chenyu
Quoted 3 lines
--
Thanks and Regards,
Prateek
K Prateek Nayak
reviewerHello Chenyu,
Thank you for looking into the results.
Quoted 5 lines · Chen Yu
[..snip..]
Just wonder what the kernel version was when you tested v1?
https://lore.kernel.org/lkml/[email protected]/
It seems that there is slight performance difference between the old baseline and current 5.17-rc5 tip sched/core.
I'll make a point to include the HEAD commit from next time onward to remove this ambiguity.
- While testing v1, the sched-tip was at:
commit: 3624ba7b5e2a ("sched/numa-balancing: Move some document to make it consistent with the code")
- While testing v2, the sched-tip was at:
commit: a0a7e453b502 ("sched/preempt: Tell about PREEMPT_DYNAMIC on kernel headers")
Quoted 21 lines
Quoted 11 lines
[..snip..]
~~~~~~~~
schbench
~~~~~~~~NPS 1
#workers: sched-tip
v2_sis_prop1: 13.00 (0.00 pct) 14.50 (-11.53 pct) 2: 31.50 (0.00 pct) 35.00 (-11.11 pct)It seems that in the old result:
NPS Mode - NPS1
#workers: sched-tip util-avg1: 13.00 (0.00 pct) 14.50 (-11.53 pct) 2: 31.50 (0.00 pct) 34.00 (-7.93 pct)we still saw some downgradings. Although in the v1 patch, there is no logic change when the utilization is below 85%. I'm thinking of this might be deviation when the load is low. For example in v2 test of schbench, 3 cycles of testings were launched:
Quoted 6 lines
case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67)The standard deviation ratio is 23%, which seams to be relatively large. But consider that v2 patch has changed the logic of how aggressive we searching for a idle CPU, even in low utilization, this result needs to be evaluated.
We too see a lot of variation for schbench. For two worker case, following is the data from 10 runs in NPS1 mode:
- sched-tip data
Min : 23.00
Max : 40.00
Median : 31.50
AMean : 30.50
GMean : 29.87
HMean : 29.25
AMean Stddev : 6.55
GMean Stddev : 6.59
HMean Stddev : 6.68
AMean CoefVar : 21.49 pct
GMean CoefVar : 22.05 pct
HMean CoefVar : 22.85 pct
- v2_sis_prop data
Min : 22.00
Max : 41.00
Median : 35.00
AMean : 33.50
GMean : 32.84
HMean : 32.13
AMean Stddev : 6.64
GMean Stddev : 6.67
HMean Stddev : 6.79
AMean CoefVar : 19.81 pct
GMean CoefVar : 20.32 pct
HMean CoefVar : 21.14 pct
The median of the data was reported previously.
Quoted 56 lines
[..snip..]
Quoted 6 lines
~~~~~~
tbench
~~~~~~NPS 1
Quoted 10 lines
Clients: sched-tip
v2_sis_prop1 477.85 (0.00 pct) 470.68 (-1.50 pct) 2 924.07 (0.00 pct) 910.82 (-1.43 pct) 4 1778.95 (0.00 pct) 1743.64 (-1.98 pct) 8 3244.81 (0.00 pct) 3200.35 (-1.37 pct) 16 5837.06 (0.00 pct) 5808.36 (-0.49 pct) 32 9339.33 (0.00 pct) 8648.03 (-7.40 pct) 64 14761.19 (0.00 pct) 15803.13 (7.05 pct) 128 27806.11 (0.00 pct) 27510.69 (-1.06 pct) 256 35262.03 (0.00 pct) 34135.78 (-3.19 pct)The result from v1 patch:
NPS Mode - NPS1
Clients: sched-tip util-avg
256 26726.29 (0.00 pct) 52502.83 (96.44 pct)Quoted 5 lines
512 52459.78 (0.00 pct) 51630.53 (-1.58 pct) 1024 52480.67 (0.00 pct) 52439.37 (-0.07 pct)
NPS 2
Quoted 10 lines
Clients: sched-tip
v2_sis_prop1 478.98 (0.00 pct) 472.98 (-1.25 pct) 2 930.52 (0.00 pct) 914.48 (-1.72 pct) 4 1743.26 (0.00 pct) 1711.16 (-1.84 pct) 8 3297.07 (0.00 pct) 3161.12 (-4.12 pct) 16 5779.10 (0.00 pct) 5738.38 (-0.70 pct) 32 10708.42 (0.00 pct) 10748.26 (0.37 pct) 64 16965.21 (0.00 pct) 16894.42 (-0.41 pct) 128 29152.49 (0.00 pct) 28287.31 (-2.96 pct) 256 27408.75 (0.00 pct) 33680.59 (22.88 pct)The result from v1 patch:
256 27654.49 (0.00 pct) 47126.18 (70.41 pct)Quoted 5 lines
512 51453.64 (0.00 pct) 47546.87 (-7.59 pct) 1024 52156.85 (0.00 pct) 51233.28 (-1.77 pct)
NPS 4
Quoted 10 lines
Clients: sched-tip
v2_sis_prop1 480.29 (0.00 pct) 473.75 (-1.36 pct) 2 940.23 (0.00 pct) 915.60 (-2.61 pct) 4 1760.21 (0.00 pct) 1687.99 (-4.10 pct) 8 3269.75 (0.00 pct) 3154.02 (-3.53 pct) 16 5503.71 (0.00 pct) 5485.01 (-0.33 pct) 32 10633.93 (0.00 pct) 10276.21 (-3.36 pct) 64 16304.44 (0.00 pct) 15351.17 (-5.84 pct) 128 26893.95 (0.00 pct) 25337.08 (-5.78 pct) 256 24469.94 (0.00 pct) 32178.33 (31.50 pct)The result from v1 patch:
256 25997.38 (0.00 pct) 47735.83 (83.61 pct)
Quoted 9 lines
In above three cases, v2 has smaller improvement compared to v1. In both v1 and v2, the improvement mainly comes from choosing previous running CPU as the target, when the system is busy. But v2 is more likely to choose a previous CPU than v1, because its threshold 50% is lower than 85% from v2. Then why v2 has less improvement than v1? It seems that v2 patch only changes the logic of
SIS_PROfor single idle CPU searching, but not touches the idle Core searching. Meanwhile v1 limits both idle CPU and idle Core searching, and this might explain the extra benefit from v1 patch IMO.
Yes, this might be the case.
Quoted 15 lines
Quoted 15 lines
[..snip..]
~~~~~~~~~~~~
ycsb-mongodb
~~~~~~~~~~~~NPS1
sched-tip: 304934.67 (var: 0.88) v2_sis_prop: 301560.0 (var: 2.0) (-1.1%)
NPS2
sched-tip: 303757.0 (var: 1.0) v2_sis_prop: 302283.0 (var: 0.58) (-0.48%)
Quoted 6 lines
Quoted 5 lines
NPS4
sched-tip: 308106.67 (var: 2.88) v2_sis_prop: 302302.67 (var: 1.12) (-1.88%)
May I know the average CPU utilization of this benchmark?
I don't have this data at hand. I'll get back to you soon with the data.
Quoted 5 lines
[..snip..]
I see. But we might have to make this per-LLC search generic, both for smaller size and bigger size. Current using exponential descent function could increase the number of CPUs to be searched when the system is not busy. I'll think about it and do some investigation.
It would indeed be great to have this work well for all LLC sizes. Thank you for looking into it :)
--
Thanks and Regards,
Prateek
K Prateek Nayak
reviewerHello Chenyu,
Quoted 2 lines · K Prateek Nayak
Quoted 1 line
May I know the average CPU utilization of this benchmark?
I don't have this data at hand. I'll get back to you soon with the data.
This is the output of vmstat captured every minute during the runtime of the benchmark:
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu----- r b swpd free buff cache si so bi bo in cs us sy id wa st 0 0 0 524179712 47956 623328 0 0 18 1 95 70 0 1 99 0 0 0 0 0 524583488 6984 296760 0 0 869 32 765 613 0 0 100 0 0 2 0 0 519057408 10840 413092 0 0 1413 97 40022 245964 2 1 98 0 0 13 0 0 515806048 11036 1560292 0 0 1 15861 47291 481310 3 1 95 0 0 0 0 0 519494240 11844 2073552 0 0 27 11934 7397 70297 1 0 99 0 0 49 1 0 508753216 12064 4519468 0 0 22 82723 160775 1219361 11 5 84 0 0 51 1 0 508787424 12188 4686136 0 0 3 177661 199218 1522425 13 5 81 0 0 51 0 0 508717088 12464 5102900 0 0 8 172393 215555 1526566 14 6 81 0 0 54 0 0 508974208 12584 5133116 0 0 0 196022 194294 1520359 14 5 81 0 0 49 0 0 509171712 12720 5133420 0 0 1 189473 181195 1520990 14 5 81 0 0 65 2 0 509624672 12820 5172400 0 0 0 192406 190311 1516981 14 5 80 0 0 50 1 0 510052864 14228 5231312 0 0 886 173806 236733 1491140 14 6 80 0 0 50 1 0 510455904 14340 5231412 0 0 0 191996 252078 1479435 14 6 80 0 0 51 0 0 510845184 14464 5231436 0 0 0 191033 251433 1480865 14 6 80 0 0 54 0 0 511137472 15128 5247844 0 0 12 198460 254401 1485615 14 6 80 0 0 54 0 0 511242816 15240 5247868 0 0 0 205262 255299 1483994 14 6 80 0 0 0 0 0 524682656 6488 302624 0 0 596 64012 55117 315385 3 1 96 0 0 11 0 0 523307136 10096 350728 0 0 788 89 3350 30092 0 0 100 0 0 9 0 0 516713440 10276 1222368 0 0 2 8941 51751 497130 3 1 95 0 0 0 0 0 519524608 10428 2009192 0 0 8 18969 29798 277747 2 1 97 0 0 50 0 0 510469184 10608 4463716 0 0 15 72376 99893 592582 6 2 92 0 0 50 1 0 510225728 10760 4954988 0 0 3 175225 223641 1531010 13 5 81 0 0 49 0 0 510185376 10856 4955084 0 0 0 167856 208568 1541377 13 5 81 0 0 51 1 0 510101696 10964 5058408 0 0 0 185400 216839 1534992 13 5 81 0 0 56 0 0 509908448 11084 5058524 0 0 0 184871 240666 1478386 14 6 81 0 0 57 0 0 509593088 11188 5058624 0 0 0 174319 257078 1472289 14 6 80 0 0 46 0 0 509449280 11320 5120364 0 0 0 199695 246095 1484076 14 6 81 0 0 47 0 0 509569120 11440 5120504 0 0 0 195409 246954 1486632 14 6 81 0 0 51 1 0 509394240 11564 5120640 0 0 0 187739 235864 1487453 14 5 81 0 0 46 1 0 509165184 11668 5137480 0 0 0 190097 225997 1510812 14 5 81 0 0 83 1 0 509214944 11788 5137564 0 0 0 185712 232513 1524289 14 5 81 0 0 0 0 0 524685792 3940 268116 0 0 48 153174 152934 966090 9 3 88 0 0 0 0 0 524574880 6560 317068 0 0 703 82 193 342 0 0 100 0 0 11 0 0 515208960 8380 877736 0 0 606 8627 31043 324947 2 1 97 0 0 1 0 0 519673440 9196 1845944 0 0 20 13871 41874 470542 3 1 96 0 0 56 0 0 513421280 9328 2819588 0 0 13 6776 21005 106752 1 0 98 0 0 46 0 0 509829408 9520 4192212 0 0 4 157023 199117 1512516 13 5 82 0 0 49 1 0 509403200 10084 4596844 0 0 22 175970 205070 1512552 13 5 81 0 0 50 0 0 508933536 10220 4828368 0 0 0 180676 224455 1512344 14 6 81 0 0 47 0 0 508529472 10364 4940972 0 0 1 196158 250799 1502868 14 6 80 0 0 58 0 0 508565344 10476 4941012 0 0 0 194334 256721 1502510 14 6 80 0 0 50 0 0 508594176 10596 4941144 0 0 0 182299 257354 1501533 14 6 80 0 0 57 1 0 508721088 10700 4965532 0 0 0 186060 255378 1501167 14 6 80 0 0 49 0 0 508646144 10824 4965644 0 0 0 191029 257866 1500889 14 6 80 0 0 49 0 0 508739136 10920 4965672 0 0 0 182014 260923 1504201 14 6 80 0 0 50 0 0 509059616 11032 4974112 0 0 0 195981 260905 1503577 14 6 80 0 0 0 1 0 516111104 11152 4975472 0 0 0 190756 186797 1452580 13 5 82 0 0 0 0 0 519977088 17876 4985004 0 0 177 18948 747 650 0 0 100 0 0
If there is any specific monitoring program you would like me to run, please let me know.
--
Thanks and Regards,
Prateek
Quoted 56 lines · K Prateek Nayak
Hello Chenyu,
This is the output of vmstat captured every minute during the runtime of the benchmark:
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
r b swpd free buff cache si so bi bo in cs us sy id wa st 0 0 0 524179712 47956 623328 0 0 18 1 95 70 0 1 99 0 0 0 0 0 524583488 6984 296760 0 0 869 32 765 613 0 0 100 0 0 2 0 0 519057408 10840 413092 0 0 1413 97 40022 245964 2 1 98 0 0 13 0 0 515806048 11036 1560292 0 0 1 15861 47291 481310 3 1 95 0 0 0 0 0 519494240 11844 2073552 0 0 27 11934 7397 70297 1 0 99 0 0 49 1 0 508753216 12064 4519468 0 0 22 82723 160775 1219361 11 5 84 0 0 51 1 0 508787424 12188 4686136 0 0 3 177661 199218 1522425 13 5 81 0 0 51 0 0 508717088 12464 5102900 0 0 8 172393 215555 1526566 14 6 81 0 0 54 0 0 508974208 12584 5133116 0 0 0 196022 194294 1520359 14 5 81 0 0 49 0 0 509171712 12720 5133420 0 0 1 189473 181195 1520990 14 5 81 0 0 65 2 0 509624672 12820 5172400 0 0 0 192406 190311 1516981 14 5 80 0 0 50 1 0 510052864 14228 5231312 0 0 886 173806 236733 1491140 14 6 80 0 0 50 1 0 510455904 14340 5231412 0 0 0 191996 252078 1479435 14 6 80 0 0 51 0 0 510845184 14464 5231436 0 0 0 191033 251433 1480865 14 6 80 0 0 54 0 0 511137472 15128 5247844 0 0 12 198460 254401 1485615 14 6 80 0 0 54 0 0 511242816 15240 5247868 0 0 0 205262 255299 1483994 14 6 80 0 0 0 0 0 524682656 6488 302624 0 0 596 64012 55117 315385 3 1 96 0 0 11 0 0 523307136 10096 350728 0 0 788 89 3350 30092 0 0 100 0 0 9 0 0 516713440 10276 1222368 0 0 2 8941 51751 497130 3 1 95 0 0 0 0 0 519524608 10428 2009192 0 0 8 18969 29798 277747 2 1 97 0 0 50 0 0 510469184 10608 4463716 0 0 15 72376 99893 592582 6 2 92 0 0 50 1 0 510225728 10760 4954988 0 0 3 175225 223641 1531010 13 5 81 0 0 49 0 0 510185376 10856 4955084 0 0 0 167856 208568 1541377 13 5 81 0 0 51 1 0 510101696 10964 5058408 0 0 0 185400 216839 1534992 13 5 81 0 0 56 0 0 509908448 11084 5058524 0 0 0 184871 240666 1478386 14 6 81 0 0 57 0 0 509593088 11188 5058624 0 0 0 174319 257078 1472289 14 6 80 0 0 46 0 0 509449280 11320 5120364 0 0 0 199695 246095 1484076 14 6 81 0 0 47 0 0 509569120 11440 5120504 0 0 0 195409 246954 1486632 14 6 81 0 0 51 1 0 509394240 11564 5120640 0 0 0 187739 235864 1487453 14 5 81 0 0 46 1 0 509165184 11668 5137480 0 0 0 190097 225997 1510812 14 5 81 0 0 83 1 0 509214944 11788 5137564 0 0 0 185712 232513 1524289 14 5 81 0 0 0 0 0 524685792 3940 268116 0 0 48 153174 152934 966090 9 3 88 0 0 0 0 0 524574880 6560 317068 0 0 703 82 193 342 0 0 100 0 0 11 0 0 515208960 8380 877736 0 0 606 8627 31043 324947 2 1 97 0 0 1 0 0 519673440 9196 1845944 0 0 20 13871 41874 470542 3 1 96 0 0 56 0 0 513421280 9328 2819588 0 0 13 6776 21005 106752 1 0 98 0 0 46 0 0 509829408 9520 4192212 0 0 4 157023 199117 1512516 13 5 82 0 0 49 1 0 509403200 10084 4596844 0 0 22 175970 205070 1512552 13 5 81 0 0 50 0 0 508933536 10220 4828368 0 0 0 180676 224455 1512344 14 6 81 0 0 47 0 0 508529472 10364 4940972 0 0 1 196158 250799 1502868 14 6 80 0 0 58 0 0 508565344 10476 4941012 0 0 0 194334 256721 1502510 14 6 80 0 0 50 0 0 508594176 10596 4941144 0 0 0 182299 257354 1501533 14 6 80 0 0 57 1 0 508721088 10700 4965532 0 0 0 186060 255378 1501167 14 6 80 0 0 49 0 0 508646144 10824 4965644 0 0 0 191029 257866 1500889 14 6 80 0 0 49 0 0 508739136 10920 4965672 0 0 0 182014 260923 1504201 14 6 80 0 0 50 0 0 509059616 11032 4974112 0 0 0 195981 260905 1503577 14 6 80 0 0 0 1 0 516111104 11152 4975472 0 0 0 190756 186797 1452580 13 5 82 0 0 0 0 0 519977088 17876 4985004 0 0 177 18948 747 650 0 0 100 0 0
Quoted 2 lines
If there is any specific monitoring program you would like me to run, please let me know.
Thanks for providing this information. So the ycsb-mongodb had some regression when the
load was around 20%. As v2 patch would change the search depth when the load is low, this
results might indicate that we should search more CPUs when the system is low.
thanks,
Chenyu
Hi Chen,
Thanks for the update. I'm still testing on this along with the sched cluster patches. I'll show some results when I get enough data. So some questions below.
Quoted 66 lines · Chen Yu
[Problem Statement]
Currentlyselect_idle_cpu()uses the percpu average idle time to estimate the total LLC domain idle time, and calculate the number of CPUs to be scanned. This might be inconsistent because idle time of a CPU does not necessarily correlate with idle time of a domain. As a result, the load could be underestimated and causes over searching when the system is very busy.The following histogram is the time spent in
select_idle_cpu(), when running 224 instance of netperf on a system with 112 CPUs per LLC domain:@usecs:
[0] 533 | | [1] 5495 | | [2, 4) 12008 | | [4, 8) 239252 | | [8, 16) 4041924 |@@@@@@@@@@@@@@ | [16, 32) 12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [32, 64) 14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [64, 128) 13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [128, 256) 8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [256, 512) 4507667 |@@@@@@@@@@@@@@@ | [512, 1K) 2600472 |@@@@@@@@@ | [1K, 2K) 927912 |@@@ | [2K, 4K) 218720 | | [4K, 8K) 98161 | | [8K, 16K) 37722 | | [16K, 32K) 6715 | | [32K, 64K) 477 | | [64K, 128K) 7 | |netperf latency:
=======case load Lat_99th std% TCP_RR thread-224 257.39 ( 0.21) UDP_RR thread-224 242.83 ( 6.29)The netperf 99th latency(usec) above is comparable with the time spent in
select_idle_cpu(). That is to say, when the system is overloaded, searching for idle CPU could be a bottleneck.[Proposal]
The main idea is to replace percpu average idle time with the domain based metric. Choose average CPUutilization(util_avg)as the candidate. In general, the number of CPUs to be scanned should be inversely proportional to the sum ofutil_avgin this domain. That is, the lower theutil_avgis, the moreselect_idle_cpu()should scan for idle CPU, and vice versa. The benefit of choosingutil_avgis that, it is a metric of accumulated historic activity, which seems to be more accurate than instantaneousmetrics(such as rq->nr_running).Furthermore, borrow the
util_avgfrom periodic load balance, which could offload the overhead ofselect_idle_cpu().According to last discussion[1], introduced the linear function for experimental purpose:
f(x) = a - bx
llc_size
x = \Sum util_avg[cpu] /llc_cpu_capacity1f(x) is the number of CPUs to be scanned, x is the sum
util_avg. To decide a and b, the following condition should be met:
Quoted 6 lines
[1] f(0) =
llc_size
[2] f(x) = 4, x >= 50%That is to say, when the
util_avgis 0, we should search for the whole LLC domain. And ifutil_avgratio reaches 50% or higher, it should search at most 4 CPUs.
I might have a question here. In your V1 patch, we won't scan when the LLC util >85%. But in this patch we'll always scan 4 cpus no matter how much the LLC is overloaded. When the LLC is rather busy the scan is probably redundant so is it better if we found a threadhold for stopping the scan? The util_avg cannot indicate how much the cpu is overloaded so perhaps just stop scan when it is 100% utilized.
Quoted 200 lines
Yes, there would be questions like:
Why using this linear function to calculate the number of CPUs to be scanned? Why choosing 50% as the threshold? These questions will be discussed in the [Limitations] section.[Benchmark]
netperf, hackbench, schbench, tbench
were tested with 25% 50% 75% 100% 125% 150% 175% 200% instance of CPU number (these ratios are not CPU utilization). Each test lasts for 100 seconds, and repeats 3 times. The system would reboot into a fresh environment for each benchmark.The following is the benchmark result comparison between baseline:vanilla and compare:patched kernel. Positive compare% indicates better performance.
netperf
=======case load baseline(std%) compare%( std%) TCP_RR 28 threads 1.00 ( 0.30) -1.26 ( 0.32) TCP_RR 56 threads 1.00 ( 0.35) -1.26 ( 0.41) TCP_RR 84 threads 1.00 ( 0.46) -0.15 ( 0.60) TCP_RR 112 threads 1.00 ( 0.36) +0.44 ( 0.41) TCP_RR 140 threads 1.00 ( 0.23) +0.95 ( 0.21) TCP_RR 168 threads 1.00 ( 0.20) +177.77 ( 3.78) TCP_RR 196 threads 1.00 ( 0.18) +185.43 ( 10.08) TCP_RR 224 threads 1.00 ( 0.16) +187.86 ( 7.32) UDP_RR 28 threads 1.00 ( 0.43) -0.93 ( 0.27) UDP_RR 56 threads 1.00 ( 0.17) -0.39 ( 10.91) UDP_RR 84 threads 1.00 ( 6.36) +1.03 ( 0.92) UDP_RR 112 threads 1.00 ( 5.55) +1.47 ( 17.67) UDP_RR 140 threads 1.00 ( 18.17) +0.31 ( 15.48) UDP_RR 168 threads 1.00 ( 15.00) +153.87 ( 13.20) UDP_RR 196 threads 1.00 ( 16.26) +169.19 ( 13.78) UDP_RR 224 threads 1.00 ( 51.81) +76.72 ( 10.95)hackbench
=========
(each group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) process-pipe 1 group 1.00 ( 0.47) -0.46 ( 0.16) process-pipe 2 groups 1.00 ( 0.42) -0.61 ( 0.74) process-pipe 3 groups 1.00 ( 0.42) +0.38 ( 0.20) process-pipe 4 groups 1.00 ( 0.15) -0.36 ( 0.56) process-pipe 5 groups 1.00 ( 0.20) -5.08 ( 0.01) process-pipe 6 groups 1.00 ( 0.28) -2.98 ( 0.29) process-pipe 7 groups 1.00 ( 0.08) -1.18 ( 0.28) process-pipe 8 groups 1.00 ( 0.11) -0.40 ( 0.07) process-sockets 1 group 1.00 ( 0.43) -1.93 ( 0.58) process-sockets 2 groups 1.00 ( 0.23) -1.10 ( 0.49) process-sockets 3 groups 1.00 ( 1.10) -0.96 ( 1.12) process-sockets 4 groups 1.00 ( 0.59) -0.08 ( 0.88) process-sockets 5 groups 1.00 ( 0.45) +0.31 ( 0.34) process-sockets 6 groups 1.00 ( 0.23) +0.06 ( 0.66) process-sockets 7 groups 1.00 ( 0.12) +1.72 ( 0.20) process-sockets 8 groups 1.00 ( 0.11) +1.98 ( 0.02) threads-pipe 1 group 1.00 ( 1.07) +0.03 ( 0.40) threads-pipe 2 groups 1.00 ( 1.05) +0.19 ( 1.27) threads-pipe 3 groups 1.00 ( 0.32) -0.42 ( 0.48) threads-pipe 4 groups 1.00 ( 0.42) -0.76 ( 0.79) threads-pipe 5 groups 1.00 ( 0.19) -4.97 ( 0.07) threads-pipe 6 groups 1.00 ( 0.05) -4.11 ( 0.04) threads-pipe 7 groups 1.00 ( 0.10) -1.13 ( 0.16) threads-pipe 8 groups 1.00 ( 0.03) -0.08 ( 0.05) threads-sockets 1 group 1.00 ( 0.33) -1.93 ( 0.69) threads-sockets 2 groups 1.00 ( 0.20) -1.55 ( 0.30) threads-sockets 3 groups 1.00 ( 0.37) -1.29 ( 0.59) threads-sockets 4 groups 1.00 ( 1.83) +0.31 ( 1.17) threads-sockets 5 groups 1.00 ( 0.28) +15.73 ( 0.24) threads-sockets 6 groups 1.00 ( 0.15) +5.02 ( 0.34) threads-sockets 7 groups 1.00 ( 0.10) +2.29 ( 0.14) threads-sockets 8 groups 1.00 ( 0.17) +2.22 ( 0.12)tbench
======case load baseline(std%) compare%( std%) loopback 28 threads 1.00 ( 0.05) -1.39 ( 0.04) loopback 56 threads 1.00 ( 0.08) -0.37 ( 0.04) loopback 84 threads 1.00 ( 0.03) +0.20 ( 0.13) loopback 112 threads 1.00 ( 0.04) +0.69 ( 0.04) loopback 140 threads 1.00 ( 0.13) +1.15 ( 0.21) loopback 168 threads 1.00 ( 0.03) +1.62 ( 0.08) loopback 196 threads 1.00 ( 0.08) +1.50 ( 0.30) loopback 224 threads 1.00 ( 0.05) +1.62 ( 0.05)schbench
========
(each mthread group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67) normal 2 mthread groups 1.00 ( 21.10) +8.32 ( 16.92) normal 3 mthread groups 1.00 ( 10.80) +10.03 ( 9.21) normal 4 mthread groups 1.00 ( 2.67) +0.11 ( 3.00) normal 5 mthread groups 1.00 ( 0.08) +0.00 ( 0.13) normal 6 mthread groups 1.00 ( 2.99) -2.66 ( 3.87) normal 7 mthread groups 1.00 ( 2.16) -0.83 ( 2.24) normal 8 mthread groups 1.00 ( 1.75) +0.18 ( 3.18)According to the results above, when the workloads is heavy, the throughput of netperf improves a lot. It might be interesting to look into the reason why this patch benefits netperf significantly. Further investigation has shown that, this might be a 'side effect' of this patch. It is found that, the CPU utilization is around 90% on vanilla kernel, while it is nearly 100% on patched kernel. According to the perf profile, with the patch applied, the scheduler would likely to choose previous running CPU for the waking task, thus reduces runqueue lock contention, so the CPU utilization is higher and get better performance.
[Limitations]
Q:Why using 50% as the util_avg/capacity threshold to search at most 4 CPUs?A: 50% is chosen as that corresponds to almost full CPU utilization, when
the CPU is fixed to run at its base frequency, with turbo enabled. 4 is the minimal number of CPUs to be scanned in currentselect_idle_cpu().A synthetic workload was used to simulate different level of load. This workload takes every 10ms as the sample period, and in each sample period:
while (!timeout_10ms) { loop(busy_pct_ms); sleep(10ms-busy_pct_ms) }to simulate busy_pct% of CPU utilization. When the workload is running, the percpu runqueue
util_avgwas monitored. The following is the result from turbostat's Busy% on CPU2 and cfs_rq[2].util_avg from/sys/kernel/debug/sched/debug:Busy% util_avg util_avg/cpu_capacity% 10.06 35 3.42 19.97 99 9.67 29.93 154 15.04 39.86 213 20.80 49.79 256 25.00 59.73 325 31.74 69.77 437 42.68 79.69 458 44.73 89.62 519 50.68 99.54 598 58.39The reason why
util_avgratio is not consistent with Busy% might be due to CPU frequency invariance. The CPU is running at fixed lower frequency than the turbo frequency, then theutil_avgscales lower thanSCHED_CAPACITY_SCALE. In our test platform, the base frequency is 1.9GHz, and the max turbo frequency is 3.7GHz, so 1.9/3.7 is around 50%. In the future maybe we could usearch_scale_freq_capacity()instead ofsds->total_capacity, so as to remove the impact from frequency. Then the 50% could be adjusted higher. For now, 50% is an aggressive threshold to restric the idle CPU searching and shows benchmark improvement.Q: Why using
nr_scan= a - b *sum_util_avgto do linear search?A: Ideally the
nr_scancould be:
nr_scan=sum_util_avg/pelt_avg_scan_costHowever consider the overhead of calculating pelt on
avg_scan_costin each wake up, choosing heuristic search for evaluation seems to be an acceptable trade-off.The
f(sum_util_avg)could be of any form, as long as it is a monotonically decreasing function. At first f(x) = a - 2^(bx) was chosen. Because when thesum_util_avgis low, the system should try very hard to find an idle CPU. And ifsum_util_avggoes higher, the system dramatically lose its interest to search for the idle CPU. But exponential function does have its drawback:Consider a system with 112 CPUs, let f(x) = 112 when x = 0, f(x) = 4 when x = 50, x belongs to [0, 100], then we have: f1(x) = 113 - 2^(x / 7.35) and f2(x) = 112 - 2.16 * x Since kernel does not support floating point, above functions are converted into: nr_scan1(x) = 113 - 2^(x / 7) and nr_scan2(x) = 112 - 2 * x util_avg% 0 1 2 ... 8 9 ... 47 48 49 nr_scan1 112 112 112 111 111 49 49 4 nr_scan2 112 110 108 96 94 18 16 14 According to above result, the granularity of exponential function is coarse-grained, while the linear function is fine-grained. So finally choose linear function. After all, it has shown benchmark benefit without noticeable regression so far.Q: How to deal with the following corner case:
It is possible that there is unbalanced tasks among CPUs due to CPU affinity. For example, suppose the LLC domain is composed of 6 CPUs, and 5 tasks are bound to CPU0~CPU4, while CPU5 is idle:
CPU0 CPU1 CPU2 CPU3 CPU4 CPU5
util_avg1024 1024 1024 1024 1024 0
Quoted 8 lines
Since the
util_avgratio is 83%( = 5/6 ), which is higher than 50%,select_idle_cpu()only searches 4 CPUs starting from CPU0, thus leaves idle CPU5 undetected.A possible workaround to mitigate this problem is that, the
nr_scanshould be increased by the number of idle CPUs found during periodic load balance inupdate_sd_lb_stats(). In above example, thenr_scanwill be adjusted to 4 + 1 = 5. Currently I don't have better solution in mind to deal with it gracefully.
Without CPU affinity, is it possible that we also meet this case? Considering we always scan from the target cpu and the further cpus have less chance to be checked, the scan possibility of each CPUs is not equal. When the util_avg ratio >50%, after several wakeups from CPU0 the CPU 1~4 will be non-idle andthe following scans may fail without checking CPU5.
Quoted 53 lines
Any comment is appreciated.
Suggested-by Tim Chen <[email protected]>Suggested-by Peter Zijlstra <[email protected]>Signed-off-by Chen Yu <[email protected]>--- include/linux/sched/topology.h | 1 + kernel/sched/fair.c | 107 +++++++++++++++++++-------------- 2 files changed, 63 insertions(+), 45 deletions(-)include/linux/sched/topology.h +1
-0@@ -81,6 +81,7 @@ struct sched_domain_shared {atomic_t ref;atomic_t nr_busy_cpus;int has_idle_cores; +int nr_idle_scan; };struct sched_domain {kernel/sched/fair.c +1
-16@@ -6271,43 +6271,14 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool {struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask);int i, cpu, idle_cpu =-1 , nr =INT_MAX ; -struct rq *this_rq =this_rq (); -int this =smp_processor_id (); -struct sched_domain *this_sd; -u64 time =0 ; - - this_sd =rcu_dereference (*this_cpu_ptr (&sd_llc)); -if (!this_sd) -return -1 ; +struct sched_domain_shared *sd_share;cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr);if (sched_feat (SIS_PROP ) && !has_idle_core) { -u64 avg_cost, avg_idle, span_avg; -unsigned long now = jiffies; - -/* -* If we're busy, the assumption that the last idle period -* predicts the future is flawed; age away the remaining -* predicted idle time. -*/
kernel/sched/fair.c static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool · line 6303
Quoted 10 lines
kernel/sched/fair.c +0
-10-if (unlikely (this_rq->wake_stamp < now)) { -while (this_rq->wake_stamp < now && this_rq->wake_avg_idle) { - this_rq->wake_stamp++; - this_rq->wake_avg_idle >>=1 ; - } - } - - avg_idle = this_rq->wake_avg_idle; - avg_cost = this_sd->avg_scan_cost +1 ; -
With this patch, sd->avg_scan_cost, rq->{wake_stamp, wake_avg_idle} may have no users.
Thanks,
Yicong
Quoted 118 lines
kernel/sched/fair.c +61
-19- span_avg = sd->span_weight * avg_idle; -if (span_avg >4 *avg_cost) - nr =div_u64 (span_avg, avg_cost); -else - nr =4 ; - - time =cpu_clock (this); + sd_share =rcu_dereference (per_cpu (sd_llc_shared, target)); +if (sd_share) + nr =READ_ONCE (sd_share->nr_idle_scan); }for_each_cpu_wrap (cpu, cpus, target +1 ) {@@ -6328,18 +6299,6 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, boolif (has_idle_core)set_idle_cores (target, false); -if (sched_feat (SIS_PROP ) && !has_idle_core) { - time =cpu_clock (this) - time; - -/* -* Account for the scan cost of wakeups against the average -* idle time. -*/ - this_rq->wake_avg_idle -=min (this_rq->wake_avg_idle, time); - -update_avg (&this_sd->avg_scan_cost, time); - } -return idle_cpu; }@@ -9199,6 +9158,60 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)return idlest; } +static inline void update_nr_idle_scan (struct lb_env *env,struct sd_lb_stats *sds, +unsigned long sum_util) +{ +struct sched_domain_shared *sd_share; +int llc_size =per_cpu (sd_llc_size, env->dst_cpu); +int nr_scan; + +/* +* Update the number of CPUs to scan in LLC domain, which could +* be used as a hint in select_idle_cpu(). The update of this hint +* occurs during periodic load balancing, rather than frequent +* newidle balance. +*/ +if (env->idle ==CPU_NEWLY_IDLE || env->sd->span_weight != llc_size) +return ; + + sd_share =rcu_dereference (per_cpu (sd_llc_shared, env->dst_cpu)); +if (!sd_share) +return ; + +/* +* In general, the number of cpus to be scanned should be +* inversely proportional to the sum_util. That is, the lower +* the sum_util is, the harder select_idle_cpu() should scan +* for idle CPU, and vice versa. Let x be the sum_util ratio +* [0-100] of the LLC domain, f(x) be the number of CPUs scanned: +* +* f(x) = a - bx [1] +* +* Consider that f(x) = nr_llc when x = 0, and f(x) = 4 when +* x >= threshold('h' below) then: +* +* a = llc_size; +* b = (nr_llc - 4) / h [2] +* +* then [2] becomes: +* +* f(x) = llc_size - (llc_size -4)x/h [3] +* +* Choose 50 (50%) for h as the threshold from experiment result. +* And since x = 100 * sum_util / total_cap, [3] becomes: +* +* f(sum_util) +* = llc_size - (llc_size - 4) * 100 * sum_util / total_cap * 50 +* = llc_size - (llc_size - 4) * 2 * sum_util / total_cap +* +*/ + nr_scan = llc_size - (llc_size -4 ) *2 * sum_util / sds->total_capacity; +if (nr_scan <4 ) + nr_scan =4 ; + +WRITE_ONCE (sd_share->nr_idle_scan, nr_scan); +} +/** * update_sd_lb_stats - Update sched_domain's statistics for load balancing. * @env: The load balancing environment. @@ -9212,6 +9225,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdstruct sg_lb_stats *local = &sds->local_stat;struct sg_lb_stats tmp_sgs;int sg_status =0 ; +unsigned long sum_util =0 ; do { struct sg_lb_stats *sgs = &tmp_sgs;@@ -9242,6 +9256,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd/* Now, start updating sd_lb_stats */ sds->total_load += sgs->group_load; sds->total_capacity += sgs->group_capacity; + sum_util += sgs->group_util; sg = sg->next; }while (sg != env->sd->groups);@@ -9268,6 +9283,8 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdWRITE_ONCE (rd->overutilized,SG_OVERUTILIZED );trace_sched_overutilized_tp (rd,SG_OVERUTILIZED ); } + +update_nr_idle_scan (env, sds, sum_util); }#define NUMA_IMBALANCE_MIN 2
Hi Yicong,
Quoted 79 lines · Yicong Yang
Hi Chen,
Thanks for the update. I'm still testing on this along with the sched cluster patches. I'll show some results when I get enough data. So some questions below.
Quoted 66 lines · Chen Yu
[Problem Statement]
Currentlyselect_idle_cpu()uses the percpu average idle time to estimate the total LLC domain idle time, and calculate the number of CPUs to be scanned. This might be inconsistent because idle time of a CPU does not necessarily correlate with idle time of a domain. As a result, the load could be underestimated and causes over searching when the system is very busy.The following histogram is the time spent in
select_idle_cpu(), when running 224 instance of netperf on a system with 112 CPUs per LLC domain:@usecs:
[0] 533 | | [1] 5495 | | [2, 4) 12008 | | [4, 8) 239252 | | [8, 16) 4041924 |@@@@@@@@@@@@@@ | [16, 32) 12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [32, 64) 14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [64, 128) 13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [128, 256) 8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [256, 512) 4507667 |@@@@@@@@@@@@@@@ | [512, 1K) 2600472 |@@@@@@@@@ | [1K, 2K) 927912 |@@@ | [2K, 4K) 218720 | | [4K, 8K) 98161 | | [8K, 16K) 37722 | | [16K, 32K) 6715 | | [32K, 64K) 477 | | [64K, 128K) 7 | |netperf latency:
=======case load Lat_99th std% TCP_RR thread-224 257.39 ( 0.21) UDP_RR thread-224 242.83 ( 6.29)The netperf 99th latency(usec) above is comparable with the time spent in
select_idle_cpu(). That is to say, when the system is overloaded, searching for idle CPU could be a bottleneck.[Proposal]
The main idea is to replace percpu average idle time with the domain based metric. Choose average CPUutilization(util_avg)as the candidate. In general, the number of CPUs to be scanned should be inversely proportional to the sum ofutil_avgin this domain. That is, the lower theutil_avgis, the moreselect_idle_cpu()should scan for idle CPU, and vice versa. The benefit of choosingutil_avgis that, it is a metric of accumulated historic activity, which seems to be more accurate than instantaneousmetrics(such as rq->nr_running).Furthermore, borrow the
util_avgfrom periodic load balance, which could offload the overhead ofselect_idle_cpu().According to last discussion[1], introduced the linear function for experimental purpose:
f(x) = a - bx
llc_size
x = \Sum util_avg[cpu] /llc_cpu_capacity1f(x) is the number of CPUs to be scanned, x is the sum
util_avg. To decide a and b, the following condition should be met:Quoted 6 lines
[1] f(0) =
llc_size
[2] f(x) = 4, x >= 50%That is to say, when the
util_avgis 0, we should search for the whole LLC domain. And ifutil_avgratio reaches 50% or higher, it should search at most 4 CPUs.
Quoted 7 lines
I might have a question here. In your V1 patch, we won't scan when the LLC util >85%. But in this patch we'll always scan 4 cpus no matter how much the LLC is overloaded. When the LLC is rather busy the scan is probably redundant so is it better if we found a threadhold for stopping the scan? The
util_avgcannot indicate how much the cpu is overloaded so perhaps just stop scan when it is 100% utilized.
The reason we makes the scan number >=4 is that:
1. In the tbench test result based on v1 in your environment, there seems to be a -8.49% downgrading with 128 threads. It is possible that, when there is 128 thread in your system, it is not fully busy, but we give up searching for an idle CPU, which causes downgrading. Tim suggested that we can still search for a minimal number of CPU even the system is very busy.
2. This is consistent with the current kernel's logic, 4 is the minal search number no matter how busy the system is.
https://lore.kernel.org/lkml/[email protected]/
Quoted 203 lines
Quoted 203 lines
Yes, there would be questions like:
Why using this linear function to calculate the number of CPUs to be scanned? Why choosing 50% as the threshold? These questions will be discussed in the [Limitations] section.[Benchmark]
netperf, hackbench, schbench, tbench
were tested with 25% 50% 75% 100% 125% 150% 175% 200% instance of CPU number (these ratios are not CPU utilization). Each test lasts for 100 seconds, and repeats 3 times. The system would reboot into a fresh environment for each benchmark.The following is the benchmark result comparison between baseline:vanilla and compare:patched kernel. Positive compare% indicates better performance.
netperf
=======case load baseline(std%) compare%( std%) TCP_RR 28 threads 1.00 ( 0.30) -1.26 ( 0.32) TCP_RR 56 threads 1.00 ( 0.35) -1.26 ( 0.41) TCP_RR 84 threads 1.00 ( 0.46) -0.15 ( 0.60) TCP_RR 112 threads 1.00 ( 0.36) +0.44 ( 0.41) TCP_RR 140 threads 1.00 ( 0.23) +0.95 ( 0.21) TCP_RR 168 threads 1.00 ( 0.20) +177.77 ( 3.78) TCP_RR 196 threads 1.00 ( 0.18) +185.43 ( 10.08) TCP_RR 224 threads 1.00 ( 0.16) +187.86 ( 7.32) UDP_RR 28 threads 1.00 ( 0.43) -0.93 ( 0.27) UDP_RR 56 threads 1.00 ( 0.17) -0.39 ( 10.91) UDP_RR 84 threads 1.00 ( 6.36) +1.03 ( 0.92) UDP_RR 112 threads 1.00 ( 5.55) +1.47 ( 17.67) UDP_RR 140 threads 1.00 ( 18.17) +0.31 ( 15.48) UDP_RR 168 threads 1.00 ( 15.00) +153.87 ( 13.20) UDP_RR 196 threads 1.00 ( 16.26) +169.19 ( 13.78) UDP_RR 224 threads 1.00 ( 51.81) +76.72 ( 10.95)hackbench
=========
(each group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) process-pipe 1 group 1.00 ( 0.47) -0.46 ( 0.16) process-pipe 2 groups 1.00 ( 0.42) -0.61 ( 0.74) process-pipe 3 groups 1.00 ( 0.42) +0.38 ( 0.20) process-pipe 4 groups 1.00 ( 0.15) -0.36 ( 0.56) process-pipe 5 groups 1.00 ( 0.20) -5.08 ( 0.01) process-pipe 6 groups 1.00 ( 0.28) -2.98 ( 0.29) process-pipe 7 groups 1.00 ( 0.08) -1.18 ( 0.28) process-pipe 8 groups 1.00 ( 0.11) -0.40 ( 0.07) process-sockets 1 group 1.00 ( 0.43) -1.93 ( 0.58) process-sockets 2 groups 1.00 ( 0.23) -1.10 ( 0.49) process-sockets 3 groups 1.00 ( 1.10) -0.96 ( 1.12) process-sockets 4 groups 1.00 ( 0.59) -0.08 ( 0.88) process-sockets 5 groups 1.00 ( 0.45) +0.31 ( 0.34) process-sockets 6 groups 1.00 ( 0.23) +0.06 ( 0.66) process-sockets 7 groups 1.00 ( 0.12) +1.72 ( 0.20) process-sockets 8 groups 1.00 ( 0.11) +1.98 ( 0.02) threads-pipe 1 group 1.00 ( 1.07) +0.03 ( 0.40) threads-pipe 2 groups 1.00 ( 1.05) +0.19 ( 1.27) threads-pipe 3 groups 1.00 ( 0.32) -0.42 ( 0.48) threads-pipe 4 groups 1.00 ( 0.42) -0.76 ( 0.79) threads-pipe 5 groups 1.00 ( 0.19) -4.97 ( 0.07) threads-pipe 6 groups 1.00 ( 0.05) -4.11 ( 0.04) threads-pipe 7 groups 1.00 ( 0.10) -1.13 ( 0.16) threads-pipe 8 groups 1.00 ( 0.03) -0.08 ( 0.05) threads-sockets 1 group 1.00 ( 0.33) -1.93 ( 0.69) threads-sockets 2 groups 1.00 ( 0.20) -1.55 ( 0.30) threads-sockets 3 groups 1.00 ( 0.37) -1.29 ( 0.59) threads-sockets 4 groups 1.00 ( 1.83) +0.31 ( 1.17) threads-sockets 5 groups 1.00 ( 0.28) +15.73 ( 0.24) threads-sockets 6 groups 1.00 ( 0.15) +5.02 ( 0.34) threads-sockets 7 groups 1.00 ( 0.10) +2.29 ( 0.14) threads-sockets 8 groups 1.00 ( 0.17) +2.22 ( 0.12)tbench
======case load baseline(std%) compare%( std%) loopback 28 threads 1.00 ( 0.05) -1.39 ( 0.04) loopback 56 threads 1.00 ( 0.08) -0.37 ( 0.04) loopback 84 threads 1.00 ( 0.03) +0.20 ( 0.13) loopback 112 threads 1.00 ( 0.04) +0.69 ( 0.04) loopback 140 threads 1.00 ( 0.13) +1.15 ( 0.21) loopback 168 threads 1.00 ( 0.03) +1.62 ( 0.08) loopback 196 threads 1.00 ( 0.08) +1.50 ( 0.30) loopback 224 threads 1.00 ( 0.05) +1.62 ( 0.05)schbench
========
(each mthread group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67) normal 2 mthread groups 1.00 ( 21.10) +8.32 ( 16.92) normal 3 mthread groups 1.00 ( 10.80) +10.03 ( 9.21) normal 4 mthread groups 1.00 ( 2.67) +0.11 ( 3.00) normal 5 mthread groups 1.00 ( 0.08) +0.00 ( 0.13) normal 6 mthread groups 1.00 ( 2.99) -2.66 ( 3.87) normal 7 mthread groups 1.00 ( 2.16) -0.83 ( 2.24) normal 8 mthread groups 1.00 ( 1.75) +0.18 ( 3.18)According to the results above, when the workloads is heavy, the throughput of netperf improves a lot. It might be interesting to look into the reason why this patch benefits netperf significantly. Further investigation has shown that, this might be a 'side effect' of this patch. It is found that, the CPU utilization is around 90% on vanilla kernel, while it is nearly 100% on patched kernel. According to the perf profile, with the patch applied, the scheduler would likely to choose previous running CPU for the waking task, thus reduces runqueue lock contention, so the CPU utilization is higher and get better performance.
[Limitations]
Q:Why using 50% as the util_avg/capacity threshold to search at most 4 CPUs?A: 50% is chosen as that corresponds to almost full CPU utilization, when
the CPU is fixed to run at its base frequency, with turbo enabled. 4 is the minimal number of CPUs to be scanned in currentselect_idle_cpu().A synthetic workload was used to simulate different level of load. This workload takes every 10ms as the sample period, and in each sample period:
while (!timeout_10ms) { loop(busy_pct_ms); sleep(10ms-busy_pct_ms) }to simulate busy_pct% of CPU utilization. When the workload is running, the percpu runqueue
util_avgwas monitored. The following is the result from turbostat's Busy% on CPU2 and cfs_rq[2].util_avg from/sys/kernel/debug/sched/debug:Busy% util_avg util_avg/cpu_capacity% 10.06 35 3.42 19.97 99 9.67 29.93 154 15.04 39.86 213 20.80 49.79 256 25.00 59.73 325 31.74 69.77 437 42.68 79.69 458 44.73 89.62 519 50.68 99.54 598 58.39The reason why
util_avgratio is not consistent with Busy% might be due to CPU frequency invariance. The CPU is running at fixed lower frequency than the turbo frequency, then theutil_avgscales lower thanSCHED_CAPACITY_SCALE. In our test platform, the base frequency is 1.9GHz, and the max turbo frequency is 3.7GHz, so 1.9/3.7 is around 50%. In the future maybe we could usearch_scale_freq_capacity()instead ofsds->total_capacity, so as to remove the impact from frequency. Then the 50% could be adjusted higher. For now, 50% is an aggressive threshold to restric the idle CPU searching and shows benchmark improvement.Q: Why using
nr_scan= a - b *sum_util_avgto do linear search?A: Ideally the
nr_scancould be:
nr_scan=sum_util_avg/pelt_avg_scan_costHowever consider the overhead of calculating pelt on
avg_scan_costin each wake up, choosing heuristic search for evaluation seems to be an acceptable trade-off.The
f(sum_util_avg)could be of any form, as long as it is a monotonically decreasing function. At first f(x) = a - 2^(bx) was chosen. Because when thesum_util_avgis low, the system should try very hard to find an idle CPU. And ifsum_util_avggoes higher, the system dramatically lose its interest to search for the idle CPU. But exponential function does have its drawback:Consider a system with 112 CPUs, let f(x) = 112 when x = 0, f(x) = 4 when x = 50, x belongs to [0, 100], then we have: f1(x) = 113 - 2^(x / 7.35) and f2(x) = 112 - 2.16 * x Since kernel does not support floating point, above functions are converted into: nr_scan1(x) = 113 - 2^(x / 7) and nr_scan2(x) = 112 - 2 * x util_avg% 0 1 2 ... 8 9 ... 47 48 49 nr_scan1 112 112 112 111 111 49 49 4 nr_scan2 112 110 108 96 94 18 16 14 According to above result, the granularity of exponential function is coarse-grained, while the linear function is fine-grained. So finally choose linear function. After all, it has shown benchmark benefit without noticeable regression so far.Q: How to deal with the following corner case:
It is possible that there is unbalanced tasks among CPUs due to CPU affinity. For example, suppose the LLC domain is composed of 6 CPUs, and 5 tasks are bound to CPU0~CPU4, while CPU5 is idle:
CPU0 CPU1 CPU2 CPU3 CPU4 CPU5
util_avg1024 1024 1024 1024 1024 0Since the
util_avgratio is 83%( = 5/6 ), which is higher than 50%,select_idle_cpu()only searches 4 CPUs starting from CPU0, thus leaves idle CPU5 undetected.
Quoted 7 lines
Quoted 5 lines
A possible workaround to mitigate this problem is that, the
nr_scanshould be increased by the number of idle CPUs found during periodic load balance inupdate_sd_lb_stats(). In above example, thenr_scanwill be adjusted to 4 + 1 = 5. Currently I don't have better solution in mind to deal with it gracefully.Without CPU affinity, is it possible that we also meet this case?
Yes, it is true.
Quoted 4 lines
Considering we always scan from the target cpu and the further cpus have less chance to be checked, the scan possibility of each CPUs is not equal. When the
util_avgratio >50%, after several wakeups from CPU0 the CPU 1~4 will be non-idle andthe following scans may fail without checking CPU5.
In this case, we relies on the load balance path to migrate some tasks among CPUs and 'saturate'this LLC domain equally.
Quoted 18 lines
Quoted 5 lines
kernel/sched/fair.c +0
-4-* If we're busy, the assumption that the last idle period -* predicts the future is flawed; age away the remaining -* predicted idle time. -*/ kernel/sched/fair.c static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool · line 6303
Quoted 10 lines
kernel/sched/fair.c +0
-10-if (unlikely (this_rq->wake_stamp < now)) { -while (this_rq->wake_stamp < now && this_rq->wake_avg_idle) { - this_rq->wake_stamp++; - this_rq->wake_avg_idle >>=1 ; - } - } - - avg_idle = this_rq->wake_avg_idle; - avg_cost = this_sd->avg_scan_cost +1 ; -With this patch,
sd->avg_scan_cost, rq->{wake_stamp,wake_avg_idle} may have no users.
If we 'rebase' the SIS_PRO to use sum_util_avg, it seems that avg_scan_cost and rq->{wake_stamp, wake_avg_idle} are not needed IMO.
For rq->{wake_stamp, wake_avg_idle}, it is used to reduce the search number when waking up a task on a busy rq. However this metric still uses one CPU's statistic to predict the whole system's status, which is trying to be avoid in this patch.
For sd->avg_scan_cost, unless we use sum_util_avg / pelt(sd->avg_scan_cost), it could be leveraged to predict the number of CPUs to scan. I'm not sure how much the overhead is when calculating pelt on sd->avg_scan_cost each time during wakeup, but I can have a try to get some data.
thanks,
Chenyu
Quoted 121 lines
Thanks,
YicongQuoted 118 lines
kernel/sched/fair.c +61
-19- span_avg = sd->span_weight * avg_idle; -if (span_avg >4 *avg_cost) - nr =div_u64 (span_avg, avg_cost); -else - nr =4 ; - - time =cpu_clock (this); + sd_share =rcu_dereference (per_cpu (sd_llc_shared, target)); +if (sd_share) + nr =READ_ONCE (sd_share->nr_idle_scan); }for_each_cpu_wrap (cpu, cpus, target +1 ) {@@ -6328,18 +6299,6 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, boolif (has_idle_core)set_idle_cores (target, false); -if (sched_feat (SIS_PROP ) && !has_idle_core) { - time =cpu_clock (this) - time; - -/* -* Account for the scan cost of wakeups against the average -* idle time. -*/ - this_rq->wake_avg_idle -=min (this_rq->wake_avg_idle, time); - -update_avg (&this_sd->avg_scan_cost, time); - } -return idle_cpu; }@@ -9199,6 +9158,60 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)return idlest; } +static inline void update_nr_idle_scan (struct lb_env *env,struct sd_lb_stats *sds, +unsigned long sum_util) +{ +struct sched_domain_shared *sd_share; +int llc_size =per_cpu (sd_llc_size, env->dst_cpu); +int nr_scan; + +/* +* Update the number of CPUs to scan in LLC domain, which could +* be used as a hint in select_idle_cpu(). The update of this hint +* occurs during periodic load balancing, rather than frequent +* newidle balance. +*/ +if (env->idle ==CPU_NEWLY_IDLE || env->sd->span_weight != llc_size) +return ; + + sd_share =rcu_dereference (per_cpu (sd_llc_shared, env->dst_cpu)); +if (!sd_share) +return ; + +/* +* In general, the number of cpus to be scanned should be +* inversely proportional to the sum_util. That is, the lower +* the sum_util is, the harder select_idle_cpu() should scan +* for idle CPU, and vice versa. Let x be the sum_util ratio +* [0-100] of the LLC domain, f(x) be the number of CPUs scanned: +* +* f(x) = a - bx [1] +* +* Consider that f(x) = nr_llc when x = 0, and f(x) = 4 when +* x >= threshold('h' below) then: +* +* a = llc_size; +* b = (nr_llc - 4) / h [2] +* +* then [2] becomes: +* +* f(x) = llc_size - (llc_size -4)x/h [3] +* +* Choose 50 (50%) for h as the threshold from experiment result. +* And since x = 100 * sum_util / total_cap, [3] becomes: +* +* f(sum_util) +* = llc_size - (llc_size - 4) * 100 * sum_util / total_cap * 50 +* = llc_size - (llc_size - 4) * 2 * sum_util / total_cap +* +*/ + nr_scan = llc_size - (llc_size -4 ) *2 * sum_util / sds->total_capacity; +if (nr_scan <4 ) + nr_scan =4 ; + +WRITE_ONCE (sd_share->nr_idle_scan, nr_scan); +} +/** * update_sd_lb_stats - Update sched_domain's statistics for load balancing. * @env: The load balancing environment. @@ -9212,6 +9225,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdstruct sg_lb_stats *local = &sds->local_stat;struct sg_lb_stats tmp_sgs;int sg_status =0 ; +unsigned long sum_util =0 ; do { struct sg_lb_stats *sgs = &tmp_sgs;@@ -9242,6 +9256,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd/* Now, start updating sd_lb_stats */ sds->total_load += sgs->group_load; sds->total_capacity += sgs->group_capacity; + sum_util += sgs->group_util; sg = sg->next; }while (sg != env->sd->groups);@@ -9268,6 +9283,8 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdWRITE_ONCE (rd->overutilized,SG_OVERUTILIZED );trace_sched_overutilized_tp (rd,SG_OVERUTILIZED ); } + +update_nr_idle_scan (env, sds, sum_util); }#define NUMA_IMBALANCE_MIN 2
Quoted 88 lines · Chen Yu
Hi Yicong,
Quoted 79 lines · Yicong Yang
Hi Chen,
Thanks for the update. I'm still testing on this along with the sched cluster patches. I'll show some results when I get enough data. So some questions below.
Quoted 66 lines · Chen Yu
[Problem Statement]
Currentlyselect_idle_cpu()uses the percpu average idle time to estimate the total LLC domain idle time, and calculate the number of CPUs to be scanned. This might be inconsistent because idle time of a CPU does not necessarily correlate with idle time of a domain. As a result, the load could be underestimated and causes over searching when the system is very busy.The following histogram is the time spent in
select_idle_cpu(), when running 224 instance of netperf on a system with 112 CPUs per LLC domain:@usecs:
[0] 533 | | [1] 5495 | | [2, 4) 12008 | | [4, 8) 239252 | | [8, 16) 4041924 |@@@@@@@@@@@@@@ | [16, 32) 12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [32, 64) 14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [64, 128) 13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [128, 256) 8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@ | [256, 512) 4507667 |@@@@@@@@@@@@@@@ | [512, 1K) 2600472 |@@@@@@@@@ | [1K, 2K) 927912 |@@@ | [2K, 4K) 218720 | | [4K, 8K) 98161 | | [8K, 16K) 37722 | | [16K, 32K) 6715 | | [32K, 64K) 477 | | [64K, 128K) 7 | |netperf latency:
=======case load Lat_99th std% TCP_RR thread-224 257.39 ( 0.21) UDP_RR thread-224 242.83 ( 6.29)The netperf 99th latency(usec) above is comparable with the time spent in
select_idle_cpu(). That is to say, when the system is overloaded, searching for idle CPU could be a bottleneck.[Proposal]
The main idea is to replace percpu average idle time with the domain based metric. Choose average CPUutilization(util_avg)as the candidate. In general, the number of CPUs to be scanned should be inversely proportional to the sum ofutil_avgin this domain. That is, the lower theutil_avgis, the moreselect_idle_cpu()should scan for idle CPU, and vice versa. The benefit of choosingutil_avgis that, it is a metric of accumulated historic activity, which seems to be more accurate than instantaneousmetrics(such as rq->nr_running).Furthermore, borrow the
util_avgfrom periodic load balance, which could offload the overhead ofselect_idle_cpu().According to last discussion[1], introduced the linear function for experimental purpose:
f(x) = a - bx
llc_size
x = \Sum util_avg[cpu] /llc_cpu_capacity1f(x) is the number of CPUs to be scanned, x is the sum
util_avg. To decide a and b, the following condition should be met:Quoted 6 lines
[1] f(0) =
llc_size
[2] f(x) = 4, x >= 50%That is to say, when the
util_avgis 0, we should search for the whole LLC domain. And ifutil_avgratio reaches 50% or higher, it should search at most 4 CPUs.Quoted 7 lines
I might have a question here. In your V1 patch, we won't scan when the LLC util >85%. But in this patch we'll always scan 4 cpus no matter how much the LLC is overloaded. When the LLC is rather busy the scan is probably redundant so is it better if we found a threadhold for stopping the scan? The
util_avgcannot indicate how much the cpu is overloaded so perhaps just stop scan when it is 100% utilized.
Quoted 10 lines
The reason we makes the scan number >=4 is that:
1. In the tbench test result based on v1 in your environment, there seems to be a -8.49% downgrading with 128 threads. It is possible that, when there is 128 thread in your system, it is not fully busy, but we give up searching for an idle CPU, which causes downgrading. Tim suggested that we can still search for a minimal number of CPU even the system is very busy.
2. This is consistent with the current kernel's logic, 4 is the minal search number no matter how busy the system is.
https://lore.kernel.org/lkml/[email protected]/
FYI, shenyang has done some investigation on whether we can get an idle cpu if the nr is 4. For netperf running on node 0-1 (32 cores on each node) with 32, 64, 128 threads, the success rate of findindg an idle cpu is about 61.8%, 7.4%, <0.1%, the CPU utilizaiton is 70.7%, 87.4% and 99.9% respectively.
I have test this patch based on 5.17-rc7 on Kunpeng 920. The benchmarks are binding to node 0 or node 0-1. The tbench result has some oscillation so I need to have a further check. For netperf I see performance enhancement when the threads equals to the cpu number.
For netperf:TCP_RR 2 nodes
threads base patched pct
16 50335.56667 49970.63333 -0.73%
32 47281.53333 48191.93333 1.93%
64 18907.7 34263.63333 81.22%
128 14391.1 14480.8 0.62%
256 6905.286667 6853.83 -0.75%
TCP_RR 1 node
threads base patched pct
16 50086.06667 49648.13333 -0.87%
32 24983.3 39489.43333 58.06%
64 18340.03333 18399.56667 0.32%
128 7174.713333 7390.09 3.00%
256 3433.696667 3404.956667 -0.84%
UDP_RR 2 nodes
threads base patched pct
16 81448.7 82659.43333 1.49%
32 75351.13333 76812.36667 1.94%
64 25539.46667 41835.96667 63.81%
128 25081.56667 23595.56667 -5.92%
256 11848.23333 11017.13333 -7.01%
UDP_RR 1 node
threads base patched pct
16 87288.96667 88719.83333 1.64%
32 22891.73333 68854.33333 200.78%
64 33853.4 35891.6 6.02%
128 12108.4 11885.76667 -1.84%
256 5620.403333 5531.006667 -1.59%
mysql on node 0-1
base patched pct
16threads-TPS 7100.27 7224.31 1.75%
16threads-QPS 142005.45 144486.19 1.75%
16threads-avg lat 2.25 2.22 1.63%
16threads-99th lat 2.46 2.43 1.08%
24threads-TPS 10424.70 10312.20 -1.08%
24threads-QPS 208493.86 206243.93 -1.08%
24threads-avg lat 2.30 2.32 -0.87%
24threads-99th lat 2.52 2.57 -1.85%
32threads-TPS 12528.79 12228.88 -2.39%
32threads-QPS 250575.92 244577.59 -2.39%
32threads-avg lat 2.55 2.61 -2.35%
32threads-99th lat 2.88 2.99 -3.82%
64threads-TPS 21386.17 21789.99 1.89%
64threads-QPS 427723.41 435799.85 1.89%
64threads-avg lat 2.99 2.94 1.78%
64threads-99th lat 5.00 4.69 6.33%
128threads-TPS 20865.13 20781.24 -0.40%
128threads-QPS 417302.73 415624.83 -0.40%
128threads-avg lat 6.13 6.16 -0.38%
128threads-99th lat 8.90 8.95 -0.60%
256threads-TPS 19258.15 19295.11 0.19%
256threads-QPS 385162.92 385902.27 0.19%
256threads-avg lat 13.29 13.26 0.23%
256threads-99th lat 20.12 20.12 0.00%
I also had a look on a machine with 2-socket Xeon 6148 (80 threads in total) For TCP_RR, the best enhancement also happens when the threads equals to the cpu number.
netperf TCP_RR
threads base patched pct
20 36584.73333 36309 -0.75%
40 26679.6 25958.56667 -2.70%
80 13969.2 14669.13333 5.01%
160 9571.28 9669.026667 1.02%
240 6367.056667 6416.93 0.78%
tbench
base patched
Hmean 1 255.73 ( 0.00%) 255.44 * -0.11%* Hmean 2 508.75 ( 0.00%) 511.09 * 0.46%* Hmean 4 1014.11 ( 0.00%) 1009.36 * -0.47%* Hmean 8 1989.11 ( 0.00%) 1978.16 * -0.55%* Hmean 16 3772.11 ( 0.00%) 3778.19 * 0.16%* Hmean 32 6106.35 ( 0.00%) 5969.34 * -2.24%* Hmean 64 6627.70 ( 0.00%) 6680.38 * 0.79%* Hmean 128 12345.44 ( 0.00%) 12436.74 * 0.74%* Hmean 256 12204.99 ( 0.00%) 12271.06 * 0.54%* Hmean 320 12037.84 ( 0.00%) 12142.56 * 0.87%*
hackbench-process-pipes
base patched
Amean 1 0.3482 ( 0.00%) 0.3385 * 2.79%* Amean 4 0.9519 ( 0.00%) 0.9423 * 1.01%* Amean 7 1.3334 ( 0.00%) 1.3665 * -2.48%* Amean 12 2.1149 ( 0.00%) 2.2927 * -8.41%* Amean 21 3.9327 ( 0.00%) 4.3591 * -10.84%* Amean 30 6.8436 ( 0.00%) 6.2177 * 9.15%* Amean 48 12.3377 ( 0.00%) 11.6233 * 5.79%* Amean 79 17.0142 ( 0.00%) 16.8587 * 0.91%* Amean 110 21.3452 ( 0.00%) 21.6252 * -1.31%* Amean 141 26.9371 ( 0.00%) 26.7137 * 0.83%* Amean 160 30.2086 ( 0.00%) 30.2942 * -0.28%*
Quoted 372 lines
Quoted 203 lines
Quoted 203 lines
Yes, there would be questions like:
Why using this linear function to calculate the number of CPUs to be scanned? Why choosing 50% as the threshold? These questions will be discussed in the [Limitations] section.[Benchmark]
netperf, hackbench, schbench, tbench
were tested with 25% 50% 75% 100% 125% 150% 175% 200% instance of CPU number (these ratios are not CPU utilization). Each test lasts for 100 seconds, and repeats 3 times. The system would reboot into a fresh environment for each benchmark.The following is the benchmark result comparison between baseline:vanilla and compare:patched kernel. Positive compare% indicates better performance.
netperf
=======case load baseline(std%) compare%( std%) TCP_RR 28 threads 1.00 ( 0.30) -1.26 ( 0.32) TCP_RR 56 threads 1.00 ( 0.35) -1.26 ( 0.41) TCP_RR 84 threads 1.00 ( 0.46) -0.15 ( 0.60) TCP_RR 112 threads 1.00 ( 0.36) +0.44 ( 0.41) TCP_RR 140 threads 1.00 ( 0.23) +0.95 ( 0.21) TCP_RR 168 threads 1.00 ( 0.20) +177.77 ( 3.78) TCP_RR 196 threads 1.00 ( 0.18) +185.43 ( 10.08) TCP_RR 224 threads 1.00 ( 0.16) +187.86 ( 7.32) UDP_RR 28 threads 1.00 ( 0.43) -0.93 ( 0.27) UDP_RR 56 threads 1.00 ( 0.17) -0.39 ( 10.91) UDP_RR 84 threads 1.00 ( 6.36) +1.03 ( 0.92) UDP_RR 112 threads 1.00 ( 5.55) +1.47 ( 17.67) UDP_RR 140 threads 1.00 ( 18.17) +0.31 ( 15.48) UDP_RR 168 threads 1.00 ( 15.00) +153.87 ( 13.20) UDP_RR 196 threads 1.00 ( 16.26) +169.19 ( 13.78) UDP_RR 224 threads 1.00 ( 51.81) +76.72 ( 10.95)hackbench
=========
(each group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) process-pipe 1 group 1.00 ( 0.47) -0.46 ( 0.16) process-pipe 2 groups 1.00 ( 0.42) -0.61 ( 0.74) process-pipe 3 groups 1.00 ( 0.42) +0.38 ( 0.20) process-pipe 4 groups 1.00 ( 0.15) -0.36 ( 0.56) process-pipe 5 groups 1.00 ( 0.20) -5.08 ( 0.01) process-pipe 6 groups 1.00 ( 0.28) -2.98 ( 0.29) process-pipe 7 groups 1.00 ( 0.08) -1.18 ( 0.28) process-pipe 8 groups 1.00 ( 0.11) -0.40 ( 0.07) process-sockets 1 group 1.00 ( 0.43) -1.93 ( 0.58) process-sockets 2 groups 1.00 ( 0.23) -1.10 ( 0.49) process-sockets 3 groups 1.00 ( 1.10) -0.96 ( 1.12) process-sockets 4 groups 1.00 ( 0.59) -0.08 ( 0.88) process-sockets 5 groups 1.00 ( 0.45) +0.31 ( 0.34) process-sockets 6 groups 1.00 ( 0.23) +0.06 ( 0.66) process-sockets 7 groups 1.00 ( 0.12) +1.72 ( 0.20) process-sockets 8 groups 1.00 ( 0.11) +1.98 ( 0.02) threads-pipe 1 group 1.00 ( 1.07) +0.03 ( 0.40) threads-pipe 2 groups 1.00 ( 1.05) +0.19 ( 1.27) threads-pipe 3 groups 1.00 ( 0.32) -0.42 ( 0.48) threads-pipe 4 groups 1.00 ( 0.42) -0.76 ( 0.79) threads-pipe 5 groups 1.00 ( 0.19) -4.97 ( 0.07) threads-pipe 6 groups 1.00 ( 0.05) -4.11 ( 0.04) threads-pipe 7 groups 1.00 ( 0.10) -1.13 ( 0.16) threads-pipe 8 groups 1.00 ( 0.03) -0.08 ( 0.05) threads-sockets 1 group 1.00 ( 0.33) -1.93 ( 0.69) threads-sockets 2 groups 1.00 ( 0.20) -1.55 ( 0.30) threads-sockets 3 groups 1.00 ( 0.37) -1.29 ( 0.59) threads-sockets 4 groups 1.00 ( 1.83) +0.31 ( 1.17) threads-sockets 5 groups 1.00 ( 0.28) +15.73 ( 0.24) threads-sockets 6 groups 1.00 ( 0.15) +5.02 ( 0.34) threads-sockets 7 groups 1.00 ( 0.10) +2.29 ( 0.14) threads-sockets 8 groups 1.00 ( 0.17) +2.22 ( 0.12)tbench
======case load baseline(std%) compare%( std%) loopback 28 threads 1.00 ( 0.05) -1.39 ( 0.04) loopback 56 threads 1.00 ( 0.08) -0.37 ( 0.04) loopback 84 threads 1.00 ( 0.03) +0.20 ( 0.13) loopback 112 threads 1.00 ( 0.04) +0.69 ( 0.04) loopback 140 threads 1.00 ( 0.13) +1.15 ( 0.21) loopback 168 threads 1.00 ( 0.03) +1.62 ( 0.08) loopback 196 threads 1.00 ( 0.08) +1.50 ( 0.30) loopback 224 threads 1.00 ( 0.05) +1.62 ( 0.05)schbench
========
(each mthread group has 1/4 * 112 tasks)case load baseline(std%) compare%( std%) normal 1 mthread group 1.00 ( 17.92) +19.23 ( 23.67) normal 2 mthread groups 1.00 ( 21.10) +8.32 ( 16.92) normal 3 mthread groups 1.00 ( 10.80) +10.03 ( 9.21) normal 4 mthread groups 1.00 ( 2.67) +0.11 ( 3.00) normal 5 mthread groups 1.00 ( 0.08) +0.00 ( 0.13) normal 6 mthread groups 1.00 ( 2.99) -2.66 ( 3.87) normal 7 mthread groups 1.00 ( 2.16) -0.83 ( 2.24) normal 8 mthread groups 1.00 ( 1.75) +0.18 ( 3.18)According to the results above, when the workloads is heavy, the throughput of netperf improves a lot. It might be interesting to look into the reason why this patch benefits netperf significantly. Further investigation has shown that, this might be a 'side effect' of this patch. It is found that, the CPU utilization is around 90% on vanilla kernel, while it is nearly 100% on patched kernel. According to the perf profile, with the patch applied, the scheduler would likely to choose previous running CPU for the waking task, thus reduces runqueue lock contention, so the CPU utilization is higher and get better performance.
[Limitations]
Q:Why using 50% as the util_avg/capacity threshold to search at most 4 CPUs?A: 50% is chosen as that corresponds to almost full CPU utilization, when
the CPU is fixed to run at its base frequency, with turbo enabled. 4 is the minimal number of CPUs to be scanned in currentselect_idle_cpu().A synthetic workload was used to simulate different level of load. This workload takes every 10ms as the sample period, and in each sample period:
while (!timeout_10ms) { loop(busy_pct_ms); sleep(10ms-busy_pct_ms) }to simulate busy_pct% of CPU utilization. When the workload is running, the percpu runqueue
util_avgwas monitored. The following is the result from turbostat's Busy% on CPU2 and cfs_rq[2].util_avg from/sys/kernel/debug/sched/debug:Busy% util_avg util_avg/cpu_capacity% 10.06 35 3.42 19.97 99 9.67 29.93 154 15.04 39.86 213 20.80 49.79 256 25.00 59.73 325 31.74 69.77 437 42.68 79.69 458 44.73 89.62 519 50.68 99.54 598 58.39The reason why
util_avgratio is not consistent with Busy% might be due to CPU frequency invariance. The CPU is running at fixed lower frequency than the turbo frequency, then theutil_avgscales lower thanSCHED_CAPACITY_SCALE. In our test platform, the base frequency is 1.9GHz, and the max turbo frequency is 3.7GHz, so 1.9/3.7 is around 50%. In the future maybe we could usearch_scale_freq_capacity()instead ofsds->total_capacity, so as to remove the impact from frequency. Then the 50% could be adjusted higher. For now, 50% is an aggressive threshold to restric the idle CPU searching and shows benchmark improvement.Q: Why using
nr_scan= a - b *sum_util_avgto do linear search?A: Ideally the
nr_scancould be:
nr_scan=sum_util_avg/pelt_avg_scan_costHowever consider the overhead of calculating pelt on
avg_scan_costin each wake up, choosing heuristic search for evaluation seems to be an acceptable trade-off.The
f(sum_util_avg)could be of any form, as long as it is a monotonically decreasing function. At first f(x) = a - 2^(bx) was chosen. Because when thesum_util_avgis low, the system should try very hard to find an idle CPU. And ifsum_util_avggoes higher, the system dramatically lose its interest to search for the idle CPU. But exponential function does have its drawback:Consider a system with 112 CPUs, let f(x) = 112 when x = 0, f(x) = 4 when x = 50, x belongs to [0, 100], then we have: f1(x) = 113 - 2^(x / 7.35) and f2(x) = 112 - 2.16 * x Since kernel does not support floating point, above functions are converted into: nr_scan1(x) = 113 - 2^(x / 7) and nr_scan2(x) = 112 - 2 * x util_avg% 0 1 2 ... 8 9 ... 47 48 49 nr_scan1 112 112 112 111 111 49 49 4 nr_scan2 112 110 108 96 94 18 16 14 According to above result, the granularity of exponential function is coarse-grained, while the linear function is fine-grained. So finally choose linear function. After all, it has shown benchmark benefit without noticeable regression so far.Q: How to deal with the following corner case:
It is possible that there is unbalanced tasks among CPUs due to CPU affinity. For example, suppose the LLC domain is composed of 6 CPUs, and 5 tasks are bound to CPU0~CPU4, while CPU5 is idle:
CPU0 CPU1 CPU2 CPU3 CPU4 CPU5
util_avg1024 1024 1024 1024 1024 0Since the
util_avgratio is 83%( = 5/6 ), which is higher than 50%,select_idle_cpu()only searches 4 CPUs starting from CPU0, thus leaves idle CPU5 undetected.Quoted 7 lines
Quoted 5 lines
A possible workaround to mitigate this problem is that, the
nr_scanshould be increased by the number of idle CPUs found during periodic load balance inupdate_sd_lb_stats(). In above example, thenr_scanwill be adjusted to 4 + 1 = 5. Currently I don't have better solution in mind to deal with it gracefully.Without CPU affinity, is it possible that we also meet this case?
Yes, it is true.
Quoted 4 lines
Considering we always scan from the target cpu and the further cpus have less chance to be checked, the scan possibility of each CPUs is not equal. When the
util_avgratio >50%, after several wakeups from CPU0 the CPU 1~4 will be non-idle andthe following scans may fail without checking CPU5.In this case, we relies on the load balance path to migrate some tasks among CPUs and 'saturate'this LLC domain equally.
Quoted 18 lines
Quoted 5 lines
kernel/sched/fair.c +0
-4-* If we're busy, the assumption that the last idle period -* predicts the future is flawed; age away the remaining -* predicted idle time. -*/ kernel/sched/fair.c static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool · line 6303
Quoted 10 lines
kernel/sched/fair.c +0
-10-if (unlikely (this_rq->wake_stamp < now)) { -while (this_rq->wake_stamp < now && this_rq->wake_avg_idle) { - this_rq->wake_stamp++; - this_rq->wake_avg_idle >>=1 ; - } - } - - avg_idle = this_rq->wake_avg_idle; - avg_cost = this_sd->avg_scan_cost +1 ; -With this patch,
sd->avg_scan_cost, rq->{wake_stamp,wake_avg_idle} may have no users.If we 'rebase' the
SIS_PROto usesum_util_avg, it seems thatavg_scan_costand rq->{wake_stamp,wake_avg_idle} are not needed IMO.
For rq->{wake_stamp,wake_avg_idle}, it is used to reduce the search number when waking up a task on a busy rq. However this metric still uses one CPU's statistic to predict the whole system's status, which is trying to be avoid in this patch.For
sd->avg_scan_cost, unless we usesum_util_avg/pelt(sd->avg_scan_cost), it could be leveraged to predict the number of CPUs to scan. I'm not sure how much the overhead is when calculating pelt onsd->avg_scan_costeach time during wakeup, but I can have a try to get some data.thanks,
ChenyuQuoted 120 lines
Thanks,
YicongQuoted 117 lines
kernel/sched/fair.c +61
-19- span_avg = sd->span_weight * avg_idle; -if (span_avg >4 *avg_cost) - nr =div_u64 (span_avg, avg_cost); -else - nr =4 ; - - time =cpu_clock (this); + sd_share =rcu_dereference (per_cpu (sd_llc_shared, target)); +if (sd_share) + nr =READ_ONCE (sd_share->nr_idle_scan); }for_each_cpu_wrap (cpu, cpus, target +1 ) {@@ -6328,18 +6299,6 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, boolif (has_idle_core)set_idle_cores (target, false); -if (sched_feat (SIS_PROP ) && !has_idle_core) { - time =cpu_clock (this) - time; - -/* -* Account for the scan cost of wakeups against the average -* idle time. -*/ - this_rq->wake_avg_idle -=min (this_rq->wake_avg_idle, time); - -update_avg (&this_sd->avg_scan_cost, time); - } -return idle_cpu; }@@ -9199,6 +9158,60 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)return idlest; } +static inline void update_nr_idle_scan (struct lb_env *env,struct sd_lb_stats *sds, +unsigned long sum_util) +{ +struct sched_domain_shared *sd_share; +int llc_size =per_cpu (sd_llc_size, env->dst_cpu); +int nr_scan; + +/* +* Update the number of CPUs to scan in LLC domain, which could +* be used as a hint in select_idle_cpu(). The update of this hint +* occurs during periodic load balancing, rather than frequent +* newidle balance. +*/ +if (env->idle ==CPU_NEWLY_IDLE || env->sd->span_weight != llc_size) +return ; + + sd_share =rcu_dereference (per_cpu (sd_llc_shared, env->dst_cpu)); +if (!sd_share) +return ; + +/* +* In general, the number of cpus to be scanned should be +* inversely proportional to the sum_util. That is, the lower +* the sum_util is, the harder select_idle_cpu() should scan +* for idle CPU, and vice versa. Let x be the sum_util ratio +* [0-100] of the LLC domain, f(x) be the number of CPUs scanned: +* +* f(x) = a - bx [1] +* +* Consider that f(x) = nr_llc when x = 0, and f(x) = 4 when +* x >= threshold('h' below) then: +* +* a = llc_size; +* b = (nr_llc - 4) / h [2] +* +* then [2] becomes: +* +* f(x) = llc_size - (llc_size -4)x/h [3] +* +* Choose 50 (50%) for h as the threshold from experiment result. +* And since x = 100 * sum_util / total_cap, [3] becomes: +* +* f(sum_util) +* = llc_size - (llc_size - 4) * 100 * sum_util / total_cap * 50 +* = llc_size - (llc_size - 4) * 2 * sum_util / total_cap +* +*/ + nr_scan = llc_size - (llc_size -4 ) *2 * sum_util / sds->total_capacity; +if (nr_scan <4 ) + nr_scan =4 ; + +WRITE_ONCE (sd_share->nr_idle_scan, nr_scan); +} +/** * update_sd_lb_stats - Update sched_domain's statistics for load balancing. * @env: The load balancing environment. @@ -9212,6 +9225,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdstruct sg_lb_stats *local = &sds->local_stat;struct sg_lb_stats tmp_sgs;int sg_status =0 ; +unsigned long sum_util =0 ; do { struct sg_lb_stats *sgs = &tmp_sgs;@@ -9242,6 +9256,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd/* Now, start updating sd_lb_stats */ sds->total_load += sgs->group_load; sds->total_capacity += sgs->group_capacity; + sum_util += sgs->group_util; sg = sg->next; }while (sg != env->sd->groups);@@ -9268,6 +9283,8 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sdWRITE_ONCE (rd->overutilized,SG_OVERUTILIZED );trace_sched_overutilized_tp (rd,SG_OVERUTILIZED ); } + +update_nr_idle_scan (env, sds, sum_util); }Quoted 1 line
kernel/sched/fair.c static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd · line 9290
Quoted 1 line
kernel/sched/fair.c +0
-0#define NUMA_IMBALANCE_MIN 2.
Quoted 6 lines · Yicong Yang
FYI, shenyang has done some investigation on whether we can get an idle cpu if the nr is 4. For netperf running on node 0-1 (32 cores on each node) with 32, 64, 128 threads, the success rate of findindg an idle cpu is about 61.8%, 7.4%, <0.1%, the CPU utilization is 70.7%, 87.4% and 99.9% respectively.
Thanks for this testing. So this indicates that nr = 4 would not improve the idle CPU search efficiency
much when the load is extremely high. Stop searching entirely when it
is nearly 100% may be
more appropriate.
Quoted 4 lines
I have test this patch based on 5.17-rc7 on Kunpeng 920. The benchmarks are binding to node 0 or node 0-1. The tbench result has some oscillation so I need to have a further check. For netperf I see performance enhancement when the threads equals to the cpu number.
The benefit might come from returning previous CPU earlier when nr_threads equals to nr_cpu.
And when the threads number exceeds that of CPU, it might have already returned previous CPU
without this patch, so we didn't see much improvements(in Shenyang's test, the success rate is only
7.4% when threads number equals to CPU number)
Quoted 60 lines
For netperf:
TCP_RR2 nodesthreads base patched pct 16 50335.56667 49970.63333 -0.73% 32 47281.53333 48191.93333 1.93% 64 18907.7 34263.63333 81.22% 128 14391.1 14480.8 0.62% 256 6905.286667 6853.83 -0.75%
TCP_RR1 nodethreads base patched pct 16 50086.06667 49648.13333 -0.87% 32 24983.3 39489.43333 58.06% 64 18340.03333 18399.56667 0.32% 128 7174.713333 7390.09 3.00% 256 3433.696667 3404.956667 -0.84%
UDP_RR2 nodesthreads base patched pct 16 81448.7 82659.43333 1.49% 32 75351.13333 76812.36667 1.94% 64 25539.46667 41835.96667 63.81% 128 25081.56667 23595.56667 -5.92% 256 11848.23333 11017.13333 -7.01%
UDP_RR1 nodethreads base patched pct 16 87288.96667 88719.83333 1.64% 32 22891.73333 68854.33333 200.78% 64 33853.4 35891.6 6.02% 128 12108.4 11885.76667 -1.84% 256 5620.403333 5531.006667 -1.59%mysql on node 0-1
base patched pct 16threads-TPS 7100.27 7224.31 1.75% 16threads-QPS 142005.45 144486.19 1.75% 16threads-avg lat 2.25 2.22 1.63% 16threads-99th lat 2.46 2.43 1.08% 24threads-TPS 10424.70 10312.20 -1.08% 24threads-QPS 208493.86 206243.93 -1.08% 24threads-avg lat 2.30 2.32 -0.87% 24threads-99th lat 2.52 2.57 -1.85% 32threads-TPS 12528.79 12228.88 -2.39% 32threads-QPS 250575.92 244577.59 -2.39% 32threads-avg lat 2.55 2.61 -2.35% 32threads-99th lat 2.88 2.99 -3.82% 64threads-TPS 21386.17 21789.99 1.89% 64threads-QPS 427723.41 435799.85 1.89% 64threads-avg lat 2.99 2.94 1.78% 64threads-99th lat 5.00 4.69 6.33% 128threads-TPS 20865.13 20781.24 -0.40% 128threads-QPS 417302.73 415624.83 -0.40% 128threads-avg lat 6.13 6.16 -0.38% 128threads-99th lat 8.90 8.95 -0.60% 256threads-TPS 19258.15 19295.11 0.19% 256threads-QPS 385162.92 385902.27 0.19% 256threads-avg lat 13.29 13.26 0.23% 256threads-99th lat 20.12 20.12 0.00%
Quoted 4 lines
I also had a look on a machine with 2-socket Xeon 6148 (80 threads in total) For
TCP_RR, the best enhancement also happens when the threads equals to the cpu number.
May I know if the test is with turbo enabled or disabled? If the turbo is disabled,
there might be some issues when calculating the util_avg. I had a workaround at
https://lore.kernel.org/all/[email protected]/
And I'm working on the v3 patch which would include above workaround, will sent it
out later.
Signature · 2 lines
Thanks, Chenyu
Quoted 16 lines · Chen Yu
Quoted 6 lines · Yicong Yang
FYI, shenyang has done some investigation on whether we can get an idle cpu if the nr is 4. For netperf running on node 0-1 (32 cores on each node) with 32, 64, 128 threads, the success rate of findindg an idle cpu is about 61.8%, 7.4%, <0.1%, the CPU utilization is 70.7%, 87.4% and 99.9% respectively.
Thanks for this testing. So this indicates that nr = 4 would not improve the idle CPU search efficiency
much when the load is extremely high. Stop searching entirely when it
is nearly 100% may be
more appropriate.Quoted 4 lines
I have test this patch based on 5.17-rc7 on Kunpeng 920. The benchmarks are binding to node 0 or node 0-1. The tbench result has some oscillation so I need to have a further check. For netperf I see performance enhancement when the threads equals to the cpu number.
Quoted 7 lines
The benefit might come from returning previous CPU earlier when
nr_threadsequals tonr_cpu.
And when the threads number exceeds that of CPU, it might have already returned previous CPU
without this patch, so we didn't see much improvements(in Shenyang's test, the success rate is only
7.4% when threads number equals to CPU number)
yes. I think it maybe the case. When the system is fully loaded the behaviour may stay the same with previous approach, both are scanning 4 cpus.
Quoted 60 lines
Quoted 60 lines
For netperf:
TCP_RR2 nodesthreads base patched pct 16 50335.56667 49970.63333 -0.73% 32 47281.53333 48191.93333 1.93% 64 18907.7 34263.63333 81.22% 128 14391.1 14480.8 0.62% 256 6905.286667 6853.83 -0.75%
TCP_RR1 nodethreads base patched pct 16 50086.06667 49648.13333 -0.87% 32 24983.3 39489.43333 58.06% 64 18340.03333 18399.56667 0.32% 128 7174.713333 7390.09 3.00% 256 3433.696667 3404.956667 -0.84%
UDP_RR2 nodesthreads base patched pct 16 81448.7 82659.43333 1.49% 32 75351.13333 76812.36667 1.94% 64 25539.46667 41835.96667 63.81% 128 25081.56667 23595.56667 -5.92% 256 11848.23333 11017.13333 -7.01%
UDP_RR1 nodethreads base patched pct 16 87288.96667 88719.83333 1.64% 32 22891.73333 68854.33333 200.78% 64 33853.4 35891.6 6.02% 128 12108.4 11885.76667 -1.84% 256 5620.403333 5531.006667 -1.59%mysql on node 0-1
base patched pct 16threads-TPS 7100.27 7224.31 1.75% 16threads-QPS 142005.45 144486.19 1.75% 16threads-avg lat 2.25 2.22 1.63% 16threads-99th lat 2.46 2.43 1.08% 24threads-TPS 10424.70 10312.20 -1.08% 24threads-QPS 208493.86 206243.93 -1.08% 24threads-avg lat 2.30 2.32 -0.87% 24threads-99th lat 2.52 2.57 -1.85% 32threads-TPS 12528.79 12228.88 -2.39% 32threads-QPS 250575.92 244577.59 -2.39% 32threads-avg lat 2.55 2.61 -2.35% 32threads-99th lat 2.88 2.99 -3.82% 64threads-TPS 21386.17 21789.99 1.89% 64threads-QPS 427723.41 435799.85 1.89% 64threads-avg lat 2.99 2.94 1.78% 64threads-99th lat 5.00 4.69 6.33% 128threads-TPS 20865.13 20781.24 -0.40% 128threads-QPS 417302.73 415624.83 -0.40% 128threads-avg lat 6.13 6.16 -0.38% 128threads-99th lat 8.90 8.95 -0.60% 256threads-TPS 19258.15 19295.11 0.19% 256threads-QPS 385162.92 385902.27 0.19% 256threads-avg lat 13.29 13.26 0.23% 256threads-99th lat 20.12 20.12 0.00%
Quoted 6 lines
Quoted 4 lines
I also had a look on a machine with 2-socket Xeon 6148 (80 threads in total) For
TCP_RR, the best enhancement also happens when the threads equals to the cpu number.May I know if the test is with turbo enabled or disabled? If the turbo is disabled,
p-state is controlled by the platform on my machine. I assume it's on as the Avg_MHz and Bzy_Mhz varies according to the load. turbostat says:
# cpu 0 idle Package Core CPU Avg_MHz Busy% Bzy_MHz TSC_MHz IPC IRQ SMI POLL C1 POLL% C1% CPU%c1 CPU%c6 CoreTmp PkgTmp PkgWatt RAMWatt PKG_% RAM_% - - - 0 0.01 3100 2400 1.41 1935 0 0 1831 0.00 100.00 99.99 0.00 69 69 150.55 44.41 0.00 0.00 0 0 0 2 0.06 3100 2400 0.99 46 0 0 45 0.00 99.95 99.94 0.00 66 68 74.12 21.71 0.00 0.00 # cpu 0 partly loaded Package Core CPU Avg_MHz Busy% Bzy_MHz TSC_MHz IPC IRQ SMI POLL C1 POLL% C1% CPU%c1 CPU%c6 CoreTmp PkgTmp PkgWatt RAMWatt PKG_% RAM_% - - - 1559 50.34 3097 2400 1.44 56952 0 64 4729 0.00 49.67 49.66 0.00 83 84 291.81 43.79 0.00 0.00 0 0 0 1642 53.01 3098 2400 1.48 1610 0 0 620 0.00 47.51 46.99 0.00 75 78 142.62 21.44 0.00 0.00 # cpu 0 loaded by stress-ng Package Core CPU Avg_MHz Busy% Bzy_MHz TSC_MHz IPC IRQ SMI POLL C1 POLL% C1% CPU%c1 CPU%c6 CoreTmp PkgTmp PkgWatt RAMWatt PKG_% RAM_% - - - 2917 99.52 2931 2400 1.06 101718 0 0 0 0.00 0.00 0.48 0.00 86 86 299.87 43.84 0.00 0.00 0 0 0 2943 99.39 2961 2400 1.05 1278 0 0 0 0.00 0.00 0.61 0.00 81 83 149.90 21.38 0.00 0.00
Quoted 6 lines
there might be some issues when calculating the
util_avg. I had a workaround at
https://lore.kernel.org/all/[email protected]/
And I'm working on the v3 patch which would include above workaround, will sent it
out later.