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

Groups > linux.kernel > #1699256 > 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 Joel Fernandes <joelaf@google.com> - 2017-07-29 10:10 +0200
    Re: wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-07-29 10:20 +0200
      Re: wake_wide mechanism clarification Michael Wang <yun.wang@profitbricks.com> - 2017-08-02 10:30 +0200
        Re: wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-08-04 01:50 +0200
    Re: wake_wide mechanism clarification Mike Galbraith <umgwanakikbuti@gmail.com> - 2017-07-29 17:10 +0200
      Re: wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-07-29 22:20 +0200
        Re: wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-07-30 00:30 +0200
          Re: wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-07-30 00:50 +0200
            Re: wake_wide mechanism clarification Josef Bacik <josef@toxicpanda.com> - 2017-07-31 14:30 +0200
              Re: wake_wide mechanism clarification Mike Galbraith <umgwanakikbuti@gmail.com> - 2017-07-31 15:50 +0200
                Re: wake_wide mechanism clarification Josef Bacik <josef@toxicpanda.com> - 2017-07-31 16:50 +0200
                  Re: wake_wide mechanism clarification Mike Galbraith <umgwanakikbuti@gmail.com> - 2017-07-31 19:30 +0200
              Re: wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-07-31 18:30 +0200
                Re: wake_wide mechanism clarification Josef Bacik <josef@toxicpanda.com> - 2017-07-31 18:50 +0200
                  Re: wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-07-31 20:00 +0200

#1699256 — Re: wake_wide mechanism clarification

Hi Mike,

I have take spent some time understanding the email thread and
previous discussions. Unfortunately the second condition we are
checking for in the wake_wide still didn't make sense to me (mentioned
below) :-(

On Fri, Jun 30, 2017 at 10:02 AM, Mike Galbraith
<umgwanakikbuti@gmail.com> 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.

Actually the original question was why do we have the second condition
as "master < slave * factor", instead of "master < factor". that's
what didn't make sense to me. Why don't we return 0 from wake_wide if
master < factor ?

Infact, as the factor is set to the llc_size, I think the condition
that makes sense to me is:

if ((master + slave) < llc_size)
  return 0;

In other words, if the master flips and the slave flips are totally
higher than the llc_size, then we are most likely waking up too many
tasks as affine and should then switch to wide to prevent overloading.

Digging further into the original patch from Michael Wang (I also CC'd
him), this was the code (before you had changed it to master/slave):

wakee->nr_wakee_switch > factor &&
waker->nr_wakee_switch > (factor * wakee->nr_wakee_switch)

To explain the second condition above, Michael Wang said the following in [1]

"Furthermore, if waker also has a high 'nr_wakee_switch', imply that multiple
tasks rely on it, then waker's higher latency will damage all of them, pull
wakee seems to be a bad deal."

Again I didn't follow why the second condition couldn't just be:
waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
wakee->nr_wakee_switch) > factor, based on the above explanation from
Micheal Wang that I quoted.
and why he's instead doing the whole multiplication thing there that I
was talking about earlier: "factor * wakee->nr_wakee_switch".

Rephrasing my question in another way, why are we talking the ratio of
master/slave instead of the sum when comparing if its > factor? I am
surely missing something here.

Just taking an example:

Say we have llc_size = 3, we have 3 masters M1, M2 and M3. M1 has 8
slaves, M2 has 4 slaves and M3 has 4 slaves. Only 1 slave is common
between all 3 masters. Also to make it a bit more interesting, let s8
wake up some random task T0. A diagram to show the master/slave
relation ships could look like:

                                    +-----+
                                    |     |
+------------------------+   +------+ M2  |
|                        |   |      |     |
|        M1              |   |      +--+--+----
|                        |   |      |  |  |   |
|                        |   |      |  |  |   s15
+--+--+--+--+--+--+---+--+---+      v  v  v
   |  |  |  |  |  |   |      |      s9 s10 s11
   v  v  v  v  v  v   v      v
   s1 s2 s3 s4 s5 s6  s7     s8 ---> T0
                             ^
                             |
                           +-+---+
                           |     |
                           | M3  |
                           |     |
                           +--+--+-----
                           |  |  |    |
                           v  v  v    v
                          s12 s13 s14 s16


Lets consider the case of M1 waking up s8. As per the above diagram,
M1 has 8 flips and s8 has 4 flips.

With llc_size = 3, the condition

(slave < factor) would return FALSE, so then we would turn to the
(master < slave * factor) condition. This would be TRUE (8 < 4 * 3),
so wake_wide would return 0 and would cause s8 to be woken up as
affine with relation to M1's core.

So basically, it seems the heuristic is saying (with help of the
second condition - master < slave * factor). that Its a good idea for
s8 to be affine-woken-up with respect to M1's core. Why is it a good
idea to do that? It seems to me M1 has already several tasks its
waking as affine so causing s8 to be woken up affine could be harmful
and it may be a better choice to wake it up elsewhere.

Thanks for your help!

-Joel

[1] https://lkml.org/lkml/2013/7/4/20


>
> 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).
>
>         -Mike

[toc] | [next] | [standalone]

#1699261

+Michael Wang on his current email address (old one bounced). (my
reply was to Mike Galbraith but I also meant to CC Michael Wang for
the discussion). Thanks

