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

Groups > linux.kernel > #1291270 > unrolled thread

Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity

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: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Peter Zijlstra <peterz@infradead.org> - 2015-12-14 16:20 +0100
    Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity Vincent Guittot <vincent.guittot@linaro.org> - 2015-12-14 17:00 +0100
      Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Juri Lelli <Juri.Lelli@arm.com> - 2015-12-14 17:10 +0100
        Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-14 22:20 +0100
      Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Peter Zijlstra <peterz@infradead.org> - 2015-12-14 18:00 +0100
        Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-14 22:40 +0100
          Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Peter Zijlstra <peterz@infradead.org> - 2015-12-15 13:40 +0100
            Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-15 14:40 +0100
              Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Peter Zijlstra <peterz@infradead.org> - 2015-12-15 14:50 +0100
                Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-15 22:30 +0100
                  Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Juri Lelli <Juri.Lelli@arm.com> - 2015-12-16 10:30 +0100
        Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity Vincent Guittot <vincent.guittot@linaro.org> - 2015-12-15 05:50 +0100
          Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Peter Zijlstra <peterz@infradead.org> - 2015-12-15 13:50 +0100
            Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity Vincent Guittot <vincent.guittot@linaro.org> - 2015-12-15 14:00 +0100
      Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-14 22:20 +0100
        Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity Vincent Guittot <vincent.guittot@linaro.org> - 2015-12-15 06:10 +0100
          Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-15 10:00 +0100
            Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Peter Zijlstra <peterz@infradead.org> - 2015-12-15 13:30 +0100
              Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity Vincent Guittot <vincent.guittot@linaro.org> - 2015-12-15 13:50 +0100
              Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-15 14:20 +0100
            Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Peter Zijlstra <peterz@infradead.org> - 2015-12-15 13:30 +0100
              Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-15 14:30 +0100
            Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity Vincent Guittot <vincent.guittot@linaro.org> - 2015-12-15 13:50 +0100
              Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-15 14:40 +0100
            Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity Vincent Guittot <vincent.guittot@linaro.org> - 2015-12-15 14:00 +0100
              Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in  scale_rt_capacity Luca Abeni <luca.abeni@unitn.it> - 2015-12-15 14:50 +0100

Page 2 of 2 — ← Prev page 1 [2]

#1292109

