Skip to contentSkip to conversation

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

PATCH In review Patrick Bellasi 5 participants 15 messages Jun 20, 2019 – Oct 21, 2019 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched/fair: util_est: fast ramp-up EWMA on utilization increases

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

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

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling" mechanisms instead of the previous "delta-scaling" approach.

Unfortunately, these drops cannot be fully absorbed by the current util_est implementation. Indeed, the low-frequency filtering introduced by the "ewma" is entirely useless while converging up and it does not help in stabilizing sooner the PELT signal.

To make util_est do better service in the above scenario, do change its definition to slow down only utilization decreases. Do that by resetting the "ewma" every time the last collected sample increases.

This change makes also the default util_est implementation more aligned with the major scheduler behavior, which is to optimize for performance. In the future, this implementation can be further refined to consider task specific hints.

[1] sched/fair: Update scale invariance of PELT

    Message-ID: <[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(-)
kernel/sched/fair.c +13 -1
index 3c11dcdedcbc..27b33caaaaf4 100644
@@ -3685,11 +3685,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;
@@ -3722,6 +3733,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);
 }
 
kernel/sched/features.h +1 -0
index 2410db5e9a35..7481cd96f391 100644
@@ -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)
Signature · 1 line
2.21.0
maintainer
#1 lore raw

Hi Patrick,

Quoted 5 lines · Patrick Bellasi

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

Quoted 7 lines

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

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling"

Could you give us more details about this? I'm not sure to understand what changes between the 1st big activation and the following one ? The utilization implied by new "time-scaling" should be the same as always running at max frequency with previous method

Quoted 75 lines

mechanisms instead of the previous "delta-scaling" approach.

Unfortunately, these drops cannot be fully absorbed by the current util_est implementation. Indeed, the low-frequency filtering introduced by the "ewma" is entirely useless while converging up and it does not help in stabilizing sooner the PELT signal.

To make util_est do better service in the above scenario, do change its definition to slow down only utilization decreases. Do that by resetting the "ewma" every time the last collected sample increases.

This change makes also the default util_est implementation more aligned with the major scheduler behavior, which is to optimize for performance. In the future, this implementation can be further refined to consider task specific hints.

[1] sched/fair: Update scale invariance of PELT

    Message-ID: <[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(-)
kernel/sched/fair.c +13 -1
index 3c11dcdedcbc..27b33caaaaf4 100644
@@ -3685,11 +3685,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;
@@ -3722,6 +3733,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);
 }
 
kernel/sched/features.h +1 -1
index 2410db5e9a35..7481cd96f391 100644
@@ -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.21.0

#2 lore raw
Quoted 12 lines · Vincent Guittot

Hi Patrick,

Quoted 9 lines · Patrick Bellasi

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

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

Quoted 6 lines
Quoted 3 lines

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling"

Could you give us more details about this? I'm not sure to understand what changes between the 1st big activation and the following one ?

We are after a solution for the problem Douglas Raillard discussed at OSPM, specifically the "Task util drop after 1st idle" highlighted in slide 6 of his presentation:

http://retis.sssup.it/ospm-summit/Downloads/02_05-Douglas_Raillard-How_can_we_make_schedutil_even_more_effective.pdf

which shows what happens with a task switches from 5% to 75% and we get these start/end values for each activation:

Act Time __comm __cpu __pid task util_avg
--------------------------------------------------------------
1 2.813559 <idle> 4 0 step_up 45

          2.902624	step_up	    4	2574	step_up	     665
  --------------------------------------------------------------
  2       2.903722	<idle>	    4	   0	step_up	     289
          2.917385	step_up	    4	2574	step_up	     452
  --------------------------------------------------------------
  3       2.919725	<idle>	    4	   0	step_up	     418
          2.953764	step_up	    4	2574	step_up	     658
  --------------------------------------------------------------
  4       2.954248	<idle>	    4	   0	step_up	     537
          2.967955	step_up	    4	2574	step_up	     645
  --------------------------------------------------------------
  5       2.970248	<idle>	    4	   0	step_up	     597
          2.983914	step_up	    4	2574	step_up	     692
  --------------------------------------------------------------
  6       2.986248	<idle>	    4	   0	step_up	     640
          2.999924	step_up	    4	2574	step_up	     725
  --------------------------------------------------------------
  7       3.002248	<idle>	    4	   0	step_up	     670
          3.015872	step_up	    4	2574	step_up	     749
  --------------------------------------------------------------
  8       3.018248	<idle>	    4	   0	step_up	     694
          3.030474	step_up	    4	2574	step_up	     767
  --------------------------------------------------------------
  9       3.034247	<idle>	    4	   0	step_up	     710
          3.046454	step_up	    4	2574	step_up	     780

