Messages in this thread | | | From | Vincent Guittot <> | Date | Thu, 12 Oct 2023 19:00:25 +0200 | Subject | Re: [RFC PATCH] sched/fair: Bias runqueue selection towards almost idle prev CPU |
| |
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
> 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 >
| |