Messages in this thread | | | Date | Thu, 12 Oct 2023 16:06:40 -0400 | Subject | Re: [RFC PATCH] sched/fair: Bias runqueue selection towards almost idle prev CPU | From | Mathieu Desnoyers <> |
| |
On 2023-10-12 13:00, Vincent Guittot wrote: > On Thu, 12 Oct 2023 at 18:48, Mathieu Desnoyers > <mathieu.desnoyers@efficios.com> wrote: >> >> On 2023-10-12 12:24, Vincent Guittot wrote: >>> On Thu, 12 Oct 2023 at 17:56, Mathieu Desnoyers >>> <mathieu.desnoyers@efficios.com> 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. >>> >>> 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
OK, after further testing, it turns out that cpu_util_without() works for my case now. I'm not sure what I got wrong in my past attempts.
> >> 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
Sounds good, I will prepare an updated patch.
Thanks,
Mathieu
> > >> >> 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 >>
-- Mathieu Desnoyers EfficiOS Inc. https://www.efficios.com
| |