Utilization estimation (util_est) for FAIR tasks

The util_avg signal computed by PELT is too variable for some use-cases. For example, a big task waking up after a long sleep period will have its utilization almost completely decayed. This introduces some latency before schedutil will be able to pick the best frequency to run a task.

kernel/sched/fair.c +5 -1

-static inline unsigned long task_util(struct task_struct *p);
 static unsigned long cpu_util_wake(int cpu, struct task_struct *p);
 
 static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)

@@ -6262,6 +6337,11 @@ static inline unsigned long task_util(struct task_struct *p)
        return p->se.avg.util_avg;
 }
 
+static inline unsigned long task_util_est(struct task_struct *p)
+{
+       return max(p->se.avg.util_est.ewma, p->se.avg.util_est.last);
+}
+
 /*
  * cpu_util_wake: Compute cpu utilization with any contributions from
  * the waking task p removed.

kernel/sched/features.h +5 -0

index 9552fd5854bf..c459a4b61544 100644
@@ -85,3 +85,8 @@ SCHED_FEAT(ATTACH_AGE_LOAD, true)
 SCHED_FEAT(WA_IDLE, true)
 SCHED_FEAT(WA_WEIGHT, true)
 SCHED_FEAT(WA_BIAS, true)
+
+/*
+ * UtilEstimation. Use estimated CPU utilization.
+ */
+SCHED_FEAT(UTIL_EST, false)

kernel/sched/sched.h +0 -0

index 2e95505e23c6..0b4d9750a927 100644

Quoted 4 lines · Patrick Bellasi

The util_avg signal computed by PELT is too variable for some use-cases. For example, a big task waking up after a long sleep period will have its utilization almost completely decayed. This introduces some latency before schedutil will be able to pick the best frequency to run a task.

[...]

Quoted 34 lines

kernel/sched/fair.c +5 -1

-static inline unsigned long task_util(struct task_struct *p);
 static unsigned long cpu_util_wake(int cpu, struct task_struct *p);
 
 static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)

@@ -6262,6 +6337,11 @@ static inline unsigned long task_util(struct task_struct *p)
        return p->se.avg.util_avg;
 }
 
+static inline unsigned long task_util_est(struct task_struct *p)
+{
+       return max(p->se.avg.util_est.ewma, p->se.avg.util_est.last);
+}
+
 /*
  * cpu_util_wake: Compute cpu utilization with any contributions from
  * the waking task p removed.

kernel/sched/features.h +5 -0

index 9552fd5854bf..c459a4b61544 100644
@@ -85,3 +85,8 @@ SCHED_FEAT(ATTACH_AGE_LOAD, true)
 SCHED_FEAT(WA_IDLE, true)
 SCHED_FEAT(WA_WEIGHT, true)
 SCHED_FEAT(WA_BIAS, true)
+
+/*
+ * UtilEstimation. Use estimated CPU utilization.
+ */
+SCHED_FEAT(UTIL_EST, false)

kernel/sched/sched.h +0 -0

index 2e95505e23c6..0b4d9750a927 100644
@@ -470,6 +470,7 @@ struct cfs_rq {

kernel/sched/sched.h struct cfs_rq { · line 473

Quoted 4 lines

kernel/sched/sched.h +1 -0

         * CFS load tracking
         */
        struct sched_avg avg;
+       unsigned long util_est_runnable;

Since struct sched_avg would now have util_est, cfs_rq gets it too. Then can we not try to reuse that struct and avoid having to expand cfs_rq more than needed?

I went through previous conversations and couldn't find a reason, if I missed something I appreciate if you can explain the rationale.

thanks,

- Joel

Quoted 41 lines · Joel Fernandes

Quoted 4 lines · Patrick Bellasi

The util_avg signal computed by PELT is too variable for some use-cases. For example, a big task waking up after a long sleep period will have its utilization almost completely decayed. This introduces some latency before schedutil will be able to pick the best frequency to run a task.

[...]

Quoted 34 lines

kernel/sched/fair.c +5 -1

-static inline unsigned long task_util(struct task_struct *p);
 static unsigned long cpu_util_wake(int cpu, struct task_struct *p);
 
 static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)

@@ -6262,6 +6337,11 @@ static inline unsigned long task_util(struct task_struct *p)
        return p->se.avg.util_avg;
 }
 