--------------------------------------------------------------

Since the first activation is running at lower-than-max OPPs we do "time-scaling" at the end of the activation. Util_avg starts at 45 and ramps up to 665 but then it drops 375 units down to 289 at the beginning of the second activation.

The second activation has a chance to run at higher OPPs, but still not at max. Util_avg starts at 289 and ramps up to 452, which is even lower then the previous max value, but then it drops 34 units down to 418.

The following activations have a similar pattern but util_avg converges toward the final value, we run almost always at the highest OPP and the drops are defined mainly by the expected PELT decay.

Quoted 2 lines

The utilization implied by new "time-scaling" should be the same as always running at max frequency with previous method

Right, the problem we are tacking with this patch however is to make util_est a better signal for the ramp-up phases.

Right now util_est "fixes" only the second activation, since:

max(util_avg, last_value, ewma) =
max(289, 665, <289) = 665

and thus we keep running on the highest OPP we reached at the end of the first activation.

While at the start of the third activation:

max(util_avg, last_value, ewma) =
max(452, 418, <452) = 452

and this time we drop the OPP quite a lot despite the signal still being ramping up.

Quoted 2 lines
Quoted 2 lines

mechanisms instead of the previous "delta-scaling" approach.

That happens because the EWMA takes multiple activations to converge up, which means it's not very helping much:

Quoted 4 lines
Quoted 4 lines

Unfortunately, these drops cannot be fully absorbed by the current util_est implementation. Indeed, the low-frequency filtering introduced by the "ewma" is entirely useless while converging up and it does not help in stabilizing sooner the PELT signal.

The idea of the patch is to exploit two observations:

1. the default scheduler behavior is to be performance oriented
2. the longher you run a task underprovisioned, the higher the util_avg will be

Which turns into:

Quoted 8 lines
Quoted 8 lines

To make util_est do better service in the above scenario, do change its definition to slow down only utilization decreases. Do that by resetting the "ewma" every time the last collected sample increases.

This change makes also the default util_est implementation more aligned with the major scheduler behavior, which is to optimize for performance. In the future, this implementation can be further refined to consider task specific hints.

Cheers,
Patrick

Signature · 3 lines
#include <best/regards.h>

Patrick Bellasi
maintainer
#3 lore raw
Quoted 17 lines · Patrick Bellasi
Quoted 16 lines · Vincent Guittot

Hi Patrick,

Quoted 12 lines · Patrick Bellasi

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

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

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling"

Quoted 9 lines
Quoted 2 lines

Could you give us more details about this? I'm not sure to understand what changes between the 1st big activation and the following one ?

We are after a solution for the problem Douglas Raillard discussed at OSPM, specifically the "Task util drop after 1st idle" highlighted in slide 6 of his presentation:

http://retis.sssup.it/ospm-summit/Downloads/02_05-Douglas_Raillard-How_can_we_make_schedutil_even_more_effective.pdf

So I see the problem, and I don't hate the patch, but I'm still struggling to understand how exactly it related to the time-scaling stuff. Afaict the fundamental problem here is layering two averages. The second (EWMA in our case) will always lag/delay the input of the first (PELT).

The time-scaling thing might make matters worse, because that helps PELT ramp up faster, but that is not the primary issue.

Or am I missing something?

maintainer
#4 lore raw
Quoted 26 lines · Peter Zijlstra
Quoted 24 lines · Patrick Bellasi
Quoted 12 lines · Vincent Guittot

Hi Patrick,

Quoted 9 lines · Patrick Bellasi

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

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

Quoted 6 lines
Quoted 3 lines

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling"

Could you give us more details about this? I'm not sure to understand what changes between the 1st big activation and the following one ?

We are after a solution for the problem Douglas Raillard discussed at OSPM, specifically the "Task util drop after 1st idle" highlighted in slide 6 of his presentation:

Quoted 6 lines
Quoted 2 lines