On Sat, Jul 29, 2017 at 1:01 AM, Joel Fernandes <joelaf@google.com> wrote:
> Hi Mike,
>
> I have take spent some time understanding the email thread and
> previous discussions. Unfortunately the second condition we are
> checking for in the wake_wide still didn't make sense to me (mentioned
> below) :-(
>
> On Fri, Jun 30, 2017 at 10:02 AM, Mike Galbraith
> <umgwanakikbuti@gmail.com> 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.
>
> Actually the original question was why do we have the second condition
> as "master < slave * factor", instead of "master < factor". that's
> what didn't make sense to me. Why don't we return 0 from wake_wide if
> master < factor ?
>
> Infact, as the factor is set to the llc_size, I think the condition
> that makes sense to me is:
>
> if ((master + slave) < llc_size)
>   return 0;
>
> In other words, if the master flips and the slave flips are totally
> higher than the llc_size, then we are most likely waking up too many
> tasks as affine and should then switch to wide to prevent overloading.
>
> Digging further into the original patch from Michael Wang (I also CC'd
> him), this was the code (before you had changed it to master/slave):
>
> wakee->nr_wakee_switch > factor &&
> waker->nr_wakee_switch > (factor * wakee->nr_wakee_switch)
>
> To explain the second condition above, Michael Wang said the following in [1]
>
> "Furthermore, if waker also has a high 'nr_wakee_switch', imply that multiple
> tasks rely on it, then waker's higher latency will damage all of them, pull
> wakee seems to be a bad deal."
>
> Again I didn't follow why the second condition couldn't just be:
> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
> wakee->nr_wakee_switch) > factor, based on the above explanation from
> Micheal Wang that I quoted.
> and why he's instead doing the whole multiplication thing there that I
> was talking about earlier: "factor * wakee->nr_wakee_switch".
>
> Rephrasing my question in another way, why are we talking the ratio of
> master/slave instead of the sum when comparing if its > factor? I am
> surely missing something here.
>
> Just taking an example:
>
> Say we have llc_size = 3, we have 3 masters M1, M2 and M3. M1 has 8
> slaves, M2 has 4 slaves and M3 has 4 slaves. Only 1 slave is common
> between all 3 masters. Also to make it a bit more interesting, let s8
> wake up some random task T0. A diagram to show the master/slave
> relation ships could look like:
>
>                                     +-----+
>                                     |     |
> +------------------------+   +------+ M2  |
> |                        |   |      |     |
> |        M1              |   |      +--+--+----
> |                        |   |      |  |  |   |
> |                        |   |      |  |  |   s15
> +--+--+--+--+--+--+---+--+---+      v  v  v
>    |  |  |  |  |  |   |      |      s9 s10 s11
>    v  v  v  v  v  v   v      v
>    s1 s2 s3 s4 s5 s6  s7     s8 ---> T0
>                              ^
>                              |
>                            +-+---+
>                            |     |
>                            | M3  |
>                            |     |
>                            +--+--+-----
>                            |  |  |    |
>                            v  v  v    v
>                           s12 s13 s14 s16
>
>
> Lets consider the case of M1 waking up s8. As per the above diagram,
> M1 has 8 flips and s8 has 4 flips.
>
> With llc_size = 3, the condition
>
> (slave < factor) would return FALSE, so then we would turn to the
> (master < slave * factor) condition. This would be TRUE (8 < 4 * 3),
> so wake_wide would return 0 and would cause s8 to be woken up as
> affine with relation to M1's core.
>
> So basically, it seems the heuristic is saying (with help of the
> second condition - master < slave * factor). that Its a good idea for
> s8 to be affine-woken-up with respect to M1's core. Why is it a good
> idea to do that? It seems to me M1 has already several tasks its
> waking as affine so causing s8 to be woken up affine could be harmful
> and it may be a better choice to wake it up elsewhere.
>
> Thanks for your help!
>
> -Joel
>
> [1] https://lkml.org/lkml/2013/7/4/20
>
>
>>
>> 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).
>>
>>         -Mike

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

#1701869

Hi, Joel

On 07/29/2017 10:13 AM, Joel Fernandes wrote:
> +Michael Wang on his current email address (old one bounced). (my
> reply was to Mike Galbraith but I also meant to CC Michael Wang for
> the discussion). Thanks

Just back from vacation and saw this long long discussion...

I think guys explained well on the idea, wake_wide() just try to filter
out the cases that may congest the waker's domain, as much as possible
without side effect (ideally).

The factor at very beginning is just a static number which picked by
enormous times of practice testing, Peter Zijlstr suggest we add the
domain size and make it a flexible factor, which by practice not that bad.

So the simple answer is we use the llc_size since no better option at
that time :-)

But things changing very fast and new feature can introduce new cases,
I'm pretty sure if we redo the testing the results will be very different,
however, the idea itself still make sense to me, at least on theory.

Recently I'm also thinking about the scheduler issue, cfs try to find out
general solution for all these cases and the best answer is obviously, all
the cases will suffer some damage and scheduler itself bloated to achieve
the goal 'taking care of all'.

So in order to achieve the maximum performance of particular workload, some
user defined scheduler would be an interesting idea :-P

Regards,
Michael Wang



> 
> On Sat, Jul 29, 2017 at 1:01 AM, Joel Fernandes <joelaf@google.com> wrote:
>> Hi Mike,
>>
>> I have take spent some time understanding the email thread and
>> previous discussions. Unfortunately the second condition we are
>> checking for in the wake_wide still didn't make sense to me (mentioned
>> below) :-(
>>
>> On Fri, Jun 30, 2017 at 10:02 AM, Mike Galbraith
>> <umgwanakikbuti@gmail.com> 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.
>>
>> Actually the original question was why do we have the second condition
>> as "master < slave * factor", instead of "master < factor". that's
>> what didn't make sense to me. Why don't we return 0 from wake_wide if
>> master < factor ?
>>
>> Infact, as the factor is set to the llc_size, I think the condition
>> that makes sense to me is:
>>
>> if ((master + slave) < llc_size)
>>   return 0;
>>
>> In other words, if the master flips and the slave flips are totally
>> higher than the llc_size, then we are most likely waking up too many
>> tasks as affine and should then switch to wide to prevent overloading.
>>
>> Digging further into the original patch from Michael Wang (I also CC'd
>> him), this was the code (before you had changed it to master/slave):
>>
>> wakee->nr_wakee_switch > factor &&
>> waker->nr_wakee_switch > (factor * wakee->nr_wakee_switch)
>>
>> To explain the second condition above, Michael Wang said the following in [1]
>>
>> "Furthermore, if waker also has a high 'nr_wakee_switch', imply that multiple
>> tasks rely on it, then waker's higher latency will damage all of them, pull
>> wakee seems to be a bad deal."
>>
>> Again I didn't follow why the second condition couldn't just be:
>> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
>> wakee->nr_wakee_switch) > factor, based on the above explanation from
>> Micheal Wang that I quoted.
>> and why he's instead doing the whole multiplication thing there that I
>> was talking about earlier: "factor * wakee->nr_wakee_switch".
>>
>> Rephrasing my question in another way, why are we talking the ratio of
>> master/slave instead of the sum when comparing if its > factor? I am
>> surely missing something here.
>>
>> Just taking an example:
>>
>> Say we have llc_size = 3, we have 3 masters M1, M2 and M3. M1 has 8
>> slaves, M2 has 4 slaves and M3 has 4 slaves. Only 1 slave is common
>> between all 3 masters. Also to make it a bit more interesting, let s8
>> wake up some random task T0. A diagram to show the master/slave
>> relation ships could look like:
>>
>>                                     +-----+
>>                                     |     |
>> +------------------------+   +------+ M2  |
>> |                        |   |      |     |
>> |        M1              |   |      +--+--+----
>> |                        |   |      |  |  |   |
>> |                        |   |      |  |  |   s15
>> +--+--+--+--+--+--+---+--+---+      v  v  v
>>    |  |  |  |  |  |   |      |      s9 s10 s11
>>    v  v  v  v  v  v   v      v
>>    s1 s2 s3 s4 s5 s6  s7     s8 ---> T0
>>                              ^
>>                              |
>>                            +-+---+
>>                            |     |
>>                            | M3  |
>>                            |     |
>>                            +--+--+-----
>>                            |  |  |    |
>>                            v  v  v    v
>>                           s12 s13 s14 s16
>>
>>
>> Lets consider the case of M1 waking up s8. As per the above diagram,
>> M1 has 8 flips and s8 has 4 flips.
>>
>> With llc_size = 3, the condition
>>
>> (slave < factor) would return FALSE, so then we would turn to the
>> (master < slave * factor) condition. This would be TRUE (8 < 4 * 3),
>> so wake_wide would return 0 and would cause s8 to be woken up as
>> affine with relation to M1's core.
>>
>> So basically, it seems the heuristic is saying (with help of the
>> second condition - master < slave * factor). that Its a good idea for
>> s8 to be affine-woken-up with respect to M1's core. Why is it a good
>> idea to do that? It seems to me M1 has already several tasks its
>> waking as affine so causing s8 to be woken up affine could be harmful
>> and it may be a better choice to wake it up elsewhere.
>>
>> Thanks for your help!
>>
>> -Joel
>>
>> [1] https://lkml.org/lkml/2013/7/4/20
>>
>>
>>>
>>> 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).
>>>
>>>         -Mike

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

