Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1351267 > unrolled thread

Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data "Rafael J. Wysocki" <rjw@rjwysocki.net> - 2016-03-07 03:40 +0100
    Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Peter Zijlstra <peterz@infradead.org> - 2016-03-08 12:30 +0100
      Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data "Rafael J. Wysocki" <rafael@kernel.org> - 2016-03-08 19:10 +0100
        Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Peter Zijlstra <peterz@infradead.org> - 2016-03-08 20:30 +0100
          Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data "Rafael J. Wysocki" <rafael@kernel.org> - 2016-03-08 21:10 +0100
            Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Juri Lelli <juri.lelli@arm.com> - 2016-03-09 11:20 +0100
              Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data "Rafael J. Wysocki" <rafael@kernel.org> - 2016-03-10 00:50 +0100
                Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Juri Lelli <juri.lelli@arm.com> - 2016-03-10 05:40 +0100
                  Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data "Rafael J. Wysocki" <rjw@rjwysocki.net> - 2016-03-10 22:10 +0100
                Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Michael Turquette <mturquette@baylibre.com> - 2016-03-11 00:30 +0100
            Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Peter Zijlstra <peterz@infradead.org> - 2016-03-09 17:40 +0100
              Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data "Rafael J. Wysocki" <rafael@kernel.org> - 2016-03-10 00:30 +0100
                Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Vincent Guittot <vincent.guittot@linaro.org> - 2016-03-10 04:50 +0100
                  Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Peter Zijlstra <peterz@infradead.org> - 2016-03-10 11:10 +0100
                    Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Vincent Guittot <vincent.guittot@linaro.org> - 2016-03-10 11:30 +0100
                    Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Peter Zijlstra <peterz@infradead.org> - 2016-03-10 11:40 +0100
                      Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Peter Zijlstra <peterz@infradead.org> - 2016-03-10 12:00 +0100
                        Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data "Rafael J. Wysocki" <rjw@rjwysocki.net> - 2016-03-10 23:30 +0100
                Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler  utilization data Peter Zijlstra <peterz@infradead.org> - 2016-03-10 09:50 +0100

#1351267 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Thursday, March 03, 2016 01:37:59 PM Steve Muckle wrote:
> On 03/03/2016 12:20 PM, Rafael J. Wysocki wrote:
> >> Here is a comparison, with frequency invariance, of ondemand and
> >> interactive with schedfreq and schedutil. The first two columns (run and
> >> period) are omitted so the table will fit.
> >>
> >>         ondemand        interactive     schedfreq       schedutil
> >> busy %  OR      OH      OR      OH      OR      OH      OR      OH
> >> 1.00%   0       68.96%  0       100.04% 0       78.49%  0       95.86%
> >> 1.00%   0       25.04%  0       22.59%  0       72.56%  0       71.61%
> >> 10.00%  0       21.75%  0       63.08%  0       52.40%  0       41.78%
> >> 10.00%  0       12.17%  0       14.41%  0       17.33%  0       47.96%
> >> 10.00%  0       2.57%   0       2.17%   0       0.29%   0       26.03%
> >> 18.18%  0       12.39%  0       9.39%   0       17.34%  0       31.61%
> >> 19.82%  0       3.74%   0       3.42%   0       12.26%  0       29.46%
> >> 40.00%  2       6.26%   1       12.23%  0       6.15%   0       12.93%
> >> 40.00%  0       0.47%   0       0.05%   0       2.68%   2       14.08%
> >> 40.00%  0       0.60%   0       0.50%   0       1.22%   0       11.58%
> >> 55.56%  2       4.25%   5       5.97%   0       2.51%   0       7.70%
> >> 55.56%  0       1.89%   0       0.04%   0       1.71%   6       8.06%
> >> 55.56%  0       0.50%   0       0.47%   0       1.82%   5       6.94%
> >> 75.00%  2       1.65%   1       0.46%   0       0.26%   56      3.59%
> >> 75.00%  0       1.68%   0       0.05%   0       0.49%   21      3.94%
> >> 75.00%  0       0.28%   0       0.23%   0       0.62%   4       4.41%
> >>
> >> Aside from the 2nd and 3rd tests schedutil is showing decreased
> >> performance across the board. The fifth test is particularly bad.
> > 
> > I guess you mean performance in terms of the overhead?
> 
> Correct. This overhead metric describes how fast the workload completes,
> with 0% equaling the perf governor and 100% equaling the powersave
> governor. So it's a reflection of general performance using the
> governor. It's called "overhead" I imagine (the metric predates my
> involvement) as it is something introduced/caused by the policy of the
> governor.

If my understanding of the requency invariant utilization idea is correct,
it is about re-scaling utilization so it is always relative to the capacity
at the max frequency.  If that's the case, then instead of using x = util_raw / max
we will use something like y = (util_raw / max) * (f / max_freq) (f - current
frequency).  This means that

(1) x = y * max_freq / f

Now, say we have an agreed-on (linear) formula for f depending on x:

f = a * x + b

and if you say "Look, if I substitute y for x in this formula, it doesn't
produce correct results", then I can only say "It doesn't, because it can't".

It *obviously* won't work, because instead of substituting y for x, you
need to substitute the right-hand side of (1) for it.  They you'll get

f = a * y * max_freq / f + b

which is obviously nonlinear, so there's no hope that the same formula
will ever work for both "raw" and "frequency invariant" utilization.

To me this means that looking for a formula that will work for both is
just pointless and there are 3 possibilities:

(a) Look for a good enough formula to apply to "raw" utilization and then
    switch over when all architectures start to use "frequency invariant"
    utilization.
(b) Make all architecuters use "frequency invariant" and then look for a
    working formula (seems rather less than realistic to me to be honest).
(c) Code for using either "raw" or "frequency invariant" depending on
    a callback flag or something like that.

I, personally, would go for (a) at this point, because that's the easiest
one, but (c) would be doable too IMO, so I don't care that much as long
as it is not (b).

Thanks,
Rafael

[toc] | [next] | [standalone]

#1352905 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Mon, Mar 07, 2016 at 03:41:15AM +0100, Rafael J. Wysocki wrote:

> If my understanding of the requency invariant utilization idea is correct,
> it is about re-scaling utilization so it is always relative to the capacity
> at the max frequency.

Right. So if a workload runs for 5ms at @1GHz and 10ms @500MHz, it would
still result in the exact same utilization.

> If that's the case, then instead of using
>   x = util_raw / max
> we will use something like
>   y = (util_raw / max) * (f / max_freq) (f - current frequency).

I don't get the last term. Assuming fixed frequency hardware (we can't
really assume anything else) I get to:

  util = util_raw * (current_freq / max_freq)		(1)
  x = util / max					(2)

> so there's no hope that the same formula will ever work for both "raw"
> and "frequency invariant" utilization.

Here I agree, however the above (current_freq / max_freq) term is easily
computable, and really the only thing we can assume if the arch doesn't
implement freq invariant accounting.

> (c) Code for using either "raw" or "frequency invariant" depending on
>     a callback flag or something like that.

Seeing how frequency invariance is an arch feature, and cpufreq drivers
are also typically arch specific, do we really need a flag at this
level?

In any case, I think the only difference between the two formula should
be the addition of (1) for the platforms that do not already implement
frequency invariance.

That is actually correct for platforms which do as told with their DVFS
bits. And there's really not much else we can do short of implementing
the scheduler arch hook to do better.