http://retis.sssup.it/ospm-summit/Downloads/02_05-Douglas_Raillard-How_can_we_make_schedutil_even_more_effective.pdf

So I see the problem, and I don't hate the patch, but I'm still struggling to understand how exactly it related to the time-scaling stuff. Afaict the fundamental problem here is layering two averages. The

AFAICT, it's not related to the time-scaling

In fact the big 1st activation happens because task runs at low OPP and hasn't enough time to finish its running phase before the time to begin the next one happens. This means that the task will run several computations phase in one go which is no more a 75% task. From a pelt PoV, the task is far larger than a 75% task and its utilization too because it runs far longer (even after scaling time with frequency). Once cpu reaches a high enough OPP that enable to have sleep phase between each running phases, the task load tracking comes back to the normal slope increase (the one that would have happen if task would have jump from 5% to 75% but already running at max OPP)

Quoted 7 lines

second (EWMA in our case) will always lag/delay the input of the first (PELT).

The time-scaling thing might make matters worse, because that helps PELT ramp up faster, but that is not the primary issue.

Or am I missing something?

#5 lore raw
Quoted 34 lines · Vincent Guittot
Quoted 26 lines · Peter Zijlstra
Quoted 24 lines · Patrick Bellasi
Quoted 12 lines · Vincent Guittot

Hi Patrick,

Quoted 9 lines · Patrick Bellasi

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

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

Quoted 6 lines
Quoted 3 lines

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling"

Could you give us more details about this? I'm not sure to understand what changes between the 1st big activation and the following one ?

We are after a solution for the problem Douglas Raillard discussed at OSPM, specifically the "Task util drop after 1st idle" highlighted in slide 6 of his presentation:

Quoted 6 lines
Quoted 2 lines

http://retis.sssup.it/ospm-summit/Downloads/02_05-Douglas_Raillard-How_can_we_make_schedutil_even_more_effective.pdf

So I see the problem, and I don't hate the patch, but I'm still struggling to understand how exactly it related to the time-scaling stuff. Afaict the fundamental problem here is layering two averages. The

Quoted 6 lines

AFAICT, it's not related to the time-scaling

In fact the big 1st activation happens because task runs at low OPP and hasn't enough time to finish its running phase before the time to begin the next one happens. This means that the task will run several computations phase in one go which is no more a 75% task.

But in that case, running multiple activations back to back, should we not expect the util_avg to exceed the 75% mark?

Quoted 3 lines

From a pelt PoV, the task is far larger than a 75% task and its utilization too because it runs far longer (even after scaling time with frequency).

Which thus should match my expectation above, no?

Quoted 4 lines

Once cpu reaches a high enough OPP that enable to have sleep phase between each running phases, the task load tracking comes back to the normal slope increase (the one that would have happen if task would have jump from 5% to 75% but already running at max OPP)

Indeed, I can see from the plots a change in slope. But there is also that big drop after the first big activation: 375 units in 1.1ms.

Is that expected? I guess yes, since we fix the clock_pelt with the lost_idle_time.

Quoted 7 lines
Quoted 7 lines

second (EWMA in our case) will always lag/delay the input of the first (PELT).

The time-scaling thing might make matters worse, because that helps PELT ramp up faster, but that is not the primary issue.

Or am I missing something?

Signature · 3 lines
#include <best/regards.h>

Patrick Bellasi
maintainer
#6 lore raw
Quoted 38 lines · Patrick Bellasi
Quoted 36 lines · Vincent Guittot
Quoted 26 lines · Peter Zijlstra
Quoted 24 lines · Patrick Bellasi
Quoted 12 lines · Vincent Guittot

Hi Patrick,

Quoted 9 lines · Patrick Bellasi

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

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

Quoted 6 lines
Quoted 3 lines

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling"

Could you give us more details about this? I'm not sure to understand what changes between the 1st big activation and the following one ?

We are after a solution for the problem Douglas Raillard discussed at OSPM, specifically the "Task util drop after 1st idle" highlighted in slide 6 of his presentation:

Quoted 6 lines
Quoted 2 lines

http://retis.sssup.it/ospm-summit/Downloads/02_05-Douglas_Raillard-How_can_we_make_schedutil_even_more_effective.pdf

