Skip to contentSkip to conversation

sched/fair: Change SIS_PROP to search idle CPU based on sum of util_avg

RFC PATCH Superseded Chen Yu 7 participants 15 messages Mar 9, 2022 – Apr 11, 2022 Scheduler

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Chen Yu

author
#0 lore raw

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
index 8054641c0a7b..aae558459f00 100644
@@ -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
#1 lore raw

Hi Chen,

Quoted 52 lines · Chen Yu

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

Quoted 5 lines

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:

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_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
index 8054641c0a7b..aae558459f00 100644
@@ -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
index 5146163bfabb..59f5f8432c21 100644
@@ -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, bool
  	if (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 *sd
  	struct 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 *sd
  		WRITE_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
author
#2 lore raw

Hi Abel,

Quoted 55 lines · Abel Wu

Hi Chen,

Quoted 52 lines · Chen Yu

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

Quoted 9 lines
Quoted 5 lines

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:

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_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%

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_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?

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

#3 lore raw
Quoted 6 lines · Chen Yu
Quoted 6 lines

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?

Quoted 12 lines

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.

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

author
#4 lore raw
Quoted 20 lines · Tim Chen
Quoted 6 lines · Chen Yu
Quoted 6 lines

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?

Quoted 12 lines

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.

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

#5 lore raw
In reply to Chen Yu

Hello Chenyu,

Quoted 161 lines · Chen Yu

[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)

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

author
#6 lore raw

Hi Prateek,

Quoted 173 lines · K Prateek Nayak

Hello Chenyu,

Quoted 161 lines · Chen Yu

[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)

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

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_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
~~~~~~~~

Quoted 5 lines

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)

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

Quoted 10 lines

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)

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_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)

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_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)

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

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

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

#7 lore raw

Hello 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_prop 1:      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:

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_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)

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_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)

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_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)

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

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

#8 lore raw

Hello 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

#9 lore raw
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

#10 lore raw
In reply to Chen Yu

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]
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:

Quoted 6 lines

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

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

Quoted 8 lines

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.

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.

---
 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
index 8054641c0a7b..aae558459f00 100644
@@ -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
index 5146163bfabb..59f5f8432c21 100644
@@ -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, bool
 	if (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 *sd
 	struct 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 *sd
 		WRITE_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
author
#11 lore raw

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]
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:

Quoted 6 lines

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

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

Quoted 7 lines
Quoted 5 lines

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.

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_avg ratio >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,
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, bool
 	if (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 *sd
 	struct 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 *sd
 		WRITE_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
#12 lore raw
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]
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:

Quoted 6 lines

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

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

Quoted 7 lines
Quoted 5 lines

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.

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_avg ratio >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 120 lines

Thanks,
Yicong

Quoted 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, bool
 	if (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 *sd
 	struct 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 *sd
 		WRITE_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

.

#13 lore raw
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_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%
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
#14 lore raw
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_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)

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