> (b) Make all architecuters use "frequency invariant" and then look for a
>     working formula (seems rather less than realistic to me to be honest).

There was a proposal to implement arch_scale_freq_capacity() as a weak
function and have it serve the cpufreq selected frequency for (1) so
that everything would default to that.

We didn't do that because that makes the function call and
multiplications unconditional. It's cheaper to add (1) to the cpufreq
side when selecting a freq rather than at every single time we update
the util statistics.

[toc] | [prev] | [next] | [standalone]

#1353284 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Tue, Mar 8, 2016 at 12:27 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Mon, Mar 07, 2016 at 03:41:15AM +0100, Rafael J. Wysocki wrote:
>
>> If my understanding of the requency invariant utilization idea is correct,
>> it is about re-scaling utilization so it is always relative to the capacity
>> at the max frequency.
>
> Right. So if a workload runs for 5ms at @1GHz and 10ms @500MHz, it would
> still result in the exact same utilization.
>
>> If that's the case, then instead of using
>>   x = util_raw / max
>> we will use something like
>>   y = (util_raw / max) * (f / max_freq) (f - current frequency).
>
> I don't get the last term.

The "(f - current frequency)" thing?  It doesn't belong to the
formula, sorry for the confusion.

So it is almost the same as your (1) below (except for the max in the
denominator), so my y is your x. :-)

> Assuming fixed frequency hardware (we can't
> really assume anything else) I get to:
>
>   util = util_raw * (current_freq / max_freq)           (1)
>   x = util / max                                        (2)
>
>> so there's no hope that the same formula will ever work for both "raw"
>> and "frequency invariant" utilization.
>
> Here I agree, however the above (current_freq / max_freq) term is easily
> computable, and really the only thing we can assume if the arch doesn't
> implement freq invariant accounting.

Right.

>> (c) Code for using either "raw" or "frequency invariant" depending on
>>     a callback flag or something like that.
>
> Seeing how frequency invariance is an arch feature, and cpufreq drivers
> are also typically arch specific, do we really need a flag at this
> level?

The next frequency is selected by the governor and that's why.  The
driver gets a frequency to set only.

Now, the governor needs to work with different platforms, so it needs
to know how to deal with the given one.

> In any case, I think the only difference between the two formula should
> be the addition of (1) for the platforms that do not already implement
> frequency invariance.

OK

So I'm reading this as a statement that linear is a better
approximation for frequency invariant utilization.

This means that on platforms where the utilization is frequency
invariant we should use

  next_freq = a * x

(where x is given by (2) above) and for platforms where the
utilization is not frequency invariant

  next_freq = a * x * current_freq / max_freq

and all boils down to finding a.

Now, it seems reasonable for a to be something like (1 + 1/n) *
max_freq, so for non-frequency invariant we get

  nex_freq = (1 + 1/n) * current_freq * x

> That is actually correct for platforms which do as told with their DVFS
> bits. And there's really not much else we can do short of implementing
> the scheduler arch hook to do better.
>
>> (b) Make all architecuters use "frequency invariant" and then look for a
>>     working formula (seems rather less than realistic to me to be honest).
>
> There was a proposal to implement arch_scale_freq_capacity() as a weak
> function and have it serve the cpufreq selected frequency for (1) so
> that everything would default to that.
>
> We didn't do that because that makes the function call and
> multiplications unconditional. It's cheaper to add (1) to the cpufreq
> side when selecting a freq rather than at every single time we update
> the util statistics.

That's fine by me.

My point was that we need different formulas for frequency invariant
and the other basically.

[toc] | [prev] | [next] | [standalone]

#1353329 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Tue, Mar 08, 2016 at 07:00:57PM +0100, Rafael J. Wysocki wrote:
> On Tue, Mar 8, 2016 at 12:27 PM, Peter Zijlstra <peterz@infradead.org> wrote:

> > Seeing how frequency invariance is an arch feature, and cpufreq drivers
> > are also typically arch specific, do we really need a flag at this
> > level?
> 
> The next frequency is selected by the governor and that's why.  The
> driver gets a frequency to set only.
> 
> Now, the governor needs to work with different platforms, so it needs
> to know how to deal with the given one.

Ah, indeed. In any case, the availability of arch_sched_scale_freq() is
a compile time thingy, so we can, at compile time, know what to use.

> > In any case, I think the only difference between the two formula should
> > be the addition of (1) for the platforms that do not already implement
> > frequency invariance.
> 
> OK
> 
> So I'm reading this as a statement that linear is a better
> approximation for frequency invariant utilization.

Well, (1) is what the scheduler does with frequency invariance, except
that allows a more flexible definition of 'current frequency' by asking
for it every time we update the util stats.

But if a platform doesn't need this, ie. it has a fixed frequency, or
simply doesn't provide anything like this, assuming we run at the
frequency we asked for is a reasonable assumption no?

> This means that on platforms where the utilization is frequency
> invariant we should use
> 
>   next_freq = a * x
> 
> (where x is given by (2) above) and for platforms where the
> utilization is not frequency invariant
> 
>   next_freq = a * x * current_freq / max_freq
> 
> and all boils down to finding a.

Right.

> Now, it seems reasonable for a to be something like (1 + 1/n) *
> max_freq, so for non-frequency invariant we get
> 
>   nex_freq = (1 + 1/n) * current_freq * x

This seems like a big leap; where does:

  (1 + 1/n) * max_freq

come from? And what is 'n'?

[toc] | [prev] | [next] | [standalone]

#1353375 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Tue, Mar 8, 2016 at 8:26 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Mar 08, 2016 at 07:00:57PM +0100, Rafael J. Wysocki wrote:
>> On Tue, Mar 8, 2016 at 12:27 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>
>> > Seeing how frequency invariance is an arch feature, and cpufreq drivers
>> > are also typically arch specific, do we really need a flag at this
>> > level?
>>
>> The next frequency is selected by the governor and that's why.  The
>> driver gets a frequency to set only.
>>
>> Now, the governor needs to work with different platforms, so it needs
>> to know how to deal with the given one.
>
> Ah, indeed. In any case, the availability of arch_sched_scale_freq() is
> a compile time thingy, so we can, at compile time, know what to use.
>
>> > In any case, I think the only difference between the two formula should
>> > be the addition of (1) for the platforms that do not already implement
>> > frequency invariance.
>>
>> OK
>>
>> So I'm reading this as a statement that linear is a better
>> approximation for frequency invariant utilization.
>
> Well, (1) is what the scheduler does with frequency invariance, except
> that allows a more flexible definition of 'current frequency' by asking
> for it every time we update the util stats.
>
> But if a platform doesn't need this, ie. it has a fixed frequency, or
> simply doesn't provide anything like this, assuming we run at the
> frequency we asked for is a reasonable assumption no?
>
>> This means that on platforms where the utilization is frequency
>> invariant we should use
>>
>>   next_freq = a * x
>>
>> (where x is given by (2) above) and for platforms where the
>> utilization is not frequency invariant
>>
>>   next_freq = a * x * current_freq / max_freq
>>
>> and all boils down to finding a.
>
> Right.

However, that doesn't seem to be in agreement with the Steve's results
posted earlier in this thread.