So I see the problem, and I don't hate the patch, but I'm still struggling to understand how exactly it related to the time-scaling stuff. Afaict the fundamental problem here is layering two averages. The

AFAICT, it's not related to the time-scaling

Quoted 7 lines
Quoted 4 lines

In fact the big 1st activation happens because task runs at low OPP and hasn't enough time to finish its running phase before the time to begin the next one happens. This means that the task will run several computations phase in one go which is no more a 75% task.

But in that case, running multiple activations back to back, should we not expect the util_avg to exceed the 75% mark?

But task starts with a very low value and Pelt needs time to ramp up.

Quoted 7 lines
Quoted 5 lines

From a pelt PoV, the task is far larger than a 75% task and its utilization too because it runs far longer (even after scaling time with frequency).

Which thus should match my expectation above, no?

But utilization has to ramp up before stabilizing to final value. The value at the end of the 1st big activation is not what would be the utilization if task was always that long

Quoted 26 lines
Quoted 5 lines

Once cpu reaches a high enough OPP that enable to have sleep phase between each running phases, the task load tracking comes back to the normal slope increase (the one that would have happen if task would have jump from 5% to 75% but already running at max OPP)

Indeed, I can see from the plots a change in slope. But there is also that big drop after the first big activation: 375 units in 1.1ms.

Is that expected? I guess yes, since we fix the clock_pelt with the lost_idle_time.

Quoted 7 lines
Quoted 7 lines

second (EWMA in our case) will always lag/delay the input of the first (PELT).

The time-scaling thing might make matters worse, because that helps PELT ramp up faster, but that is not the primary issue.

Or am I missing something?

--
#include <best/regards.h>

Patrick Bellasi

#7 lore raw
Quoted 5 lines · Vincent Guittot
Quoted 4 lines · Patrick Bellasi
Quoted 3 lines · Vincent Guittot
Quoted 2 lines · Peter Zijlstra
Quoted 1 line · Patrick Bellasi

On 26-Jun 13:40, Vincent Guittot wrote:

Hi Vincent,

[...]

Quoted 11 lines
Quoted 9 lines
Quoted 6 lines

AFAICT, it's not related to the time-scaling

In fact the big 1st activation happens because task runs at low OPP and hasn't enough time to finish its running phase before the time to begin the next one happens. This means that the task will run several computations phase in one go which is no more a 75% task.

But in that case, running multiple activations back to back, should we not expect the util_avg to exceed the 75% mark?

But task starts with a very low value and Pelt needs time to ramp up.

Of course...

[...]

Quoted 11 lines
Quoted 11 lines
Quoted 4 lines

Once cpu reaches a high enough OPP that enable to have sleep phase between each running phases, the task load tracking comes back to the normal slope increase (the one that would have happen if task would have jump from 5% to 75% but already running at max OPP)

Indeed, I can see from the plots a change in slope. But there is also that big drop after the first big activation: 375 units in 1.1ms.

Is that expected? I guess yes, since we fix the clock_pelt with the lost_idle_time.

... but, I guess Peter was mainly asking about the point above: is that "big" drop after the first activation related to time-scaling or not?

Cheers,
Patrick

Signature · 3 lines
#include <best/regards.h>

Patrick Bellasi
#8 lore raw
In reply to Peter Zijlstra
Quoted 28 lines · Peter Zijlstra
Quoted 17 lines · Patrick Bellasi
Quoted 16 lines · Vincent Guittot

Hi Patrick,

Quoted 12 lines · Patrick Bellasi

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

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

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling"

Quoted 9 lines
Quoted 2 lines

Could you give us more details about this? I'm not sure to understand what changes between the 1st big activation and the following one ?

We are after a solution for the problem Douglas Raillard discussed at OSPM, specifically the "Task util drop after 1st idle" highlighted in slide 6 of his presentation:

http://retis.sssup.it/ospm-summit/Downloads/02_05-Douglas_Raillard-How_can_we_make_schedutil_even_more_effective.pdf

Quoted 8 lines

So I see the problem, and I don't hate the patch, but I'm still struggling to understand how exactly it related to the time-scaling stuff. Afaict the fundamental problem here is layering two averages. The second (EWMA in our case) will always lag/delay the input of the first (PELT).

The time-scaling thing might make matters worse, because that helps PELT ramp up faster, but that is not the primary issue.