#1703548

Hi Michael,

Thanks for your reply.

On Wed, Aug 2, 2017 at 1:26 AM, Michael Wang <yun.wang@profitbricks.com> wrote:
> Hi, Joel
>
> On 07/29/2017 10:13 AM, Joel Fernandes wrote:
>> +Michael Wang on his current email address (old one bounced). (my
>> reply was to Mike Galbraith but I also meant to CC Michael Wang for
>> the discussion). Thanks
>
> Just back from vacation and saw this long long discussion...
>
> I think guys explained well on the idea, wake_wide() just try to filter
> out the cases that may congest the waker's domain, as much as possible
> without side effect (ideally).
>
> The factor at very beginning is just a static number which picked by
> enormous times of practice testing, Peter Zijlstr suggest we add the
> domain size and make it a flexible factor, which by practice not that bad.

Yeah making it flexible might be better.

>
> So the simple answer is we use the llc_size since no better option at
> that time :-)

:-)

>
> But things changing very fast and new feature can introduce new cases,
> I'm pretty sure if we redo the testing the results will be very different,
> however, the idea itself still make sense to me, at least on theory.
>
> Recently I'm also thinking about the scheduler issue, cfs try to find out
> general solution for all these cases and the best answer is obviously, all
> the cases will suffer some damage and scheduler itself bloated to achieve
> the goal 'taking care of all'.

My team is definitely seeing some weirdness with wake_wide() itself
not working correctly. We're collecting more data and do a more
thorough analysis of the behavior. I think it can be improved. Will
update soon as we have something.

thanks,

-Joel

>
> Regards,
> Michael Wang
>
>
>
>>
>> On Sat, Jul 29, 2017 at 1:01 AM, Joel Fernandes <joelaf@google.com> wrote:
>>> Hi Mike,
>>>
>>> I have take spent some time understanding the email thread and
>>> previous discussions. Unfortunately the second condition we are
>>> checking for in the wake_wide still didn't make sense to me (mentioned
>>> below) :-(
>>>
>>> On Fri, Jun 30, 2017 at 10:02 AM, Mike Galbraith
>>> <umgwanakikbuti@gmail.com> 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.
>>>
>>> Actually the original question was why do we have the second condition
>>> as "master < slave * factor", instead of "master < factor". that's
>>> what didn't make sense to me. Why don't we return 0 from wake_wide if
>>> master < factor ?
>>>
>>> Infact, as the factor is set to the llc_size, I think the condition
>>> that makes sense to me is:
>>>
>>> if ((master + slave) < llc_size)
>>>   return 0;
>>>
>>> In other words, if the master flips and the slave flips are totally
>>> higher than the llc_size, then we are most likely waking up too many
>>> tasks as affine and should then switch to wide to prevent overloading.
>>>
>>> Digging further into the original patch from Michael Wang (I also CC'd
>>> him), this was the code (before you had changed it to master/slave):
>>>
>>> wakee->nr_wakee_switch > factor &&
>>> waker->nr_wakee_switch > (factor * wakee->nr_wakee_switch)
>>>
>>> To explain the second condition above, Michael Wang said the following in [1]
>>>
>>> "Furthermore, if waker also has a high 'nr_wakee_switch', imply that multiple
>>> tasks rely on it, then waker's higher latency will damage all of them, pull
>>> wakee seems to be a bad deal."
>>>
>>> Again I didn't follow why the second condition couldn't just be:
>>> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
>>> wakee->nr_wakee_switch) > factor, based on the above explanation from
>>> Micheal Wang that I quoted.
>>> and why he's instead doing the whole multiplication thing there that I
>>> was talking about earlier: "factor * wakee->nr_wakee_switch".
>>>
>>> Rephrasing my question in another way, why are we talking the ratio of
>>> master/slave instead of the sum when comparing if its > factor? I am
>>> surely missing something here.
>>>
>>> Just taking an example:
>>>
>>> Say we have llc_size = 3, we have 3 masters M1, M2 and M3. M1 has 8
>>> slaves, M2 has 4 slaves and M3 has 4 slaves. Only 1 slave is common
>>> between all 3 masters. Also to make it a bit more interesting, let s8
>>> wake up some random task T0. A diagram to show the master/slave
>>> relation ships could look like:
>>>
>>>                                     +-----+
>>>                                     |     |
>>> +------------------------+   +------+ M2  |
>>> |                        |   |      |     |
>>> |        M1              |   |      +--+--+----
>>> |                        |   |      |  |  |   |
>>> |                        |   |      |  |  |   s15
>>> +--+--+--+--+--+--+---+--+---+      v  v  v
>>>    |  |  |  |  |  |   |      |      s9 s10 s11
>>>    v  v  v  v  v  v   v      v
>>>    s1 s2 s3 s4 s5 s6  s7     s8 ---> T0
>>>                              ^
>>>                              |
>>>                            +-+---+
>>>                            |     |
>>>                            | M3  |
>>>                            |     |
>>>                            +--+--+-----
>>>                            |  |  |    |
>>>                            v  v  v    v
>>>                           s12 s13 s14 s16
>>>
>>>
>>> Lets consider the case of M1 waking up s8. As per the above diagram,
>>> M1 has 8 flips and s8 has 4 flips.
>>>
>>> With llc_size = 3, the condition
>>>
>>> (slave < factor) would return FALSE, so then we would turn to the
>>> (master < slave * factor) condition. This would be TRUE (8 < 4 * 3),
>>> so wake_wide would return 0 and would cause s8 to be woken up as
>>> affine with relation to M1's core.
>>>
>>> So basically, it seems the heuristic is saying (with help of the
>>> second condition - master < slave * factor). that Its a good idea for
>>> s8 to be affine-woken-up with respect to M1's core. Why is it a good
>>> idea to do that? It seems to me M1 has already several tasks its
>>> waking as affine so causing s8 to be woken up affine could be harmful
>>> and it may be a better choice to wake it up elsewhere.
>>>
>>> Thanks for your help!
>>>
>>> -Joel
>>>
>>> [1] https://lkml.org/lkml/2013/7/4/20
>>>
>>>
>>>>
>>>> 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).
>>>>
>>>>         -Mike

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