+static inline unsigned long task_util_est(struct task_struct *p)
+{
+       return max(p->se.avg.util_est.ewma, p->se.avg.util_est.last);
+}
+
 /*
  * cpu_util_wake: Compute cpu utilization with any contributions from
  * the waking task p removed.

kernel/sched/features.h +5 -0

index 9552fd5854bf..c459a4b61544 100644
@@ -85,3 +85,8 @@ SCHED_FEAT(ATTACH_AGE_LOAD, true)
 SCHED_FEAT(WA_IDLE, true)
 SCHED_FEAT(WA_WEIGHT, true)
 SCHED_FEAT(WA_BIAS, true)
+
+/*
+ * UtilEstimation. Use estimated CPU utilization.
+ */
+SCHED_FEAT(UTIL_EST, false)

kernel/sched/sched.h +0 -0

index 2e95505e23c6..0b4d9750a927 100644
@@ -470,6 +470,7 @@ struct cfs_rq {

Quoted 8 lines

kernel/sched/sched.h struct cfs_rq { · line 473

Quoted 4 lines

kernel/sched/sched.h +1 -0

         * CFS load tracking
         */
        struct sched_avg avg;
+       unsigned long util_est_runnable;

Since struct sched_avg would now have util_est, cfs_rq gets it too. Then can we not try to reuse that struct and avoid having to expand cfs_rq more than needed?

Yes, that's possible now... the main issue is that for RQ's we do not track an EWMA, but still we can use the util_est::last field or maybe use a union just to use a better name when used from the RQ side.

Quoted 3 lines

I went through previous conversations and couldn't find a reason, if I missed something I appreciate if you can explain the rationale.

I've used a separate filed just because SE's util_est was not part of sched_avg, and missed the opportunity to consolidate better this now that we moved it. Thanks for pointing this out ;-)

kernel/sched/fair.c +20 -0

+static inline void util_est_dequeue(struct task_struct *p, int flags)
+{
+	struct cfs_rq *cfs_rq = &task_rq(p)->cfs;
+	unsigned long util_last = task_util(p);
+	bool sleep = flags & DEQUEUE_SLEEP;
+	unsigned long ewma;
+	long util_est = 0;
+
+	if (!sched_feat(UTIL_EST))
+		return;
+
+	/*
+	 * Update root cfs_rq's estimated utilization
+	 *
+	 * If *p is the last task then the root cfs_rq's estimated utilization
+	 * of a CPU is 0 by definition.
+	 */
+	if (cfs_rq->nr_running) {
+		util_est  = READ_ONCE(cfs_rq->util_est_runnable);
+		util_est -= min_t(long, util_est, task_util_est(p));

kernel/sched/fair.c +9 -0

+
+	/*
+	 * Update Task's estimated utilization
+	 *
+	 * When *p completes an activation we can consolidate another sample
+	 * about the task size. This is done by storing the last PELT value
+	 * for this task and using this value to load another sample in the
+	 * exponential weighted moving average:
+	 *

Quoted 24 lines · Patrick Bellasi

kernel/sched/fair.c +24 -0

+static inline void util_est_dequeue(struct task_struct *p, int flags)
+{
+	struct cfs_rq *cfs_rq = &task_rq(p)->cfs;
+	unsigned long util_last = task_util(p);
+	bool sleep = flags & DEQUEUE_SLEEP;
+	unsigned long ewma;
+	long util_est = 0;
+
+	if (!sched_feat(UTIL_EST))
+		return;
+
+	/*
+	 * Update root cfs_rq's estimated utilization
+	 *
+	 * If *p is the last task then the root cfs_rq's estimated utilization
+	 * of a CPU is 0 by definition.
+	 */
+	if (cfs_rq->nr_running) {
+		util_est  = READ_ONCE(cfs_rq->util_est_runnable);
+		util_est -= min_t(long, util_est, task_util_est(p));
+	}
+	WRITE_ONCE(cfs_rq->util_est_runnable, util_est);
+
+	/*

kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 5295

Quoted 6 lines

kernel/sched/fair.c +6 -0

+	 * Skip update of task's estimated utilization when the task has not
+	 * yet completed an activation, e.g. being migrated.
+	 */
+	if (!sleep)
+		return;
+

Since you only use sleep once, you might as well write it out there.

Also, does GCC lower the task_util() eval to here?

kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 5302

Quoted 7 lines

kernel/sched/fair.c +7 -0

+        /*
+         * Skip update of task's estimated utilization when its EWMA is already
+         * ~1% close to its last activation value.
+         */
+        util_est = p->util_est.ewma;
+        if (abs(util_est - util_last) <= (SCHED_CAPACITY_SCALE / 100))
+                return;

Aside from that being whitespace challenged, did you also try:

	if ((unsigned)((util_est - util_last) + LIM - 1) < (2 * LIM - 1))

Also, since we only care about the absolute value; we could use:

util_last - ewma

here (note the above also forgets to use READ_ONCE), and reuse the result:

Quoted 13 lines

kernel/sched/fair.c +13 -0

+
+	/*
+	 * Update Task's estimated utilization
+	 *
+	 * When *p completes an activation we can consolidate another sample
+	 * about the task size. This is done by storing the last PELT value
+	 * for this task and using this value to load another sample in the
+	 * exponential weighted moving average:
+	 *
+	 *      ewma(t) = w *  task_util(p) + (1 - w) ewma(t-1)
+	 *              = w *  task_util(p) + ewma(t-1) - w * ewma(t-1)
+	 *              = w * (task_util(p) + ewma(t-1) / w - ewma(t-1))
+	 *

kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 5321

Quoted 6 lines

kernel/sched/fair.c +6 -0

+	 * Where 'w' is the weight of new samples, which is configured to be
+	 * 0.25, thus making w=1/4
+	 */
+	p->se.avg.util_est.last = util_last;
+	ewma = READ_ONCE(p->se.avg.util_est.ewma);
+	ewma   = util_last + (ewma << UTIL_EST_WEIGHT_SHIFT) - ewma;

here.

kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 5324

Quoted 4 lines

kernel/sched/fair.c +3 -0

+	ewma >>= UTIL_EST_WEIGHT_SHIFT;
+	WRITE_ONCE(p->se.avg.util_est.ewma, ewma);
+}

So something along these lines:

	ewma = READ_ONCE(p->se.avg.util_est.ewma);
	diff = util_last - ewma;
	if ((unsigned)(diff + LIM - 1) < (2 * LIM - 1))
		return;

	p->se.avg.util_est.last = util_last;
	ewma = (diff + (ewma << EWMA_SHIFT)) >> EWMA_SHIFT;
	WRITE_ONCE(p->se.avg.util_est.ewma, ewma);

Make sense?

Quoted 3 lines

Aside from that being whitespace challenged, did you also try:

	if ((unsigned)((util_est - util_last) + LIM - 1) < (2 * LIM - 1))

No, since the above code IMO is so much "easy to parse for humans" :)

But, mainly because since the cache alignment update, also while testing on a "big" Intel machine I cannot see regressions on hackbench.

This is the code I get on my Xeon E5-2690 v2:

       if (abs(util_est - util_last) <= (SCHED_CAPACITY_SCALE / 100))
   6ba0:       8b 86 7c 02 00 00       mov    0x27c(%rsi),%eax
   6ba6:       48 29 c8                sub    %rcx,%rax
   6ba9:       48 99                   cqto
   6bab:       48 31 d0                xor    %rdx,%rax
   6bae:       48 29 d0                sub    %rdx,%rax
   6bb1:       48 83 f8 0a             cmp    $0xa,%rax
   6bb5:       7e 1d                   jle    6bd4 <dequeue_task_fair+0x7e4>

Does it look so bad?

Quoted 5 lines · Patrick Bellasi

Quoted 3 lines

Aside from that being whitespace challenged, did you also try:

	if ((unsigned)((util_est - util_last) + LIM - 1) < (2 * LIM - 1))

No, since the above code IMO is so much "easy to parse for humans" :)

