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

Groups > linux.kernel > #1702934 > unrolled thread

Re: wake_wide mechanism clarification

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: wake_wide mechanism clarification Brendan Jackman <brendan.jackman@arm.com> - 2017-08-03 13:00 +0200
    Re: wake_wide mechanism clarification Josef Bacik <josef@toxicpanda.com> - 2017-08-03 15:20 +0200
      Re: wake_wide mechanism clarification Brendan Jackman <brendan.jackman@arm.com> - 2017-08-03 17:10 +0200
        Re: wake_wide mechanism clarification Atish Patra <atish.patra@oracle.com> - 2017-08-09 23:30 +0200
          Re: wake_wide mechanism clarification Brendan Jackman <brendan.jackman@arm.com> - 2017-08-10 11:50 +0200
            Re: wake_wide mechanism clarification Atish Patra <atish.patra@oracle.com> - 2017-08-10 19:50 +0200

#1702934 — Re: wake_wide mechanism clarification

Hi,

On Fri, Jun 30 2017 at 17:55, Josef Bacik wrote:
> On Fri, Jun 30, 2017 at 07:02:20PM +0200, Mike Galbraith wrote:
>> On Fri, 2017-06-30 at 10:28 -0400, Josef Bacik wrote:
>> > On Thu, Jun 29, 2017 at 08:04:59PM -0700, Joel Fernandes wrote:
>> >
>> > > That makes sense that we multiply slave's flips by a factor because
>> > > its low, but I still didn't get why the factor is chosen to be
>> > > llc_size instead of something else for the multiplication with slave
>> > > (slave * factor).
>>
>> > Yeah I don't know why llc_size was chosen...
>>
>> static void update_top_cache_domain(int cpu)
>> {
>> struct sched_domain_shared *sds = NULL;
>> struct sched_domain *sd;
>> int id = cpu;
>> int size = 1;
>>
>> sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
>> if (sd) {
>> id = cpumask_first(sched_domain_span(sd));
>> size = cpumask_weight(sched_domain_span(sd));
>> sds = sd->shared;
>> }
>>
>> rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
>> per_cpu(sd_llc_size, cpu) = size;
>>
>> The goal of wake wide was to approximate when pulling would be a futile
>> consolidation effort and counterproductive to scaling. 'course with
>> ever increasing socket size, any 1:N waker is ever more likely to run
>> out of CPU for its one and only self (slamming into scaling wall)
>> before it needing to turn its minions loose to conquer the world.
>>
>> Something else to consider: network interrupt waking multiple workers
>> at high frequency. If the waking CPU is idle, do you really want to
>> place a worker directly in front of a tattoo artist, or is it better
>> off nearly anywhere but there?
>>
>> If the box is virtual, with no topology exposed (or real but ancient)
>> to let select_idle_sibling() come to the rescue, two workers can even
>> get tattooed simultaneously (see sync wakeup).
>>
>
> Heuristics are hard, news at 11.  I think messing with wake_wide() itself is too
> big of a hammer, we probably need a middle ground.  I'm messing with it right
> now so it's too early to say for sure, but i _suspect_ the bigger latencies we
> see are not because we overload the cpu we're trying to pull to, but because
> when we fail to do the wake_affine() we only look at siblings of the affine_sd
> instead of doing the full "find the idlest cpu in the land!" thing.

This is the problem I've been hitting lately. My use case is 1 task per
CPU on ARM big.LITTLE (asymmetrical CPU capacity). The workload is 1
task per CPU, they all do X amount of work then pthread_barrier_wait
(i.e. sleep until the last task finishes its X and hits the barrier). On
big.LITTLE, the tasks which get a "big" CPU finish faster, and then
those CPUs pull over the tasks that are still running:

     v CPU v           ->time->

                    -------------
   0  (big)         11111  /333
                    -------------
   1  (big)         22222   /444|
                    -------------
   2  (LITTLE)      333333/
                    -------------
   3  (LITTLE)      444444/
                    -------------

Now when task 4 hits the barrier (at |) and wakes the others up, there
are 4 tasks with prev_cpu=<big> and 0 tasks with
prev_cpu=<little>. Assuming that those wakeups happen on CPU4,
regardless of wake_affine, want_affine means that we'll only look in
sd_llc (cpus 0 and 1), so tasks will be unnecessarily coscheduled on the
bigs until the next load balance, something like this:

     v CPU v           ->time->

                    ------------------------
   0  (big)         11111  /333  31313\33333
                    ------------------------
   1  (big)         22222   /444|424\4444444
                    ------------------------
   2  (LITTLE)      333333/          \222222
                    ------------------------
   3  (LITTLE)      444444/            \1111
                    ------------------------
                                 ^^^
                           underutilization

> I _think_
> the answer is to make select_idle_sibling() try less hard to find something
> workable and only use obviously idle cpu's in the affine sd, and fall back to
> the full load balance esque search.

So this idea of allowing select_idle_sibling to fail, and falling back
to the slow path, would help me too, I think.

This is also why I was playing with your
don't-affine-recently-balanced-tasks patch[1], which also helps my case
since it prevents want_affine for tasks 3 and 4 (which were recently
moved by an active balance).

[1] https://marc.info/?l=linux-kernel&m=150003849602535&w=2
    (also linked elsewhere in this thread)

> This would make affine misses really expensive, but we can probably negate this
> by tracking per task how often it misses the target, and use that to adjust when
> we do wake_affine in the future for that task.  Still experimenting some, I just
> found out a few hours ago I need to rework some of this to fix my cpu imbalance
> problem with cgroups, so once I get something working I'll throw it your way to
> take a look.  Thanks,

Cheers,
Brendan

[toc] | [next] | [standalone]

#1703096

On Thu, Aug 03, 2017 at 11:53:19AM +0100, Brendan Jackman wrote:
> 
> Hi,
> 
> On Fri, Jun 30 2017 at 17:55, Josef Bacik wrote:
> > On Fri, Jun 30, 2017 at 07:02:20PM +0200, Mike Galbraith wrote:
> >> On Fri, 2017-06-30 at 10:28 -0400, Josef Bacik wrote:
> >> > On Thu, Jun 29, 2017 at 08:04:59PM -0700, Joel Fernandes wrote:
> >> >
> >> > > That makes sense that we multiply slave's flips by a factor because
> >> > > its low, but I still didn't get why the factor is chosen to be
> >> > > llc_size instead of something else for the multiplication with slave
> >> > > (slave * factor).
> >>
> >> > Yeah I don't know why llc_size was chosen...
> >>
> >> static void update_top_cache_domain(int cpu)
> >> {
> >> struct sched_domain_shared *sds = NULL;
> >> struct sched_domain *sd;
> >> int id = cpu;
> >> int size = 1;
> >>
> >> sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
> >> if (sd) {
> >> id = cpumask_first(sched_domain_span(sd));
> >> size = cpumask_weight(sched_domain_span(sd));
> >> sds = sd->shared;
> >> }
> >>
> >> rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
> >> per_cpu(sd_llc_size, cpu) = size;
> >>
> >> The goal of wake wide was to approximate when pulling would be a futile
> >> consolidation effort and counterproductive to scaling. 'course with
> >> ever increasing socket size, any 1:N waker is ever more likely to run
> >> out of CPU for its one and only self (slamming into scaling wall)
> >> before it needing to turn its minions loose to conquer the world.
> >>
> >> Something else to consider: network interrupt waking multiple workers
> >> at high frequency. If the waking CPU is idle, do you really want to
> >> place a worker directly in front of a tattoo artist, or is it better
> >> off nearly anywhere but there?
> >>
> >> If the box is virtual, with no topology exposed (or real but ancient)
> >> to let select_idle_sibling() come to the rescue, two workers can even
> >> get tattooed simultaneously (see sync wakeup).
> >>
> >
> > Heuristics are hard, news at 11.  I think messing with wake_wide() itself is too
> > big of a hammer, we probably need a middle ground.  I'm messing with it right
> > now so it's too early to say for sure, but i _suspect_ the bigger latencies we
> > see are not because we overload the cpu we're trying to pull to, but because
> > when we fail to do the wake_affine() we only look at siblings of the affine_sd
> > instead of doing the full "find the idlest cpu in the land!" thing.
> 
> This is the problem I've been hitting lately. My use case is 1 task per
> CPU on ARM big.LITTLE (asymmetrical CPU capacity). The workload is 1
> task per CPU, they all do X amount of work then pthread_barrier_wait
> (i.e. sleep until the last task finishes its X and hits the barrier). On
> big.LITTLE, the tasks which get a "big" CPU finish faster, and then
> those CPUs pull over the tasks that are still running:
> 
>      v CPU v           ->time->
> 
>                     -------------
>    0  (big)         11111  /333
>                     -------------
>    1  (big)         22222   /444|
>                     -------------
>    2  (LITTLE)      333333/
>                     -------------
>    3  (LITTLE)      444444/
>                     -------------
> 
> Now when task 4 hits the barrier (at |) and wakes the others up, there
> are 4 tasks with prev_cpu=<big> and 0 tasks with
> prev_cpu=<little>. Assuming that those wakeups happen on CPU4,
> regardless of wake_affine, want_affine means that we'll only look in
> sd_llc (cpus 0 and 1), so tasks will be unnecessarily coscheduled on the
> bigs until the next load balance, something like this:
> 
>      v CPU v           ->time->
> 
>                     ------------------------
>    0  (big)         11111  /333  31313\33333
>                     ------------------------
>    1  (big)         22222   /444|424\4444444
>                     ------------------------
>    2  (LITTLE)      333333/          \222222
>                     ------------------------
>    3  (LITTLE)      444444/            \1111
>                     ------------------------
>                                  ^^^
>                            underutilization
> 
> > I _think_
> > the answer is to make select_idle_sibling() try less hard to find something
> > workable and only use obviously idle cpu's in the affine sd, and fall back to
> > the full load balance esque search.
> 
> So this idea of allowing select_idle_sibling to fail, and falling back
> to the slow path, would help me too, I think.

Unfortunately this statement of mine was wrong, I had it in my head that we
would fall back to a find the idlest cpu thing provided we failed to wake
affine, but we just do select_idle_sibling() and expect the load balancer to
move things around as needed.

> 
> This is also why I was playing with your
> don't-affine-recently-balanced-tasks patch[1], which also helps my case
> since it prevents want_affine for tasks 3 and 4 (which were recently
> moved by an active balance).
> 
> [1] https://marc.info/?l=linux-kernel&m=150003849602535&w=2
>     (also linked elsewhere in this thread)
> 

Would you try peter's sched/experimental branch and see how that affects your
workload?  I'm still messing with my patches and I may drop this one as it now
appears to be too aggressive with the new set of patches.  Thanks,

Josef

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

#1703183

On Thu, Aug 03 2017 at 13:15, Josef Bacik wrote:
> On Thu, Aug 03, 2017 at 11:53:19AM +0100, Brendan Jackman wrote:
>>
>> Hi,
>>
>> On Fri, Jun 30 2017 at 17:55, Josef Bacik wrote:
>> > On Fri, Jun 30, 2017 at 07:02:20PM +0200, Mike Galbraith wrote:
>> >> On Fri, 2017-06-30 at 10:28 -0400, Josef Bacik wrote:
>> >> > On Thu, Jun 29, 2017 at 08:04:59PM -0700, Joel Fernandes wrote:
>> >> >
>> >> > > That makes sense that we multiply slave's flips by a factor because
>> >> > > its low, but I still didn't get why the factor is chosen to be
>> >> > > llc_size instead of something else for the multiplication with slave
>> >> > > (slave * factor).
>> >>
>> >> > Yeah I don't know why llc_size was chosen...
>> >>
>> >> static void update_top_cache_domain(int cpu)
>> >> {
>> >> struct sched_domain_shared *sds = NULL;
>> >> struct sched_domain *sd;
>> >> int id = cpu;
>> >> int size = 1;
>> >>
>> >> sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
>> >> if (sd) {
>> >> id = cpumask_first(sched_domain_span(sd));
>> >> size = cpumask_weight(sched_domain_span(sd));
>> >> sds = sd->shared;
>> >> }
>> >>
>> >> rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
>> >> per_cpu(sd_llc_size, cpu) = size;
>> >>
>> >> The goal of wake wide was to approximate when pulling would be a futile
>> >> consolidation effort and counterproductive to scaling. 'course with
>> >> ever increasing socket size, any 1:N waker is ever more likely to run
>> >> out of CPU for its one and only self (slamming into scaling wall)
>> >> before it needing to turn its minions loose to conquer the world.
>> >>
>> >> Something else to consider: network interrupt waking multiple workers
>> >> at high frequency. If the waking CPU is idle, do you really want to
>> >> place a worker directly in front of a tattoo artist, or is it better
>> >> off nearly anywhere but there?
>> >>
>> >> If the box is virtual, with no topology exposed (or real but ancient)
>> >> to let select_idle_sibling() come to the rescue, two workers can even
>> >> get tattooed simultaneously (see sync wakeup).
>> >>
>> >
>> > Heuristics are hard, news at 11.  I think messing with wake_wide() itself is too
>> > big of a hammer, we probably need a middle ground.  I'm messing with it right
>> > now so it's too early to say for sure, but i _suspect_ the bigger latencies we
>> > see are not because we overload the cpu we're trying to pull to, but because
>> > when we fail to do the wake_affine() we only look at siblings of the affine_sd
>> > instead of doing the full "find the idlest cpu in the land!" thing.
>>
>> This is the problem I've been hitting lately. My use case is 1 task per
>> CPU on ARM big.LITTLE (asymmetrical CPU capacity). The workload is 1
>> task per CPU, they all do X amount of work then pthread_barrier_wait
>> (i.e. sleep until the last task finishes its X and hits the barrier). On
>> big.LITTLE, the tasks which get a "big" CPU finish faster, and then
>> those CPUs pull over the tasks that are still running:
>>
>>      v CPU v           ->time->
>>
>>                     -------------
>>    0  (big)         11111  /333
>>                     -------------
>>    1  (big)         22222   /444|
>>                     -------------
>>    2  (LITTLE)      333333/
>>                     -------------
>>    3  (LITTLE)      444444/
>>                     -------------
>>
>> Now when task 4 hits the barrier (at |) and wakes the others up, there
>> are 4 tasks with prev_cpu=<big> and 0 tasks with
>> prev_cpu=<little>. Assuming that those wakeups happen on CPU4,
>> regardless of wake_affine, want_affine means that we'll only look in
>> sd_llc (cpus 0 and 1), so tasks will be unnecessarily coscheduled on the
>> bigs until the next load balance, something like this:
>>
>>      v CPU v           ->time->
>>
>>                     ------------------------
>>    0  (big)         11111  /333  31313\33333
>>                     ------------------------
>>    1  (big)         22222   /444|424\4444444
>>                     ------------------------
>>    2  (LITTLE)      333333/          \222222
>>                     ------------------------
>>    3  (LITTLE)      444444/            \1111
>>                     ------------------------
>>                                  ^^^
>>                            underutilization
>>
>> > I _think_
>> > the answer is to make select_idle_sibling() try less hard to find something
>> > workable and only use obviously idle cpu's in the affine sd, and fall back to
>> > the full load balance esque search.
>>
>> So this idea of allowing select_idle_sibling to fail, and falling back
>> to the slow path, would help me too, I think.
>
> Unfortunately this statement of mine was wrong, I had it in my head that we
> would fall back to a find the idlest cpu thing provided we failed to wake
> affine, but we just do select_idle_sibling() and expect the load balancer to
> move things around as needed.

Ah yes, when wake_affine() returns false, we still do
select_idle_sibling (except in prev_cpu's sd_llc instead of
smp_processor_id()'s), and that is the problem faced by my workload. I
thought you were suggesting to change the flow so that
select_idle_sibling can say "I didn't find any idle siblings - go to the
find_idlest_group path".

>> This is also why I was playing with your
>> don't-affine-recently-balanced-tasks patch[1], which also helps my case
>> since it prevents want_affine for tasks 3 and 4 (which were recently
>> moved by an active balance).
>>
>> [1] https://marc.info/?l=linux-kernel&m=150003849602535&w=2
>>     (also linked elsewhere in this thread)
>>
>
> Would you try peter's sched/experimental branch and see how that affects your
> workload?  I'm still messing with my patches and I may drop this one as it now
> appears to be too aggressive with the new set of patches.  Thanks,

Sure, I'll take a look at those, thanks. I guess the idea of caching
values in LB and then using them in wakeup[2] is a lighter-handed way of
achieving the same thing as last_balance_ts? It won't solve my problem
directly since we'll still only look in sd_llc, but I think it could be
a basis for a way to say "go find_idlest_group path on these tasks" at
the beginning of select_task_rq_fair.

[2] https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/commit/?h=sched/experimental&id=5b4ed509027a5b6f495e6fe871cae850d5762bef

Thanks,
Brendan

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

#1707966

On 08/03/2017 10:05 AM, Brendan Jackman wrote:
>
> On Thu, Aug 03 2017 at 13:15, Josef Bacik wrote:
>> On Thu, Aug 03, 2017 at 11:53:19AM +0100, Brendan Jackman wrote:
>>>
>>> Hi,
>>>
>>> On Fri, Jun 30 2017 at 17:55, Josef Bacik wrote:
>>>> On Fri, Jun 30, 2017 at 07:02:20PM +0200, Mike Galbraith wrote:
>>>>> On Fri, 2017-06-30 at 10:28 -0400, Josef Bacik wrote:
>>>>>> On Thu, Jun 29, 2017 at 08:04:59PM -0700, Joel Fernandes wrote:
>>>>>>
>>>>>>> That makes sense that we multiply slave's flips by a factor because
>>>>>>> its low, but I still didn't get why the factor is chosen to be
>>>>>>> llc_size instead of something else for the multiplication with slave
>>>>>>> (slave * factor).
>>>>>
>>>>>> Yeah I don't know why llc_size was chosen...
>>>>>
>>>>> static void update_top_cache_domain(int cpu)
>>>>> {
>>>>> struct sched_domain_shared *sds = NULL;
>>>>> struct sched_domain *sd;
>>>>> int id = cpu;
>>>>> int size = 1;
>>>>>
>>>>> sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
>>>>> if (sd) {
>>>>> id = cpumask_first(sched_domain_span(sd));
>>>>> size = cpumask_weight(sched_domain_span(sd));
>>>>> sds = sd->shared;
>>>>> }
>>>>>
>>>>> rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
>>>>> per_cpu(sd_llc_size, cpu) = size;
>>>>>
>>>>> The goal of wake wide was to approximate when pulling would be a futile
>>>>> consolidation effort and counterproductive to scaling. 'course with
>>>>> ever increasing socket size, any 1:N waker is ever more likely to run
>>>>> out of CPU for its one and only self (slamming into scaling wall)
>>>>> before it needing to turn its minions loose to conquer the world.
>>>>>
>>>>> Something else to consider: network interrupt waking multiple workers
>>>>> at high frequency. If the waking CPU is idle, do you really want to
>>>>> place a worker directly in front of a tattoo artist, or is it better
>>>>> off nearly anywhere but there?
>>>>>
>>>>> If the box is virtual, with no topology exposed (or real but ancient)
>>>>> to let select_idle_sibling() come to the rescue, two workers can even
>>>>> get tattooed simultaneously (see sync wakeup).
>>>>>
>>>>
>>>> Heuristics are hard, news at 11.  I think messing with wake_wide() itself is too
>>>> big of a hammer, we probably need a middle ground.  I'm messing with it right
>>>> now so it's too early to say for sure, but i _suspect_ the bigger latencies we
>>>> see are not because we overload the cpu we're trying to pull to, but because
>>>> when we fail to do the wake_affine() we only look at siblings of the affine_sd
>>>> instead of doing the full "find the idlest cpu in the land!" thing.
>>>
>>> This is the problem I've been hitting lately. My use case is 1 task per
>>> CPU on ARM big.LITTLE (asymmetrical CPU capacity). The workload is 1
>>> task per CPU, they all do X amount of work then pthread_barrier_wait
>>> (i.e. sleep until the last task finishes its X and hits the barrier). On
>>> big.LITTLE, the tasks which get a "big" CPU finish faster, and then
>>> those CPUs pull over the tasks that are still running:
>>>
>>>      v CPU v           ->time->
>>>
>>>                     -------------
>>>    0  (big)         11111  /333
>>>                     -------------
>>>    1  (big)         22222   /444|
>>>                     -------------
>>>    2  (LITTLE)      333333/
>>>                     -------------
>>>    3  (LITTLE)      444444/
>>>                     -------------
>>>
>>> Now when task 4 hits the barrier (at |) and wakes the others up, there
>>> are 4 tasks with prev_cpu=<big> and 0 tasks with
>>> prev_cpu=<little>. Assuming that those wakeups happen on CPU4,
>>> regardless of wake_affine, want_affine means that we'll only look in
>>> sd_llc (cpus 0 and 1), so tasks will be unnecessarily coscheduled on the
>>> bigs until the next load balance, something like this:
>>>
>>>      v CPU v           ->time->
>>>
>>>                     ------------------------
>>>    0  (big)         11111  /333  31313\33333
>>>                     ------------------------
>>>    1  (big)         22222   /444|424\4444444
>>>                     ------------------------
>>>    2  (LITTLE)      333333/          \222222
>>>                     ------------------------
>>>    3  (LITTLE)      444444/            \1111
>>>                     ------------------------
>>>                                  ^^^
>>>                            underutilization
>>>
>>>> I _think_
>>>> the answer is to make select_idle_sibling() try less hard to find something
>>>> workable and only use obviously idle cpu's in the affine sd, and fall back to
>>>> the full load balance esque search.
>>>
>>> So this idea of allowing select_idle_sibling to fail, and falling back
>>> to the slow path, would help me too, I think.
>>
>> Unfortunately this statement of mine was wrong, I had it in my head that we
>> would fall back to a find the idlest cpu thing provided we failed to wake
>> affine, but we just do select_idle_sibling() and expect the load balancer to
>> move things around as needed.
>
> Ah yes, when wake_affine() returns false, we still do
> select_idle_sibling (except in prev_cpu's sd_llc instead of
> smp_processor_id()'s), and that is the problem faced by my workload. I
> thought you were suggesting to change the flow so that
> select_idle_sibling can say "I didn't find any idle siblings - go to the
> find_idlest_group path".
>
>>> This is also why I was playing with your
>>> don't-affine-recently-balanced-tasks patch[1], which also helps my case
>>> since it prevents want_affine for tasks 3 and 4 (which were recently
>>> moved by an active balance).
>>>
>>> [1] https://marc.info/?l=linux-kernel&m=150003849602535&w=2
>>>     (also linked elsewhere in this thread)
>>>
>>
>> Would you try peter's sched/experimental branch and see how that affects your
>> workload?  I'm still messing with my patches and I may drop this one as it now
>> appears to be too aggressive with the new set of patches.  Thanks,
>
> Sure, I'll take a look at those, thanks. I guess the idea of caching
> values in LB and then using them in wakeup[2] is a lighter-handed way of
> achieving the same thing as last_balance_ts? It won't solve my problem
> directly since we'll still only look in sd_llc, but I think it could be
> a basis for a way to say "go find_idlest_group path on these tasks" at
> the beginning of select_task_rq_fair.
>
> [2] https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/commit/?h=sched/experimental&id=5b4ed509027a5b6f495e6fe871cae850d5762bef
>
> Thanks,
> Brendan
>

Would it be better if it searches for idle cpus in next higher domain 
(if that is not NUMA) instead of doing find_idlest_group ?

The above approach [2] will still try to search a idle cpu in the llc 
domain of new_cpu. If it finds one great. Otherwise, let's search for an 
idle cpu in next higher domain(if that is not NUMA) excluding the 
current domain which we have already searched. I think it would help in 
cases where LLC < NUMA.


Regards,
Atish

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

#1708380

On Wed, Aug 09 2017 at 21:22, Atish Patra wrote:
> On 08/03/2017 10:05 AM, Brendan Jackman wrote:
>>
>> On Thu, Aug 03 2017 at 13:15, Josef Bacik wrote:
>>> On Thu, Aug 03, 2017 at 11:53:19AM +0100, Brendan Jackman wrote:
>>>>
>>>> Hi,
>>>>
>>>> On Fri, Jun 30 2017 at 17:55, Josef Bacik wrote:
>>>>> On Fri, Jun 30, 2017 at 07:02:20PM +0200, Mike Galbraith wrote:
>>>>>> On Fri, 2017-06-30 at 10:28 -0400, Josef Bacik wrote:
>>>>>>> On Thu, Jun 29, 2017 at 08:04:59PM -0700, Joel Fernandes wrote:
>>>>>>>
>>>>>>>> That makes sense that we multiply slave's flips by a factor because
>>>>>>>> its low, but I still didn't get why the factor is chosen to be
>>>>>>>> llc_size instead of something else for the multiplication with slave
>>>>>>>> (slave * factor).
>>>>>>
>>>>>>> Yeah I don't know why llc_size was chosen...
>>>>>>
>>>>>> static void update_top_cache_domain(int cpu)
>>>>>> {
>>>>>> struct sched_domain_shared *sds = NULL;
>>>>>> struct sched_domain *sd;
>>>>>> int id = cpu;
>>>>>> int size = 1;
>>>>>>
>>>>>> sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
>>>>>> if (sd) {
>>>>>> id = cpumask_first(sched_domain_span(sd));
>>>>>> size = cpumask_weight(sched_domain_span(sd));
>>>>>> sds = sd->shared;
>>>>>> }
>>>>>>
>>>>>> rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
>>>>>> per_cpu(sd_llc_size, cpu) = size;
>>>>>>
>>>>>> The goal of wake wide was to approximate when pulling would be a futile
>>>>>> consolidation effort and counterproductive to scaling. 'course with
>>>>>> ever increasing socket size, any 1:N waker is ever more likely to run
>>>>>> out of CPU for its one and only self (slamming into scaling wall)
>>>>>> before it needing to turn its minions loose to conquer the world.
>>>>>>
>>>>>> Something else to consider: network interrupt waking multiple workers
>>>>>> at high frequency. If the waking CPU is idle, do you really want to
>>>>>> place a worker directly in front of a tattoo artist, or is it better
>>>>>> off nearly anywhere but there?
>>>>>>
>>>>>> If the box is virtual, with no topology exposed (or real but ancient)
>>>>>> to let select_idle_sibling() come to the rescue, two workers can even
>>>>>> get tattooed simultaneously (see sync wakeup).
>>>>>>
>>>>>
>>>>> Heuristics are hard, news at 11.  I think messing with wake_wide() itself is too
>>>>> big of a hammer, we probably need a middle ground.  I'm messing with it right
>>>>> now so it's too early to say for sure, but i _suspect_ the bigger latencies we
>>>>> see are not because we overload the cpu we're trying to pull to, but because
>>>>> when we fail to do the wake_affine() we only look at siblings of the affine_sd
>>>>> instead of doing the full "find the idlest cpu in the land!" thing.
>>>>
>>>> This is the problem I've been hitting lately. My use case is 1 task per
>>>> CPU on ARM big.LITTLE (asymmetrical CPU capacity). The workload is 1
>>>> task per CPU, they all do X amount of work then pthread_barrier_wait
>>>> (i.e. sleep until the last task finishes its X and hits the barrier). On
>>>> big.LITTLE, the tasks which get a "big" CPU finish faster, and then
>>>> those CPUs pull over the tasks that are still running:
>>>>
>>>>      v CPU v           ->time->
>>>>
>>>>                     -------------
>>>>    0  (big)         11111  /333
>>>>                     -------------
>>>>    1  (big)         22222   /444|
>>>>                     -------------
>>>>    2  (LITTLE)      333333/
>>>>                     -------------
>>>>    3  (LITTLE)      444444/
>>>>                     -------------
>>>>
>>>> Now when task 4 hits the barrier (at |) and wakes the others up, there
>>>> are 4 tasks with prev_cpu=<big> and 0 tasks with
>>>> prev_cpu=<little>. Assuming that those wakeups happen on CPU4,
>>>> regardless of wake_affine, want_affine means that we'll only look in
>>>> sd_llc (cpus 0 and 1), so tasks will be unnecessarily coscheduled on the
>>>> bigs until the next load balance, something like this:
>>>>
>>>>      v CPU v           ->time->
>>>>
>>>>                     ------------------------
>>>>    0  (big)         11111  /333  31313\33333
>>>>                     ------------------------
>>>>    1  (big)         22222   /444|424\4444444
>>>>                     ------------------------
>>>>    2  (LITTLE)      333333/          \222222
>>>>                     ------------------------
>>>>    3  (LITTLE)      444444/            \1111
>>>>                     ------------------------
>>>>                                  ^^^
>>>>                            underutilization
>>>>
>>>>> I _think_
>>>>> the answer is to make select_idle_sibling() try less hard to find something
>>>>> workable and only use obviously idle cpu's in the affine sd, and fall back to
>>>>> the full load balance esque search.
>>>>
>>>> So this idea of allowing select_idle_sibling to fail, and falling back
>>>> to the slow path, would help me too, I think.
>>>
>>> Unfortunately this statement of mine was wrong, I had it in my head that we
>>> would fall back to a find the idlest cpu thing provided we failed to wake
>>> affine, but we just do select_idle_sibling() and expect the load balancer to
>>> move things around as needed.
>>
>> Ah yes, when wake_affine() returns false, we still do
>> select_idle_sibling (except in prev_cpu's sd_llc instead of
>> smp_processor_id()'s), and that is the problem faced by my workload. I
>> thought you were suggesting to change the flow so that
>> select_idle_sibling can say "I didn't find any idle siblings - go to the
>> find_idlest_group path".
>>
>>>> This is also why I was playing with your
>>>> don't-affine-recently-balanced-tasks patch[1], which also helps my case
>>>> since it prevents want_affine for tasks 3 and 4 (which were recently
>>>> moved by an active balance).
>>>>
>>>> [1] https://marc.info/?l=linux-kernel&m=150003849602535&w=2
>>>>     (also linked elsewhere in this thread)
>>>>
>>>
>>> Would you try peter's sched/experimental branch and see how that affects your
>>> workload?  I'm still messing with my patches and I may drop this one as it now
>>> appears to be too aggressive with the new set of patches.  Thanks,
>>
>> Sure, I'll take a look at those, thanks. I guess the idea of caching
>> values in LB and then using them in wakeup[2] is a lighter-handed way of
>> achieving the same thing as last_balance_ts? It won't solve my problem
>> directly since we'll still only look in sd_llc, but I think it could be
>> a basis for a way to say "go find_idlest_group path on these tasks" at
>> the beginning of select_task_rq_fair.
>>
>> [2] https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/commit/?h=sched/experimental&id=5b4ed509027a5b6f495e6fe871cae850d5762bef
>>
>> Thanks,
>> Brendan
>>
>
> Would it be better if it searches for idle cpus in next higher domain
> (if that is not NUMA) instead of doing find_idlest_group ?
>
> The above approach [2] will still try to search a idle cpu in the llc
> domain of new_cpu. If it finds one great. Otherwise, let's search for an
> idle cpu in next higher domain(if that is not NUMA) excluding the
> current domain which we have already searched. I think it would help in
> cases where LLC < NUMA.

Well for my use case, "search for idle cpus in the next higher domain"
and "go to find_busiest_group & co" mean the same thing. But for NUMA
boxes (where I'm guessing there are >=3 sched_domains?) then yeah that
sounds like a good idea at least to my inexpert ears. Currently it's
either "only look at siblings of either prev_cpu or smp_processor_id()"
or "look through the whole system (or at least as far as sd_flag takes
us)", so maybe you want middle ground?

On the other hand, I'm guessing remote wakeups across NUMA nodes are
expensive, so that's why we only look at siblings? There's already a
choice between prev_cpu's and smp_processor_id()'s LLC siblings.

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

#1708925

On 08/10/2017 04:48 AM, Brendan Jackman wrote:
>
> On Wed, Aug 09 2017 at 21:22, Atish Patra wrote:
>> On 08/03/2017 10:05 AM, Brendan Jackman wrote:
>>>
>>> On Thu, Aug 03 2017 at 13:15, Josef Bacik wrote:
>>>> On Thu, Aug 03, 2017 at 11:53:19AM +0100, Brendan Jackman wrote:
>>>>>
>>>>> Hi,
>>>>>
>>>>> On Fri, Jun 30 2017 at 17:55, Josef Bacik wrote:
>>>>>> On Fri, Jun 30, 2017 at 07:02:20PM +0200, Mike Galbraith wrote:
>>>>>>> On Fri, 2017-06-30 at 10:28 -0400, Josef Bacik wrote:
>>>>>>>> On Thu, Jun 29, 2017 at 08:04:59PM -0700, Joel Fernandes wrote:
>>>>>>>>
>>>>>>>>> That makes sense that we multiply slave's flips by a factor because
>>>>>>>>> its low, but I still didn't get why the factor is chosen to be
>>>>>>>>> llc_size instead of something else for the multiplication with slave
>>>>>>>>> (slave * factor).
>>>>>>>
>>>>>>>> Yeah I don't know why llc_size was chosen...
>>>>>>>
>>>>>>> static void update_top_cache_domain(int cpu)
>>>>>>> {
>>>>>>> struct sched_domain_shared *sds = NULL;
>>>>>>> struct sched_domain *sd;
>>>>>>> int id = cpu;
>>>>>>> int size = 1;
>>>>>>>
>>>>>>> sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
>>>>>>> if (sd) {
>>>>>>> id = cpumask_first(sched_domain_span(sd));
>>>>>>> size = cpumask_weight(sched_domain_span(sd));
>>>>>>> sds = sd->shared;
>>>>>>> }
>>>>>>>
>>>>>>> rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
>>>>>>> per_cpu(sd_llc_size, cpu) = size;
>>>>>>>
>>>>>>> The goal of wake wide was to approximate when pulling would be a futile
>>>>>>> consolidation effort and counterproductive to scaling. 'course with
>>>>>>> ever increasing socket size, any 1:N waker is ever more likely to run
>>>>>>> out of CPU for its one and only self (slamming into scaling wall)
>>>>>>> before it needing to turn its minions loose to conquer the world.
>>>>>>>
>>>>>>> Something else to consider: network interrupt waking multiple workers
>>>>>>> at high frequency. If the waking CPU is idle, do you really want to
>>>>>>> place a worker directly in front of a tattoo artist, or is it better
>>>>>>> off nearly anywhere but there?
>>>>>>>
>>>>>>> If the box is virtual, with no topology exposed (or real but ancient)
>>>>>>> to let select_idle_sibling() come to the rescue, two workers can even
>>>>>>> get tattooed simultaneously (see sync wakeup).
>>>>>>>
>>>>>>
>>>>>> Heuristics are hard, news at 11.  I think messing with wake_wide() itself is too
>>>>>> big of a hammer, we probably need a middle ground.  I'm messing with it right
>>>>>> now so it's too early to say for sure, but i _suspect_ the bigger latencies we
>>>>>> see are not because we overload the cpu we're trying to pull to, but because
>>>>>> when we fail to do the wake_affine() we only look at siblings of the affine_sd
>>>>>> instead of doing the full "find the idlest cpu in the land!" thing.
>>>>>
>>>>> This is the problem I've been hitting lately. My use case is 1 task per
>>>>> CPU on ARM big.LITTLE (asymmetrical CPU capacity). The workload is 1
>>>>> task per CPU, they all do X amount of work then pthread_barrier_wait
>>>>> (i.e. sleep until the last task finishes its X and hits the barrier). On
>>>>> big.LITTLE, the tasks which get a "big" CPU finish faster, and then
>>>>> those CPUs pull over the tasks that are still running:
>>>>>
>>>>>      v CPU v           ->time->
>>>>>
>>>>>                     -------------
>>>>>    0  (big)         11111  /333
>>>>>                     -------------
>>>>>    1  (big)         22222   /444|
>>>>>                     -------------
>>>>>    2  (LITTLE)      333333/
>>>>>                     -------------
>>>>>    3  (LITTLE)      444444/
>>>>>                     -------------
>>>>>
>>>>> Now when task 4 hits the barrier (at |) and wakes the others up, there
>>>>> are 4 tasks with prev_cpu=<big> and 0 tasks with
>>>>> prev_cpu=<little>. Assuming that those wakeups happen on CPU4,
>>>>> regardless of wake_affine, want_affine means that we'll only look in
>>>>> sd_llc (cpus 0 and 1), so tasks will be unnecessarily coscheduled on the
>>>>> bigs until the next load balance, something like this:
>>>>>
>>>>>      v CPU v           ->time->
>>>>>
>>>>>                     ------------------------
>>>>>    0  (big)         11111  /333  31313\33333
>>>>>                     ------------------------
>>>>>    1  (big)         22222   /444|424\4444444
>>>>>                     ------------------------
>>>>>    2  (LITTLE)      333333/          \222222
>>>>>                     ------------------------
>>>>>    3  (LITTLE)      444444/            \1111
>>>>>                     ------------------------
>>>>>                                  ^^^
>>>>>                            underutilization
>>>>>
>>>>>> I _think_
>>>>>> the answer is to make select_idle_sibling() try less hard to find something
>>>>>> workable and only use obviously idle cpu's in the affine sd, and fall back to
>>>>>> the full load balance esque search.
>>>>>
>>>>> So this idea of allowing select_idle_sibling to fail, and falling back
>>>>> to the slow path, would help me too, I think.
>>>>
>>>> Unfortunately this statement of mine was wrong, I had it in my head that we
>>>> would fall back to a find the idlest cpu thing provided we failed to wake
>>>> affine, but we just do select_idle_sibling() and expect the load balancer to
>>>> move things around as needed.
>>>
>>> Ah yes, when wake_affine() returns false, we still do
>>> select_idle_sibling (except in prev_cpu's sd_llc instead of
>>> smp_processor_id()'s), and that is the problem faced by my workload. I
>>> thought you were suggesting to change the flow so that
>>> select_idle_sibling can say "I didn't find any idle siblings - go to the
>>> find_idlest_group path".
>>>
>>>>> This is also why I was playing with your
>>>>> don't-affine-recently-balanced-tasks patch[1], which also helps my case
>>>>> since it prevents want_affine for tasks 3 and 4 (which were recently
>>>>> moved by an active balance).
>>>>>
>>>>> [1] https://marc.info/?l=linux-kernel&m=150003849602535&w=2
>>>>>     (also linked elsewhere in this thread)
>>>>>
>>>>
>>>> Would you try peter's sched/experimental branch and see how that affects your
>>>> workload?  I'm still messing with my patches and I may drop this one as it now
>>>> appears to be too aggressive with the new set of patches.  Thanks,
>>>
>>> Sure, I'll take a look at those, thanks. I guess the idea of caching
>>> values in LB and then using them in wakeup[2] is a lighter-handed way of
>>> achieving the same thing as last_balance_ts? It won't solve my problem
>>> directly since we'll still only look in sd_llc, but I think it could be
>>> a basis for a way to say "go find_idlest_group path on these tasks" at
>>> the beginning of select_task_rq_fair.
>>>
>>> [2] https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/commit/?h=sched/experimental&id=5b4ed509027a5b6f495e6fe871cae850d5762bef
>>>
>>> Thanks,
>>> Brendan
>>>
>>
>> Would it be better if it searches for idle cpus in next higher domain
>> (if that is not NUMA) instead of doing find_idlest_group ?
>>
>> The above approach [2] will still try to search a idle cpu in the llc
>> domain of new_cpu. If it finds one great. Otherwise, let's search for an
>> idle cpu in next higher domain(if that is not NUMA) excluding the
>> current domain which we have already searched. I think it would help in
>> cases where LLC < NUMA.
>
> Well for my use case, "search for idle cpus in the next higher domain"
> and "go to find_busiest_group & co" mean the same thing.
Yeah. It just may be tad cheaper to do idle cpu search than to 
find_idlest_group and find_idlest_cpu.

But for NUMA
> boxes (where I'm guessing there are >=3 sched_domains?)
Yeah.
then yeah that
> sounds like a good idea at least to my inexpert ears. Currently it's
> either "only look at siblings of either prev_cpu or smp_processor_id()"
> or "look through the whole system (or at least as far as sd_flag takes
> us)", so maybe you want middle ground?
>
> On the other hand, I'm guessing remote wakeups across NUMA nodes are
> expensive, so that's why we only look at siblings?
Correct. But I am suggesting the above modification impacting only for 
archs where LLC < NUMA i.e. you have SMT, LLC, DIE/CPU, NUMA.. domains.
For your case, I guess the domains would stop at CPU. Any architecture 
with above domain hierarchy can search wide to find out an idle cpu.

Other architectures where NUMA is the next domain to LLC, it won't do
anything.

There's already a
> choice between prev_cpu's and smp_processor_id()'s LLC siblings.
>
Yes. So we may benefit by searching idle cpus other LLC groups as well.
Initially, I was worried about it may be too expensive to search wide
but Peter's recent patch (1ad3aaf3fcd2:Implement new approach to scale 
select_idle_cpu) should abandon the search if it becomes too costly.

Did I miss any case it may affect performance negatively ?

Regards,
Atish

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web