#1699331

On Sat, 2017-07-29 at 01:01 -0700, Joel Fernandes wrote:
> Hi Mike,
> 
> I have take spent some time understanding the email thread and
> previous discussions. Unfortunately the second condition we are
> checking for in the wake_wide still didn't make sense to me (mentioned
> below) :-(
> 
> On Fri, Jun 30, 2017 at 10:02 AM, Mike Galbraith
> <umgwanakikbuti@gmail.com> 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.
> 
> Actually the original question was why do we have the second condition
> as "master < slave * factor", instead of "master < factor". that's
> what didn't make sense to me. Why don't we return 0 from wake_wide if
> master < factor ?
> 
> Infact, as the factor is set to the llc_size, I think the condition
> that makes sense to me is:
> 
> if ((master + slave) < llc_size)
>   return 0;

That says to me turn affine wakeups off for nearly everything.

> In other words, if the master flips and the slave flips are totally
> higher than the llc_size, then we are most likely waking up too many
> tasks as affine and should then switch to wide to prevent overloading.

The heuristic is mostly about the ratio of flip counts.

> Digging further into the original patch from Michael Wang (I also CC'd
> him), this was the code (before you had changed it to master/slave):
> 
> wakee->nr_wakee_switch > factor &&
> waker->nr_wakee_switch > (factor * wakee->nr_wakee_switch)

Yeah, it was originally unidirectional.

> To explain the second condition above, Michael Wang said the following in [1]
> 
> "Furthermore, if waker also has a high 'nr_wakee_switch', imply that multiple
> tasks rely on it, then waker's higher latency will damage all of them, pull
> wakee seems to be a bad deal."

Yes, "Furthermore". To detect 1:N, Michael chose llc_size as his N.  Is
the one flipping partners at least N/s, and the other about N times as
often?  If so, the two may be part of a too big to wisely pull 1:N.

If you have a better idea, by all means, pull it out.  Nobody is
attached to wake_wide(), in fact, I suspect Peter hates it.  I'm not
fond of it either, it having obvious holes.  The only thing it has
going for it is simplicity.  Bend it up, replace it, fire away.
  
> Again I didn't follow why the second condition couldn't just be:
> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
> wakee->nr_wakee_switch) > factor, based on the above explanation from
> Micheal Wang that I quoted.
> and why he's instead doing the whole multiplication thing there that I
> was talking about earlier: "factor * wakee->nr_wakee_switch".
> 
> Rephrasing my question in another way, why are we talking the ratio of
> master/slave instead of the sum when comparing if its > factor? I am
> surely missing something here.

Because the heuristic tries to not demolish 1:1 buddies.  Big partner
flip delta means the pair are unlikely to be a communicating pair,
perhaps at high frequency where misses hurt like hell.

> Just taking an example:
> 
> Say we have llc_size = 3, we have 3 masters M1, M2 and M3. M1 has 8
> slaves, M2 has 4 slaves and M3 has 4 slaves. Only 1 slave is common
> between all 3 masters. Also to make it a bit more interesting, let s8
> wake up some random task T0. A diagram to show the master/slave
> relation ships could look like:

I don't need the artwork, as soon as you describe a squid orgie in a
bucket with no adult supervision, I can visualize what happens: the
load balancer tries to make pedantically perfect load numbers, caring
not one whit about any of the relationships in either text or graphic
description, stirs bucket vigorously, making squid soup.

IMHO, placement optimization of that is a job for a human, the
scheduler ain't that smart. (quick like bunny -> smart like bunny)

> 
>                                     +-----+
>                                     |     |
> +------------------------+   +------+ M2  |
> |                        |   |      |     |
> |        M1              |   |      +--+--+----
> |                        |   |      |  |  |   |
> |                        |   |      |  |  |   s15
> +--+--+--+--+--+--+---+--+---+      v  v  v
>    |  |  |  |  |  |   |      |      s9 s10 s11
>    v  v  v  v  v  v   v      v
>    s1 s2 s3 s4 s5 s6  s7     s8 ---> T0
>                              ^
>                              |
>                            +-+---+
>                            |     |
>                            | M3  |
>                            |     |
>                            +--+--+-----
>                            |  |  |    |
>                            v  v  v    v
>                           s12 s13 s14 s16
> 
> 
> Lets consider the case of M1 waking up s8. As per the above diagram,
> M1 has 8 flips and s8 has 4 flips.
> 
> With llc_size = 3, the condition
> 
> (slave < factor) would return FALSE, so then we would turn to the
> (master < slave * factor) condition. This would be TRUE (8 < 4 * 3),
> so wake_wide would return 0 and would cause s8 to be woken up as
> affine with relation to M1's core.
> 
> So basically, it seems the heuristic is saying (with help of the
> second condition - master < slave * factor). that Its a good idea for
> s8 to be affine-woken-up with respect to M1's core. Why is it a good
> idea to do that? It seems to me M1 has already several tasks its
> waking as affine so causing s8 to be woken up affine could be harmful
> and it may be a better choice to wake it up elsewhere.

No matter what you do with s8, you'll be wrong from some POV.. unless
of course s8 is a high frequency waker, then migration is a good bet.

	-Mike

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

#1699364

Hi Mike,