Heh, true. Although that's fixable by wrapping it in some helper with a comment.

Quoted 14 lines

But, mainly because since the cache alignment update, also while testing on a "big" Intel machine I cannot see regressions on hackbench.

This is the code I get on my Xeon E5-2690 v2:

       if (abs(util_est - util_last) <= (SCHED_CAPACITY_SCALE / 100))
   6ba0:       8b 86 7c 02 00 00       mov    0x27c(%rsi),%eax
   6ba6:       48 29 c8                sub    %rcx,%rax
   6ba9:       48 99                   cqto
   6bab:       48 31 d0                xor    %rdx,%rax
   6bae:       48 29 d0                sub    %rdx,%rax
   6bb1:       48 83 f8 0a             cmp    $0xa,%rax
   6bb5:       7e 1d                   jle    6bd4 <dequeue_task_fair+0x7e4>

Quoted 1 line

Does it look so bad?

Its not terrible, and I think your GCC is far more clever than the one I

used at the time. But that's 4 dependent instructions (cqto,xor,sub,cmp) whereas the one I proposed uses only 2 (add,cmp).

Now, my proposal is, as you say, somewhat hard to read, and it also doesn't work right when our values are 'big' (which they will not be in our case, because util has a very definite bound), and I suspect you're right that ~2 cycles here will not be measurable.

