Re: [RFC PATCH] sched/fair: Bias runqueue selection towards almost idle prev CPU

From: Vincent Guittot
Date: Thu Oct 12 2023 - 13:00:42 EST

On Thu, 12 Oct 2023 at 18:48, Mathieu Desnoyers
<mathieu.desnoyers@xxxxxxxxxxxx> wrote:
>
> On 2023-10-12 12:24, Vincent Guittot wrote:
> > On Thu, 12 Oct 2023 at 17:56, Mathieu Desnoyers
> > <mathieu.desnoyers@xxxxxxxxxxxx> wrote:
> >>
> >> On 2023-10-12 11:01, Vincent Guittot wrote:
> >>> On Thu, 12 Oct 2023 at 16:33, Mathieu Desnoyers
> >>> <mathieu.desnoyers@xxxxxxxxxxxx> wrote:
> >>>>
> >>>> 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:
> >>>
> >>> Please don't use load_sum but only *_avg.
> >>> As already said, util_avg or runnable_avg are better metrics for you
> >>
> >> I think I found out why using util_avg was not working for me.
> >>
> >> Considering this comment from cpu_util():
> >>
> >> * CPU utilization is the sum of running time of runnable tasks plus the
> >> * recent utilization of currently non-runnable tasks on that CPU.
> >>
> >> I don't want to include the recent utilization of currently non-runnable
> >> tasks on that CPU in order to choose that CPU to do task placement in a
> >> context where many tasks were recently running on that cpu (but are
> >> currently blocked). I do not want those blocked tasks to be part of the
> >> avg.
> >
> > But you have the exact same behavior with load_sum/avg.
> >
> >>
> >> So I think the issue here is that I was using the cpu_util() (and
> >> cpu_util_without()) helpers which are considering max(util, runnable),
> >> rather than just "util".
> >
> > cpu_util_without() only use util_avg but not runnable_avg.
>
> Ah, yes, @boost=0, which prevents it from using the runnable_avg.
>
> > Nevertheless, cpu_util_without ans cpu_util uses util_est which is
> > used to predict the final utilization.
>
> Yes, I suspect it's the util_est which prevents me from getting
> performance improvements when I use cpu_util_without to implement
> almost-idle.
>
> >
> > Let's take the example of task A running 20ms every 200ms on CPU0.
> > The util_avg of the cpu will vary in the range [7:365]. When task A
> > wakes up on CPU0, CPU0 util_avg = 7 (below 1%) but taskA will run for
> > 20ms which is not really almost idle. On the other side, CPU0 util_est
> > will be 365 as soon as task A is enqueued (which will be the value of
> > CPU0 util_avg just before going idle)
>
> If task A sleeps (becomes non-runnable) without being migrated, and therefore
> still have CPU0 as its cpu, is it still considered as part of the util_est of
> CPU0 while it is blocked ? If it is the case, then the util_est is preventing

No, the util_est of a cpu only accounts the runnable tasks not the sleeping one

CPU's util_est = /Sum of the util_est of runnable tasks

> rq selection from considering a rq almost idle when waking up sleeping tasks
> due to taking into account the set of sleeping tasks in its utilization estimate.
>
> >
> > Let's now take a task B running 100us every 1024us
> > The util_avg of the cpu should vary in the range [101:103] and once
> > task B is enqueued, CPU0 util_est will be 103
> >
> >>
> >> Based on your comments, just doing this to match a rq util_avg <= 1% (10us of 1024us)
> >
> > it's not 10us of 1024us
>
> Is the range of util_avg within [0..1024] * capacity_of(cpu), or am I missing something ?

util_avg is in the range [0:1024] and CPU's capacity is in the range
[0:1024] too. 1024 is the compute capacity of the most powerful CPU of
the system. On SMP system, all CPUs have a capacity of 1024. On
heterogeneous system, big core have a capacity of 1024 and others will
have a lower capacity


>
> Thanks,
>
> Mathieu
>
>
> >
> >> seems to work fine:
> >>
> >> return cpu_rq(cpu)->cfs.avg.util_avg <= 10 * capacity_of(cpu);
> >>
> >> Is this approach acceptable ?
> >>
> >> Thanks!
> >>
> >> Mathieu
> >>
> >>>
> >>>>
> >>>> 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
> >>>>
> >>
> >> --
> >> Mathieu Desnoyers
> >> EfficiOS Inc.
> >> https://www.efficios.com
> >>
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com
>