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

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

On 2023-10-12 11:56, Mathieu Desnoyers wrote:
> 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".

Actually AFAIU the part of cpu_util() responsible for adding
the utilization of recently blocked tasks is the code under UTIL_EST.

Thanks,

Mathieu

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