| Message ID | 1491815909-13345-1-git-send-email-vincent.guittot@linaro.org |
|---|---|
| State | New |
| Headers | show |
Thanks for the rebase. On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: Ok, so let me try and paraphrase what this patch does. So consider a task that runs 16 out of our 32ms window: running idle |---------|---------| You're saying that when we scale running with the frequency, suppose we were at 50% freq, we'll end up with: run idle |----|---------| Which is obviously a shorter total then before; so what you do is add back the lost idle time like: run lost idle |----|----|---------| to arrive at the same total time. Which seems to make sense. Now I have vague memories of Morten having issues with your previous patches, so I'll wait for him to chime in as well. On to the implementation: > /* > + * Scale the time to reflect the effective amount of computation done during > + * this delta time. > + */ > +static __always_inline u64 > +scale_time(u64 delta, int cpu, struct sched_avg *sa, > + unsigned long weight, int running) > +{ > + if (running) { > + sa->stolen_idle_time += delta; > + /* > + * scale the elapsed time to reflect the real amount of > + * computation > + */ > + delta = cap_scale(delta, arch_scale_freq_capacity(NULL, cpu)); > + delta = cap_scale(delta, arch_scale_cpu_capacity(NULL, cpu)); > + > + /* > + * Track the amount of stolen idle time due to running at > + * lower capacity > + */ > + sa->stolen_idle_time -= delta; OK so far so good, this tracks, in stolen_idle_time, the 'lost' bit from above. > + } else if (!weight) { > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { But here I'm completely lost. WTF just happened ;-) Firstly, I think we want a comment on why we care about the !weight case. Why isn't !running sufficient? Secondly, what's up with the util_sum < LOAD_AVG_MAX * 1000 thing? Is that to deal with cpu_capacity? > + /* > + * Add the idle time stolen by running at lower compute > + * capacity > + */ > + delta += sa->stolen_idle_time; > + } > + sa->stolen_idle_time = 0; > + } > + > + return delta; > +} Thirdly, I'm thinking this isn't quite right. Imagine a task that's running across a decay window, then we'll only add back the stolen_idle time in the next window, even though it should've been in this one, right?
Le Monday 10 Apr 2017 à 19:38:02 (+0200), Peter Zijlstra a écrit : > > Thanks for the rebase. > > On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > > Ok, so let me try and paraphrase what this patch does. > > So consider a task that runs 16 out of our 32ms window: > > running idle > |---------|---------| > > > You're saying that when we scale running with the frequency, suppose we > were at 50% freq, we'll end up with: > > run idle > |----|---------| > > > Which is obviously a shorter total then before; so what you do is add > back the lost idle time like: > > run lost idle > |----|----|---------| > > > to arrive at the same total time. Which seems to make sense. Yes > > Now I have vague memories of Morten having issues with your previous > patches, so I'll wait for him to chime in as well. IIRC, Morten's concerns were about the lost idle time which was not taken into account in previous version. > > > On to the implementation: > > > /* > > + * Scale the time to reflect the effective amount of computation done during > > + * this delta time. > > + */ > > +static __always_inline u64 > > +scale_time(u64 delta, int cpu, struct sched_avg *sa, > > + unsigned long weight, int running) > > +{ > > + if (running) { > > + sa->stolen_idle_time += delta; > > + /* > > + * scale the elapsed time to reflect the real amount of > > + * computation > > + */ > > + delta = cap_scale(delta, arch_scale_freq_capacity(NULL, cpu)); > > + delta = cap_scale(delta, arch_scale_cpu_capacity(NULL, cpu)); > > + > > + /* > > + * Track the amount of stolen idle time due to running at > > + * lower capacity > > + */ > > + sa->stolen_idle_time -= delta; > > OK so far so good, this tracks, in stolen_idle_time, the 'lost' bit from > above. > > > + } else if (!weight) { > > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { > > But here I'm completely lost. WTF just happened ;-) > > Firstly, I think we want a comment on why we care about the !weight > case. Why isn't !running sufficient? We track the time when the task is "really" idle but not the time that the task spent to wait for running on the CPU. Running is used to detect when the task is really running and how much idle time has been lost while weight is used to detect when the task is back to sleep state and when we have account the lost idle time. > > > Secondly, what's up with the util_sum < LOAD_AVG_MAX * 1000 thing? The lost idle time makes sense only if the task can also be "idle" when running at max capacity. When util_sum reaches the LOAD_AVG_MAX*SCHED_CAPACITY_SCALE value, all tasks are considered to be the same as we can't make any difference between a task running 400ms or a task running 400sec. It means that these tasks are "always running" tasks even at max capacity. In this case, there is no lost idle time as they always run and tracking and adding back the lost idle time because we run at lower capacity doesn't make sense anymore so we discard it. Then an always running task can have a util_sum that is less than the max value because of the rounding (util_avg varies between [1006..1023]), so I use LOAD_AVG_MAX*1000 instead of LOAD_AVG_MAX*1024 > > Is that to deal with cpu_capacity? > > > > + /* > > + * Add the idle time stolen by running at lower compute > > + * capacity > > + */ > > + delta += sa->stolen_idle_time; > > + } > > + sa->stolen_idle_time = 0; > > + } > > + > > + return delta; > > +} > > > Thirdly, I'm thinking this isn't quite right. Imagine a task that's > running across a decay window, then we'll only add back the stolen_idle > time in the next window, even though it should've been in this one, > right? I don't think so because the PELT should not see more decay window at half capacity than at max capacity. In the example below we can see that we cross the absolute time decay window when running at half capacity but once we scale the running delta time we don't cross it anymore and the update of PELT is done in the same manner in both case decay window |-------|-------|-------|-- max capacity ---xxxx------------xxxx---- update * * * * half capacity---xxxxxxxx--------xxxxxxxx accounted ---xxxx____--------xxxx____ update * * * * x running - sleep _ lost idle time
On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > Le Monday 10 Apr 2017 à 19:38:02 (+0200), Peter Zijlstra a écrit : > > > > Thanks for the rebase. > > > > On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > > > > Ok, so let me try and paraphrase what this patch does. > > > > So consider a task that runs 16 out of our 32ms window: > > > > running idle > > |---------|---------| > > > > > > You're saying that when we scale running with the frequency, suppose we > > were at 50% freq, we'll end up with: > > > > run idle > > |----|---------| > > > > > > Which is obviously a shorter total then before; so what you do is add > > back the lost idle time like: > > > > run lost idle > > |----|----|---------| > > > > > > to arrive at the same total time. Which seems to make sense. > > Yes OK, bear with me. So we have: util_sum' = utilsum * y^p + p-1 d1 * y^p + 1024 * \Sum y^n + d3 * y^0 n=1 For the unscaled version, right? Now for the scaled version, instead of adding a full 'd1,d2,d3' running segments, we want to add partially running segments, where r=f*d/f_max, and lost segments l=d-r to fill out the idle time. But afaict we then end up with (F=f/f_max): util_sum' = utilsum * y^p + p-1 F * d1 * y^p + F * 1024 * \Sum y^n + F * d3 * y^0 n=1 And we can collect the common term F: util_sum' = utilsum * y^p + p-1 F * (d1 * y^p + 1024 * \Sum y^n + d3 * y^0) n=1 Which is exactly what we already did. So now I'm confused. Where did I go wrong? Because by scaling the contribution we get the exact result of doing the smaller 'running' + 'lost' segments.
On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > > > + } else if (!weight) { > > > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { > > > > But here I'm completely lost. WTF just happened ;-) > > > > Firstly, I think we want a comment on why we care about the !weight > > case. Why isn't !running sufficient? > > We track the time when the task is "really" idle but not the time that > the task spent to wait for running on the CPU. Running is used to > detect when the task is really running and how much idle time has been > lost while weight is used to detect when the task is back to sleep > state and when we have account the lost idle time. Huh? You're redefining what 'idle' means wrt. util_sum. util used to consider anything !running as idle. So this is the main trickery? I feel that deserves a comment of exceptional clarity.
Le Tuesday 11 Apr 2017 à 10:53:05 (+0200), Peter Zijlstra a écrit : > On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > > Le Monday 10 Apr 2017 à 19:38:02 (+0200), Peter Zijlstra a écrit : > > > > > > Thanks for the rebase. > > > > > > On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > > > > > > Ok, so let me try and paraphrase what this patch does. > > > > > > So consider a task that runs 16 out of our 32ms window: > > > > > > running idle > > > |---------|---------| > > > > > > > > > You're saying that when we scale running with the frequency, suppose we > > > were at 50% freq, we'll end up with: > > > > > > run idle > > > |----|---------| > > > > > > > > > Which is obviously a shorter total then before; so what you do is add > > > back the lost idle time like: > > > > > > run lost idle > > > |----|----|---------| > > > > > > > > > to arrive at the same total time. Which seems to make sense. > > > > Yes > > OK, bear with me. > > > So we have: > > > util_sum' = utilsum * y^p + > > p-1 > d1 * y^p + 1024 * \Sum y^n + d3 * y^0 > n=1 > > For the unscaled version, right? Yes for the running state. For sleeping state, it's just util_sum' = utilsum * y^p > > > > Now for the scaled version, instead of adding a full 'd1,d2,d3' running > segments, we want to add partially running segments, where r=f*d/f_max, > and lost segments l=d-r to fill out the idle time. > > But afaict we then end up with (F=f/f_max): > > > util_sum' = utilsum * y^p + > > p-1 > F * d1 * y^p + F * 1024 * \Sum y^n + F * d3 * y^0 > n=1 you also have a longer running time as it runs slower. We make the assumption that d1+d2+d3 = (d1'+d2'+d3') * F If we consider that we cross a decay window, we still have the d1 to complete the past one but then p'*F= p and d'3 will be the remaining part of the current window and most probably not equal to d3 so we have with current invariance: util_sum' = utilsum * y^(p/F) + (p/F - 1) F * d1 * y^(p/F) + F * 1024 * \Sum y^n + F * d'3 * y^0 n=1 with the new invariance we have util_sum' = utilsum * y^(F*p/F) + (F*p/F - 1) d1 * y^(F*p/F) + 1024 * \Sum y^n + d3 * y^0 n=1 For a sleeping time of d at max capacity, we have a sleeping time d'=d-l, with l the lost time of the previous running time With the current implementation: util_sum' = utilsum * y^(p') util_sum' = utilsum * y^(p-l) With the new invaraince, we have util_sum' = utilsum * y^(p'+l) util_sum' = utilsum * y^(p-l+l) > > And we can collect the common term F: > > util_sum' = utilsum * y^p + > > p-1 > F * (d1 * y^p + 1024 * \Sum y^n + d3 * y^0) > n=1 > > > Which is exactly what we already did. In the new invariance scale, the F is applied on p not on the contribution value > > > So now I'm confused. Where did I go wrong? > > > Because by scaling the contribution we get the exact result of doing the > smaller 'running' + 'lost' segments.
On 11 April 2017 at 11:12, Peter Zijlstra <peterz@infradead.org> wrote: > On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > >> > > + } else if (!weight) { >> > > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { >> > >> > But here I'm completely lost. WTF just happened ;-) >> > >> > Firstly, I think we want a comment on why we care about the !weight >> > case. Why isn't !running sufficient? >> >> We track the time when the task is "really" idle but not the time that >> the task spent to wait for running on the CPU. Running is used to >> detect when the task is really running and how much idle time has been >> lost while weight is used to detect when the task is back to sleep >> state and when we have account the lost idle time. > > Huh? You're redefining what 'idle' means wrt. util_sum. > > util used to consider anything !running as idle. So this is the main > trickery? I feel that deserves a comment of exceptional clarity. So we still decay during runnable but !running state but we don't add the lost idle time of the previous running step yet. We wait the task to go back to sleep before applying the lost idle time in order to not apply the decay of the lost idle time in the middle of a run phase that has been preempted by RT task as an example I will try to make a comment that will explain these details
On Tue, Apr 11, 2017 at 11:40:21AM +0200, Vincent Guittot wrote: > Le Tuesday 11 Apr 2017 à 10:53:05 (+0200), Peter Zijlstra a écrit : > > On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > > > Le Monday 10 Apr 2017 à 19:38:02 (+0200), Peter Zijlstra a écrit : > > > > > > > > Thanks for the rebase. > > > > > > > > On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > > > > > > > > Ok, so let me try and paraphrase what this patch does. > > > > > > > > So consider a task that runs 16 out of our 32ms window: > > > > > > > > running idle > > > > |---------|---------| (A) > > > > > > > > > > > > You're saying that when we scale running with the frequency, suppose we > > > > were at 50% freq, we'll end up with: > > > > > > > > run idle > > > > |----|---------| (B) > > > > > > > > > > > > Which is obviously a shorter total then before; so what you do is add > > > > back the lost idle time like: > > > > > > > > run lost idle > > > > |----|----|---------| (C) > > > > > > > > > > > > to arrive at the same total time. Which seems to make sense. > > > > > > Yes > > > > OK, bear with me. > > > > > > So we have: > > > > > > util_sum' = utilsum * y^p + > > > > p-1 > > d1 * y^p + 1024 * \Sum y^n + d3 * y^0 > > n=1 > > > > For the unscaled version, right? > > Yes for the running state. > > For sleeping state, it's just util_sum' = utilsum * y^p Sure, and from this is follows that for idle time we add 0, while we do decay. Lets call this (1). > > > > > > > > Now for the scaled version, instead of adding a full 'd1,d2,d3' running > > segments, we want to add partially running segments, where r=f*d/f_max, > > and lost segments l=d-r to fill out the idle time. > > > > But afaict we then end up with (F=f/f_max): > > > > > > util_sum' = utilsum * y^p + > > > > p-1 > > F * d1 * y^p + F * 1024 * \Sum y^n + F * d3 * y^0 > > n=1 > > you also have a longer running time as it runs slower. We make the assumption that > d1+d2+d3 = (d1'+d2'+d3') * F No, d's stay the same length, r's are the scaled d, and l's the remainder, or lost idle time. That is; r + l = d, that way the time scale stays invariant as above (A) & (C). So if we run slower, we scale back r and l becomes !0. > If we consider that we cross a decay window, we still have the d1 to > complete the past one but then p'*F= p and d'3 will be the remaining > part of the current window and most probably not equal to d3 So by doing r=Fd we get some (lost) idle time for every bit of runtime, equally distributed, as if the CPU inserted NOP cycles to lower the effective frequency. You want to explicitly place the idle time at the end? That would bias the sum downwards. To what point? > so we have with current invariance: > > util_sum' = utilsum * y^(p/F) + > (p/F - 1) > F * d1 * y^(p/F) + F * 1024 * \Sum y^n + F * d'3 * y^0 > n=1 No, we don't have p/F. p is very much _NOT_ scaled. Look at accumulate_sum(), we compute p from d, not r. > > > > And we can collect the common term F: > > > > util_sum' = utilsum * y^p + > > > > p-1 > > F * (d1 * y^p + 1024 * \Sum y^n + d3 * y^0) > > n=1 > > > > > > Which is exactly what we already did. > > In the new invariance scale, the F is applied on p not on the contribution > value That's wrong... That would result in (B) not (C).
Lets go back to the unscaled version:
running idle
|*********|---------|
With the current code, that would effectively end up like (again
assuming 50%):
running idle
|*_*_*_*_*|---------|
Time stays the same, but we add extra idle cycles.
Le Tuesday 11 Apr 2017 à 12:41:36 (+0200), Peter Zijlstra a écrit : > On Tue, Apr 11, 2017 at 11:40:21AM +0200, Vincent Guittot wrote: > > Le Tuesday 11 Apr 2017 à 10:53:05 (+0200), Peter Zijlstra a écrit : > > > On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > > > > Le Monday 10 Apr 2017 à 19:38:02 (+0200), Peter Zijlstra a écrit : > > > > > > > > > > Thanks for the rebase. > > > > > > > > > > On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > > > > > > > > > > Ok, so let me try and paraphrase what this patch does. > > > > > > > > > > So consider a task that runs 16 out of our 32ms window: > > > > > > > > > > running idle > > > > > |---------|---------| > > (A) > > > > > > > > > > > > > > > > You're saying that when we scale running with the frequency, suppose we > > > > > were at 50% freq, we'll end up with: > > > > > > > > > > run idle > > > > > |----|---------| > > (B) > > > > > > > > > > > > > > > > Which is obviously a shorter total then before; so what you do is add > > > > > back the lost idle time like: > > > > > > > > > > run lost idle > > > > > |----|----|---------| > > (C) > > > > > > > > > > > > > > > > to arrive at the same total time. Which seems to make sense. > > > > > > > > Yes > > > > > > OK, bear with me. > > > > > > > > > So we have: > > > > > > > > > util_sum' = utilsum * y^p + > > > > > > p-1 > > > d1 * y^p + 1024 * \Sum y^n + d3 * y^0 > > > n=1 > > > > > > For the unscaled version, right? > > > > Yes for the running state. > > > > For sleeping state, it's just util_sum' = utilsum * y^p > > Sure, and from this is follows that for idle time we add 0, while we do > decay. Lets call this (1). > > > > > > > > > > > > > Now for the scaled version, instead of adding a full 'd1,d2,d3' running > > > segments, we want to add partially running segments, where r=f*d/f_max, > > > and lost segments l=d-r to fill out the idle time. > > > > > > But afaict we then end up with (F=f/f_max): > > > > > > > > > util_sum' = utilsum * y^p + > > > > > > p-1 > > > F * d1 * y^p + F * 1024 * \Sum y^n + F * d3 * y^0 > > > n=1 > > > > you also have a longer running time as it runs slower. We make the assumption that > > d1+d2+d3 = (d1'+d2'+d3') * F > > No, d's stay the same length, r's are the scaled d, and l's the > remainder, or lost idle time. > > That is; r + l = d, that way the time scale stays invariant as above (A) > & (C). > > So if we run slower, we scale back r and l becomes !0. > > > If we consider that we cross a decay window, we still have the d1 to > > complete the past one but then p'*F= p and d'3 will be the remaining > > part of the current window and most probably not equal to d3 > > So by doing r=Fd we get some (lost) idle time for every bit of runtime, > equally distributed, as if the CPU inserted NOP cycles to lower the > effective frequency. > > You want to explicitly place the idle time at the end? That would bias > the sum downwards. To what point? > > > so we have with current invariance: > > > > util_sum' = utilsum * y^(p/F) + > > (p/F - 1) > > F * d1 * y^(p/F) + F * 1024 * \Sum y^n + F * d'3 * y^0 > > n=1 > > No, we don't have p/F. p is very much _NOT_ scaled. ok. so confusion may come from that we don't have the same meaning of p and I have skipped important intermediate formula. I'm going to continue on the new fresh thread > > Look at accumulate_sum(), we compute p from d, not r. > > > > > > > And we can collect the common term F: > > > > > > util_sum' = utilsum * y^p + > > > > > > p-1 > > > F * (d1 * y^p + 1024 * \Sum y^n + d3 * y^0) > > > n=1 > > > > > > > > > Which is exactly what we already did. > > > > In the new invariance scale, the F is applied on p not on the contribution > > value > > That's wrong... That would result in (B) not (C).
Le Tuesday 11 Apr 2017 à 12:49:49 (+0200), Peter Zijlstra a écrit : > > Lets go back to the unscaled version: > > running idle > |*********|---------| > > With the current code, that would effectively end up like (again > assuming 50%): > > running idle > |*_*_*_*_*|---------| > > > Time stays the same, but we add extra idle cycles. In fact it's not really like that because this doesn't reflect the impact of the decay window which is not linear with time For a task that run at max freq (1) |-------|-------|-------|---- **** **** ---****------------****------ The same task running at half frequency, will run twice longer |-------|-------|-------|---- ******** ******** ---********--------********-- With the current implementation, we are not inserting idle cycle but dividing the contribution by half in order to compensate the fact that the task will run twice longer: (2) |-------|-------|-------|---- ---********--------********-- But the final result is neither equal to |-------|-------|-------|---- * * * * * * * * ---*_*_*_*---------*_*_*_*--- nor to (1) as described below: Let assume all durations are aligned with decay window. This will simplify the formula for the explanation and will not change the demonstration. We can come back on the full equation later on. For (1), we have the equation that you write previously: util_sum' = utilsum * y^p + p-1 d1 * y^p + 1024 * \Sum y^n + d3 * y^0 n=1 Which becomes like below when we are aligned to decay window (d1 and d3 are null) (A) util_sum' = utilsum * y^p + p-1 1024 * \Sum y^n n=1 The running time at max frequency is d and p is the number of decay window period In this case p = d/1024us and l = 0 For (2), task runs at half frequency so the duration d' is twice longer than d and p'=2*p. In current implementation, we compensate the increase of running duration (and lost idle time) by dividing the contribution by 2: util_sum' = utilsum * y^p' + p'-1 512 * \Sum y^n n=1 (B) util_sum' = utilsum * y^(2*p) + 2*p-1 512 * \Sum y^n n=1 With the new scale invariance, we have the following pattern before scaling time: |-------|-------|-------|-- ******** ******** ---********--------******** Task still runs at half frequency so the duration d' is twice longer than d and p': p'=2*p just like for (2). But before computing util_sum', we change the temporal referencial to reflect what would have been done at max frequency: we scale the running time (divide it by 2) in order to have something like: |-------|-------|-------|-- **** **** ---****____--------****____ so we now have a duration d'' that is half d'and a number of period p'' that is half p' so p'' = 1/2 * p' == p util_sum' = utilsum * y^p'' + p''-1 1024 * \Sum y^n n=1 util_sum' = utilsum * y^p + p-1 512 * \Sum y^n n=1 Then l = p' - p''. The lost idle time is tracked to apply the same amount of decay window when the task is sleeping so at the end we have a number of decay window of p''+l = p'' so we still have the same amount of decay window than previously. >
On Tue, Apr 11, 2017 at 03:09:20PM +0200, Vincent Guittot wrote: > Le Tuesday 11 Apr 2017 à 12:49:49 (+0200), Peter Zijlstra a écrit : > > > > Lets go back to the unscaled version: > > > > running idle > > |*********|---------| > > > > With the current code, that would effectively end up like (again > > assuming 50%): > > > > running idle > > |*_*_*_*_*|---------| > > > > > > Time stays the same, but we add extra idle cycles. > > In fact it's not really like that because this doesn't reflect the impact of > the decay window which is not linear with time > > For a task that run at max freq > > (1) |-------|-------|-------|---- > **** **** > ---****------------****------ > > The same task running at half frequency, will run twice longer > |-------|-------|-------|---- > ******** ******** > ---********--------********-- > > With the current implementation, we are not inserting idle cycle but > dividing the contribution by half in order to compensate the fact that the task > will run twice longer: > > (2) |-------|-------|-------|---- > > ---********--------********-- > > But the final result is neither equal to > > |-------|-------|-------|---- > * * * * * * * * > ---*_*_*_*---------*_*_*_*--- > > nor to (1) as described below: I'm not sure I get what you say; dividing the contribution in half is exactly equal to the above picture. Because as you can see, there's half the number of * per window. > Let assume all durations are aligned with decay window. This will simplify the > formula for the explanation and will not change the demonstration. We can come back > on the full equation later on. > > For (1), we have the equation that you write previously: > > util_sum' = utilsum * y^p + > p-1 > d1 * y^p + 1024 * \Sum y^n + d3 * y^0 > n=1 > > Which becomes like below when we are aligned to decay window (d1 and d3 are null) > (A) util_sum' = utilsum * y^p + > p-1 > 1024 * \Sum y^n > n=1 > > The running time at max frequency is d and p is the number of decay window period > In this case p = d/1024us and l = 0 > > For (2), task runs at half frequency so the duration d' is twice longer than > d and p'=2*p. In current implementation, we compensate the increase of running > duration (and lost idle time) by dividing the contribution by 2: > util_sum' = utilsum * y^p' + > p'-1 > 512 * \Sum y^n > n=1 > > (B) util_sum' = utilsum * y^(2*p) + > 2*p-1 > 512 * \Sum y^n > n=1 Hmmm.. but 2p is the actual wall-time of the window period. > With the new scale invariance, we have the following pattern before scaling > time: > > |-------|-------|-------|-- > ******** ******** > ---********--------******** > > Task still runs at half frequency so the duration d' is twice longer than > d and p': p'=2*p just like for (2). > But before computing util_sum', we change the temporal referencial to reflect > what would have been done at max frequency: we scale the running time (divide it by 2) > in order to have something like: > > |-------|-------|-------|-- > **** **** > ---****____--------****____ So you're moving the window edges away from wall-time. > so we now have a duration d'' that is half d'and a number of period p'' that > is half p' so p'' = 1/2 * p' == p > util_sum' = utilsum * y^p'' + > p''-1 > 1024 * \Sum y^n > n=1 > util_sum' = utilsum * y^p + > p-1 > 512 * \Sum y^n > n=1 |---------|---------| (wall-time) ----****------------- F=100% ----******----------- F= 66% |--------------|----| (fudge-time) (explicitly not used 50%, because then the second window would have collapsed to 0, imagine the joy if you go lower still) So in fudge-time the first window has 6/15 == 4/10 for the max-freq / wall-time combo. > > Then l = p' - p''. The lost idle time is tracked to apply the same amount of decay > window when the task is sleeping > > so at the end we have a number of decay window of p''+l = p'' so we still have > the same amount of decay window than previously. Now, we have to stretch time back to equal window size, and while you do that for the active windows, we have to do manual compensation for idle windows (which is somewhat ugleh) and is where the lost-time comes from. Also, this all feels entirely yucky, because as per the above, if we'd ran at 33%, we'd have ended up with a negative time window. Not to mention that this only seems to work for low utilization. Once you hit higher utilization scenarios, where there isn't much idle time to compensate for the stretching, things go wobbly. Although both scenarios might end up being the same. And instead of resurrecting 0 sized windows, you throw them out, which results in max-util at low F being reported as max-util at F=1, which I suppose is a useful property and results in the increased ramp-up (which is a desired property). So not only do you have non-linear time, you also have non-continuous time. I still wonder about the whole !running vs !weight thing.. this all needs more thinking.
Le Wednesday 12 Apr 2017 à 13:28:58 (+0200), Peter Zijlstra a écrit : > On Tue, Apr 11, 2017 at 03:09:20PM +0200, Vincent Guittot wrote: > > Le Tuesday 11 Apr 2017 à 12:49:49 (+0200), Peter Zijlstra a écrit : > > > > > > Lets go back to the unscaled version: > > > > > > running idle > > > |*********|---------| > > > > > > With the current code, that would effectively end up like (again > > > assuming 50%): > > > > > > running idle > > > |*_*_*_*_*|---------| > > > > > > > > > Time stays the same, but we add extra idle cycles. > > > > In fact it's not really like that because this doesn't reflect the impact of > > the decay window which is not linear with time > > > > For a task that run at max freq > > > > (1) |-------|-------|-------|---- > > **** **** > > ---****------------****------ > > > > The same task running at half frequency, will run twice longer > > |-------|-------|-------|---- > > ******** ******** > > ---********--------********-- > > > > With the current implementation, we are not inserting idle cycle but > > dividing the contribution by half in order to compensate the fact that the task > > will run twice longer: > > > > (2) |-------|-------|-------|---- > > > > ---********--------********-- > > > > But the final result is neither equal to > > > > |-------|-------|-------|---- > > * * * * * * * * > > ---*_*_*_*---------*_*_*_*--- > > > > nor to (1) as described below: > > I'm not sure I get what you say; dividing the contribution in half is > exactly equal to the above picture. Because as you can see, there's half > the number of * per window. yes you're right, the above is equal to (2) but not to (1) I mess up the _ which some additional decays > > > Let assume all durations are aligned with decay window. This will simplify the > > formula for the explanation and will not change the demonstration. We can come back > > on the full equation later on. > > > > For (1), we have the equation that you write previously: > > > > util_sum' = utilsum * y^p + > > p-1 > > d1 * y^p + 1024 * \Sum y^n + d3 * y^0 > > n=1 > > > > Which becomes like below when we are aligned to decay window (d1 and d3 are null) > > > (A) util_sum' = utilsum * y^p + > > p-1 > > 1024 * \Sum y^n > > n=1 > > > > The running time at max frequency is d and p is the number of decay window period > > In this case p = d/1024us and l = 0 > > > > For (2), task runs at half frequency so the duration d' is twice longer than > > d and p'=2*p. In current implementation, we compensate the increase of running > > duration (and lost idle time) by dividing the contribution by 2: > > > util_sum' = utilsum * y^p' + > > p'-1 > > 512 * \Sum y^n > > n=1 > > > > (B) util_sum' = utilsum * y^(2*p) + > > 2*p-1 > > 512 * \Sum y^n > > n=1 > > Hmmm.. but 2p is the actual wall-time of the window period. > > > With the new scale invariance, we have the following pattern before scaling > > time: > > > > |-------|-------|-------|-- > > ******** ******** > > ---********--------******** > > > > Task still runs at half frequency so the duration d' is twice longer than > > d and p': p'=2*p just like for (2). > > > But before computing util_sum', we change the temporal referencial to reflect > > what would have been done at max frequency: we scale the running time (divide it by 2) > > in order to have something like: > > > > |-------|-------|-------|-- > > **** **** > > ---****____--------****____ > > So you're moving the window edges away from wall-time. > > > so we now have a duration d'' that is half d'and a number of period p'' that > > is half p' so p'' = 1/2 * p' == p > > > util_sum' = utilsum * y^p'' + > > p''-1 > > 1024 * \Sum y^n > > n=1 > > util_sum' = utilsum * y^p + > > p-1 > > 512 * \Sum y^n > > n=1 > > > |---------|---------| (wall-time) > ----****------------- F=100% > ----******----------- F= 66% > |--------------|----| (fudge-time) It has been a bit hard for me to catch the diagram above because you scale the idle time to get same ratio at 100% and 66% wherease I don't scale idle time but only running time. Then, we are not reducing the next window but delaying it so it's something like below |---------|---------| (wall-time) ----****------------- F=100% ----******----------- F= 66% |--------------|---------| (fudge-time) > > (explicitly not used 50%, because then the second window would have > collapsed to 0, imagine the joy if you go lower still) The second window can't collapse because we are working on delta time not absolute wall-time and the delta is for only 1 type at a time: running or idle > > > So in fudge-time the first window has 6/15 == 4/10 for the max-freq / > wall-time combo. > > > > > Then l = p' - p''. The lost idle time is tracked to apply the same amount of decay > > window when the task is sleeping > > > > so at the end we have a number of decay window of p''+l = p'' so we still have > > the same amount of decay window than previously. > > Now, we have to stretch time back to equal window size, and while you do > that for the active windows, we have to do manual compensation for idle > windows (which is somewhat ugleh) and is where the lost-time comes from. We can't stretch idle time because there is no relation between the idle time and the current capacity. > > Also, this all feels entirely yucky, because as per the above, if we'd > ran at 33%, we'd have ended up with a negative time window. Not sure to catch how we can end up with negative window. We are working with delta time not absolute time. > > > Not to mention that this only seems to work for low utilization. Once > you hit higher utilization scenarios, where there isn't much idle time > to compensate for the stretching, things go wobbly. Although both > scenarios might end up being the same. During the running phase, we calculate how much idle time has diseappeared because we are running at lower frequency and we compensate it once back to idle. > > And instead of resurrecting 0 sized windows, you throw them out, which I don't catch point above > results in max-util at low F being reported as max-util at F=1, which I > suppose is a useful property and results in the increased ramp-up (which > is a desired property). > > So not only do you have non-linear time, you also have non-continuous > time. > > I still wonder about the whole !running vs !weight thing.. this all > needs more thinking. >
On Wed, Apr 12, 2017 at 04:50:47PM +0200, Vincent Guittot wrote: > Le Wednesday 12 Apr 2017 à 13:28:58 (+0200), Peter Zijlstra a écrit : > > > > |---------|---------| (wall-time) > > ----****------------- F=100% > > ----******----------- F= 66% > > |--------------|----| (fudge-time) > > It has been a bit hard for me to catch the diagram above because you scale the > idle time to get same ratio at 100% and 66% wherease I don't scale idle > time but only running time. Ah, so below I wrote that we then scale each window back to equal size, so the absolute size in wall-time becomes immaterial. > > (explicitly not used 50%, because then the second window would have > > collapsed to 0, imagine the joy if you go lower still) > > The second window can't collapse because we are working on delta time not > absolute wall-time and the delta is for only 1 type at a time: running or idle Right, but consider what happens when F drops too low, idle goes away from where there would've been some at F=1. At that point things become unrecoverable afaict. > > So in fudge-time the first window has 6/15 == 4/10 for the max-freq / > > wall-time combo. > > > > > > > > Then l = p' - p''. The lost idle time is tracked to apply the same amount of decay > > > window when the task is sleeping > > > > > > so at the end we have a number of decay window of p''+l = p'' so we still have > > > the same amount of decay window than previously. > > > > Now, we have to stretch time back to equal window size, and while you do > > that for the active windows, we have to do manual compensation for idle > > windows (which is somewhat ugleh) and is where the lost-time comes from. > > We can't stretch idle time because there is no relation between the idle time > and the current capacity. Brain melts.. > > Also, this all feels entirely yucky, because as per the above, if we'd > > ran at 33%, we'd have ended up with a negative time window. > > Not sure to catch how we can end up with negative window. We are working with > delta time not absolute time. |---------|---------|---------| F=100% --****------------------------ |--------------|----|---------| F= 66% --******---------------------- |-------------------|---------| F= 50% --********-------------------- |-----------------------------| F= 33% --************---------------- So what happens is that when the (wall) time for a window goes negative it simply moves the next window along, until that too is compressed etc.. So in the above figure, the right most edge of F=33% contains 2 whole periods of idle time, both contracted to measure 0 (wall) time. The only thing you have to recover them from is the lost idle time measure. > > Not to mention that this only seems to work for low utilization. Once > > you hit higher utilization scenarios, where there isn't much idle time > > to compensate for the stretching, things go wobbly. Although both > > scenarios might end up being the same. > > During the running phase, we calculate how much idle time has diseappeared > because we are running at lower frequency and we compensate it once back to > idle. > > > > > And instead of resurrecting 0 sized windows, you throw them out, which > > I don't catch point above It might've been slightly inaccurate. But the point remains that you destroy time. Not all accrued lost idle time is recovered. + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { + /* + * Add the idle time stolen by running at lower compute + * capacity + */ + delta += sa->stolen_idle_time; + } + sa->stolen_idle_time = 0; See here, stolen_idle_time is reset regardless. Time is non-continuous at that point. I still have to draw me more interesting cases, I'm not convinced I fully understand things.
On 12 April 2017 at 17:44, Peter Zijlstra <peterz@infradead.org> wrote: > On Wed, Apr 12, 2017 at 04:50:47PM +0200, Vincent Guittot wrote: >> Le Wednesday 12 Apr 2017 à 13:28:58 (+0200), Peter Zijlstra a écrit : > >> > >> > |---------|---------| (wall-time) >> > ----****------------- F=100% >> > ----******----------- F= 66% >> > |--------------|----| (fudge-time) >> >> It has been a bit hard for me to catch the diagram above because you scale the >> idle time to get same ratio at 100% and 66% wherease I don't scale idle >> time but only running time. > > Ah, so below I wrote that we then scale each window back to equal size, > so the absolute size in wall-time becomes immaterial. > >> > (explicitly not used 50%, because then the second window would have >> > collapsed to 0, imagine the joy if you go lower still) >> >> The second window can't collapse because we are working on delta time not >> absolute wall-time and the delta is for only 1 type at a time: running or idle > > Right, but consider what happens when F drops too low, idle goes away > from where there would've been some at F=1. At that point things become > unrecoverable afaict. Yes I agree that if the frequency is too low to handle the running time in the period, there is no more idle time to recover lost idle time. In this case, either the frequency will be increase by cpufreq and we will finally run fast enough to recover the lost idle time or we stay at this frequency and the task is always running and we can't do anything else than assuming that this is an always running task and at this end (once task util_avg reach max value) discard the lost idle time > >> > So in fudge-time the first window has 6/15 == 4/10 for the max-freq / >> > wall-time combo. >> > >> > > >> > > Then l = p' - p''. The lost idle time is tracked to apply the same amount of decay >> > > window when the task is sleeping >> > > >> > > so at the end we have a number of decay window of p''+l = p'' so we still have >> > > the same amount of decay window than previously. >> > >> > Now, we have to stretch time back to equal window size, and while you do >> > that for the active windows, we have to do manual compensation for idle >> > windows (which is somewhat ugleh) and is where the lost-time comes from. >> >> We can't stretch idle time because there is no relation between the idle time >> and the current capacity. > > Brain melts.. > >> > Also, this all feels entirely yucky, because as per the above, if we'd >> > ran at 33%, we'd have ended up with a negative time window. >> >> Not sure to catch how we can end up with negative window. We are working with >> delta time not absolute time. > > > |---------|---------|---------| F=100% > --****------------------------ > > |--------------|----|---------| F= 66% > --******---------------------- > > |-------------------|---------| F= 50% > --********-------------------- > > |-----------------------------| F= 33% > --************---------------- > > > So what happens is that when the (wall) time for a window goes negative > it simply moves the next window along, until that too is compressed > etc.. > > So in the above figure, the right most edge of F=33% contains 2 whole > periods of idle time, both contracted to measure 0 (wall) time. > > The only thing you have to recover them from is the lost idle time > measure. > >> > Not to mention that this only seems to work for low utilization. Once >> > you hit higher utilization scenarios, where there isn't much idle time >> > to compensate for the stretching, things go wobbly. Although both >> > scenarios might end up being the same. >> >> During the running phase, we calculate how much idle time has diseappeared >> because we are running at lower frequency and we compensate it once back to >> idle. >> >> > >> > And instead of resurrecting 0 sized windows, you throw them out, which >> >> I don't catch point above > > It might've been slightly inaccurate. But the point remains that you > destroy time. Not all accrued lost idle time is recovered. > > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { > + /* > + * Add the idle time stolen by running at lower compute > + * capacity > + */ > + delta += sa->stolen_idle_time; > + } > + sa->stolen_idle_time = 0; > > See here, stolen_idle_time is reset regardless. Time is non-continuous > at that point. In fact, we are provisioning some possible stolen time when running at lower frequency but it can happen that there is no idle time even if the task runs at max frequency. In this case, there is no lost idle time to recover. I consider that a task that have a utilization at max value (minus a threshold) is an always running time and in this case there is no lost idle time to recover > > > I still have to draw me more interesting cases, I'm not convinced I > fully understand things.
On Wed, Apr 12, 2017 at 01:28:58PM +0200, Peter Zijlstra wrote:
> I still wonder about the whole !running vs !weight thing.,
Ah, since we use this for both util _and_ load, we need !running &&
!weight, and it so happens that !weight implies !running. Is that it?
On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > > Secondly, what's up with the util_sum < LOAD_AVG_MAX * 1000 thing? > > The lost idle time makes sense only if the task can also be "idle" > when running at max capacity. When util_sum reaches the > LOAD_AVG_MAX*SCHED_CAPACITY_SCALE value, all tasks are considered to > be the same as we can't make any difference between a task running > 400ms or a task running 400sec. It means that these tasks are "always > running" tasks even at max capacity. In this case, there is no lost > idle time as they always run and tracking and adding back the lost > idle time because we run at lower capacity doesn't make sense anymore > so we discard it. Right, this is the point we reached yesterday with the too low F. At that point you cannot know and we assuming u=1, F<1 -> u=1, F=1, which is a sensible assumption. > Then an always running task can have a util_sum that is less than the > max value because of the rounding (util_avg varies between > [1006..1023]), so I use LOAD_AVG_MAX*1000 instead of LOAD_AVG_MAX*1024 OK, so the reason util_avg varies is because we compute it wrong. And I think we can easily fix that once we pull out all the factors (which would mean your patch and the pulling out of weight patch which still needs to be finished). But you're comparing against util_sum here, that behaves slightly different. I think you want 'util_sum >= 1024 * (LOAD_AVG_MAX - 1024)' instead.
On 13 April 2017 at 15:32, Peter Zijlstra <peterz@infradead.org> wrote: > On Wed, Apr 12, 2017 at 01:28:58PM +0200, Peter Zijlstra wrote: > >> I still wonder about the whole !running vs !weight thing., > > Ah, since we use this for both util _and_ load, we need !running && > !weight, and it so happens that !weight implies !running. Is that it? exactly sorry, I should have started with that >
On 13 April 2017 at 15:39, Peter Zijlstra <peterz@infradead.org> wrote: > On Tue, Apr 11, 2017 at 09:52:21AM +0200, Vincent Guittot wrote: > >> > Secondly, what's up with the util_sum < LOAD_AVG_MAX * 1000 thing? >> >> The lost idle time makes sense only if the task can also be "idle" >> when running at max capacity. When util_sum reaches the >> LOAD_AVG_MAX*SCHED_CAPACITY_SCALE value, all tasks are considered to >> be the same as we can't make any difference between a task running >> 400ms or a task running 400sec. It means that these tasks are "always >> running" tasks even at max capacity. In this case, there is no lost >> idle time as they always run and tracking and adding back the lost >> idle time because we run at lower capacity doesn't make sense anymore >> so we discard it. > > Right, this is the point we reached yesterday with the too low F. At > that point you cannot know and we assuming u=1, F<1 -> u=1, F=1, which > is a sensible assumption. > >> Then an always running task can have a util_sum that is less than the >> max value because of the rounding (util_avg varies between >> [1006..1023]), so I use LOAD_AVG_MAX*1000 instead of LOAD_AVG_MAX*1024 > > OK, so the reason util_avg varies is because we compute it wrong. And I > think we can easily fix that once we pull out all the factors (which > would mean your patch and the pulling out of weight patch which still > needs to be finished). That would be great to remove this unwanted variation. > > But you're comparing against util_sum here, that behaves slightly > different. I think you want 'util_sum >= 1024 * (LOAD_AVG_MAX - 1024)' > instead. yes, the variation happens on the util_sum
On Thu, Apr 13, 2017 at 05:16:20PM +0200, Vincent Guittot wrote: > On 13 April 2017 at 15:39, Peter Zijlstra <peterz@infradead.org> wrote: > > OK, so the reason util_avg varies is because we compute it wrong. And I > > think we can easily fix that once we pull out all the factors (which > > would mean your patch and the pulling out of weight patch which still > > needs to be finished). > > That would be great to remove this unwanted variation. So the problem with the _avg stuff is that we include the d3 segment, that is the unfinished current window. Since we only re-compute the _avg whenever we roll over, the intent already seems to be to only compute it on completed windows. But because 'complicated/expensive', its hard to not include d3 and thus we get the wobble. Once we compute pure running/runnable sums, without extra contrib factors, we can simply subtract our d3 term from sum when doing the division and change the divider to LOAD_AVG_MAX*y, getting the stable _avg over all completed windows. (you could do the same with factors, but then we get to do a bunch of extra multiplications which aren't free). > > > > But you're comparing against util_sum here, that behaves slightly > > different. I think you want 'util_sum >= 1024 * (LOAD_AVG_MAX - 1024)' > > instead. > > yes, the variation happens on the util_sum Well, for util_sum its simple to ignore the current window, which is what the suggested equation does (note that LOAD_AVG_MAX*y == LOAD_AVG_MAX-1024).
On Thu, Apr 13, 2017 at 04:59:15PM +0200, Vincent Guittot wrote: > On 13 April 2017 at 15:32, Peter Zijlstra <peterz@infradead.org> wrote: > > On Wed, Apr 12, 2017 at 01:28:58PM +0200, Peter Zijlstra wrote: > > > >> I still wonder about the whole !running vs !weight thing., > > > > Ah, since we use this for both util _and_ load, we need !running && > > !weight, and it so happens that !weight implies !running. Is that it? > > exactly > sorry, I should have started with that Damn, that just bring me around to wondering why running is the right condition to create lost-time. Because for runnable we want everything that has weight.
On 13 April 2017 at 20:06, Peter Zijlstra <peterz@infradead.org> wrote: > On Thu, Apr 13, 2017 at 04:59:15PM +0200, Vincent Guittot wrote: >> On 13 April 2017 at 15:32, Peter Zijlstra <peterz@infradead.org> wrote: >> > On Wed, Apr 12, 2017 at 01:28:58PM +0200, Peter Zijlstra wrote: >> > >> >> I still wonder about the whole !running vs !weight thing., >> > >> > Ah, since we use this for both util _and_ load, we need !running && >> > !weight, and it so happens that !weight implies !running. Is that it? >> >> exactly >> sorry, I should have started with that > > Damn, that just bring me around to wondering why running is the right > condition to create lost-time. > > Because for runnable we want everything that has weight. I have considered that the waiting time doesn't have to be scaled unlike the running time of the runnable because waiting is the same whatever the current capacity >
On 13 April 2017 at 18:13, Peter Zijlstra <peterz@infradead.org> wrote: > On Thu, Apr 13, 2017 at 05:16:20PM +0200, Vincent Guittot wrote: >> On 13 April 2017 at 15:39, Peter Zijlstra <peterz@infradead.org> wrote: > >> > OK, so the reason util_avg varies is because we compute it wrong. And I >> > think we can easily fix that once we pull out all the factors (which >> > would mean your patch and the pulling out of weight patch which still >> > needs to be finished). >> >> That would be great to remove this unwanted variation. > > So the problem with the _avg stuff is that we include the d3 segment, > that is the unfinished current window. Since we only re-compute the _avg > whenever we roll over, the intent already seems to be to only compute it > on completed windows. yes make sense > > But because 'complicated/expensive', its hard to not include d3 and thus > we get the wobble. > > Once we compute pure running/runnable sums, without extra contrib > factors, we can simply subtract our d3 term from sum when doing the > division and change the divider to LOAD_AVG_MAX*y, getting the stable > _avg over all completed windows. I'm going to make it a try to check that it removes the variation i'm seeing > > (you could do the same with factors, but then we get to do a bunch of > extra multiplications which aren't free). > >> > >> > But you're comparing against util_sum here, that behaves slightly >> > different. I think you want 'util_sum >= 1024 * (LOAD_AVG_MAX - 1024)' >> > instead. >> >> yes, the variation happens on the util_sum > > Well, for util_sum its simple to ignore the current window, which is > what the suggested equation does (note that LOAD_AVG_MAX*y == > LOAD_AVG_MAX-1024).
On 14 April 2017 at 10:49, Vincent Guittot <vincent.guittot@linaro.org> wrote: > On 13 April 2017 at 18:13, Peter Zijlstra <peterz@infradead.org> wrote: >> On Thu, Apr 13, 2017 at 05:16:20PM +0200, Vincent Guittot wrote: >>> On 13 April 2017 at 15:39, Peter Zijlstra <peterz@infradead.org> wrote: >> >>> > OK, so the reason util_avg varies is because we compute it wrong. And I >>> > think we can easily fix that once we pull out all the factors (which >>> > would mean your patch and the pulling out of weight patch which still >>> > needs to be finished). >>> >>> That would be great to remove this unwanted variation. >> >> So the problem with the _avg stuff is that we include the d3 segment, >> that is the unfinished current window. Since we only re-compute the _avg >> whenever we roll over, the intent already seems to be to only compute it >> on completed windows. > > yes make sense > >> >> But because 'complicated/expensive', its hard to not include d3 and thus >> we get the wobble. >> >> Once we compute pure running/runnable sums, without extra contrib >> factors, we can simply subtract our d3 term from sum when doing the >> division and change the divider to LOAD_AVG_MAX*y, getting the stable >> _avg over all completed windows. > > I'm going to make it a try to check that it removes the variation i'm seeing I have sent a patchset based on your proposal that fix this variation issue > >> >> (you could do the same with factors, but then we get to do a bunch of >> extra multiplications which aren't free). >> >>> > >>> > But you're comparing against util_sum here, that behaves slightly >>> > different. I think you want 'util_sum >= 1024 * (LOAD_AVG_MAX - 1024)' >>> > instead. >>> >>> yes, the variation happens on the util_sum >> >> Well, for util_sum its simple to ignore the current window, which is >> what the suggested equation does (note that LOAD_AVG_MAX*y == >> LOAD_AVG_MAX-1024).
Hi Vincent, Sorry for crashing the party this late. As you know, it takes a long period of uninterrupted review time to properly review PELT stuff. Disclaimer: I haven't read the rest of the thread yet. On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > The current implementation of load tracking invariance scales the > contribution with current frequency and uarch performance (only for > utilization) of the CPU. One main result of this formula is that the > figures are capped by current capacity of CPU. Another one is that the > load_avg is not invariant because not scaled with uarch. > > The util_avg of a periodic task that runs r time slots every p time slots > varies in the range : > > U * (1-y^r)/(1-y^p) * y^i < Utilization < U * (1-y^r)/(1-y^p) > > with U is the max util_avg value = SCHED_CAPACITY_SCALE > > At a lower capacity, the range becomes: > > U * C * (1-y^r')/(1-y^p) * y^i' < Utilization < U * C * (1-y^r')/(1-y^p) > > with C reflecting the compute capacity ratio between current capacity and > max capacity. > > so C tries to compensate changes in (1-y^r') but it can't be accurate. I would say that C is trying to compensate for difference in running time, which is difference between r and r'. But I think that is what you are saying as well. > Instead of scaling the contribution value of PELT algo, we should scale the > running time. The PELT signal aims to track the amount of computation of > tasks and/or rq so it seems more correct to scale the running time to > reflect the effective amount of computation done since the last update. > > In order to be fully invariant, we need to apply the same amount of > running time and idle time whatever the current capacity. Because running > at lower capacity implies that the task will run longer, we have to track > the amount of "stolen" idle time and to apply it when task becomes idle. Overall, I agree that scaling time according to compute capacity is the right thing to do, if we want accurate scale-invariance. The current implementation is an approximation which isn't perfect, but it is easy to implement. One thing that became clear to me after reading the patch and tried to recreate what it does, is that you don't seem to consider waiting time and the patch doesn't scale it. That is fine for utilization, but it breaks load. For load, you have to scale waiting time as well, which makes things rather complicated as you would need two scaled time deltas, one for utilization and one for load. What currently happens is that waiting tasks as low OPPs are accumulating load at the rate of the highest OPP without accumulating "stolen" time. So waiting tasks accumulate too much load at lower OPPs. We have confirmed it by scheduling two periodic tasks on the same cpu and verified that the load does ramp up faster than it should. For the aggregate cfs_rq util/load sums, I can't convince myself whether they break when "stolen" time isn't inserted at the same time in the task signal as it is for the cfs_rq signal. If you have two periodic tasks scheduled on the same cpu with aligned periods, then the first task will inject its stolen time as soon as it finishes, while the aggregate sum won't inject the stolen time until it has completed the second task and inject the stolen for both tasks at the same time. As long as no tasks are migrated to/from the cpu it should work, but I'm not convinced that it works if tasks are migrated or new tasks show up before the stolen time has been committed to the aggregate sum. Have you looked more into this? Another question is what happens to blocked utilization? IIUC, the stolen time is injected when the task wakes up again so the utilization drops to where it should be. Does that mean that the blocked contribution of the task is inflated the entire time while it is blocked? > But once we have reached the maximum utilization value (SCHED_CAPACITY_SCALE), > it means that the task is seen as an always-running task whatever the > capacity of the cpu (even at max compute capacity). In this case, we can > discard the "stolen" idle times which becomes meaningless. In order to > cope with rounding effect of PELT algo we take a margin and consider task > with utilization greater than 1000 (vs 1024 max) as an always-running task. I understand why the threshold is necessary, but I'm slightly concerned that it might introduce corner cases where things could go very wrong. I haven't proven that it is indeed a problem, but is it possible to have aggregate sum of utilization >1000 without the cpu being fully utilized? So the tasks will have their stolen time injected, but the cfs_rq utilization won't? > > Then, we can use the same algorithm for both utilization and load and > simplify __update_load_avg now that the load of a task doesn't have to be > capped by CPU uarch. As said above, waiting time has to be handled differently for utilization and load. > The responsivness of PELT is improved when CPU is not running at max > capacity with this new algorithm. I have put below some examples of > duration to reach some typical load values according to the capacity of the > CPU with current implementation and with this patch. > > Util (%) max capacity half capacity(mainline) half capacity(w/ patch) > 972 (95%) 138ms not reachable 276ms > 486 (47.5%) 30ms 138ms 60ms > 256 (25%) 13ms 32ms 26ms > > On my hikey (octo ARM platform) with schedutil governor, the time to reach > max OPP when starting from a null utilization, decreases from 223ms with > current scale invariance down to 121ms with the new algorithm. For this > test, i have enable arch_scale_freq for arm64. Note that the time to reach a specific utilization with your implementation depends on the OPP. The lower the OPP, the slower utilization accumulates. [...] > @@ -2852,19 +2850,54 @@ accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, > } > sa->period_contrib = delta; > > - contrib = cap_scale(contrib, scale_freq); > if (weight) { > sa->load_sum += weight * contrib; > if (cfs_rq) > cfs_rq->runnable_load_sum += weight * contrib; > } > if (running) > - sa->util_sum += contrib * scale_cpu; > + sa->util_sum += contrib << SCHED_CAPACITY_SHIFT; > > return periods; > } > > /* > + * Scale the time to reflect the effective amount of computation done during > + * this delta time. > + */ > +static __always_inline u64 > +scale_time(u64 delta, int cpu, struct sched_avg *sa, > + unsigned long weight, int running) > +{ > + if (running) { > + sa->stolen_idle_time += delta; > + /* > + * scale the elapsed time to reflect the real amount of > + * computation > + */ > + delta = cap_scale(delta, arch_scale_freq_capacity(NULL, cpu)); > + delta = cap_scale(delta, arch_scale_cpu_capacity(NULL, cpu)); > + > + /* > + * Track the amount of stolen idle time due to running at > + * lower capacity > + */ > + sa->stolen_idle_time -= delta; > + } else if (!weight) { > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { > + /* > + * Add the idle time stolen by running at lower compute > + * capacity > + */ > + delta += sa->stolen_idle_time; > + } > + sa->stolen_idle_time = 0; > + } > + > + return delta; As mentioned above, waiting time, i.e. !running && weight, is not scaled, which causes trouble for load. Morten
On 28/04/17 16:52, Morten Rasmussen wrote: > Hi Vincent, [...] > As mentioned above, waiting time, i.e. !running && weight, is not > scaled, which causes trouble for load. I ran some rt-app-based tests on a system with frequency and cpu invariance. (1) Two periodic 20% tasks with 12ms period on a cpu (capacity=1024) at 625Mhz (max 1100Mhz) starting to run at the same time, so one task (task1) is wakeup preempted. (I'm only considering the phase of the test run where this is a stable condition, i.e. task1 is always wakeup preempted by task2). So the runtime of a task is 0.2*12ms*1100/625 = 4.2ms. At the beginning of the preemption period, __update_load_avg_se(task1) is called with running=0 and weight=0, at the end with running=0 and weight=1024. When task1 finally runs there are two calls with (running=1, weight=1024) before the next wakeup preemption period for task1 starts again with (running=0, weight=0). Task task2 which doesn't suffer from wakeup preemption starts running with (running=0, weight=0), then there are 2 calls with (running=1, weight=1024) before it starts running again with (running=0, weight=0). Task1 is runnable for 8.4ms and sleeps for 3.6ms whereas task is runnable for 4.2ms and sleeps for 7.8ms. The load signal of task1 is ~600 whereas the the load of task2 is ~200. (2) Two periodic 20% tasks with 12ms period on a cpu (capacity=1024) at 1100Mhz (max 1100Mhz) starting to run at the same time, so one task (task1) is wakeup preempted. So the runtime of one task is 0.2*12ms*1100/1100 = 2.4ms. Task1 is runnable for 4.8ms and sleeps for 7.2ms whereas task is runnable for 2.4ms and sleeps for 9.6ms. The load signal of task1 is ~400 whereas the the load of task2 is ~200. Like Morten said, the scaling for load works differently on different OPP's. Scaling for utilization looks fine. IMHO, the implementation of your scale_time() function can't take preemption into consideration. I also did tests comparing the time_scaling implementation with tip (contribution scaling) (two periodic tasks 20%/16ms at 625Mhz/1100Mhz and 20%/32ms at 625Mhz/1100Mhz) showing this as a difference between time_scaling and tip. -- Dietmar [...]
On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > +++ b/include/linux/sched.h > @@ -313,6 +313,7 @@ struct load_weight { > */ > struct sched_avg { > u64 last_update_time; > + u64 stolen_idle_time; > u64 load_sum; > u32 util_sum; > u32 period_contrib; > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { > + /* > + * Add the idle time stolen by running at lower compute > + * capacity > + */ > + delta += sa->stolen_idle_time; > + } > + sa->stolen_idle_time = 0; So I was wondering if stolen_idle_time really needs to be a u64. Afaict we'll be at LOAD_AVG_MAX after LOAD_AVG_MAX_N periods, or LOAD_AVG_MAX_N * LOAD_AVG_PERIOD time, which ends up being 11040. After that you'll truncate it anyway.. so there shouldn't be a need to be much larger than that, no?
On Sat, Apr 29, 2017 at 12:09:24AM +0200, Peter Zijlstra wrote: > On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > > +++ b/include/linux/sched.h > > @@ -313,6 +313,7 @@ struct load_weight { > > */ > > struct sched_avg { > > u64 last_update_time; > > + u64 stolen_idle_time; > > u64 load_sum; > > u32 util_sum; > > u32 period_contrib; > > > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { > > + /* > > + * Add the idle time stolen by running at lower compute > > + * capacity > > + */ > > + delta += sa->stolen_idle_time; > > + } > > + sa->stolen_idle_time = 0; > > > So I was wondering if stolen_idle_time really needs to be a u64. Afaict > we'll be at LOAD_AVG_MAX after LOAD_AVG_MAX_N periods, or LOAD_AVG_MAX_N > * LOAD_AVG_PERIOD time, which ends up being 11040. * 1024 or course, but still easily fits in u32.
On 1 May 2017 at 11:00, Peter Zijlstra <peterz@infradead.org> wrote: > On Sat, Apr 29, 2017 at 12:09:24AM +0200, Peter Zijlstra wrote: >> On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: >> > +++ b/include/linux/sched.h >> > @@ -313,6 +313,7 @@ struct load_weight { >> > */ >> > struct sched_avg { >> > u64 last_update_time; >> > + u64 stolen_idle_time; >> > u64 load_sum; >> > u32 util_sum; >> > u32 period_contrib; >> >> > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { >> > + /* >> > + * Add the idle time stolen by running at lower compute >> > + * capacity >> > + */ >> > + delta += sa->stolen_idle_time; >> > + } >> > + sa->stolen_idle_time = 0; >> >> >> So I was wondering if stolen_idle_time really needs to be a u64. Afaict >> we'll be at LOAD_AVG_MAX after LOAD_AVG_MAX_N periods, or LOAD_AVG_MAX_N >> * LOAD_AVG_PERIOD time, which ends up being 11040. > > * 1024 or course, but still easily fits in u32. Correct >
Le Friday 28 Apr 2017 à 16:52:59 (+0100), Morten Rasmussen a écrit : > Hi Vincent, > > Sorry for crashing the party this late. As you know, it takes a long > period of uninterrupted review time to properly review PELT stuff. > > Disclaimer: I haven't read the rest of the thread yet. > > On Mon, Apr 10, 2017 at 11:18:29AM +0200, Vincent Guittot wrote: > > The current implementation of load tracking invariance scales the > > contribution with current frequency and uarch performance (only for > > utilization) of the CPU. One main result of this formula is that the > > figures are capped by current capacity of CPU. Another one is that the > > load_avg is not invariant because not scaled with uarch. > > > > The util_avg of a periodic task that runs r time slots every p time slots > > varies in the range : > > > > U * (1-y^r)/(1-y^p) * y^i < Utilization < U * (1-y^r)/(1-y^p) > > > > with U is the max util_avg value = SCHED_CAPACITY_SCALE > > > > At a lower capacity, the range becomes: > > > > U * C * (1-y^r')/(1-y^p) * y^i' < Utilization < U * C * (1-y^r')/(1-y^p) > > > > with C reflecting the compute capacity ratio between current capacity and > > max capacity. > > > > so C tries to compensate changes in (1-y^r') but it can't be accurate. > > I would say that C is trying to compensate for difference in running > time, which is difference between r and r'. But I think that is what you > are saying as well. > > > Instead of scaling the contribution value of PELT algo, we should scale the > > running time. The PELT signal aims to track the amount of computation of > > tasks and/or rq so it seems more correct to scale the running time to > > reflect the effective amount of computation done since the last update. > > > > In order to be fully invariant, we need to apply the same amount of > > running time and idle time whatever the current capacity. Because running > > at lower capacity implies that the task will run longer, we have to track > > the amount of "stolen" idle time and to apply it when task becomes idle. > > Overall, I agree that scaling time according to compute capacity is the > right thing to do, if we want accurate scale-invariance. The current > implementation is an approximation which isn't perfect, but it is easy > to implement. > > One thing that became clear to me after reading the patch and tried to > recreate what it does, is that you don't seem to consider waiting time > and the patch doesn't scale it. That is fine for utilization, but it > breaks load. For load, you have to scale waiting time as well, which > makes things rather complicated as you would need two scaled time > deltas, one for utilization and one for load. > In fact I have always considered that we don't need to scale !running time (runnable and sleep time) because waiting is the same whatever the frequency or the micro arch. Nevertheless, i agree that running longer at lower capacity increases the number of time a task can be preempted by another another thus increasing the runnable time. The solution would be to scale both running and runnable and to add stolen time once idle. This seems to be also more accurate in the case of utilization when the running task is preempted by another task. In fact, it's something that Peter raised in former comments but i didn't saw the benefit of scaling runnable at that time... I was probably too much focused on utilization This behavior is not really noticeable with the short running time use case of dietmar's example but it becomes relevant when tasks need more time and are preempted more often by others. With the addons below of top of the patch, the load_avg issue raised by dietmar's example is fixed and the utilization remains ok --- kernel/sched/fair.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) -- > > What currently happens is that waiting tasks as low OPPs are > accumulating load at the rate of the highest OPP without accumulating > "stolen" time. So waiting tasks accumulate too much load at lower OPPs. > We have confirmed it by scheduling two periodic tasks on the same cpu > and verified that the load does ramp up faster than it should. > > For the aggregate cfs_rq util/load sums, I can't convince myself whether > they break when "stolen" time isn't inserted at the same time in the > task signal as it is for the cfs_rq signal. If you have two periodic > tasks scheduled on the same cpu with aligned periods, then the first > task will inject its stolen time as soon as it finishes, while thei In fact, I think that the 1st task will wait for its next update before adding lost idle time but that doesn't change the point > aggregate sum won't inject the stolen time until it has completed the > second task and inject the stolen for both tasks at the same time. As > long as no tasks are migrated to/from the cpu it should work, but I'm not > convinced that it works if tasks are migrated or new tasks show up > before the stolen time has been committed to the aggregate sum. Have you > looked more into this? > > task and cfs_rq are synced before any change of the state of task attach/detach or enqueue/dequeue so i don't expect any out of sync > > Another question is what happens to blocked utilization? IIUC, the > stolen time is injected when the task wakes up again so the utilization > drops to where it should be. Does that mean that the blocked > contribution of the task is inflated the entire time while it is > blocked? > only at the task level but its contribution to the cfs_rq will be updated. This is exactly what already happen, we update task metrics only when it wakes up > > > But once we have reached the maximum utilization value (SCHED_CAPACITY_SCALE), > > it means that the task is seen as an always-running task whatever the > > capacity of the cpu (even at max compute capacity). In this case, we can > > discard the "stolen" idle times which becomes meaningless. In order to > > cope with rounding effect of PELT algo we take a margin and consider task > > with utilization greater than 1000 (vs 1024 max) as an always-running task. > > I understand why the threshold is necessary, but I'm slightly concerned > that it might introduce corner cases where things could go very wrong. I > haven't proven that it is indeed a problem, but is it possible to have > aggregate sum of utilization >1000 without the cpu being fully utilized? > So the tasks will have their stolen time injected, but the cfs_rq > utilization won't? > > > > > Then, we can use the same algorithm for both utilization and load and > > simplify __update_load_avg now that the load of a task doesn't have to be > > capped by CPU uarch. > > As said above, waiting time has to be handled differently for > utilization and load. > > > The responsivness of PELT is improved when CPU is not running at max > > capacity with this new algorithm. I have put below some examples of > > duration to reach some typical load values according to the capacity of the > > CPU with current implementation and with this patch. > > > > Util (%) max capacity half capacity(mainline) half capacity(w/ patch) > > 972 (95%) 138ms not reachable 276ms > > 486 (47.5%) 30ms 138ms 60ms > > 256 (25%) 13ms 32ms 26ms > > > > On my hikey (octo ARM platform) with schedutil governor, the time to reach > > max OPP when starting from a null utilization, decreases from 223ms with > > current scale invariance down to 121ms with the new algorithm. For this > > test, i have enable arch_scale_freq for arm64. > > Note that the time to reach a specific utilization with your > implementation depends on the OPP. The lower the OPP, the slower > utilization accumulates. yes like the current implementation. Everything is based on : lower OPP means proportionally longer running time. Thanks > > [...] > > > @@ -2852,19 +2850,54 @@ accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, > > } > > sa->period_contrib = delta; > > > > - contrib = cap_scale(contrib, scale_freq); > > if (weight) { > > sa->load_sum += weight * contrib; > > if (cfs_rq) > > cfs_rq->runnable_load_sum += weight * contrib; > > } > > if (running) > > - sa->util_sum += contrib * scale_cpu; > > + sa->util_sum += contrib << SCHED_CAPACITY_SHIFT; > > > > return periods; > > } > > > > /* > > + * Scale the time to reflect the effective amount of computation done during > > + * this delta time. > > + */ > > +static __always_inline u64 > > +scale_time(u64 delta, int cpu, struct sched_avg *sa, > > + unsigned long weight, int running) > > +{ > > + if (running) { > > + sa->stolen_idle_time += delta; > > + /* > > + * scale the elapsed time to reflect the real amount of > > + * computation > > + */ > > + delta = cap_scale(delta, arch_scale_freq_capacity(NULL, cpu)); > > + delta = cap_scale(delta, arch_scale_cpu_capacity(NULL, cpu)); > > + > > + /* > > + * Track the amount of stolen idle time due to running at > > + * lower capacity > > + */ > > + sa->stolen_idle_time -= delta; > > + } else if (!weight) { > > + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { > > + /* > > + * Add the idle time stolen by running at lower compute > > + * capacity > > + */ > > + delta += sa->stolen_idle_time; > > + } > > + sa->stolen_idle_time = 0; > > + } > > + > > + return delta; > > As mentioned above, waiting time, i.e. !running && weight, is not > scaled, which causes trouble for load. > > Mortendiff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 8b036f1..3e647b9 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2854,12 +2854,15 @@ static __always_inline u64 scale_time(u64 delta, int cpu, struct sched_avg *sa, unsigned long weight, int running) { - if (running) { + if (weight) { /* - * When an entity runs at a lower compute capacity, it will - * need more time to do the same amount of work than at max - * capacity. In order to be invariant, we scale the delta to - * reflect how much work has been really done. + * When an entity is runnable at a lower compute capacity, + * it will need more time to do the same amount of work than + * at max capacity: either because it takes more time to + * compute the same amount of work or because taking more time + * means sharing more often the CPU with others. + * In order to be invariant, we scale the delta to reflect how + * much work has been really done. * Running at lower capacity also means running longer to do * the same amount of work and this results in stealing some * idle time that will disturbed the load signal compared to @@ -2883,7 +2886,7 @@ scale_time(u64 delta, int cpu, struct sched_avg *sa, * lower capacity */ sa->stolen_idle_time -= delta; - } else if (!weight) { + } else { /* * Entity is sleeping so both utilization and load will decay * and we can safely add the stolen time. Reflecting some
diff --git a/include/linux/sched.h b/include/linux/sched.h index d67eee8..ca9d00f 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -313,6 +313,7 @@ struct load_weight { */ struct sched_avg { u64 last_update_time; + u64 stolen_idle_time; u64 load_sum; u32 util_sum; u32 period_contrib; diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 1e5f580..b6f4253 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -734,6 +734,7 @@ void init_entity_runnable_average(struct sched_entity *se) struct sched_avg *sa = &se->avg; sa->last_update_time = 0; + sa->stolen_idle_time = 0; /* * sched_avg's period_contrib should be strictly less then 1024, so * we give it 1023 to make sure it is almost a period (1024us), and @@ -2819,15 +2820,12 @@ static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3) * n=1 */ static __always_inline u32 -accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, +accumulate_sum(u64 delta, struct sched_avg *sa, unsigned long weight, int running, struct cfs_rq *cfs_rq) { - unsigned long scale_freq, scale_cpu; u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */ u64 periods; - scale_freq = arch_scale_freq_capacity(NULL, cpu); - scale_cpu = arch_scale_cpu_capacity(NULL, cpu); delta += sa->period_contrib; periods = delta / 1024; /* A period is 1024us (~1ms) */ @@ -2852,19 +2850,54 @@ accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, } sa->period_contrib = delta; - contrib = cap_scale(contrib, scale_freq); if (weight) { sa->load_sum += weight * contrib; if (cfs_rq) cfs_rq->runnable_load_sum += weight * contrib; } if (running) - sa->util_sum += contrib * scale_cpu; + sa->util_sum += contrib << SCHED_CAPACITY_SHIFT; return periods; } /* + * Scale the time to reflect the effective amount of computation done during + * this delta time. + */ +static __always_inline u64 +scale_time(u64 delta, int cpu, struct sched_avg *sa, + unsigned long weight, int running) +{ + if (running) { + sa->stolen_idle_time += delta; + /* + * scale the elapsed time to reflect the real amount of + * computation + */ + delta = cap_scale(delta, arch_scale_freq_capacity(NULL, cpu)); + delta = cap_scale(delta, arch_scale_cpu_capacity(NULL, cpu)); + + /* + * Track the amount of stolen idle time due to running at + * lower capacity + */ + sa->stolen_idle_time -= delta; + } else if (!weight) { + if (sa->util_sum < (LOAD_AVG_MAX * 1000)) { + /* + * Add the idle time stolen by running at lower compute + * capacity + */ + delta += sa->stolen_idle_time; + } + sa->stolen_idle_time = 0; + } + + return delta; +} + +/* * We can represent the historical contribution to runnable average as the * coefficients of a geometric series. To do this we sub-divide our runnable * history into segments of approximately 1ms (1024us); label the segment that @@ -2918,13 +2951,19 @@ ___update_load_avg(u64 now, int cpu, struct sched_avg *sa, sa->last_update_time = now; /* + * Scale time to reflect the amount a computation effectively done + * during the time slot at current capacity + */ + delta = scale_time(delta, cpu, sa, weight, running); + + /* * Now we know we crossed measurement unit boundaries. The *_avg * accrues by two steps: * * Step 1: accumulate *_sum since last_update_time. If we haven't * crossed period boundaries, finish. */ - if (!accumulate_sum(delta, cpu, sa, weight, running, cfs_rq)) + if (!accumulate_sum(delta, sa, weight, running, cfs_rq)) return 0; /*
The current implementation of load tracking invariance scales the contribution with current frequency and uarch performance (only for utilization) of the CPU. One main result of this formula is that the figures are capped by current capacity of CPU. Another one is that the load_avg is not invariant because not scaled with uarch. The util_avg of a periodic task that runs r time slots every p time slots varies in the range : U * (1-y^r)/(1-y^p) * y^i < Utilization < U * (1-y^r)/(1-y^p) with U is the max util_avg value = SCHED_CAPACITY_SCALE At a lower capacity, the range becomes: U * C * (1-y^r')/(1-y^p) * y^i' < Utilization < U * C * (1-y^r')/(1-y^p) with C reflecting the compute capacity ratio between current capacity and max capacity. so C tries to compensate changes in (1-y^r') but it can't be accurate. Instead of scaling the contribution value of PELT algo, we should scale the running time. The PELT signal aims to track the amount of computation of tasks and/or rq so it seems more correct to scale the running time to reflect the effective amount of computation done since the last update. In order to be fully invariant, we need to apply the same amount of running time and idle time whatever the current capacity. Because running at lower capacity implies that the task will run longer, we have to track the amount of "stolen" idle time and to apply it when task becomes idle. But once we have reached the maximum utilization value (SCHED_CAPACITY_SCALE), it means that the task is seen as an always-running task whatever the capacity of the cpu (even at max compute capacity). In this case, we can discard the "stolen" idle times which becomes meaningless. In order to cope with rounding effect of PELT algo we take a margin and consider task with utilization greater than 1000 (vs 1024 max) as an always-running task. Then, we can use the same algorithm for both utilization and load and simplify __update_load_avg now that the load of a task doesn't have to be capped by CPU uarch. The responsivness of PELT is improved when CPU is not running at max capacity with this new algorithm. I have put below some examples of duration to reach some typical load values according to the capacity of the CPU with current implementation and with this patch. Util (%) max capacity half capacity(mainline) half capacity(w/ patch) 972 (95%) 138ms not reachable 276ms 486 (47.5%) 30ms 138ms 60ms 256 (25%) 13ms 32ms 26ms On my hikey (octo ARM platform) with schedutil governor, the time to reach max OPP when starting from a null utilization, decreases from 223ms with current scale invariance down to 121ms with the new algorithm. For this test, i have enable arch_scale_freq for arm64. Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org> --- Update since v1: - rebase on latest tip/sched/core which includes "Optimize __update_sched_avg()" + patch : https://lkml.org/lkml/2017/3/31/308 include/linux/sched.h | 1 + kernel/sched/fair.c | 53 ++++++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 47 insertions(+), 7 deletions(-) -- 2.7.4