On Sat, Jul 29, 2017 at 8:07 AM, Mike Galbraith
<umgwanakikbuti@gmail.com> wrote:
> On Sat, 2017-07-29 at 01:01 -0700, Joel Fernandes wrote:
>> Hi Mike,
>>
>> I have take spent some time understanding the email thread and
>> previous discussions. Unfortunately the second condition we are
>> checking for in the wake_wide still didn't make sense to me (mentioned
>> below) :-(
>>
>> On Fri, Jun 30, 2017 at 10:02 AM, Mike Galbraith
>> <umgwanakikbuti@gmail.com> 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...
<snip>
>> >
>> > 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.
>>
>> Actually the original question was why do we have the second condition
>> as "master < slave * factor", instead of "master < factor". that's
>> what didn't make sense to me. Why don't we return 0 from wake_wide if
>> master < factor ?
>>
>> Infact, as the factor is set to the llc_size, I think the condition
>> that makes sense to me is:
>>
>> if ((master + slave) < llc_size)
>>   return 0;
>
> That says to me turn affine wakeups off for nearly everything.

Ok, I see that now. thanks

>> To explain the second condition above, Michael Wang said the following in [1]
>>
>> "Furthermore, if waker also has a high 'nr_wakee_switch', imply that multiple
>> tasks rely on it, then waker's higher latency will damage all of them, pull
>> wakee seems to be a bad deal."
>
> Yes, "Furthermore". To detect 1:N, Michael chose llc_size as his N.  Is
> the one flipping partners at least N/s, and the other about N times as
> often?  If so, the two may be part of a too big to wisely pull 1:N.
>
> If you have a better idea, by all means, pull it out.  Nobody is

Sure yeah, first I'm trying to understand the heuristic itself which
I'm glad to be making progress with thanks to yours and others' help!

> attached to wake_wide(), in fact, I suspect Peter hates it.  I'm not
> fond of it either, it having obvious holes.  The only thing it has
> going for it is simplicity.  Bend it up, replace it, fire away.
>

Ok, it makes much more sense to me now. Also for the N:N case,
wouldn't the excessive wake-affine increase the latency and a
spreading might be better? Say if slave and master flips are much
greater than factor (llc_size), then slave > factor && master < slave
* factor, would probably return true a lot (and we would return 0
causing an affine wakeup). That's probably a bad thing right as it
could overload the waker's CPU quickly? I guess the heuristic tries to
maximize cache-hits more than reduce latency?

>> Again I didn't follow why the second condition couldn't just be:
>> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
>> wakee->nr_wakee_switch) > factor, based on the above explanation from
>> Micheal Wang that I quoted.
>> and why he's instead doing the whole multiplication thing there that I
>> was talking about earlier: "factor * wakee->nr_wakee_switch".
>>
>> Rephrasing my question in another way, why are we talking the ratio of
>> master/slave instead of the sum when comparing if its > factor? I am
>> surely missing something here.
>
> Because the heuristic tries to not demolish 1:1 buddies.  Big partner
> flip delta means the pair are unlikely to be a communicating pair,
> perhaps at high frequency where misses hurt like hell.

But it does seem to me to demolish the N:N communicating pairs from a
latency/load balancing standpoint. For he case of N readers and N
writers, the ratio (master/slave) comes down to 1:1 and we wake
affine. Hopefully I didn't miss something too obvious about that.

thanks,

-Joel

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

#1699385

Hi Mike,

On Sat, Jul 29, 2017 at 1:19 PM, Joel Fernandes <joelaf@google.com> wrote:
<snip>
>
>>> To explain the second condition above, Michael Wang said the following in [1]
>>>
>>> "Furthermore, if waker also has a high 'nr_wakee_switch', imply that multiple
>>> tasks rely on it, then waker's higher latency will damage all of them, pull
>>> wakee seems to be a bad deal."
>>
>> Yes, "Furthermore". To detect 1:N, Michael chose llc_size as his N.  Is
>> the one flipping partners at least N/s, and the other about N times as
>> often?  If so, the two may be part of a too big to wisely pull 1:N.
>>
>> If you have a better idea, by all means, pull it out.  Nobody is
>
> Sure yeah, first I'm trying to understand the heuristic itself which
> I'm glad to be making progress with thanks to yours and others' help!
>
>> attached to wake_wide(), in fact, I suspect Peter hates it.  I'm not
>> fond of it either, it having obvious holes.  The only thing it has
>> going for it is simplicity.  Bend it up, replace it, fire away.
>>
>
> Ok, it makes much more sense to me now. Also for the N:N case,
> wouldn't the excessive wake-affine increase the latency and a
> spreading might be better? Say if slave and master flips are much
> greater than factor (llc_size), then slave > factor && master < slave
> * factor, would probably return true a lot (and we would return 0
> causing an affine wakeup). That's probably a bad thing right as it
> could overload the waker's CPU quickly? I guess the heuristic tries to
> maximize cache-hits more than reduce latency?
>
>>> Again I didn't follow why the second condition couldn't just be:
>>> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
>>> wakee->nr_wakee_switch) > factor, based on the above explanation from
>>> Micheal Wang that I quoted.
>>> and why he's instead doing the whole multiplication thing there that I
>>> was talking about earlier: "factor * wakee->nr_wakee_switch".
>>>
>>> Rephrasing my question in another way, why are we talking the ratio of
>>> master/slave instead of the sum when comparing if its > factor? I am
>>> surely missing something here.
>>
>> Because the heuristic tries to not demolish 1:1 buddies.  Big partner
>> flip delta means the pair are unlikely to be a communicating pair,
>> perhaps at high frequency where misses hurt like hell.
>
> But it does seem to me to demolish the N:N communicating pairs from a
> latency/load balancing standpoint. For he case of N readers and N
> writers, the ratio (master/slave) comes down to 1:1 and we wake
> affine. Hopefully I didn't miss something too obvious about that.

I think wake_affine() should correctly handle the case (of
overloading) I bring up here where wake_wide() is too conservative and
does affine a lot, (I don't have any data for this though, this just
from code reading), so I take this comment back for this reason.

thanks,

-Joel

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

#1699392

On Sat, Jul 29, 2017 at 3:28 PM, Joel Fernandes <joelaf@google.com> wrote:
<snip>
>>>> Again I didn't follow why the second condition couldn't just be:
>>>> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
>>>> wakee->nr_wakee_switch) > factor, based on the above explanation from
>>>> Micheal Wang that I quoted.
>>>> and why he's instead doing the whole multiplication thing there that I
>>>> was talking about earlier: "factor * wakee->nr_wakee_switch".
>>>>
>>>> Rephrasing my question in another way, why are we talking the ratio of
>>>> master/slave instead of the sum when comparing if its > factor? I am
>>>> surely missing something here.
>>>
>>> Because the heuristic tries to not demolish 1:1 buddies.  Big partner
>>> flip delta means the pair are unlikely to be a communicating pair,
>>> perhaps at high frequency where misses hurt like hell.
>>
>> But it does seem to me to demolish the N:N communicating pairs from a
>> latency/load balancing standpoint. For he case of N readers and N
>> writers, the ratio (master/slave) comes down to 1:1 and we wake
>> affine. Hopefully I didn't miss something too obvious about that.
>
> I think wake_affine() should correctly handle the case (of
> overloading) I bring up here where wake_wide() is too conservative and
> does affine a lot, (I don't have any data for this though, this just
> from code reading), so I take this comment back for this reason.

aargh, nope :( it still runs select_idle_sibling although on the
previous CPU even if want_affine is 0 (and doesn't do the wider
wakeup..), so the comment still applies.. its easy to get lost into
the code with so many if statements :-\  sorry about the noise :)

thanks,

-Joel

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

#1699990

