2019-10-24 14:25:40

by Patrick Bellasi

[permalink] [raw]
Subject: [PATCH v2] sched/fair: util_est: fast ramp-up EWMA on utilization increases

The estimated utilization for a task:

util_est = max(util_avg, est.enqueue, est.ewma)

is defined based on:
- util_avg: the PELT defined utilization
- est.enqueued: the util_avg at the end of the last activation
- est.ewma: a exponential moving average on the est.enqueued
samples

According to this definition, when a task suddenly change its bandwidth
requirements from small to big, the EWMA will need to collect multiple
samples before converging up to track the new big utilization.

This slow convergence towards bigger utilization values is not
aligned to the default scheduler behavior, which is to optimize for
performance. Moreover, the est.ewma component fails to compensate for
temporarely utilization drops which spans just few est.enqueued samples.

To let util_est do a better job in the scenario depicted above, change
its definition by making util_est directly follow upward motion and
only decay the est.ewma on downward.

Signed-off-by: Patrick Bellasi <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Peter Zijlstra <[email protected]>
---
kernel/sched/fair.c | 14 +++++++++++++-
kernel/sched/features.h | 1 +
2 files changed, 14 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a81c36472822..a14487462b6c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3768,11 +3768,22 @@ util_est_dequeue(struct cfs_rq *cfs_rq, struct task_struct *p, bool task_sleep)
if (ue.enqueued & UTIL_AVG_UNCHANGED)
return;

+ /*
+ * Reset EWMA on utilization increases, the moving average is used only
+ * to smooth utilization decreases.
+ */
+ ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
+ if (sched_feat(UTIL_EST_FASTUP)) {
+ if (ue.ewma < ue.enqueued) {
+ ue.ewma = ue.enqueued;
+ goto done;
+ }
+ }
+
/*
* Skip update of task's estimated utilization when its EWMA is
* already ~1% close to its last activation value.
*/
- ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
last_ewma_diff = ue.enqueued - ue.ewma;
if (within_margin(last_ewma_diff, (SCHED_CAPACITY_SCALE / 100)))
return;
@@ -3805,6 +3816,7 @@ util_est_dequeue(struct cfs_rq *cfs_rq, struct task_struct *p, bool task_sleep)
ue.ewma <<= UTIL_EST_WEIGHT_SHIFT;
ue.ewma += last_ewma_diff;
ue.ewma >>= UTIL_EST_WEIGHT_SHIFT;
+done:
WRITE_ONCE(p->se.avg.util_est, ue);
}

diff --git a/kernel/sched/features.h b/kernel/sched/features.h
index 2410db5e9a35..7481cd96f391 100644
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -89,3 +89,4 @@ SCHED_FEAT(WA_BIAS, true)
* UtilEstimation. Use estimated CPU utilization.
*/
SCHED_FEAT(UTIL_EST, true)
+SCHED_FEAT(UTIL_EST_FASTUP, true)
--
2.17.1


2019-10-25 16:10:03

by Vincent Guittot

[permalink] [raw]
Subject: Re: [PATCH v2] sched/fair: util_est: fast ramp-up EWMA on utilization increases

On Wed, 23 Oct 2019 at 22:56, Patrick Bellasi
<[email protected]> wrote:
>
> The estimated utilization for a task:
>
> util_est = max(util_avg, est.enqueue, est.ewma)
>
> is defined based on:
> - util_avg: the PELT defined utilization
> - est.enqueued: the util_avg at the end of the last activation
> - est.ewma: a exponential moving average on the est.enqueued
> samples
>
> According to this definition, when a task suddenly change its bandwidth
> requirements from small to big, the EWMA will need to collect multiple
> samples before converging up to track the new big utilization.
>
> This slow convergence towards bigger utilization values is not
> aligned to the default scheduler behavior, which is to optimize for
> performance. Moreover, the est.ewma component fails to compensate for
> temporarely utilization drops which spans just few est.enqueued samples.
>
> To let util_est do a better job in the scenario depicted above, change
> its definition by making util_est directly follow upward motion and
> only decay the est.ewma on downward.
>
> Signed-off-by: Patrick Bellasi <[email protected]>
> Cc: Ingo Molnar <[email protected]>
> Cc: Peter Zijlstra <[email protected]>

Acked-by: Vincent Guittot <[email protected]>