Also theoretically, with frequency invariant, the only way you can get
to 100% utilization is by running at the max frequency, so the closer
to 100% you get, the faster you need to run to get any further.  That
indicates nonlinear to me.

>> Now, it seems reasonable for a to be something like (1 + 1/n) *
>> max_freq, so for non-frequency invariant we get
>>
>>   nex_freq = (1 + 1/n) * current_freq * x
>
> This seems like a big leap; where does:
>
>   (1 + 1/n) * max_freq
>
> come from? And what is 'n'?

a = max_freq gives next_freq = max_freq for x = 1, but with that
choice of a you may never get to x = 1 with frequency invariant
because of the feedback effect mentioned above, so the 1/n produces
the extra boost needed for that (n is a positive integer).

Quite frankly, to me it looks like linear really is a better
approximation for "raw" utilization.  That is, for frequency invariant
x we should take:

  next_freq = a * x * max_freq / current_freq

(and if x is not frequency invariant, the right-hand side becomes a *
x).  Then, the extra boost needed to get to x = 1 for frequency
invariant is produced by the (max_freq / current_freq) factor that is
greater than 1 as long as we are not running at max_freq and a can be
chosen as max_freq.

[toc] | [prev] | [next] | [standalone]

#1353945 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

Hi,

sorry if I didn't reply yet. Trying to cope with jetlag and
talks/meetings these days :-). Let me see if I'm getting what you are
discussing, though.

On 08/03/16 21:05, Rafael J. Wysocki wrote:
> On Tue, Mar 8, 2016 at 8:26 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Tue, Mar 08, 2016 at 07:00:57PM +0100, Rafael J. Wysocki wrote:
> >> On Tue, Mar 8, 2016 at 12:27 PM, Peter Zijlstra <peterz@infradead.org> wrote:

[...]

> a = max_freq gives next_freq = max_freq for x = 1, but with that
> choice of a you may never get to x = 1 with frequency invariant
> because of the feedback effect mentioned above, so the 1/n produces
> the extra boost needed for that (n is a positive integer).
> 
> Quite frankly, to me it looks like linear really is a better
> approximation for "raw" utilization.  That is, for frequency invariant
> x we should take:
> 
>   next_freq = a * x * max_freq / current_freq
> 
> (and if x is not frequency invariant, the right-hand side becomes a *
> x).  Then, the extra boost needed to get to x = 1 for frequency
> invariant is produced by the (max_freq / current_freq) factor that is
> greater than 1 as long as we are not running at max_freq and a can be
> chosen as max_freq.
> 

Expanding terms again, your original formula (without the 1.1 factor of
the last version) was:

 next_freq = util / max_cap * max_freq

and this doesn't work when we have freq invariance since util won't go
over curr_cap.

What you propose above is to add another factor, so that we have:

 next_freq = util / max_cap * max_freq / curr_freq * max_freq

which should give us the opportunity to reach max_freq also with freq
invariance.

This should actually be the same of doing:

 next_freq = util / max_cap * max_cap / curr_cap * max_freq

We are basically scaling how much the cpu is busy at curr_cap back to
the 0..1024 scale. And we use this to select next_freq. Also, we can
simplify this to:

 next_freq = util / curr_cap * max_freq

and we save some ops.

However, if that is correct, I think we might have a problem, as we are
skewing OPP selection towards higher frequencies. Let's suppose we have
a platform with 3 OPPs:

  freq     cap
  1200     1024
  900      768
  600      512

As soon a task reaches an utilization of 257 we will be selecting the
second OPP as

 next_freq = 257 / 512 * 1200 ~ 602

While the cpu is only 50% busy in this case. And we will go at max OPP
when reaching ~492 (~64% of 768).

That said, I guess this might work as a first solution, but we will
probably need something better in the future. I understand Rafael's
concerns regardin margins, but it seems to me that some kind of
additional parameter will be probably needed anyway to fix this.
Just to say again how we handle this in schedfreq, with a -20% margin
applied to the lowest OPP we will get to the next one when utilization
reaches ~410 (80% busy at curr OPP), and so on for the subsequent ones,
which is less aggressive and might be better IMHO.

Best,

- Juri

[toc] | [prev] | [next] | [standalone]

#1354685 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Wed, Mar 9, 2016 at 11:15 AM, Juri Lelli <juri.lelli@arm.com> wrote:
> Hi,
>
> sorry if I didn't reply yet. Trying to cope with jetlag and
> talks/meetings these days :-). Let me see if I'm getting what you are
> discussing, though.
>
> On 08/03/16 21:05, Rafael J. Wysocki wrote:
>> On Tue, Mar 8, 2016 at 8:26 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>> > On Tue, Mar 08, 2016 at 07:00:57PM +0100, Rafael J. Wysocki wrote:
>> >> On Tue, Mar 8, 2016 at 12:27 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>
> [...]
>
>> a = max_freq gives next_freq = max_freq for x = 1, but with that
>> choice of a you may never get to x = 1 with frequency invariant
>> because of the feedback effect mentioned above, so the 1/n produces
>> the extra boost needed for that (n is a positive integer).
>>
>> Quite frankly, to me it looks like linear really is a better
>> approximation for "raw" utilization.  That is, for frequency invariant
>> x we should take:
>>
>>   next_freq = a * x * max_freq / current_freq
>>
>> (and if x is not frequency invariant, the right-hand side becomes a *
>> x).  Then, the extra boost needed to get to x = 1 for frequency
>> invariant is produced by the (max_freq / current_freq) factor that is
>> greater than 1 as long as we are not running at max_freq and a can be
>> chosen as max_freq.
>>
>
> Expanding terms again, your original formula (without the 1.1 factor of
> the last version) was:
>
>  next_freq = util / max_cap * max_freq
>
> and this doesn't work when we have freq invariance since util won't go
> over curr_cap.

Can you please remind me what curr_cap is?

> What you propose above is to add another factor, so that we have:
>
>  next_freq = util / max_cap * max_freq / curr_freq * max_freq
>
> which should give us the opportunity to reach max_freq also with freq
> invariance.
>
> This should actually be the same of doing:
>
>  next_freq = util / max_cap * max_cap / curr_cap * max_freq
>
> We are basically scaling how much the cpu is busy at curr_cap back to
> the 0..1024 scale. And we use this to select next_freq. Also, we can
> simplify this to:
>
>  next_freq = util / curr_cap * max_freq
>
> and we save some ops.
>
> However, if that is correct, I think we might have a problem, as we are
> skewing OPP selection towards higher frequencies. Let's suppose we have
> a platform with 3 OPPs:
>
>   freq     cap
>   1200     1024
>   900      768
>   600      512
>
> As soon a task reaches an utilization of 257 we will be selecting the
> second OPP as
>
>  next_freq = 257 / 512 * 1200 ~ 602
>
> While the cpu is only 50% busy in this case. And we will go at max OPP
> when reaching ~492 (~64% of 768).
>
> That said, I guess this might work as a first solution, but we will
> probably need something better in the future. I understand Rafael's
> concerns regardin margins, but it seems to me that some kind of
> additional parameter will be probably needed anyway to fix this.
> Just to say again how we handle this in schedfreq, with a -20% margin
> applied to the lowest OPP we will get to the next one when utilization
> reaches ~410 (80% busy at curr OPP), and so on for the subsequent ones,
> which is less aggressive and might be better IMHO.