On Sat, Jul 29, 2017 at 03:41:56PM -0700, Joel Fernandes wrote:
> On Sat, Jul 29, 2017 at 3:28 PM, Joel Fernandes <joelaf@google.com> wrote:
> <snip>
> >>>> Again I didn't follow why the second condition couldn't just be:
> >>>> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
> >>>> wakee->nr_wakee_switch) > factor, based on the above explanation from
> >>>> Micheal Wang that I quoted.
> >>>> and why he's instead doing the whole multiplication thing there that I
> >>>> was talking about earlier: "factor * wakee->nr_wakee_switch".
> >>>>
> >>>> Rephrasing my question in another way, why are we talking the ratio of
> >>>> master/slave instead of the sum when comparing if its > factor? I am
> >>>> surely missing something here.
> >>>
> >>> Because the heuristic tries to not demolish 1:1 buddies.  Big partner
> >>> flip delta means the pair are unlikely to be a communicating pair,
> >>> perhaps at high frequency where misses hurt like hell.
> >>
> >> But it does seem to me to demolish the N:N communicating pairs from a
> >> latency/load balancing standpoint. For he case of N readers and N
> >> writers, the ratio (master/slave) comes down to 1:1 and we wake
> >> affine. Hopefully I didn't miss something too obvious about that.
> >
> > I think wake_affine() should correctly handle the case (of
> > overloading) I bring up here where wake_wide() is too conservative and
> > does affine a lot, (I don't have any data for this though, this just
> > from code reading), so I take this comment back for this reason.
> 
> aargh, nope :( it still runs select_idle_sibling although on the
> previous CPU even if want_affine is 0 (and doesn't do the wider
> wakeup..), so the comment still applies.. its easy to get lost into
> the code with so many if statements :-\  sorry about the noise :)
> 

I've been working in this area recently because of a cpu imbalance problem.
Wake_wide() definitely makes it so we're waking affine way too often, but I
think messing with wake_waide to solve that problem is the wrong solution.  This
is just a heuristic to see if we should wake affine, the simpler the better.  I
solved the problem of waking affine too often like this

https://marc.info/?l=linux-kernel&m=150003849602535&w=2

So why do you care about wake_wide() anyway?  Are you observing some problem
that you suspect is affected by the affine wakeup stuff?  Or are you just trying
to understand what is going on for fun?  Cause if you are just doing this for
fun you are a very strange person, thanks,

Josef

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

#1700065

On Mon, 2017-07-31 at 12:21 +0000, Josef Bacik wrote:
> 
> I've been working in this area recently because of a cpu imbalance problem.
> Wake_wide() definitely makes it so we're waking affine way too often, but I
> think messing with wake_waide to solve that problem is the wrong solution.  This
> is just a heuristic to see if we should wake affine, the simpler the better.  I
> solved the problem of waking affine too often like this
> 
> https://marc.info/?l=linux-kernel&m=150003849602535&w=2

Wait a minute, that's not quite fair :)  Wake_wide() can't be blamed
for causing too frequent affine wakeups when what it does is filter
some out.  While it may not reject aggressively enough for you (why you
bent it up to be very aggressive), seems the problem from your loads
POV is the scheduler generally being too eager to bounce.

I've also played with rate limiting migration per task, but it had
negative effects too: when idle/periodic balance pulls buddies apart,
rate limiting inhibits them quickly finding each other again, making
undoing all that hard load balancer work a throughput win.  Sigh.

	-Mike

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

#1700098

On Mon, Jul 31, 2017 at 03:42:25PM +0200, Mike Galbraith wrote:
> On Mon, 2017-07-31 at 12:21 +0000, Josef Bacik wrote:
> > 
> > I've been working in this area recently because of a cpu imbalance problem.
> > Wake_wide() definitely makes it so we're waking affine way too often, but I
> > think messing with wake_waide to solve that problem is the wrong solution.  This
> > is just a heuristic to see if we should wake affine, the simpler the better.  I
> > solved the problem of waking affine too often like this
> > 
> > https://marc.info/?l=linux-kernel&m=150003849602535&w=2
> 
> Wait a minute, that's not quite fair :)  Wake_wide() can't be blamed
> for causing too frequent affine wakeups when what it does is filter
> some out.  While it may not reject aggressively enough for you (why you
> bent it up to be very aggressive), seems the problem from your loads
> POV is the scheduler generally being too eager to bounce.
>

Yeah sorry, I hate this stuff because it's so hard to talk about without mixing
up different ideas.  I should say the scheduler in general prefers to wake
affine super hard, and wake_wide() is conservative in it's filtering of this
behavior.  The rest still holds true, I think tinkering with it is just hard and
the wrong place to do it, it's a good first step, and we can be smarter further
down.
 
> I've also played with rate limiting migration per task, but it had
> negative effects too: when idle/periodic balance pulls buddies apart,
> rate limiting inhibits them quickly finding each other again, making
> undoing all that hard load balancer work a throughput win.  Sigh.
> 

That's why I did the HZ thing, we don't touch the task for HZ to let things
settle out, and then allow affine wakeups after that.  Now HZ may be an eternity
in scheduler time, but I think its a good middle ground.  For our case the box
is loaded constantly, so we basically never want affine wakeups for our app.
For the case where there's spikey behavior we'll return to normal affine wakeups
a short while later.

But from my admittedly limited testing it appears to be a win overall.  Thanks,

Josef

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

#1700239

On Mon, 2017-07-31 at 14:48 +0000, Josef Bacik wrote:
> On Mon, Jul 31, 2017 at 03:42:25PM +0200, Mike Galbraith wrote:
> > On Mon, 2017-07-31 at 12:21 +0000, Josef Bacik wrote:
> > > 
> > > I've been working in this area recently because of a cpu imbalance problem.
> > > Wake_wide() definitely makes it so we're waking affine way too often, but I
> > > think messing with wake_waide to solve that problem is the wrong solution.  This
> > > is just a heuristic to see if we should wake affine, the simpler the better.  I
> > > solved the problem of waking affine too often like this
> > > 
> > > https://marc.info/?l=linux-kernel&m=150003849602535&w=2
> > 
> > Wait a minute, that's not quite fair :)  Wake_wide() can't be blamed
> > for causing too frequent affine wakeups when what it does is filter
> > some out.  While it may not reject aggressively enough for you (why you
> > bent it up to be very aggressive), seems the problem from your loads
> > POV is the scheduler generally being too eager to bounce.
> >
> 
> Yeah sorry, I hate this stuff because it's so hard to talk about without mixing
> up different ideas.  I should say the scheduler in general prefers to wake
> affine super hard, and wake_wide() is conservative in it's filtering of this
> behavior.  The rest still holds true, I think tinkering with it is just hard and
> the wrong place to do it, it's a good first step, and we can be smarter further
> down.

Yeah, it's hard, and yeah, bottom line remains unchanged.