So yeah.... whatever ;-)

Quoted 26 lines · Peter Zijlstra

Quoted 5 lines · Patrick Bellasi

Quoted 3 lines

Aside from that being whitespace challenged, did you also try:

	if ((unsigned)((util_est - util_last) + LIM - 1) < (2 * LIM - 1))

No, since the above code IMO is so much "easy to parse for humans" :)

Heh, true. Although that's fixable by wrapping it in some helper with a comment.

Quoted 15 lines

But, mainly because since the cache alignment update, also while testing on a "big" Intel machine I cannot see regressions on hackbench.

This is the code I get on my Xeon E5-2690 v2:

       if (abs(util_est - util_last) <= (SCHED_CAPACITY_SCALE / 100))
   6ba0:       8b 86 7c 02 00 00       mov    0x27c(%rsi),%eax
   6ba6:       48 29 c8                sub    %rcx,%rax
   6ba9:       48 99                   cqto
   6bab:       48 31 d0                xor    %rdx,%rax
   6bae:       48 29 d0                sub    %rdx,%rax
   6bb1:       48 83 f8 0a             cmp    $0xa,%rax
   6bb5:       7e 1d                   jle    6bd4 <dequeue_task_fair+0x7e4>

Does it look so bad?

Quoted 1 line

Its not terrible, and I think your GCC is far more clever than the one I

To clarify; my GCC at the time generated conditional branches to compute the absolute value; and in that case the thing I proposed wins hands down because its unconditional.

However the above is also unconditional and then the difference is much less important.

Quoted 2 lines

used at the time. But that's 4 dependent instructions (cqto,xor,sub,cmp) whereas the one I proposed uses only 2 (add,cmp).

Quoted 4 lines

Now, my proposal is, as you say, somewhat hard to read, and it also doesn't work right when our values are 'big' (which they will not be in our case, because util has a very definite bound), and I suspect you're right that ~2 cycles here will not be measurable.

Quoted 2 lines

So yeah.... whatever ;-)

