Re: [RFC PATCH] sched/fair: Bias runqueue selection towards almost idle prev CPU
From: Mathieu Desnoyers
Date: Thu Oct 12 2023 - 10:34:03 EST
On 2023-10-11 06:16, Chen Yu wrote:
On 2023-10-10 at 09:49:54 -0400, Mathieu Desnoyers wrote:
On 2023-10-09 01:14, Chen Yu wrote:
On 2023-09-30 at 07:45:38 -0400, Mathieu Desnoyers wrote:
On 9/30/23 03:11, Chen Yu wrote:
Hi Mathieu,
On 2023-09-29 at 14:33:50 -0400, Mathieu Desnoyers wrote:
Introduce the WAKEUP_BIAS_PREV_IDLE scheduler feature. It biases
select_task_rq towards the previous CPU if it was almost idle
(avg_load <= 0.1%).
Yes, this is a promising direction IMO. One question is that,
can cfs_rq->avg.load_avg be used for percentage comparison?
If I understand correctly, load_avg reflects that more than
1 tasks could have been running this runqueue, and the
load_avg is the direct proportion to the load_weight of that
cfs_rq. Besides, LOAD_AVG_MAX seems to not be the max value
that load_avg can reach, it is the sum of
1024 * (y + y^1 + y^2 ... )
For example,
taskset -c 1 nice -n -20 stress -c 1
cat /sys/kernel/debug/sched/debug | grep 'cfs_rq\[1\]' -A 12 | grep "\.load_avg"
.load_avg : 88763
.load_avg : 1024
88763 is higher than LOAD_AVG_MAX=47742
I would have expected the load_avg to be limited to LOAD_AVG_MAX somehow,
but it appears that it does not happen in practice.
That being said, if the cutoff is really at 0.1% or 0.2% of the real max,
does it really matter ?
Maybe the util_avg can be used for precentage comparison I suppose?
[...]
Or
return cpu_util_without(cpu_rq(cpu), p) * 1000 <= capacity_orig_of(cpu) ?
Unfortunately using util_avg does not seem to work based on my testing.
Even at utilization thresholds at 0.1%, 1% and 10%.
Based on comments in fair.c:
* CPU utilization is the sum of running time of runnable tasks plus the
* recent utilization of currently non-runnable tasks on that CPU.
I think we don't want to include currently non-runnable tasks in the
statistics we use, because we are trying to figure out if the cpu is a
idle-enough target based on the tasks which are currently running, for the
purpose of runqueue selection when waking up a task which is considered at
that point in time a non-runnable task on that cpu, and which is about to
become runnable again.
Although LOAD_AVG_MAX is not the max possible load_avg, we still want to find
a proper threshold to decide if the CPU is almost idle. The LOAD_AVG_MAX
based threshold is modified a little bit:
The theory is, if there is only 1 task on the CPU, and that task has a nice
of 0, the task runs 50 us every 1000 us, then this CPU is regarded as almost
idle.
The load_sum of the task is:
50 * (1 + y + y^2 + ... + y^n)
The corresponding avg_load of the task is approximately
NICE_0_WEIGHT * load_sum / LOAD_AVG_MAX = 50.
So:
/* which is close to LOAD_AVG_MAX/1000 = 47 */
#define ALMOST_IDLE_CPU_LOAD 50
Sorry to be slow at understanding this concept, but this whole "load" value
is still somewhat magic to me.
Should it vary based on CONFIG_HZ_{100,250,300,1000}, or is it independent ?
Where is it documented that the load is a value in "us" out of a window of
1000 us ?
My understanding is that, the load_sum of a single task is a value in "us" out
of a window of 1000 us, while the load_avg of the task will multiply the weight
of the task. In this case a task with nice 0 is NICE_0_WEIGHT = 1024.
__update_load_avg_se -> ___update_load_sum calculate the load_sum of a task(there
is comments around ___update_load_sum to describe the pelt calculation),
and ___update_load_avg() calculate the load_avg based on the task's weight.
Thanks for your thorough explanation, now it makes sense.
I understand as well that the cfs_rq->avg.load_sum is the result of summing
each task load_sum multiplied by their weight:
static inline void
enqueue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
cfs_rq->avg.load_avg += se->avg.load_avg;
cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
}
Therefore I think we need to multiply the load_sum value we aim for by
get_pelt_divider(&cpu_rq(cpu)->cfs.avg) to compare it to a rq load_sum.
I plan to compare the rq load sum to "10 * get_pelt_divider(&cpu_rq(cpu)->cfs.avg)"
to match runqueues which were previously idle (therefore with prior periods contribution
to the rq->load_sum being pretty much zero), and which have a current period rq load_sum
below or equal 10us per 1024us (<= 1%):
static inline unsigned long cfs_rq_weighted_load_sum(struct cfs_rq *cfs_rq)
{
return cfs_rq->avg.load_sum;
}
static unsigned long cpu_weighted_load_sum(struct rq *rq)
{
return cfs_rq_weighted_load_sum(&rq->cfs);
}
/*
* A runqueue is considered almost idle if:
*
* cfs_rq->avg.load_sum / get_pelt_divider(&cfs_rq->avg) / 1024 <= 1%
*
* This inequality is transformed as follows to minimize arithmetic:
*
* cfs_rq->avg.load_sum <= get_pelt_divider(&cfs_rq->avg) * 10
*/
static bool
almost_idle_cpu(int cpu, struct task_struct *p)
{
if (!sched_feat(WAKEUP_BIAS_PREV_IDLE))
return false;
return cpu_weighted_load_sum(cpu_rq(cpu)) <= 10 * get_pelt_divider(&cpu_rq(cpu)->cfs.avg);
}
Does it make sense ?
Thanks,
Mathieu
And with this value "50", it would cover the case where there is only a
single task taking less than 50us per 1000us, and cases where the sum for
the set of tasks on the runqueue is taking less than 50us per 1000us
overall.
static bool
almost_idle_cpu(int cpu, struct task_struct *p)
{
if (!sched_feat(WAKEUP_BIAS_PREV_IDLE))
return false;
return cpu_load_without(cpu_rq(cpu), p) <= ALMOST_IDLE_CPU_LOAD;
}
Tested this on Intel Xeon Platinum 8360Y, Ice Lake server, 36 core/package,
total 72 core/144 CPUs. Slight improvement is observed in hackbench socket mode:
socket mode:
hackbench -g 16 -f 20 -l 480000 -s 100
Before patch:
Running in process mode with 16 groups using 40 file descriptors each (== 640 tasks)
Each sender will pass 480000 messages of 100 bytes
Time: 81.084
After patch:
Running in process mode with 16 groups using 40 file descriptors each (== 640 tasks)
Each sender will pass 480000 messages of 100 bytes
Time: 78.083
pipe mode:
hackbench -g 16 -f 20 --pipe -l 480000 -s 100
Before patch:
Running in process mode with 16 groups using 40 file descriptors each (== 640 tasks)
Each sender will pass 480000 messages of 100 bytes
Time: 38.219
After patch:
Running in process mode with 16 groups using 40 file descriptors each (== 640 tasks)
Each sender will pass 480000 messages of 100 bytes
Time: 38.348
It suggests that, if the workload has larger working-set/cache footprint, waking up
the task on its previous CPU could get more benefit.
In those tests, what is the average % of idleness of your cpus ?
For hackbench -g 16 -f 20 --pipe -l 480000 -s 100, it is around 8~10% idle
For hackbench -g 16 -f 20 -l 480000 -s 100, it is around 2~3% idle
Then the CPUs in packge 1 are offlined to get stable result when the group number is low.
hackbench -g 1 -f 20 --pipe -l 480000 -s 100
Some CPUs are busy, others are idle, and some are half-busy.
Core CPU Busy%
- - 49.57
0 0 1.89
0 72 75.55
1 1 100.00
1 73 0.00
2 2 100.00
2 74 0.00
3 3 100.00
3 75 0.01
4 4 78.29
4 76 17.72
5 5 100.00
5 77 0.00
hackbench -g 1 -f 20 -l 480000 -s 100
Core CPU Busy%
- - 48.29
0 0 57.94
0 72 21.41
1 1 83.28
1 73 0.00
2 2 11.44
2 74 83.38
3 3 21.45
3 75 77.27
4 4 26.89
4 76 80.95
5 5 5.01
5 77 83.09
echo NO_WAKEUP_BIAS_PREV_IDLE > /sys/kernel/debug/sched/features
hackbench -g 1 -f 20 --pipe -l 480000 -s 100
Running in process mode with 1 groups using 40 file descriptors each (== 40 tasks)
Each sender will pass 480000 messages of 100 bytes
Time: 9.434
echo WAKEUP_BIAS_PREV_IDLE > /sys/kernel/debug/sched/features
hackbench -g 1 -f 20 --pipe -l 480000 -s 100
Running in process mode with 1 groups using 40 file descriptors each (== 40 tasks)
Each sender will pass 480000 messages of 100 bytes
Time: 9.373
thanks,
Chenyu
--
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com