Sure, we like the new time-scaling PELT which ramps up faster and, as long as we have idle time, it's better in predicting what would be the utilization as if we was running at max OPP.

However, the experiment above shows that:

- despite the task being a 75% after a certain activation, it takes multiple activations for PELT to actually enter that range.

- the first activation ends at 665, 10% short wrt the configured utilization

- while the PELT signal converge toward the 75%, we have some pretty consistent drops at wakeup time, especially after the first big activation.

Quoted 1 line

Or am I missing something?

I'm not sure the above happens because of a problem in the new time-scaling PELT, I actually think it's kind of expected given the way we re-scale time contributions depending on the current OPPs.

It's just that a 375 drops in utilization with just 1.1ms sleep time looks to me more related to the time-scaling invariance then just the normal/expected PELT decay.

Could it be an out-of-sync issue between the PELT time scaling code and capacity scaling code?
Perhaps due to some OPP changes/notification going wrong?

Sorry for not being much more useful on that, maybe Vincent has some better ideas.

The only thing I've kind of convinced myself is that an EWMA on util_est does not make a lot of sense for increasing utilization tracking.

Best,
Patrick

Signature · 3 lines
#include <best/regards.h>

Patrick Bellasi
#9 lore raw

Hi Peter, Vincent,
is there anything different I can do on this?

Cheers,
Patrick

Quoted 82 lines · Patrick Bellasi
Quoted 28 lines · Peter Zijlstra
Quoted 17 lines · Patrick Bellasi
Quoted 16 lines · Vincent Guittot

Hi Patrick,

Quoted 12 lines · Patrick Bellasi

The estimated utilization for a task is currently defined based on:
- enqueued: the utilization value at the end of the last activation
- ewma: an exponential moving average which samples are the enqueued values

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

Moreover, after the PELT scale invariance update [1], in the above scenario we can see that the utilization of the task has a significant drop from the first big activation to the following one. That's implied by the new "time-scaling"

Quoted 9 lines
Quoted 2 lines

Could you give us more details about this? I'm not sure to understand what changes between the 1st big activation and the following one ?

We are after a solution for the problem Douglas Raillard discussed at OSPM, specifically the "Task util drop after 1st idle" highlighted in slide 6 of his presentation:

http://retis.sssup.it/ospm-summit/Downloads/02_05-Douglas_Raillard-How_can_we_make_schedutil_even_more_effective.pdf

Quoted 8 lines

So I see the problem, and I don't hate the patch, but I'm still struggling to understand how exactly it related to the time-scaling stuff. Afaict the fundamental problem here is layering two averages. The second (EWMA in our case) will always lag/delay the input of the first (PELT).

The time-scaling thing might make matters worse, because that helps PELT ramp up faster, but that is not the primary issue.

Sure, we like the new time-scaling PELT which ramps up faster and, as long as we have idle time, it's better in predicting what would be the utilization as if we was running at max OPP.

However, the experiment above shows that:

- despite the task being a 75% after a certain activation, it takes multiple activations for PELT to actually enter that range.

- the first activation ends at 665, 10% short wrt the configured utilization

- while the PELT signal converge toward the 75%, we have some pretty consistent drops at wakeup time, especially after the first big activation.

Quoted 1 line

Or am I missing something?

I'm not sure the above happens because of a problem in the new time-scaling PELT, I actually think it's kind of expected given the way we re-scale time contributions depending on the current OPPs.

It's just that a 375 drops in utilization with just 1.1ms sleep time looks to me more related to the time-scaling invariance then just the normal/expected PELT decay.

Could it be an out-of-sync issue between the PELT time scaling code and capacity scaling code?
Perhaps due to some OPP changes/notification going wrong?

Sorry for not being much more useful on that, maybe Vincent has some better ideas.

The only thing I've kind of convinced myself is that an EWMA on util_est does not make a lot of sense for increasing utilization tracking.

Best,
Patrick

Signature · 3 lines
#include <best/regards.h>

Patrick Bellasi
Signature · 3 lines
#include <best/regards.h>

Patrick Bellasi
maintainer
#10 lore raw

The energy aware schedutil patches remimded me this was still pending.

Quoted 2 lines · Patrick Bellasi

Hi Peter, Vincent,
is there anything different I can do on this?

I think both Vincent and me are basically fine with the patch, it was the Changelog/explanation for it that sat uneasy.