static unsigned long cpu_util_wake(int cpu, struct task_struct *p) {

kernel/sched/fair.c +2 -2

-	unsigned long util, capacity;
+	long util, util_est;
 
 	/* Task has no contribution or is new */
 	if (cpu != task_cpu(p) || !p->se.avg.last_update_time)
-		return cpu_util(cpu);
+		return cpu_util_est(cpu);

Hi Patrick,

Quoted 16 lines

static unsigned long cpu_util_wake(int cpu, struct task_struct *p) {

kernel/sched/fair.c +5 -4

-	unsigned long util, capacity;
+	long util, util_est;
 
 	/* Task has no contribution or is new */
 	if (cpu != task_cpu(p) || !p->se.avg.last_update_time)
-		return cpu_util(cpu);
+		return cpu_util_est(cpu);
 
-	capacity = capacity_orig_of(cpu);
-	util = max_t(long, cpu_rq(cpu)->cfs.avg.util_avg - task_util(p), 0);
+	/* Discount task's blocked util from CPU's util */
+	util = cpu_util(cpu) - task_util(p);
+	util = max(util, 0L);

kernel/sched/fair.c static inline unsigned long task_util_est(struct task_struct *p) · line 6397

Quoted 3 lines

kernel/sched/fair.c +2 -1

-	return (util >= capacity) ? capacity : util;
+	if (!sched_feat(UTIL_EST))
+		return util;

At first, It is not clear to me why you are not clamping the capacity to CPU original capacity. It looks like it is not needed any more with commit f453ae2200b0 ("sched/fair: Consider RT/IRQ pressure in capacity_spare_wake()") inclusion.

Quoted 16 lines

kernel/sched/fair.c +16 -0

+       /*
+        * These are the main cases covered:
+        * - if *p is the only task sleeping on this CPU, then:
+        *      cpu_util (== task_util) > util_est (== 0)
+        *   and thus we return:
+        *      cpu_util_wake = (cpu_util - task_util) = 0
+        *
+        * - if other tasks are SLEEPING on the same CPU, which is just waking
+        *   up, then:
+        *      cpu_util >= task_util
+        *      cpu_util > util_est (== 0)
+        *   and thus we discount *p's blocked utilization to return:
+        *      cpu_util_wake = (cpu_util - task_util) >= 0
+        *
+        * - if other tasks are RUNNABLE on that CPU and
+        *      util_est > cpu_util

kernel/sched/fair.c static inline unsigned long task_util_est(struct task_struct *p) · line 6422

Quoted 8 lines

kernel/sched/fair.c +8 -0

+        *   then we use util_est since it returns a more restrictive
+        *   estimation of the spare capacity on that CPU, by just considering
+        *   the expected utilization of tasks already runnable on that CPU.
+        */
+       util_est = cpu_rq(cpu)->cfs.util_est_runnable;
+       util = max(util, util_est);
+
+       return util;

May be a separate patch to remove the clamping part?

Thanks,
Pavan

Quoted 17 lines

Quoted 17 lines

kernel/sched/fair.c +16 -0

+       /*
+        * These are the main cases covered:
+        * - if *p is the only task sleeping on this CPU, then:
+        *      cpu_util (== task_util) > util_est (== 0)
+        *   and thus we return:
+        *      cpu_util_wake = (cpu_util - task_util) = 0
+        *
+        * - if other tasks are SLEEPING on the same CPU, which is just waking
+        *   up, then:
+        *      cpu_util >= task_util
+        *      cpu_util > util_est (== 0)
+        *   and thus we discount *p's blocked utilization to return:
+        *      cpu_util_wake = (cpu_util - task_util) >= 0
+        *
+        * - if other tasks are RUNNABLE on that CPU and
+        *      util_est > cpu_util

Quoted 8 lines

kernel/sched/fair.c static inline unsigned long task_util_est(struct task_struct *p) · line 6422

Quoted 8 lines

kernel/sched/fair.c +8 -0

+        *   then we use util_est since it returns a more restrictive
+        *   estimation of the spare capacity on that CPU, by just considering
+        *   the expected utilization of tasks already runnable on that CPU.
+        */
+       util_est = cpu_rq(cpu)->cfs.util_est_runnable;
+       util = max(util, util_est);
+
+       return util;

I should instead clamp util before returning it! ;-)

Quoted 1 line

May be a separate patch to remove the clamping part?

No, I think we should keep cpu_util_wake clamped to not affect the existing call sites. I just need to remove it where not needed (done) and add it where needed (will do on the next iteration).

Quoted 28 lines · Patrick Bellasi

Quoted 17 lines

Quoted 17 lines

kernel/sched/fair.c +16 -0

+       /*
+        * These are the main cases covered:
+        * - if *p is the only task sleeping on this CPU, then:
+        *      cpu_util (== task_util) > util_est (== 0)
+        *   and thus we return:
+        *      cpu_util_wake = (cpu_util - task_util) = 0
+        *
+        * - if other tasks are SLEEPING on the same CPU, which is just waking
+        *   up, then:
+        *      cpu_util >= task_util
+        *      cpu_util > util_est (== 0)
+        *   and thus we discount *p's blocked utilization to return:
+        *      cpu_util_wake = (cpu_util - task_util) >= 0
+        *
+        * - if other tasks are RUNNABLE on that CPU and
+        *      util_est > cpu_util

Quoted 8 lines

kernel/sched/fair.c static inline unsigned long task_util_est(struct task_struct *p) · line 6422

Quoted 8 lines

kernel/sched/fair.c +8 -0

+        *   then we use util_est since it returns a more restrictive
+        *   estimation of the spare capacity on that CPU, by just considering
+        *   the expected utilization of tasks already runnable on that CPU.
+        */
+       util_est = cpu_rq(cpu)->cfs.util_est_runnable;
+       util = max(util, util_est);
+
+       return util;

I should instead clamp util before returning it! ;-)

Quoted 5 lines

Quoted 1 line

May be a separate patch to remove the clamping part?

No, I think we should keep cpu_util_wake clamped to not affect the existing call sites. I just need to remove it where not needed (done) and add it where needed (will do on the next iteration).

cpu_util_wake() is called only from capacity_spare_wake(). There are no other callsites.

The capacity_spare_wake() is clamping the return value of cpu_util_wake() to CPU capacity.

The clamping is not needed, I think.