> ---
> kernel/sched/fair.c | 14 +++++++++++++-
> kernel/sched/features.h | 1 +
> 2 files changed, 14 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index a81c36472822..a14487462b6c 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -3768,11 +3768,22 @@ util_est_dequeue(struct cfs_rq *cfs_rq, struct task_struct *p, bool task_sleep)
> if (ue.enqueued & UTIL_AVG_UNCHANGED)
> return;
>
> + /*
> + * Reset EWMA on utilization increases, the moving average is used only
> + * to smooth utilization decreases.
> + */
> + ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
> + if (sched_feat(UTIL_EST_FASTUP)) {
> + if (ue.ewma < ue.enqueued) {
> + ue.ewma = ue.enqueued;
> + goto done;
> + }
> + }
> +
> /*
> * Skip update of task's estimated utilization when its EWMA is
> * already ~1% close to its last activation value.
> */
> - ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
> last_ewma_diff = ue.enqueued - ue.ewma;
> if (within_margin(last_ewma_diff, (SCHED_CAPACITY_SCALE / 100)))
> return;
> @@ -3805,6 +3816,7 @@ util_est_dequeue(struct cfs_rq *cfs_rq, struct task_struct *p, bool task_sleep)
> ue.ewma <<= UTIL_EST_WEIGHT_SHIFT;
> ue.ewma += last_ewma_diff;
> ue.ewma >>= UTIL_EST_WEIGHT_SHIFT;
> +done:
> WRITE_ONCE(p->se.avg.util_est, ue);
> }
>
> diff --git a/kernel/sched/features.h b/kernel/sched/features.h
> index 2410db5e9a35..7481cd96f391 100644
> --- a/kernel/sched/features.h
> +++ b/kernel/sched/features.h
> @@ -89,3 +89,4 @@ SCHED_FEAT(WA_BIAS, true)
> * UtilEstimation. Use estimated CPU utilization.
> */
> SCHED_FEAT(UTIL_EST, true)
> +SCHED_FEAT(UTIL_EST_FASTUP, true)
> --
> 2.17.1
>

2019-10-29 17:50:11

by tip-bot2 for Jacob Pan

[permalink] [raw]
Subject: [tip: sched/core] sched/fair/util_est: Implement faster ramp-up EWMA on utilization increases

The following commit has been merged into the sched/core branch of tip:

Commit-ID: b8c96361402aa3e74ad48ceef18aed99153d8da8
Gitweb: https://git.kernel.org/tip/b8c96361402aa3e74ad48ceef18aed99153d8da8
Author: Patrick Bellasi <[email protected]>
AuthorDate: Wed, 23 Oct 2019 21:56:30 +01:00
Committer: Ingo Molnar <[email protected]>
CommitterDate: Tue, 29 Oct 2019 10:01:07 +01:00

sched/fair/util_est: Implement faster ramp-up EWMA on utilization increases

The estimated utilization for a task:

util_est = max(util_avg, est.enqueue, est.ewma)

is defined based on:

- util_avg: the PELT defined utilization
- est.enqueued: the util_avg at the end of the last activation
- est.ewma: a exponential moving average on the est.enqueued samples

According to this definition, when a task suddenly changes its bandwidth
requirements from small to big, the EWMA will need to collect multiple
samples before converging up to track the new big utilization.

This slow convergence towards bigger utilization values is not
aligned to the default scheduler behavior, which is to optimize for
performance. Moreover, the est.ewma component fails to compensate for
temporarely utilization drops which spans just few est.enqueued samples.

To let util_est do a better job in the scenario depicted above, change
its definition by making util_est directly follow upward motion and
only decay the est.ewma on downward.

Signed-off-by: Patrick Bellasi <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
Acked-by: Vincent Guittot <[email protected]>
Cc: Dietmar Eggemann <[email protected]>
Cc: Douglas Raillard <[email protected]>
Cc: Juri Lelli <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Quentin Perret <[email protected]>
Cc: Rafael J . Wysocki <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Link: https://lkml.kernel.org/r/[email protected]
Signed-off-by: Ingo Molnar <[email protected]>
---
kernel/sched/fair.c | 14 +++++++++++++-
kernel/sched/features.h | 1 +
2 files changed, 14 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a81c364..a144874 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3769,10 +3769,21 @@ util_est_dequeue(struct cfs_rq *cfs_rq, struct task_struct *p, bool task_sleep)
return;

/*
+ * Reset EWMA on utilization increases, the moving average is used only
+ * to smooth utilization decreases.
+ */
+ ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
+ if (sched_feat(UTIL_EST_FASTUP)) {
+ if (ue.ewma < ue.enqueued) {
+ ue.ewma = ue.enqueued;
+ goto done;
+ }
+ }
+
+ /*
* Skip update of task's estimated utilization when its EWMA is
* already ~1% close to its last activation value.
*/
- ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
last_ewma_diff = ue.enqueued - ue.ewma;
if (within_margin(last_ewma_diff, (SCHED_CAPACITY_SCALE / 100)))
return;
@@ -3805,6 +3816,7 @@ util_est_dequeue(struct cfs_rq *cfs_rq, struct task_struct *p, bool task_sleep)
ue.ewma <<= UTIL_EST_WEIGHT_SHIFT;
ue.ewma += last_ewma_diff;
ue.ewma >>= UTIL_EST_WEIGHT_SHIFT;
+done:
WRITE_ONCE(p->se.avg.util_est, ue);
}

diff --git a/kernel/sched/features.h b/kernel/sched/features.h
index 2410db5..7481cd9 100644
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -89,3 +89,4 @@ SCHED_FEAT(WA_BIAS, true)
* UtilEstimation. Use estimated CPU utilization.
*/
SCHED_FEAT(UTIL_EST, true)
+SCHED_FEAT(UTIL_EST_FASTUP, true)