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

Groups > linux.kernel > #1468340 > unrolled thread

Re: [PATCH v1 00/10] Optimize sched avgs computation and implement flat util hierarchy

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 v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Yuyang Du <yuyang.du@intel.com> - 2016-08-23 09:30 +0200
    Re: [PATCH v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Vincent Guittot <vincent.guittot@linaro.org> - 2016-08-23 15:40 +0200
      Re: [PATCH v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Peter Zijlstra <peterz@infradead.org> - 2016-08-23 16:20 +0200
        Re: [PATCH v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Vincent Guittot <vincent.guittot@linaro.org> - 2016-08-23 16:50 +0200
          Re: [PATCH v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Dietmar Eggemann <dietmar.eggemann@arm.com> - 2016-08-23 17:50 +0200
          Re: [PATCH v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Morten Rasmussen <morten.rasmussen@arm.com> - 2016-08-24 11:10 +0200
            Re: [PATCH v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Vincent Guittot <vincent.guittot@linaro.org> - 2016-08-24 11:50 +0200
        Re: [PATCH v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Yuyang Du <yuyang.du@intel.com> - 2016-08-24 05:10 +0200
      Re: [PATCH v1 00/10] Optimize sched avgs computation and implement  flat util hierarchy Yuyang Du <yuyang.du@intel.com> - 2016-08-24 05:10 +0200

#1468340 — Re: [PATCH v1 00/10] Optimize sched avgs computation and implement flat util hierarchy

Hi Peter and others,

Could you give this patchset a look?

Thanks,
Yuyang

On Wed, Aug 10, 2016 at 08:23:52AM +0800, Yuyang Du wrote:
> On Wed, Aug 10, 2016 at 08:14:45AM +0800, Yuyang Du wrote:
> > Hi Peter,
> > 
> > I should have sent out my flat util hierarchy implementation long time ago,
> > actually code was there but not rebased. I finally have time to do this,
> > so here it is. There are also other proposals to solve migrated tasks' util
> > mobility problem, such as the ones from Dietmar and Vincent.
> > 
> > The sched avgs computation optimization was initiated for the flat util thing,
> > so I send them out together.
> > 
> > According to Morten and Ben's feedback, I removed 32-bit as a period's upper
> > bound limit. So, thanks a lot to them.
> > 
> 
> To compare the effectiveness of the flat util hierarchy, a simple experiment
> was done: rt-app to generate a 50% duty-cycling workload (100us/200us), and
> in the meantime a script to set the CPU affinity of the task, alternating
> to taskset the task to run on CPU x and CPU y every 0.3 sec, so forcing the
> task to ping-pong migrate. By auto-group and ssh itself, the task under test
> is at the third level task group.
> 
> So compare the top cfs_rq's util_avg (group_hierarchy.jpg) vs. the rq's util_avg
> (flat_hierarchy.jpg)
> 
> Thanks,
> Yuyang

[toc] | [next] | [standalone]

#1468551

On 23 August 2016 at 01:26, Yuyang Du <yuyang.du@intel.com> wrote:
>
> Hi Peter and others,
>
> Could you give this patchset a look?

Hi Yuyang,

I still wonder if using a flat util hierarchy is the right solution to
solve this problem with utilization and task group. I have noticed
exact same issues with load that generates weird task placement
decision and i think that we should probably try to solve both wrong
behavior with same mechanism. but this is not possible with flat
hierarchy for load

Let me take an example.
TA is a always running task on CPU1 in group /root/level1/
TB wakes up on CPU0 and moves TA into group /root/level2/
Even if TA stays on CPU1, runnable_load_avg of CPU1 root cfs rq will become 0.
Then, TB forks a new task TC. TC will probably be schedule on CPU1
because its root cfs_rq's runnable_load_avg is null and CPU1 is the
next CPU after CPU0

Similar behavior can happen when TA migrates

Beside flat utilization consideration, i'm going to have a look at the
optimization part

Regards,
Vincent

>
>
> Thanks,
> Yuyang
>
> On Wed, Aug 10, 2016 at 08:23:52AM +0800, Yuyang Du wrote:
> > On Wed, Aug 10, 2016 at 08:14:45AM +0800, Yuyang Du wrote:
> > > Hi Peter,
> > >
> > > I should have sent out my flat util hierarchy implementation long time ago,
> > > actually code was there but not rebased. I finally have time to do this,
> > > so here it is. There are also other proposals to solve migrated tasks' util
> > > mobility problem, such as the ones from Dietmar and Vincent.
> > >
> > > The sched avgs computation optimization was initiated for the flat util thing,
> > > so I send them out together.
> > >
> > > According to Morten and Ben's feedback, I removed 32-bit as a period's upper
> > > bound limit. So, thanks a lot to them.
> > >
> >
> > To compare the effectiveness of the flat util hierarchy, a simple experiment
> > was done: rt-app to generate a 50% duty-cycling workload (100us/200us), and
> > in the meantime a script to set the CPU affinity of the task, alternating
> > to taskset the task to run on CPU x and CPU y every 0.3 sec, so forcing the
> > task to ping-pong migrate. By auto-group and ssh itself, the task under test
> > is at the third level task group.
> >
> > So compare the top cfs_rq's util_avg (group_hierarchy.jpg) vs. the rq's util_avg
> > (flat_hierarchy.jpg)
> >
> > Thanks,
> > Yuyang
>
>
>

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

#1468587

On Tue, Aug 23, 2016 at 03:28:19PM +0200, Vincent Guittot wrote:
> I still wonder if using a flat util hierarchy is the right solution to
> solve this problem with utilization and task group. I have noticed
> exact same issues with load that generates weird task placement
> decision and i think that we should probably try to solve both wrong
> behavior with same mechanism. but this is not possible with flat
> hierarchy for load
> 
> Let me take an example.
> TA is a always running task on CPU1 in group /root/level1/
> TB wakes up on CPU0 and moves TA into group /root/level2/
> Even if TA stays on CPU1, runnable_load_avg of CPU1 root cfs rq will become 0.

Because while we migrate the load_avg on /root/level2, we do not
propagate the load_avg up the hierarchy?

And always propagating everyrthing up will indeed also fix the
utilization issue.

Of course, doing that propagation has its costs..

Didn't you post a patch doing just this a while ago?

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

#1468609

On 23 August 2016 at 16:13, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Aug 23, 2016 at 03:28:19PM +0200, Vincent Guittot wrote:
>> I still wonder if using a flat util hierarchy is the right solution to
>> solve this problem with utilization and task group. I have noticed
>> exact same issues with load that generates weird task placement
>> decision and i think that we should probably try to solve both wrong
>> behavior with same mechanism. but this is not possible with flat
>> hierarchy for load
>>
>> Let me take an example.
>> TA is a always running task on CPU1 in group /root/level1/
>> TB wakes up on CPU0 and moves TA into group /root/level2/
>> Even if TA stays on CPU1, runnable_load_avg of CPU1 root cfs rq will become 0.
>
> Because while we migrate the load_avg on /root/level2, we do not
> propagate the load_avg up the hierarchy?

yes. At now, the load of a cfs_rq and the load of its sched_entity
that represents it at parent level are disconnected

>
> And always propagating everyrthing up will indeed also fix the
> utilization issue.
>
> Of course, doing that propagation has its costs..

yes, that's the counterpart

>
> Didn't you post a patch doing just this a while ago?

My patch was doing that but only for utilization and i have start to
work on adding the propagation of load as well

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

#1468661

On 23/08/16 15:45, Vincent Guittot wrote:
> On 23 August 2016 at 16:13, Peter Zijlstra <peterz@infradead.org> wrote:
>> On Tue, Aug 23, 2016 at 03:28:19PM +0200, Vincent Guittot wrote:
>>> I still wonder if using a flat util hierarchy is the right solution to
>>> solve this problem with utilization and task group. I have noticed
>>> exact same issues with load that generates weird task placement
>>> decision and i think that we should probably try to solve both wrong
>>> behavior with same mechanism. but this is not possible with flat
>>> hierarchy for load
>>>
>>> Let me take an example.
>>> TA is a always running task on CPU1 in group /root/level1/
>>> TB wakes up on CPU0 and moves TA into group /root/level2/
>>> Even if TA stays on CPU1, runnable_load_avg of CPU1 root cfs rq will become 0.
>>
>> Because while we migrate the load_avg on /root/level2, we do not
>> propagate the load_avg up the hierarchy?
> 
> yes. At now, the load of a cfs_rq and the load of its sched_entity
> that represents it at parent level are disconnected

I guess you say 'disconnected' because cfs_rq and se (w/ cfs_rq eq.
se->my_q) are now independent pelt signals where as before the rewrite
they were 'connected' for load via __update_tg_runnable_avg(),
__update_group_entity_contrib() in __update_entity_load_avg_contrib()
and for utilization via 'se->avg.utilization_avg_contrib =
group_cfs_rq(se)->utilization_load_avg' in
__update_entity_utilization_avg_contrib().

IMHO, there was also this 'connection' between se and cfs_rq (w/
se->cfs_rq eq. cfs_rq) in update_entity_load_avg(, update_cfs_rq = 1)
which guaranteed that the change in the se was immediately visible on
the cfs_rq representing the parent task group.

 if (se->on_rq) {
   cfs_rq->runnable_load_avg += contrib_delta;
   cfs_rq->utilization_load_avg += utilization_delta;
 }

I guess, these two things somehow belonged together to achieve this
load/util propagation.

>> And always propagating everyrthing up will indeed also fix the
>> utilization issue.
>>
>> Of course, doing that propagation has its costs..
> 
> yes, that's the counterpart
> 
>>
>> Didn't you post a patch doing just this a while ago?
> 
> My patch was doing that but only for utilization and i have start to
> work on adding the propagation of load as well
> 

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

#1469238

On Tue, Aug 23, 2016 at 04:45:57PM +0200, Vincent Guittot wrote:
> On 23 August 2016 at 16:13, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Tue, Aug 23, 2016 at 03:28:19PM +0200, Vincent Guittot wrote:
> >> I still wonder if using a flat util hierarchy is the right solution to
> >> solve this problem with utilization and task group. I have noticed
> >> exact same issues with load that generates weird task placement
> >> decision and i think that we should probably try to solve both wrong
> >> behavior with same mechanism. but this is not possible with flat
> >> hierarchy for load
> >>
> >> Let me take an example.
> >> TA is a always running task on CPU1 in group /root/level1/
> >> TB wakes up on CPU0 and moves TA into group /root/level2/
> >> Even if TA stays on CPU1, runnable_load_avg of CPU1 root cfs rq will become 0.
> >
> > Because while we migrate the load_avg on /root/level2, we do not
> > propagate the load_avg up the hierarchy?
> 
> yes. At now, the load of a cfs_rq and the load of its sched_entity
> that represents it at parent level are disconnected
> 
> >
> > And always propagating everyrthing up will indeed also fix the
> > utilization issue.
> >
> > Of course, doing that propagation has its costs..
> 
> yes, that's the counterpart
> 
> >
> > Didn't you post a patch doing just this a while ago?
> 
> My patch was doing that but only for utilization and i have start to
> work on adding the propagation of load as well

As Dietmar mentioned already, the 'disconnect' is a feature of the PELT
rewrite. Paul and Ben's original implementation had full propagation up
and down the hierarchy. IIRC, one of the key points of the rewrite was
more 'stable' signals, which we would loose by re-introducing immediate
updates throughout hierarchy.

It is a significant change to group scheduling, so I'm a bit surprised
that nobody has observed any problems post the rewrite. But maybe most
users don't care about the load-balance being slightly off when tasks
have migrated or new tasks are added to a group.

If we want to re-introduce propagation of both load and utilization I
would suggest that we just look at the original implementation. It
seemed to work.

Handling utilization and load differently will inevitably result in more
code. The 'flat hierarchy' approach seems slightly less complicated, but
it prevents us from using group utilization later should we wish to do
so. It might for example become useful for the schedutil cpufreq
governor should it ever consider selecting frequencies differently based
on whether the current task is in a (specific) group or not.

Morten

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

#1469300

On 24 August 2016 at 10:54, Morten Rasmussen <morten.rasmussen@arm.com> wrote:
> On Tue, Aug 23, 2016 at 04:45:57PM +0200, Vincent Guittot wrote:
>> On 23 August 2016 at 16:13, Peter Zijlstra <peterz@infradead.org> wrote:
>> > On Tue, Aug 23, 2016 at 03:28:19PM +0200, Vincent Guittot wrote:
>> >> I still wonder if using a flat util hierarchy is the right solution to
>> >> solve this problem with utilization and task group. I have noticed
>> >> exact same issues with load that generates weird task placement
>> >> decision and i think that we should probably try to solve both wrong
>> >> behavior with same mechanism. but this is not possible with flat
>> >> hierarchy for load
>> >>
>> >> Let me take an example.
>> >> TA is a always running task on CPU1 in group /root/level1/
>> >> TB wakes up on CPU0 and moves TA into group /root/level2/
>> >> Even if TA stays on CPU1, runnable_load_avg of CPU1 root cfs rq will become 0.
>> >
>> > Because while we migrate the load_avg on /root/level2, we do not
>> > propagate the load_avg up the hierarchy?
>>
>> yes. At now, the load of a cfs_rq and the load of its sched_entity
>> that represents it at parent level are disconnected
>>
>> >
>> > And always propagating everyrthing up will indeed also fix the
>> > utilization issue.
>> >
>> > Of course, doing that propagation has its costs..
>>
>> yes, that's the counterpart
>>
>> >
>> > Didn't you post a patch doing just this a while ago?
>>
>> My patch was doing that but only for utilization and i have start to
>> work on adding the propagation of load as well
>
> As Dietmar mentioned already, the 'disconnect' is a feature of the PELT
> rewrite. Paul and Ben's original implementation had full propagation up
> and down the hierarchy. IIRC, one of the key points of the rewrite was
> more 'stable' signals, which we would loose by re-introducing immediate
> updates throughout hierarchy.
>
> It is a significant change to group scheduling, so I'm a bit surprised
> that nobody has observed any problems post the rewrite. But maybe most
> users don't care about the load-balance being slightly off when tasks
> have migrated or new tasks are added to a group.
>
> If we want to re-introduce propagation of both load and utilization I
> would suggest that we just look at the original implementation. It
> seemed to work.

The previous implementation was propagating the changes of load and
utilization of an entity for most of its update whereas we only need
to sync when entity is attached/detached or migrated

>
> Handling utilization and load differently will inevitably result in more
> code. The 'flat hierarchy' approach seems slightly less complicated, but
> it prevents us from using group utilization later should we wish to do
> so. It might for example become useful for the schedutil cpufreq
> governor should it ever consider selecting frequencies differently based
> on whether the current task is in a (specific) group or not.
>
> Morten

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

#1469048

On Tue, Aug 23, 2016 at 04:13:41PM +0200, Peter Zijlstra wrote:
> On Tue, Aug 23, 2016 at 03:28:19PM +0200, Vincent Guittot wrote:
> > I still wonder if using a flat util hierarchy is the right solution to
> > solve this problem with utilization and task group. I have noticed
> > exact same issues with load that generates weird task placement
> > decision and i think that we should probably try to solve both wrong
> > behavior with same mechanism. but this is not possible with flat
> > hierarchy for load
> > 
> > Let me take an example.
> > TA is a always running task on CPU1 in group /root/level1/
> > TB wakes up on CPU0 and moves TA into group /root/level2/
> > Even if TA stays on CPU1, runnable_load_avg of CPU1 root cfs rq will become 0.
> 
> Because while we migrate the load_avg on /root/level2, we do not
> propagate the load_avg up the hierarchy?
> 
> And always propagating everyrthing up will indeed also fix the
> utilization issue.

Yes, but for util it's actually irrespective to the number of
hirarchical levels, just propagating directly to the top cfs_rq
or simply rq will do. In other words, it's flat :)
 
> Of course, doing that propagation has its costs..
> 
> Didn't you post a patch doing just this a while ago?

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

#1469047

Hi Vincent,

On Tue, Aug 23, 2016 at 03:28:19PM +0200, Vincent Guittot wrote:
> I still wonder if using a flat util hierarchy is the right solution to
> solve this problem with utilization and task group. I have noticed
> exact same issues with load that generates weird task placement
> decision and i think that we should probably try to solve both wrong
> behavior with same mechanism. but this is not possible with flat
> hierarchy for load

I agree both util and load have the same hierarchical propagation
problem.

But util and load are different with respect to task group distribution
among CPUs and along hierarchical structure. Util is "fundamentally"
flat (CPU's util = tasks' util), so it's pretty natural as well as
simple to implement a flat hierarchy util. And because of that, I
feel util propagating up the hierarchical structure seems unnecessary.

It might be better to have a converged mechanism to solve both, but
it shouldn't be necessary. Right?

> Let me take an example.
> TA is a always running task on CPU1 in group /root/level1/
> TB wakes up on CPU0 and moves TA into group /root/level2/
> Even if TA stays on CPU1, runnable_load_avg of CPU1 root cfs rq will become 0.
> Then, TB forks a new task TC. TC will probably be schedule on CPU1
> because its root cfs_rq's runnable_load_avg is null and CPU1 is the
> next CPU after CPU0
> 
> Similar behavior can happen when TA migrates
> 
> Beside flat utilization consideration, i'm going to have a look at the

Many thanks.

Yuyang

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web