Well, Peter says that my idea is incorrect, so I'll go for

  next_freq = C * current_freq * util_raw / max

where C > 1 (and likely C < 1.5) instead.

That means C has to be determined somehow or guessed.  The 80% tipping
point condition seems reasonable to me, though, which leads to C =
1.25.

[toc] | [prev] | [next] | [standalone]

#1354850 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On 10/03/16 00:41, Rafael J. Wysocki wrote:
> On Wed, Mar 9, 2016 at 11:15 AM, Juri Lelli <juri.lelli@arm.com> wrote:
> > Hi,
> >
> > sorry if I didn't reply yet. Trying to cope with jetlag and
> > talks/meetings these days :-). Let me see if I'm getting what you are
> > discussing, though.
> >
> > On 08/03/16 21:05, Rafael J. Wysocki wrote:
> >> On Tue, Mar 8, 2016 at 8:26 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> >> > On Tue, Mar 08, 2016 at 07:00:57PM +0100, Rafael J. Wysocki wrote:
> >> >> On Tue, Mar 8, 2016 at 12:27 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > [...]
> >
> >> a = max_freq gives next_freq = max_freq for x = 1, but with that
> >> choice of a you may never get to x = 1 with frequency invariant
> >> because of the feedback effect mentioned above, so the 1/n produces
> >> the extra boost needed for that (n is a positive integer).
> >>
> >> Quite frankly, to me it looks like linear really is a better
> >> approximation for "raw" utilization.  That is, for frequency invariant
> >> x we should take:
> >>
> >>   next_freq = a * x * max_freq / current_freq
> >>
> >> (and if x is not frequency invariant, the right-hand side becomes a *
> >> x).  Then, the extra boost needed to get to x = 1 for frequency
> >> invariant is produced by the (max_freq / current_freq) factor that is
> >> greater than 1 as long as we are not running at max_freq and a can be
> >> chosen as max_freq.
> >>
> >
> > Expanding terms again, your original formula (without the 1.1 factor of
> > the last version) was:
> >
> >  next_freq = util / max_cap * max_freq
> >
> > and this doesn't work when we have freq invariance since util won't go
> > over curr_cap.
> 
> Can you please remind me what curr_cap is?
> 

The capacity at current frequency.

> > What you propose above is to add another factor, so that we have:
> >
> >  next_freq = util / max_cap * max_freq / curr_freq * max_freq
> >
> > which should give us the opportunity to reach max_freq also with freq
> > invariance.
> >
> > This should actually be the same of doing:
> >
> >  next_freq = util / max_cap * max_cap / curr_cap * max_freq
> >
> > We are basically scaling how much the cpu is busy at curr_cap back to
> > the 0..1024 scale. And we use this to select next_freq. Also, we can
> > simplify this to:
> >
> >  next_freq = util / curr_cap * max_freq
> >
> > and we save some ops.
> >
> > However, if that is correct, I think we might have a problem, as we are
> > skewing OPP selection towards higher frequencies. Let's suppose we have
> > a platform with 3 OPPs:
> >
> >   freq     cap
> >   1200     1024
> >   900      768
> >   600      512
> >
> > As soon a task reaches an utilization of 257 we will be selecting the
> > second OPP as
> >
> >  next_freq = 257 / 512 * 1200 ~ 602
> >
> > While the cpu is only 50% busy in this case. And we will go at max OPP
> > when reaching ~492 (~64% of 768).
> >
> > That said, I guess this might work as a first solution, but we will
> > probably need something better in the future. I understand Rafael's
> > concerns regardin margins, but it seems to me that some kind of
> > additional parameter will be probably needed anyway to fix this.
> > Just to say again how we handle this in schedfreq, with a -20% margin
> > applied to the lowest OPP we will get to the next one when utilization
> > reaches ~410 (80% busy at curr OPP), and so on for the subsequent ones,
> > which is less aggressive and might be better IMHO.
> 
> Well, Peter says that my idea is incorrect, so I'll go for
> 
>   next_freq = C * current_freq * util_raw / max
> 
> where C > 1 (and likely C < 1.5) instead.
> 
> That means C has to be determined somehow or guessed.  The 80% tipping
> point condition seems reasonable to me, though, which leads to C =
> 1.25.
> 

Right. So, when using freq. invariant util we have:

 next_freq = C * curr_freq * util / curr_cap

as

 util_raw = util * max / curr_cap

What Vincent is saying makes sense, though. If we use
arch_scale_freq_capacity() as denominator instead of max, we can use a
single formula for both cases.

Best,

- Juri

[toc] | [prev] | [next] | [standalone]

#1355400

On Thursday, March 10, 2016 11:30:34 AM Juri Lelli wrote:
> On 10/03/16 00:41, Rafael J. Wysocki wrote:
> > On Wed, Mar 9, 2016 at 11:15 AM, Juri Lelli <juri.lelli@arm.com> wrote:
> > > Hi,
> > >
> > > sorry if I didn't reply yet. Trying to cope with jetlag and
> > > talks/meetings these days :-). Let me see if I'm getting what you are
> > > discussing, though.
> > >
> > > On 08/03/16 21:05, Rafael J. Wysocki wrote:
> > >> On Tue, Mar 8, 2016 at 8:26 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> > >> > On Tue, Mar 08, 2016 at 07:00:57PM +0100, Rafael J. Wysocki wrote:
> > >> >> On Tue, Mar 8, 2016 at 12:27 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> > >
> > > [...]
> > >
> > >> a = max_freq gives next_freq = max_freq for x = 1, but with that
> > >> choice of a you may never get to x = 1 with frequency invariant
> > >> because of the feedback effect mentioned above, so the 1/n produces
> > >> the extra boost needed for that (n is a positive integer).
> > >>
> > >> Quite frankly, to me it looks like linear really is a better
> > >> approximation for "raw" utilization.  That is, for frequency invariant
> > >> x we should take:
> > >>
> > >>   next_freq = a * x * max_freq / current_freq
> > >>
> > >> (and if x is not frequency invariant, the right-hand side becomes a *
> > >> x).  Then, the extra boost needed to get to x = 1 for frequency
> > >> invariant is produced by the (max_freq / current_freq) factor that is
> > >> greater than 1 as long as we are not running at max_freq and a can be
> > >> chosen as max_freq.
> > >>
> > >
> > > Expanding terms again, your original formula (without the 1.1 factor of
> > > the last version) was:
> > >
> > >  next_freq = util / max_cap * max_freq
> > >
> > > and this doesn't work when we have freq invariance since util won't go
> > > over curr_cap.
> > 
> > Can you please remind me what curr_cap is?
> > 
> 
> The capacity at current frequency.

I see, thanks!