Specifically I think the 'confusion' around the PELT invariance stuff doesn't help.

I think that if you present it simply as making util_est directly follow upward motion and only decay on downward -- and the rationale for it -- then it should be fine.

maintainer
#11 lore raw
Quoted 10 lines · Peter Zijlstra

The energy aware schedutil patches remimded me this was still pending.

Quoted 2 lines · Patrick Bellasi

Hi Peter, Vincent,
is there anything different I can do on this?

I think both Vincent and me are basically fine with the patch, it was the Changelog/explanation for it that sat uneasy.

I agree

Quoted 9 lines

Specifically I think the 'confusion' around the PELT invariance stuff doesn't help.

I think that if you present it simply as making util_est directly follow upward motion and only decay on downward -- and the rationale for it -- then it should be fine.

#12 lore raw
In reply to Peter Zijlstra

Hi Peter,

Quoted 10 lines · Peter Zijlstra

The energy aware schedutil patches remimded me this was still pending.

Quoted 2 lines · Patrick Bellasi

Hi Peter, Vincent,
is there anything different I can do on this?

I think both Vincent and me are basically fine with the patch, it was the Changelog/explanation for it that sat uneasy.

Quoted 6 lines

Specifically I think the 'confusion' around the PELT invariance stuff doesn't help.

I think that if you present it simply as making util_est directly follow upward motion and only decay on downward -- and the rationale for it -- then it should be fine.

random idea: Since these things are much easier to understand by looking at a graph
of util over time, we may agree on some mailing-list-friendly way to convey graphs.
For example, a simple CSV with:
* before/after delimiters (line of # or =)
* graph title
* one point per signal transition, so that it can be plotted with gnuplot style "steps" or matplotlib drawstyle='steps-post'
* consistent column names:
- time: in seconds (scientific notation for nanoseconds)
- activation: 1 when the task is actually running, 0 otherwise
(so it can be turned into transparent coloured bands like using gnuplot filledcurves, like in [1])
- util: util_avg of the task being talked about

The delimiters allow writing a scripts to render graphs directly out of an mbox file or ML archive URL. This won't solve the issue for the commit message itself, but that may ease the ML discussions.

[1] https://lisa-linux-integrated-system-analysis.readthedocs.io/en/master/trace_analysis.html#lisa.analysis.tasks.TasksAnalysis.plot_task_activation

Cheers,
Douglas

maintainer
#13 lore raw
Quoted 2 lines · Douglas Raillard

random idea: Since these things are much easier to understand by looking at a graph of util over time, we may agree on some mailing-list-friendly way to convey graphs.

I don't think that this patch warrants something like that. It is fairly clear what it does.

For other stuff, maybe.

Quoted 10 lines

For example, a simple CSV with:
* before/after delimiters (line of # or =)
* graph title
* one point per signal transition, so that it can be plotted with gnuplot style "steps" or matplotlib drawstyle='steps-post'
* consistent column names:
- time: in seconds (scientific notation for nanoseconds)
- activation: 1 when the task is actually running, 0 otherwise
(so it can be turned into transparent coloured bands like using gnuplot filledcurves, like in [1])
- util: util_avg of the task being talked about

Quoted 2 lines

The delimiters allow writing a scripts to render graphs directly out of an mbox file or ML archive URL. This won't solve the issue for the commit message itself, but that may ease the ML discussions.

Something like that could work; mutt can easily pipe emails into scripts. OTOH gnuplot also has ASCII output, so one can easily stick something like that into email.

#14 lore raw
In reply to Peter Zijlstra

Hi Peter,

Quoted 10 lines · Peter Zijlstra

The energy aware schedutil patches remimded me this was still pending.

Quoted 2 lines · Patrick Bellasi

Hi Peter, Vincent,
is there anything different I can do on this?

I think both Vincent and me are basically fine with the patch, it was the Changelog/explanation for it that sat uneasy.

Quoted 6 lines

Specifically I think the 'confusion' around the PELT invariance stuff doesn't help.

I think that if you present it simply as making util_est directly follow upward motion and only decay on downward -- and the rationale for it -- then it should be fine.

Ok, I'll update the commit message to remove the PELT related ambiguity and post a new version soon.

Cheers,
Patrick

Signature · 3 lines
#include <best/regards.h>

Patrick Bellasi