> > I've also played with rate limiting migration per task, but it had
> > negative effects too: when idle/periodic balance pulls buddies apart,
> > rate limiting inhibits them quickly finding each other again, making
> > undoing all that hard load balancer work a throughput win.  Sigh.
> > 
> 
> That's why I did the HZ thing, we don't touch the task for HZ to let things
> settle out, and then allow affine wakeups after that.

I kinda like the way you did it better than what I tried, but until a
means exists to _target_ the win, it's gonna be rob Peter to pay Paul,
swap rolls, repeat endlessly.

	-Mike

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

#1700177

Hi Josef,

On Mon, Jul 31, 2017 at 5:21 AM, Josef Bacik <josef@toxicpanda.com> wrote:
> On Sat, Jul 29, 2017 at 03:41:56PM -0700, Joel Fernandes wrote:
>> On Sat, Jul 29, 2017 at 3:28 PM, Joel Fernandes <joelaf@google.com> wrote:
>> <snip>
>> >>>> Again I didn't follow why the second condition couldn't just be:
>> >>>> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
>> >>>> wakee->nr_wakee_switch) > factor, based on the above explanation from
>> >>>> Micheal Wang that I quoted.
>> >>>> and why he's instead doing the whole multiplication thing there that I
>> >>>> was talking about earlier: "factor * wakee->nr_wakee_switch".
>> >>>>
>> >>>> Rephrasing my question in another way, why are we talking the ratio of
>> >>>> master/slave instead of the sum when comparing if its > factor? I am
>> >>>> surely missing something here.
>> >>>
>> >>> Because the heuristic tries to not demolish 1:1 buddies.  Big partner
>> >>> flip delta means the pair are unlikely to be a communicating pair,
>> >>> perhaps at high frequency where misses hurt like hell.
>> >>
>> >> But it does seem to me to demolish the N:N communicating pairs from a
>> >> latency/load balancing standpoint. For he case of N readers and N
>> >> writers, the ratio (master/slave) comes down to 1:1 and we wake
>> >> affine. Hopefully I didn't miss something too obvious about that.
>> >
>> > I think wake_affine() should correctly handle the case (of
>> > overloading) I bring up here where wake_wide() is too conservative and
>> > does affine a lot, (I don't have any data for this though, this just
>> > from code reading), so I take this comment back for this reason.
>>
>> aargh, nope :( it still runs select_idle_sibling although on the
>> previous CPU even if want_affine is 0 (and doesn't do the wider
>> wakeup..), so the comment still applies.. its easy to get lost into
>> the code with so many if statements :-\  sorry about the noise :)
>>
>
> I've been working in this area recently because of a cpu imbalance problem.
> Wake_wide() definitely makes it so we're waking affine way too often, but I
> think messing with wake_waide to solve that problem is the wrong solution.  This
> is just a heuristic to see if we should wake affine, the simpler the better.  I
> solved the problem of waking affine too often like this
>
> https://marc.info/?l=linux-kernel&m=150003849602535&w=2

Thanks! Cool!

>
> So why do you care about wake_wide() anyway?  Are you observing some problem
> that you suspect is affected by the affine wakeup stuff?  Or are you just trying

I am dealing with an affine wake up issue, yes.

> to understand what is going on for fun?  Cause if you are just doing this for
> fun you are a very strange person, thanks,

Its not just for fun :) Let me give you some background about me, I
work in the Android team and one of the things I want to do is to take
an out of tree patch that's been carried for some time and post a more
upstreamable solution - this is related to wake ups from the binder
driver which does sync wake ups (WF_SYNC). I can't find the exact out
of tree patch publicly since it wasn't posted to a list, but the code
is here [1]. What's worse is I have recently found really bad issues
with this patch itself where runnable times are increased. I should
have provided this background earlier (sorry that I didn't, my plan
was to trigger a separate discussion about the binder sync wake up
thing as a part of a patch/proposal I want to post - which I plan to
do so). Anyway, as a part of this effort, I want to understand
wake_wide() better and "respect" it since it sits in the wake up path
and I wanted to my proposal to work well with it, especially since I
want to solve this problem in an upstream-friendly way.

The other reason to trigger the discussion, is, I have seen
wake_wide() enough number of times and asked enough number of folks
how it works that it seems sensible to ask about it here (I was also
suggested to ask about wake_wide on LKML because since few people
seemingly understand how it works) and hopefully now its a bit better
understood.

I agree with you that instead of spending insane amounts of time on
wake_wide itself, its better to directly work on a problem and collect
some data - which is also what I'm doing, but I still thought its
worth doing some digging into wake_wide() during some free time I had,
thanks.

Cheers,

-Joel

[1] https://android.googlesource.com/kernel/msm.git/+/377e6e28b6097b3d6de7245d3d3def45fc8c9ffc/kernel/sched/fair.c#5492

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

#1700198