> > > What you propose above is to add another factor, so that we have:
> > >
> > >  next_freq = util / max_cap * max_freq / curr_freq * max_freq
> > >
> > > which should give us the opportunity to reach max_freq also with freq
> > > invariance.
> > >
> > > This should actually be the same of doing:
> > >
> > >  next_freq = util / max_cap * max_cap / curr_cap * max_freq
> > >
> > > We are basically scaling how much the cpu is busy at curr_cap back to
> > > the 0..1024 scale. And we use this to select next_freq. Also, we can
> > > simplify this to:
> > >
> > >  next_freq = util / curr_cap * max_freq
> > >
> > > and we save some ops.
> > >
> > > However, if that is correct, I think we might have a problem, as we are
> > > skewing OPP selection towards higher frequencies. Let's suppose we have
> > > a platform with 3 OPPs:
> > >
> > >   freq     cap
> > >   1200     1024
> > >   900      768
> > >   600      512
> > >
> > > As soon a task reaches an utilization of 257 we will be selecting the
> > > second OPP as
> > >
> > >  next_freq = 257 / 512 * 1200 ~ 602
> > >
> > > While the cpu is only 50% busy in this case. And we will go at max OPP
> > > when reaching ~492 (~64% of 768).
> > >
> > > That said, I guess this might work as a first solution, but we will
> > > probably need something better in the future. I understand Rafael's
> > > concerns regardin margins, but it seems to me that some kind of
> > > additional parameter will be probably needed anyway to fix this.
> > > Just to say again how we handle this in schedfreq, with a -20% margin
> > > applied to the lowest OPP we will get to the next one when utilization
> > > reaches ~410 (80% busy at curr OPP), and so on for the subsequent ones,
> > > which is less aggressive and might be better IMHO.
> > 
> > Well, Peter says that my idea is incorrect, so I'll go for
> > 
> >   next_freq = C * current_freq * util_raw / max
> > 
> > where C > 1 (and likely C < 1.5) instead.
> > 
> > That means C has to be determined somehow or guessed.  The 80% tipping
> > point condition seems reasonable to me, though, which leads to C =
> > 1.25.
> > 
> 
> Right. So, when using freq. invariant util we have:
> 
>  next_freq = C * curr_freq * util / curr_cap
> 
> as
> 
>  util_raw = util * max / curr_cap
> 
> What Vincent is saying makes sense, though. If we use
> arch_scale_freq_capacity() as denominator instead of max, we can use a
> single formula for both cases.

I'm not convinced about that yet, but let me think about it some more. :-)

Thanks,
Rafael

[toc] | [prev] | [next] | [standalone]

#1355452 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

Quoting Rafael J. Wysocki (2016-03-09 15:41:34)
> On Wed, Mar 9, 2016 at 11:15 AM, Juri Lelli <juri.lelli@arm.com> wrote:
> > Hi,
> >
> > sorry if I didn't reply yet. Trying to cope with jetlag and
> > talks/meetings these days :-). Let me see if I'm getting what you are
> > discussing, though.
> >
> > On 08/03/16 21:05, Rafael J. Wysocki wrote:
> >> On Tue, Mar 8, 2016 at 8:26 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> >> > On Tue, Mar 08, 2016 at 07:00:57PM +0100, Rafael J. Wysocki wrote:
> >> >> On Tue, Mar 8, 2016 at 12:27 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > [...]
> >
> >> a = max_freq gives next_freq = max_freq for x = 1, but with that
> >> choice of a you may never get to x = 1 with frequency invariant
> >> because of the feedback effect mentioned above, so the 1/n produces
> >> the extra boost needed for that (n is a positive integer).
> >>
> >> Quite frankly, to me it looks like linear really is a better
> >> approximation for "raw" utilization.  That is, for frequency invariant
> >> x we should take:
> >>
> >>   next_freq = a * x * max_freq / current_freq
> >>
> >> (and if x is not frequency invariant, the right-hand side becomes a *
> >> x).  Then, the extra boost needed to get to x = 1 for frequency
> >> invariant is produced by the (max_freq / current_freq) factor that is
> >> greater than 1 as long as we are not running at max_freq and a can be
> >> chosen as max_freq.
> >>
> >
> > Expanding terms again, your original formula (without the 1.1 factor of
> > the last version) was:
> >
> >  next_freq = util / max_cap * max_freq
> >
> > and this doesn't work when we have freq invariance since util won't go
> > over curr_cap.
> 
> Can you please remind me what curr_cap is?
> 
> > What you propose above is to add another factor, so that we have:
> >
> >  next_freq = util / max_cap * max_freq / curr_freq * max_freq
> >
> > which should give us the opportunity to reach max_freq also with freq
> > invariance.
> >
> > This should actually be the same of doing:
> >
> >  next_freq = util / max_cap * max_cap / curr_cap * max_freq
> >
> > We are basically scaling how much the cpu is busy at curr_cap back to
> > the 0..1024 scale. And we use this to select next_freq. Also, we can
> > simplify this to:
> >
> >  next_freq = util / curr_cap * max_freq
> >
> > and we save some ops.
> >
> > However, if that is correct, I think we might have a problem, as we are
> > skewing OPP selection towards higher frequencies. Let's suppose we have
> > a platform with 3 OPPs:
> >
> >   freq     cap
> >   1200     1024
> >   900      768
> >   600      512
> >
> > As soon a task reaches an utilization of 257 we will be selecting the
> > second OPP as
> >
> >  next_freq = 257 / 512 * 1200 ~ 602
> >
> > While the cpu is only 50% busy in this case. And we will go at max OPP
> > when reaching ~492 (~64% of 768).
> >
> > That said, I guess this might work as a first solution, but we will
> > probably need something better in the future. I understand Rafael's
> > concerns regardin margins, but it seems to me that some kind of
> > additional parameter will be probably needed anyway to fix this.
> > Just to say again how we handle this in schedfreq, with a -20% margin
> > applied to the lowest OPP we will get to the next one when utilization
> > reaches ~410 (80% busy at curr OPP), and so on for the subsequent ones,
> > which is less aggressive and might be better IMHO.
> 
> Well, Peter says that my idea is incorrect, so I'll go for
> 
>   next_freq = C * current_freq * util_raw / max
> 
> where C > 1 (and likely C < 1.5) instead.
> 
> That means C has to be determined somehow or guessed.  The 80% tipping
> point condition seems reasonable to me, though, which leads to C =
> 1.25.

Right, that is the same value used in the schedfreq series:

+/*
+ * Capacity margin added to CFS and RT capacity requests to provide
+ * some head room if task utilization further increases.
+ */
+unsigned int capacity_margin = 1280;

Regards,
Mike

[toc] | [prev] | [next] | [standalone]

#1354260 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Tue, Mar 08, 2016 at 09:05:50PM +0100, Rafael J. Wysocki wrote:
> >> This means that on platforms where the utilization is frequency
> >> invariant we should use
> >>
> >>   next_freq = a * x
> >>
> >> (where x is given by (2) above) and for platforms where the
> >> utilization is not frequency invariant
> >>
> >>   next_freq = a * x * current_freq / max_freq
> >>
> >> and all boils down to finding a.
> >
> > Right.
> 
> However, that doesn't seem to be in agreement with the Steve's results
> posted earlier in this thread.

I could not make anything of those numbers.

> Also theoretically, with frequency invariant, the only way you can get
> to 100% utilization is by running at the max frequency, so the closer
> to 100% you get, the faster you need to run to get any further.  That
> indicates nonlinear to me.

I'm not seeing that, you get that by using a > 1. No need for
non-linear.

> >> Now, it seems reasonable for a to be something like (1 + 1/n) *
> >> max_freq, so for non-frequency invariant we get
> >>
> >>   nex_freq = (1 + 1/n) * current_freq * x
> >
> > This seems like a big leap; where does:
> >
> >   (1 + 1/n) * max_freq
> >
> > come from? And what is 'n'?