On Tue, Dec 15, 2015 at 09:50:14AM +0100, Luca Abeni wrote:
> Strictly speaking, the active utilisation must be updated when a task
> wakes up and when a task sleeps/terminates (but when a task sleeps/terminates
> you cannot decrease the active utilisation immediately: you have to wait
> some time because the task might already have used part of its "future
> utilisation").
> The active utilisation must not be updated when a task is throttled: a
> task is throttled when its current runtime is 0, so it already used all
> of its utilisation for the current period (think about two tasks with
> runtime=50ms and period 100ms: they consume 100% of the time on a CPU,
> and when the first task consumed all of its runtime, you cannot decrease
> the active utilisation).

Hehe, this reminds me of the lag tracking in EEVDF/WF2Q/BFQ etc., that
had similar issues.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1292178

On 12/15/2015 01:23 PM, Peter Zijlstra wrote:
> On Tue, Dec 15, 2015 at 09:50:14AM +0100, Luca Abeni wrote:
>> Strictly speaking, the active utilisation must be updated when a task
>> wakes up and when a task sleeps/terminates (but when a task sleeps/terminates
>> you cannot decrease the active utilisation immediately: you have to wait
>> some time because the task might already have used part of its "future
>> utilisation").
>> The active utilisation must not be updated when a task is throttled: a
>> task is throttled when its current runtime is 0, so it already used all
>> of its utilisation for the current period (think about two tasks with
>> runtime=50ms and period 100ms: they consume 100% of the time on a CPU,
>> and when the first task consumed all of its runtime, you cannot decrease
>> the active utilisation).
>
> Hehe, this reminds me of the lag tracking in EEVDF/WF2Q/BFQ etc., that
> had similar issues.
Yes, I remember EEVDF and similar algorithms also needed to keep track of
the current lag (and to reset it at a later time respect to the "task is
blocking" event). I do not remember the exact details, but I "borrowed" the
"0-lag time" name from one of those papers :)


				Luca

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1292123 — Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity

On 15 December 2015 at 09:50, Luca Abeni <luca.abeni@unitn.it> wrote:
> On 12/15/2015 05:59 AM, Vincent Guittot wrote:
> [...]
>>>>>
>>>>> So I don't think this is right. AFAICT this projects the WCET as the
>>>>> amount of time actually used by DL. This will, under many
>>>>> circumstances, vastly overestimate the amount of time actually
>>>>> spend on it. Therefore unduly pessimisme the fair capacity of this
>>>>> CPU.
>>>>
>>>>
>>>> I agree that if the WCET is far from reality, we will underestimate
>>>> available capacity for CFS. Have you got some use case in mind which
>>>> overestimates the WCET ?
>>>> If we can't rely on this parameters to evaluate the amount of capacity
>>>> used by deadline scheduler on a core, this will imply that we can't
>>>> also use it for requesting capacity to cpufreq and we should fallback
>>>> on a monitoring mechanism which reacts to a change instead of
>>>> anticipating it.
>>>
>>> I think a more "theoretically sound" approach would be to track the
>>> _active_ utilisation (informally speaking, the sum of the utilisations
>>> of the tasks that are actually active on a core - the exact definition
>>> of "active" is the trick here).
>>
>>
>> The point is that we probably need 2 definitions of "active" tasks.
>
> Ok; thanks for clarifying. I do not know much about the remaining capacity
> used by CFS; however, from what you write I guess CFS really need an
> "average"
> utilisation (while frequency scaling needs the active utilisation).

yes. this patch is only about the "average" utilization

> So, I suspect you really need to track 2 different things.
> From a quick look at the code that is currently in mainline, it seems to
> me that it does a reasonable thing for tracking the remaining capacity
> used by CFS...
>
>> The 1st one would be used to scale the frequency. From a power saving
>> point of view, it have to reflect the minimum frequency needed at the
>> current time to handle all works without missing deadline.
>
> Right. And it can be computed as shown in the GRUB-PA paper I mentioned
> in a previous mail (that is, by tracking the active utilisation, as done
> by my patches).

I fully trust you on that part.
>
>> This one
>> should be updated quite often with the wake up and the sleep of tasks
>> as well as the throttling.
>
> Strictly speaking, the active utilisation must be updated when a task
> wakes up and when a task sleeps/terminates (but when a task
> sleeps/terminates
> you cannot decrease the active utilisation immediately: you have to wait
> some time because the task might already have used part of its "future
> utilisation").
> The active utilisation must not be updated when a task is throttled: a
> task is throttled when its current runtime is 0, so it already used all
> of its utilisation for the current period (think about two tasks with
> runtime=50ms and period 100ms: they consume 100% of the time on a CPU,
> and when the first task consumed all of its runtime, you cannot decrease
> the active utilisation).

 I haven't read the paper you pointed in the previous email but it's
on my todo list. Does the GRUB-PA take into account the frequency
transition when selecting the best frequency ?

>
>> The 2nd definition is used to compute the remaining capacity for the
>> CFS scheduler. This one doesn't need to be updated at each wake/sleep
>> of a deadline task but should reflect the capacity used by deadline in
>> a larger time scale. The latter will be used by the CFS scheduler  at
>> the periodic load balance pace
>
> Ok, so as I wrote above this really looks like an average utilisation.
> My impression (but I do not know the CFS code too much) is that the mainline
> kernel is currently doing the right thing to compute it, so maybe there is
> no
> need to change the current code in this regard.
> If the current code is not acceptable for some reason, an alternative would
> be to measure the active utilisation for frequency scaling, and then apply a
> low-pass filter to it for CFS.
>
>
>                                 Luca
>
>
>>
>>> As done, for example, here:
>>> https://github.com/lucabe72/linux-reclaiming/tree/track-utilisation-v2
>>> (in particular, see
>>>
>>> https://github.com/lucabe72/linux-reclaiming/commit/49fc786a1c453148625f064fa38ea538470df55b
>>> )
>>> I understand this approach might look too complex... But I think it is
>>> much less pessimistic while still being "safe".
>>> If there is something that I can do to make that code more acceptable,
>>> let me know.
>>>
>>>
>>>                          Luca
>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1292179

On 12/15/2015 01:43 PM, Vincent Guittot wrote:
[...]
>>>>> I agree that if the WCET is far from reality, we will underestimate
>>>>> available capacity for CFS. Have you got some use case in mind which
>>>>> overestimates the WCET ?
>>>>> If we can't rely on this parameters to evaluate the amount of capacity
>>>>> used by deadline scheduler on a core, this will imply that we can't
>>>>> also use it for requesting capacity to cpufreq and we should fallback
>>>>> on a monitoring mechanism which reacts to a change instead of
>>>>> anticipating it.
>>>>
>>>> I think a more "theoretically sound" approach would be to track the
>>>> _active_ utilisation (informally speaking, the sum of the utilisations
>>>> of the tasks that are actually active on a core - the exact definition
>>>> of "active" is the trick here).
>>>
>>>
>>> The point is that we probably need 2 definitions of "active" tasks.
>>
>> Ok; thanks for clarifying. I do not know much about the remaining capacity
>> used by CFS; however, from what you write I guess CFS really need an
>> "average"
>> utilisation (while frequency scaling needs the active utilisation).
>
> yes. this patch is only about the "average" utilization
Ok; so, I think that the approach of this patch is too pessimistic (it uses
the "worst-case" utilisation as an estimation of the average one).

>>> This one
>>> should be updated quite often with the wake up and the sleep of tasks
>>> as well as the throttling.
>>
>> Strictly speaking, the active utilisation must be updated when a task
>> wakes up and when a task sleeps/terminates (but when a task
>> sleeps/terminates
>> you cannot decrease the active utilisation immediately: you have to wait
>> some time because the task might already have used part of its "future
>> utilisation").
>> The active utilisation must not be updated when a task is throttled: a
>> task is throttled when its current runtime is 0, so it already used all
>> of its utilisation for the current period (think about two tasks with
>> runtime=50ms and period 100ms: they consume 100% of the time on a CPU,
>> and when the first task consumed all of its runtime, you cannot decrease
>> the active utilisation).
>
>   I haven't read the paper you pointed in the previous email but it's
> on my todo list. Does the GRUB-PA take into account the frequency
> transition when selecting the best frequency ?
I do not know...
As far as I understand, the GRUB-PA approach is simple: if the active
utilisation of SCHED_DEADLINE tasks is Ua, then the CPU frequency can be
reduced to the maximum possible frequency multiplied by Ua (of course,
this must be adjusted a little bit, because the original GRUB-PA paper
only considered real-time/SCHED_DEADLINE tasks... To leave some CPU time
for other tasks, you have to increase Ua a little bit).

Some time ago one of the authors of the GRUB-PA paper told me that they
evaluated the performance of the algorithm by simulating the behaviour of
a real CPU, but I do not know the details, and I do not know if they took
the frequency transition into account.



				Luca
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1292138 — Re: [RFCv6 PATCH 09/10] sched: deadline: use deadline bandwidth in scale_rt_capacity

On 15 December 2015 at 09:50, Luca Abeni <luca.abeni@unitn.it> wrote:
> On 12/15/2015 05:59 AM, Vincent Guittot wrote:
> [...]
>>>>>
>>>>> So I don't think this is right. AFAICT this projects the WCET as the
>>>>> amount of time actually used by DL. This will, under many
>>>>> circumstances, vastly overestimate the amount of time actually
>>>>> spend on it. Therefore unduly pessimisme the fair capacity of this
>>>>> CPU.
>>>>
>>>>

[snip]

>> The 2nd definition is used to compute the remaining capacity for the
>> CFS scheduler. This one doesn't need to be updated at each wake/sleep
>> of a deadline task but should reflect the capacity used by deadline in
>> a larger time scale. The latter will be used by the CFS scheduler  at
>> the periodic load balance pace
>
> Ok, so as I wrote above this really looks like an average utilisation.
> My impression (but I do not know the CFS code too much) is that the mainline
> kernel is currently doing the right thing to compute it, so maybe there is
> no
> need to change the current code in this regard.
> If the current code is not acceptable for some reason, an alternative would
> be to measure the active utilisation for frequency scaling, and then apply a
> low-pass filter to it for CFS.

In this case, it's probably easier to split what is already done into
a rt_avg metric  and a dl_avg metric

Vincent
>
>
>                                 Luca
>
>
>>
>>> As done, for example, here:
>>> https://github.com/lucabe72/linux-reclaiming/tree/track-utilisation-v2
>>> (in particular, see
>>>
>>> https://github.com/lucabe72/linux-reclaiming/commit/49fc786a1c453148625f064fa38ea538470df55b
>>> )
>>> I understand this approach might look too complex... But I think it is
>>> much less pessimistic while still being "safe".
>>> If there is something that I can do to make that code more acceptable,
>>> let me know.
>>>
>>>
>>>                          Luca
>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1292196

On 12/15/2015 01:58 PM, Vincent Guittot wrote:
> On 15 December 2015 at 09:50, Luca Abeni <luca.abeni@unitn.it> wrote:
>> On 12/15/2015 05:59 AM, Vincent Guittot wrote:
>> [...]
>>>>>>
>>>>>> So I don't think this is right. AFAICT this projects the WCET as the
>>>>>> amount of time actually used by DL. This will, under many
>>>>>> circumstances, vastly overestimate the amount of time actually
>>>>>> spend on it. Therefore unduly pessimisme the fair capacity of this
>>>>>> CPU.
>>>>>
>>>>>
>
> [snip]
>
>>> The 2nd definition is used to compute the remaining capacity for the
>>> CFS scheduler. This one doesn't need to be updated at each wake/sleep
>>> of a deadline task but should reflect the capacity used by deadline in
>>> a larger time scale. The latter will be used by the CFS scheduler  at
>>> the periodic load balance pace
>>
>> Ok, so as I wrote above this really looks like an average utilisation.
>> My impression (but I do not know the CFS code too much) is that the mainline
>> kernel is currently doing the right thing to compute it, so maybe there is
>> no
>> need to change the current code in this regard.
>> If the current code is not acceptable for some reason, an alternative would
>> be to measure the active utilisation for frequency scaling, and then apply a
>> low-pass filter to it for CFS.
>
> In this case, it's probably easier to split what is already done into
> a rt_avg metric  and a dl_avg metric
Yes, I think this could be the best approach for what concerns the average
utilisation used by CFS.



				Luca
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | linux.kernel

csiph-web