On Mon, Jul 31, 2017 at 09:21:46AM -0700, Joel Fernandes wrote:
> Hi Josef,
> 
> On Mon, Jul 31, 2017 at 5:21 AM, Josef Bacik <josef@toxicpanda.com> wrote:
> > On Sat, Jul 29, 2017 at 03:41:56PM -0700, Joel Fernandes wrote:
> >> On Sat, Jul 29, 2017 at 3:28 PM, Joel Fernandes <joelaf@google.com> wrote:
> >> <snip>
> >> >>>> Again I didn't follow why the second condition couldn't just be:
> >> >>>> waker->nr_wakee_switch > factor, or, (waker->nr_wakee_switch +
> >> >>>> wakee->nr_wakee_switch) > factor, based on the above explanation from
> >> >>>> Micheal Wang that I quoted.
> >> >>>> and why he's instead doing the whole multiplication thing there that I
> >> >>>> was talking about earlier: "factor * wakee->nr_wakee_switch".
> >> >>>>
> >> >>>> Rephrasing my question in another way, why are we talking the ratio of
> >> >>>> master/slave instead of the sum when comparing if its > factor? I am
> >> >>>> surely missing something here.
> >> >>>
> >> >>> Because the heuristic tries to not demolish 1:1 buddies.  Big partner
> >> >>> flip delta means the pair are unlikely to be a communicating pair,
> >> >>> perhaps at high frequency where misses hurt like hell.
> >> >>
> >> >> But it does seem to me to demolish the N:N communicating pairs from a
> >> >> latency/load balancing standpoint. For he case of N readers and N
> >> >> writers, the ratio (master/slave) comes down to 1:1 and we wake
> >> >> affine. Hopefully I didn't miss something too obvious about that.
> >> >
> >> > I think wake_affine() should correctly handle the case (of
> >> > overloading) I bring up here where wake_wide() is too conservative and
> >> > does affine a lot, (I don't have any data for this though, this just
> >> > from code reading), so I take this comment back for this reason.
> >>
> >> aargh, nope :( it still runs select_idle_sibling although on the
> >> previous CPU even if want_affine is 0 (and doesn't do the wider
> >> wakeup..), so the comment still applies.. its easy to get lost into
> >> the code with so many if statements :-\  sorry about the noise :)
> >>
> >
> > I've been working in this area recently because of a cpu imbalance problem.
> > Wake_wide() definitely makes it so we're waking affine way too often, but I
> > think messing with wake_waide to solve that problem is the wrong solution.  This
> > is just a heuristic to see if we should wake affine, the simpler the better.  I
> > solved the problem of waking affine too often like this
> >
> > https://marc.info/?l=linux-kernel&m=150003849602535&w=2
> 
> Thanks! Cool!
> 
> >
> > So why do you care about wake_wide() anyway?  Are you observing some problem
> > that you suspect is affected by the affine wakeup stuff?  Or are you just trying
> 
> I am dealing with an affine wake up issue, yes.
> 
> > to understand what is going on for fun?  Cause if you are just doing this for
> > fun you are a very strange person, thanks,
> 
> Its not just for fun :) Let me give you some background about me, I
> work in the Android team and one of the things I want to do is to take
> an out of tree patch that's been carried for some time and post a more
> upstreamable solution - this is related to wake ups from the binder
> driver which does sync wake ups (WF_SYNC). I can't find the exact out
> of tree patch publicly since it wasn't posted to a list, but the code
> is here [1]. What's worse is I have recently found really bad issues
> with this patch itself where runnable times are increased. I should
> have provided this background earlier (sorry that I didn't, my plan
> was to trigger a separate discussion about the binder sync wake up
> thing as a part of a patch/proposal I want to post - which I plan to
> do so). Anyway, as a part of this effort, I want to understand
> wake_wide() better and "respect" it since it sits in the wake up path
> and I wanted to my proposal to work well with it, especially since I
> want to solve this problem in an upstream-friendly way.
> 
> The other reason to trigger the discussion, is, I have seen
> wake_wide() enough number of times and asked enough number of folks
> how it works that it seems sensible to ask about it here (I was also
> suggested to ask about wake_wide on LKML because since few people
> seemingly understand how it works) and hopefully now its a bit better
> understood.
> 
> I agree with you that instead of spending insane amounts of time on
> wake_wide itself, its better to directly work on a problem and collect
> some data - which is also what I'm doing, but I still thought its
> worth doing some digging into wake_wide() during some free time I had,
> thanks.
> 

Ok so your usecase is to _always_ wake affine if we're doing a sync wakeup.  I
_think_ for your case it's best to make wake_affine() make this decision, and
you don't want wake_wide() to filter out your wakeup as not-affine?  So perhaps
just throw a test in there to not wake wide if WF_SYNC is set.  This makes
logical sense to me as synchronous wakeups are probably going to want to be
affine wakeups, and then we can rely on wake_affine() to do the load checks to
make sure it really makes sense.  How does that sound?  Thanks,

Josef

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

#1700287

On Mon, Jul 31, 2017 at 9:42 AM, Josef Bacik <josef@toxicpanda.com> wrote:
<snip>
>>
>> >
>> > So why do you care about wake_wide() anyway?  Are you observing some problem
>> > that you suspect is affected by the affine wakeup stuff?  Or are you just trying
>>
>> I am dealing with an affine wake up issue, yes.
>>
>> > to understand what is going on for fun?  Cause if you are just doing this for
>> > fun you are a very strange person, thanks,
>>
>> Its not just for fun :) Let me give you some background about me, I
>> work in the Android team and one of the things I want to do is to take
>> an out of tree patch that's been carried for some time and post a more
>> upstreamable solution - this is related to wake ups from the binder
>> driver which does sync wake ups (WF_SYNC). I can't find the exact out
>> of tree patch publicly since it wasn't posted to a list, but the code
>> is here [1]. What's worse is I have recently found really bad issues
>> with this patch itself where runnable times are increased. I should
>> have provided this background earlier (sorry that I didn't, my plan
>> was to trigger a separate discussion about the binder sync wake up
>> thing as a part of a patch/proposal I want to post - which I plan to
>> do so). Anyway, as a part of this effort, I want to understand
>> wake_wide() better and "respect" it since it sits in the wake up path
>> and I wanted to my proposal to work well with it, especially since I
>> want to solve this problem in an upstream-friendly way.
>>
>> The other reason to trigger the discussion, is, I have seen
>> wake_wide() enough number of times and asked enough number of folks
>> how it works that it seems sensible to ask about it here (I was also
>> suggested to ask about wake_wide on LKML because since few people
>> seemingly understand how it works) and hopefully now its a bit better
>> understood.
>>
>> I agree with you that instead of spending insane amounts of time on
>> wake_wide itself, its better to directly work on a problem and collect
>> some data - which is also what I'm doing, but I still thought its
>> worth doing some digging into wake_wide() during some free time I had,
>> thanks.
>>
>
> Ok so your usecase is to _always_ wake affine if we're doing a sync wakeup.  I
> _think_ for your case it's best to make wake_affine() make this decision, and
> you don't want wake_wide() to filter out your wakeup as not-affine?  So perhaps
> just throw a test in there to not wake wide if WF_SYNC is set.  This makes

Hmm I was actually thinking that since 'sync' is more of a hint, that
we do a wake_wide() first anyway since its already so conservative,
and for the times it does resort to wide, its probably the right
decision from a scheduling standpoint to avoid affine and avoid too
many tasks too quickly. Do you think that's a fair?

I tried a quick patch and doing wake_wide first, and then checking for
sync does seem to work well.

> logical sense to me as synchronous wakeups are probably going to want to be
> affine wakeups, and then we can rely on wake_affine() to do the load checks to
> make sure it really makes sense.  How does that sound?  Thanks,

Yep that sounds good and I will try that.

What I was thinking was do the regular wake_wide and wake_affine
checks, and then do something like this:

in select_task_rq_fair, before calling select_idle_sibling, do
something like this to check if only 1 task is running on the waker's
CPU (this is after doing the wake_wide and wake_affine checks)

+               idle_sync = (sync && (new_cpu == cpu) &&
+                            cpu_rq(cpu)->nr_running == 1);

and then in select_idle_sibling, something like:

+               /*
+                * If the previous and target CPU share cache and a sync wakeup
+                * is requested and the CPU is about to goto idle, because it
+                * has only the waker running which requested sync, the target
+                * is a better choice for cache affinity and keeping task's
+                * previous core idle and low power state.
+                */
+               if (idle_sync && cpus_share_cache(prev, target))
+                       return target;
+

I haven't tested this patch though so I'm not sure it works well yet,
but just sharing the idea. What do you think?

thanks,

-Joel

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web