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

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

On 2023-10-12 11:01, Vincent Guittot wrote:
> On Thu, 12 Oct 2023 at 16:33, Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> 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.

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

Based on your comments, just doing this to match a rq util_avg <= 1% (10us of 1024us)
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