> a = max_freq gives next_freq = max_freq for x = 1,

next_freq = a        * x * current_freq / max_freq

  [ a := max_freq, x := 1 ] ->

          = max_freq * 1 * current_freq / max_freq
	  = current_freq

	  != max_freq

But I think I see what you're saying; because at x = 1,
current_frequency must be max_frequency. Per your earlier point.

> but with that choice of a you may never get to x = 1 with frequency
> invariant because of the feedback effect mentioned above, so the 1/n
> produces the extra boost needed for that (n is a positive integer).

OK, so that gets us:

	a = (1 + 1/n) ; n > 0

[ I would not have chosen (1 + 1/n), but lets stick to that ]

So for n = 4 that gets you: a = 1.25, which effectively gets you an 80%
utilization tipping point. That is, 1.25 * .8 = 1, iow. you'll pick the
next frequency (assuming RELATION_L like selection).

Together this gets you:

	next_freq = (1 + 1/n) * max_freq * x * current_freq / max_freq
	          = (1 + 1/n) * x * current_freq

Again, with n = 4, x > .8 will result in a next_freq > current_freq, and
hence (RELATION_L) pick a higher one.

> Quite frankly, to me it looks like linear really is a better
> approximation for "raw" utilization.  That is, for frequency invariant
> x we should take:
> 
>   next_freq = a * x * max_freq / current_freq

(its very confusing how you use 'x' for both invariant and
non-invariant).

That doesn't make sense, remember:

	util = \Sum_i u_i * freq_i / max_freq		(1)

Which for systems where freq_i is constant reduces to:

	util = util_raw * current_freq / max_freq	(2)

But you cannot reverse this. IOW you cannot try and divide out
current_freq on a frequency invariant metric.

So going by:

	next_freq = (1 + 1/n) * max_freq * util		(3)

if we substitute (2) into (3) we get:

	          = (1 + 1/n) * max_freq * util_raw * current_freq / max_freq
		  = (1 + 1/n) * current_freq * util_raw	(4)

Which gets you two formula with the same general behaviour. As (2) is
the only approximation of (1) we can make.

[toc] | [prev] | [next] | [standalone]

#1354595 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Wed, Mar 9, 2016 at 5:39 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Mar 08, 2016 at 09:05:50PM +0100, Rafael J. Wysocki wrote:
>> >> This means that on platforms where the utilization is frequency
>> >> invariant we should use
>> >>
>> >>   next_freq = a * x
>> >>
>> >> (where x is given by (2) above) and for platforms where the
>> >> utilization is not frequency invariant
>> >>
>> >>   next_freq = a * x * current_freq / max_freq
>> >>
>> >> and all boils down to finding a.
>> >
>> > Right.
>>
>> However, that doesn't seem to be in agreement with the Steve's results
>> posted earlier in this thread.
>
> I could not make anything of those numbers.
>
>> Also theoretically, with frequency invariant, the only way you can get
>> to 100% utilization is by running at the max frequency, so the closer
>> to 100% you get, the faster you need to run to get any further.  That
>> indicates nonlinear to me.
>
> I'm not seeing that, you get that by using a > 1. No need for
> non-linear.

OK

>> >> Now, it seems reasonable for a to be something like (1 + 1/n) *
>> >> max_freq, so for non-frequency invariant we get
>> >>
>> >>   nex_freq = (1 + 1/n) * current_freq * x

(*) (see below)

>> > This seems like a big leap; where does:
>> >
>> >   (1 + 1/n) * max_freq
>> >
>> > come from? And what is 'n'?
>
>> a = max_freq gives next_freq = max_freq for x = 1,
>
> next_freq = a        * x * current_freq / max_freq
>
>   [ a := max_freq, x := 1 ] ->
>
>           = max_freq * 1 * current_freq / max_freq
>           = current_freq
>
>           != max_freq
>
> But I think I see what you're saying; because at x = 1,
> current_frequency must be max_frequency. Per your earlier point.

Correct.

>> but with that choice of a you may never get to x = 1 with frequency
>> invariant because of the feedback effect mentioned above, so the 1/n
>> produces the extra boost needed for that (n is a positive integer).
>
> OK, so that gets us:
>
>         a = (1 + 1/n) ; n > 0
>
> [ I would not have chosen (1 + 1/n), but lets stick to that ]

Well, what would you choose then? :-)

> So for n = 4 that gets you: a = 1.25, which effectively gets you an 80%
> utilization tipping point. That is, 1.25 * .8 = 1, iow. you'll pick the
> next frequency (assuming RELATION_L like selection).
>
> Together this gets you:
>
>         next_freq = (1 + 1/n) * max_freq * x * current_freq / max_freq
>                   = (1 + 1/n) * x * current_freq

That seems to be what I said above (*), isn't it?

> Again, with n = 4, x > .8 will result in a next_freq > current_freq, and
> hence (RELATION_L) pick a higher one.

OK

>> Quite frankly, to me it looks like linear really is a better
>> approximation for "raw" utilization.  That is, for frequency invariant
>> x we should take:
>>
>>   next_freq = a * x * max_freq / current_freq
>
> (its very confusing how you use 'x' for both invariant and
> non-invariant).
>
> That doesn't make sense, remember:
>
>         util = \Sum_i u_i * freq_i / max_freq           (1)
>
> Which for systems where freq_i is constant reduces to:
>
>         util = util_raw * current_freq / max_freq       (2)
>
> But you cannot reverse this. IOW you cannot try and divide out
> current_freq on a frequency invariant metric.

I see.

> So going by:
>
>         next_freq = (1 + 1/n) * max_freq * util         (3)

I think that should be

  next_freq = (1 + 1/n) * max_freq * util / max

(where max is the second argument of cpufreq_update_util) or the
dimensions on both sides don't match.

> if we substitute (2) into (3) we get:
>
>                   = (1 + 1/n) * max_freq * util_raw * current_freq / max_freq
>                   = (1 + 1/n) * current_freq * util_raw (4)
>
> Which gets you two formula with the same general behaviour. As (2) is
> the only approximation of (1) we can make.

OK

So since utilization is not frequency invariant in the current
mainline (or linux-next for that matter) AFAIC, I'm going to use the
following in the next version of the schedutil patch series:

  next_freq = 1.25 * current_freq * util_raw / max

where util_raw and max are what I get from cpufreq_update_util().

1.25 is for the 80% tipping point which I think is reasonable.

[toc] | [prev] | [next] | [standalone]

#1354833 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On 10 March 2016 at 06:28, Rafael J. Wysocki <rafael@kernel.org> wrote:
> On Wed, Mar 9, 2016 at 5:39 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>> On Tue, Mar 08, 2016 at 09:05:50PM +0100, Rafael J. Wysocki wrote:
>>> >> This means that on platforms where the utilization is frequency
>>> >> invariant we should use
>>> >>
>>> >>   next_freq = a * x
>>> >>
>>> >> (where x is given by (2) above) and for platforms where the
>>> >> utilization is not frequency invariant
>>> >>
>>> >>   next_freq = a * x * current_freq / max_freq
>>> >>
>>> >> and all boils down to finding a.
>>> >
>>> > Right.
>>>
>>> However, that doesn't seem to be in agreement with the Steve's results
>>> posted earlier in this thread.
>>
>> I could not make anything of those numbers.
>>
>>> Also theoretically, with frequency invariant, the only way you can get
>>> to 100% utilization is by running at the max frequency, so the closer
>>> to 100% you get, the faster you need to run to get any further.  That
>>> indicates nonlinear to me.
>>
>> I'm not seeing that, you get that by using a > 1. No need for
>> non-linear.
>
> OK
>
>>> >> Now, it seems reasonable for a to be something like (1 + 1/n) *
>>> >> max_freq, so for non-frequency invariant we get
>>> >>
>>> >>   nex_freq = (1 + 1/n) * current_freq * x
>
> (*) (see below)
>
>>> > This seems like a big leap; where does:
>>> >
>>> >   (1 + 1/n) * max_freq
>>> >
>>> > come from? And what is 'n'?
>>
>>> a = max_freq gives next_freq = max_freq for x = 1,
>>
>> next_freq = a        * x * current_freq / max_freq
>>
>>   [ a := max_freq, x := 1 ] ->
>>
>>           = max_freq * 1 * current_freq / max_freq
>>           = current_freq
>>
>>           != max_freq
>>
>> But I think I see what you're saying; because at x = 1,
>> current_frequency must be max_frequency. Per your earlier point.
>
> Correct.
>
>>> but with that choice of a you may never get to x = 1 with frequency
>>> invariant because of the feedback effect mentioned above, so the 1/n
>>> produces the extra boost needed for that (n is a positive integer).
>>
>> OK, so that gets us:
>>
>>         a = (1 + 1/n) ; n > 0
>>
>> [ I would not have chosen (1 + 1/n), but lets stick to that ]
>
> Well, what would you choose then? :-)
>
>> So for n = 4 that gets you: a = 1.25, which effectively gets you an 80%
>> utilization tipping point. That is, 1.25 * .8 = 1, iow. you'll pick the
>> next frequency (assuming RELATION_L like selection).
>>
>> Together this gets you:
>>
>>         next_freq = (1 + 1/n) * max_freq * x * current_freq / max_freq
>>                   = (1 + 1/n) * x * current_freq
>
> That seems to be what I said above (*), isn't it?
>
>> Again, with n = 4, x > .8 will result in a next_freq > current_freq, and
>> hence (RELATION_L) pick a higher one.
>
> OK
>
>>> Quite frankly, to me it looks like linear really is a better
>>> approximation for "raw" utilization.  That is, for frequency invariant
>>> x we should take:
>>>
>>>   next_freq = a * x * max_freq / current_freq
>>
>> (its very confusing how you use 'x' for both invariant and
>> non-invariant).
>>
>> That doesn't make sense, remember:
>>
>>         util = \Sum_i u_i * freq_i / max_freq           (1)
>>
>> Which for systems where freq_i is constant reduces to:
>>
>>         util = util_raw * current_freq / max_freq       (2)
>>
>> But you cannot reverse this. IOW you cannot try and divide out
>> current_freq on a frequency invariant metric.
>
> I see.
>
>> So going by:
>>
>>         next_freq = (1 + 1/n) * max_freq * util         (3)
>
> I think that should be
>
>   next_freq = (1 + 1/n) * max_freq * util / max
>
> (where max is the second argument of cpufreq_update_util) or the
> dimensions on both sides don't match.
>
>> if we substitute (2) into (3) we get:
>>
>>                   = (1 + 1/n) * max_freq * util_raw * current_freq / max_freq
>>                   = (1 + 1/n) * current_freq * util_raw (4)
>>
>> Which gets you two formula with the same general behaviour. As (2) is
>> the only approximation of (1) we can make.
>
> OK
>
> So since utilization is not frequency invariant in the current
> mainline (or linux-next for that matter) AFAIC, I'm going to use the
> following in the next version of the schedutil patch series:
>
>   next_freq = 1.25 * current_freq * util_raw / max
>
> where util_raw and max are what I get from cpufreq_update_util().
>
> 1.25 is for the 80% tipping point which I think is reasonable.


We have the arch_scale_freq_capacity function that is arch dependent
and can be used to merge the 2 formula that were described by peter
above.
By default, arch_scale_freq_capacity return SCHED_CAPACITY_SCALE which
is max capacity
but when arch_scale_freq_capacity is defined by an architecture,
arch_scale_freq_capacity returns current_freq * max_capacity/max_freq

so can't we use arch_scale_freq in your formula ? Taking your formula
above it becomes:
next_freq = 1.25 * current_freq * util / arch_scale_freq_capacity()

Without invariance feature, we have the same formula than above :
next_freq = 1.25 * current_freq * util_raw / max because
SCHED_CAPACITY_SCALE is max capacity

With invariance feature, we have next_freq = 1.25 * current_freq *
util / (current_freq*max_capacity/max_freq) = 1.25 * util * max_freq /
max which is the formula that has to be used with frequency invariant
utilization.

so we have one formula that works for both configuration (this is not
really optimized for invariant system because we multiply then divide
by current_freq in 2 different places but it's better than a wrong
formula)

Now, arch_scale_freq_capacity is available in kernel/sched/sched.h
header file which can only be accessed by scheduler code...

May be we can pass arch_scale_freq_capacity value instead of max one
as a parameter of update_util function prototype

Vincent

[toc] | [prev] | [next] | [standalone]

#1354967 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Thu, Mar 10, 2016 at 10:44:21AM +0700, Vincent Guittot wrote:
> We have the arch_scale_freq_capacity function that is arch dependent
> and can be used to merge the 2 formula that were described by peter
> above.
> By default, arch_scale_freq_capacity return SCHED_CAPACITY_SCALE which
> is max capacity
> but when arch_scale_freq_capacity is defined by an architecture,

> arch_scale_freq_capacity returns current_freq * max_capacity/max_freq

However, current_freq is a very fluid thing, it might (and will) change
very rapidly on some platforms.

This is the same point I made earlier, you cannot try and divide out
current_freq from the invariant measure.

> so can't we use arch_scale_freq in your formula ? Taking your formula
> above it becomes:
> next_freq = 1.25 * current_freq * util / arch_scale_freq_capacity()

No, that cannot work, nor makes any sense, per the above.

> With invariance feature, we have:
>
>   next_freq = 1.25 * current_freq * util / (current_freq*max_capacity/max_freq)
>             = 1.25 * util * max_freq / max
>
> which is the formula that has to be used with frequency invariant
> utilization.

Wrong, you cannot talk about current_freq in the invariant case.

> May be we can pass arch_scale_freq_capacity value instead of max one
> as a parameter of update_util function prototype

No, since its a compile time thing, we can simply do:

#ifdef arch_scale_freq_capacity
	next_freq = (1 + 1/n) * max_freq * (util / max)
#else
	next_freq = (1 + 1/n) * current_freq * (util_raw / max)
#endif

[toc] | [prev] | [next] | [standalone]

#1354990 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On 10 March 2016 at 17:07, Peter Zijlstra <peterz@infradead.org> wrote:
> On Thu, Mar 10, 2016 at 10:44:21AM +0700, Vincent Guittot wrote:
>> We have the arch_scale_freq_capacity function that is arch dependent
>> and can be used to merge the 2 formula that were described by peter
>> above.
>> By default, arch_scale_freq_capacity return SCHED_CAPACITY_SCALE which
>> is max capacity
>> but when arch_scale_freq_capacity is defined by an architecture,
>
>> arch_scale_freq_capacity returns current_freq * max_capacity/max_freq
>
> However, current_freq is a very fluid thing, it might (and will) change
> very rapidly on some platforms.
>
> This is the same point I made earlier, you cannot try and divide out
> current_freq from the invariant measure.
>
>> so can't we use arch_scale_freq in your formula ? Taking your formula
>> above it becomes:
>> next_freq = 1.25 * current_freq * util / arch_scale_freq_capacity()
>
> No, that cannot work, nor makes any sense, per the above.
>
>> With invariance feature, we have:
>>
>>   next_freq = 1.25 * current_freq * util / (current_freq*max_capacity/max_freq)
>>             = 1.25 * util * max_freq / max
>>
>> which is the formula that has to be used with frequency invariant
>> utilization.
>
> Wrong, you cannot talk about current_freq in the invariant case.
>
>> May be we can pass arch_scale_freq_capacity value instead of max one
>> as a parameter of update_util function prototype
>
> No, since its a compile time thing, we can simply do:
>
> #ifdef arch_scale_freq_capacity
>         next_freq = (1 + 1/n) * max_freq * (util / max)
> #else
>         next_freq = (1 + 1/n) * current_freq * (util_raw / max)
> #endif

selecting formula at compilation is clearly better. I wrongly thought
that it can't be accepted as a solution.

[toc] | [prev] | [next] | [standalone]

#1354995 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Thu, Mar 10, 2016 at 05:23:54PM +0700, Vincent Guittot wrote:

> > No, since its a compile time thing, we can simply do:
> >
> > #ifdef arch_scale_freq_capacity
> >         next_freq = (1 + 1/n) * max_freq * (util / max)
> > #else
> >         next_freq = (1 + 1/n) * current_freq * (util_raw / max)
> > #endif
> 
> selecting formula at compilation is clearly better. I wrongly thought that
> it can't be accepted as a solution.

Well, its bound to get more 'interesting' since I forse implementations
not always actually doing the invariant thing.

Take for example the thing I send:

  lkml.kernel.org/r/20160303162829.GB6375@twins.programming.kicks-ass.net

it both shows why you cannot talk about current_freq but also that the
above needs a little more help (for the !X86_FEATURE_APERFMPERF case).

But the !arch_scale_freq_capacity case should indeed be that simple.

[toc] | [prev] | [next] | [standalone]

#1355007 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Thu, Mar 10, 2016 at 11:30:08AM +0100, Peter Zijlstra wrote:
> On Thu, Mar 10, 2016 at 05:23:54PM +0700, Vincent Guittot wrote:
> 
> > > No, since its a compile time thing, we can simply do:
> > >
> > > #ifdef arch_scale_freq_capacity
> > >         next_freq = (1 + 1/n) * max_freq * (util / max)
> > > #else
> > >         next_freq = (1 + 1/n) * current_freq * (util_raw / max)
> > > #endif
> > 
> > selecting formula at compilation is clearly better. I wrongly thought that
> > it can't be accepted as a solution.
> 
> Well, its bound to get more 'interesting' since I forse implementations
> not always actually doing the invariant thing.
> 
> Take for example the thing I send:
> 
>   lkml.kernel.org/r/20160303162829.GB6375@twins.programming.kicks-ass.net
> 
> it both shows why you cannot talk about current_freq but also that the
> above needs a little more help (for the !X86_FEATURE_APERFMPERF case).
> 
> But the !arch_scale_freq_capacity case should indeed be that simple.

Maybe something like:

#ifdef arch_scale_freq_capacity
#ifndef arch_scale_freq_invariant
#define arch_scale_freq_invariant()	(true)
#endif
#else /* arch_scale_freq_capacity */
#define arch_scale_freq_invariant()	(false)
#endif

	if (arch_scale_freq_invariant())

And have archs that have conditional arch_scale_freq_capacity()
implementation provide a arch_scale_freq_invariant implementation.

[toc] | [prev] | [next] | [standalone]

#1355431

On Thursday, March 10, 2016 11:56:14 AM Peter Zijlstra wrote:
> On Thu, Mar 10, 2016 at 11:30:08AM +0100, Peter Zijlstra wrote:
> > On Thu, Mar 10, 2016 at 05:23:54PM +0700, Vincent Guittot wrote:
> > 
> > > > No, since its a compile time thing, we can simply do:
> > > >
> > > > #ifdef arch_scale_freq_capacity
> > > >         next_freq = (1 + 1/n) * max_freq * (util / max)
> > > > #else
> > > >         next_freq = (1 + 1/n) * current_freq * (util_raw / max)
> > > > #endif
> > > 
> > > selecting formula at compilation is clearly better. I wrongly thought that
> > > it can't be accepted as a solution.
> > 
> > Well, its bound to get more 'interesting' since I forse implementations
> > not always actually doing the invariant thing.
> > 
> > Take for example the thing I send:
> > 
> >   lkml.kernel.org/r/20160303162829.GB6375@twins.programming.kicks-ass.net
> > 
> > it both shows why you cannot talk about current_freq but also that the
> > above needs a little more help (for the !X86_FEATURE_APERFMPERF case).
> > 
> > But the !arch_scale_freq_capacity case should indeed be that simple.
> 
> Maybe something like:
> 
> #ifdef arch_scale_freq_capacity
> #ifndef arch_scale_freq_invariant
> #define arch_scale_freq_invariant()	(true)
> #endif
> #else /* arch_scale_freq_capacity */
> #define arch_scale_freq_invariant()	(false)
> #endif
> 
> 	if (arch_scale_freq_invariant())
> 
> And have archs that have conditional arch_scale_freq_capacity()
> implementation provide a arch_scale_freq_invariant implementation.

Yeah, looks workable to me.

[toc] | [prev] | [next] | [standalone]

#1354929 — Re: [PATCH 6/6] cpufreq: schedutil: New governor based on scheduler utilization data

On Thu, Mar 10, 2016 at 12:28:52AM +0100, Rafael J. Wysocki wrote:
> > [ I would not have chosen (1 + 1/n), but lets stick to that ]
> 
> Well, what would you choose then? :-)

1/p ; 0 < p < 1

or so. Where p then represents the percentile threshold where you want
to bump to the next freq.

> I think that should be
> 
>   next_freq = (1 + 1/n) * max_freq * util / max
> 
> (where max is the second argument of cpufreq_update_util) or the
> dimensions on both sides don't match.

Well yes, but so far we were treating util (and util_raw) as 0 < u < 1,
values, so already normalized against max.

But yes..

> > if we substitute (2) into (3) we get:
> >
> >                   = (1 + 1/n) * max_freq * util_raw * current_freq / max_freq
> >                   = (1 + 1/n) * current_freq * util_raw (4)
> >
> > Which gets you two formula with the same general behaviour. As (2) is
> > the only approximation of (1) we can make.
> 
> OK
> 
> So since utilization is not frequency invariant in the current
> mainline (or linux-next for that matter) AFAIC, I'm going to use the
> following in the next version of the schedutil patch series:
> 
>   next_freq = 1.25 * current_freq * util_raw / max
> 
> where util_raw and max are what I get from cpufreq_update_util().
> 
> 1.25 is for the 80% tipping point which I think is reasonable.

OK.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web