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

Groups > linux.kernel > #1678336 > unrolled thread

wake_wide mechanism clarification

Back to article view | Back to linux.kernel

Contents

  wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-06-30 02:20 +0200
    Re: wake_wide mechanism clarification Josef Bacik <josef@toxicpanda.com> - 2017-06-30 02:50 +0200
      Re: wake_wide mechanism clarification Joel Fernandes <joelaf@google.com> - 2017-06-30 05:10 +0200
        Re: wake_wide mechanism clarification Josef Bacik <josef@toxicpanda.com> - 2017-06-30 16:30 +0200
          Re: wake_wide mechanism clarification Mike Galbraith <umgwanakikbuti@gmail.com> - 2017-06-30 19:10 +0200
            Re: wake_wide mechanism clarification Josef Bacik <josef@toxicpanda.com> - 2017-06-30 20:00 +0200
      Re: wake_wide mechanism clarification Mike Galbraith <umgwanakikbuti@gmail.com> - 2017-06-30 05:20 +0200
      Re: wake_wide mechanism clarification Matt Fleming <matt@codeblueprint.co.uk> - 2017-06-30 15:20 +0200

#1678336 — wake_wide mechanism clarification

Dear Mike,

I wanted your kind help to understand your patch "sched: beef up
wake_wide()"[1] which is a modification to the original patch from
Michael Wang [2].

In particular, I didn't following the following comment:
" to shared cache, we look for a minimum 'flip' frequency of llc_size
in one partner, and a factor of lls_size higher frequency in the
other."

Why are wanting the master's flip frequency to be higher than the
slaves by the factor?

The code here is written as:

if (slave < factor || master < slave * factor)
   return 0;

However I think we should just do (with my current and probably wrong
understanding):

if (slave < factor || master < factor)
    return 0;

Basically, I didn't follow why we multiply the slave's flips with
llc_size. That makes it sound like the master has to have way more
flips than the slave to return 0 from wake_wide. Could you maybe give
an example to clarify? Thanks a lot for your help,

I am also CC'ing Peter and some ARM folks for the discussion (and also
Jocef who was discuss it with Mike on the mailing list few years ago).

Thanks,
Joel

[1] https://patchwork.kernel.org/patch/6787941/
[2] https://lkml.org/lkml/2013/7/4/20

[toc] | [next] | [standalone]

#1678344

On Thu, Jun 29, 2017 at 05:19:14PM -0700, Joel Fernandes wrote:
> Dear Mike,
> 
> I wanted your kind help to understand your patch "sched: beef up
> wake_wide()"[1] which is a modification to the original patch from
> Michael Wang [2].
> 
> In particular, I didn't following the following comment:
> " to shared cache, we look for a minimum 'flip' frequency of llc_size
> in one partner, and a factor of lls_size higher frequency in the
> other."
> 
> Why are wanting the master's flip frequency to be higher than the
> slaves by the factor?

(Responding from my personal email as my work email is outlook shit and
impossible to use)

Because we are trying to detect the case that the master is waking many
different processes, and the 'slave' processes are only waking up the
master/some other specific processes to determine if we don't care about cache
locality.

> 
> The code here is written as:
> 
> if (slave < factor || master < slave * factor)
>    return 0;
> 
> However I think we should just do (with my current and probably wrong
> understanding):
> 
> if (slave < factor || master < factor)
>     return 0;
> 

Actually I think both are wrong, but I need Mike to weigh in.  In my example
above we'd return 0, because the 'producer' will definitely have a wakee_flip of
ridiculous values, but the 'consumer' could essentially have a wakee_flip of 1,
just the master to tell it that it's done.  I _suppose_ in practice you have a
lock or something so the wakee_flip isn't going to be strictly 1, but some
significantly lower value than master.  I'm skeptical of the slave < factor
test, I think it's too high of a bar in the case where cache locality doesn't
really matter, but the master < slave * factor makes sense, as slave is going to
be orders of magnitude lower than master.

> Basically, I didn't follow why we multiply the slave's flips with
> llc_size. That makes it sound like the master has to have way more
> flips than the slave to return 0 from wake_wide. Could you maybe give
> an example to clarify? Thanks a lot for your help,
> 

It may be worth to try with schedbench and trace it to see how this turns out in
practice, as that's the workload that generated all this discussion before.  I
imagine generally speaking this works out properly.  The small regression I
reported before was at low RPS, so we wouldn't be waking up as many tasks as
often, so we would be returning 0 from wake_wide() and we'd get screwed.  This
is where I think possibly dropping the slave < factor part of the test would
address that, but I'd have to trace it to say for sure.  Thanks,

Josef

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

#1678420

Hi Josef,

Thanks a lot for your reply, :-)

On Thu, Jun 29, 2017 at 5:49 PM, Josef Bacik <josef@toxicpanda.com> wrote:
> Because we are trying to detect the case that the master is waking many
> different processes, and the 'slave' processes are only waking up the
> master/some other specific processes to determine if we don't care about cache
> locality.
>
>>
>> The code here is written as:
>>
>> if (slave < factor || master < slave * factor)
>>    return 0;
>>
>> However I think we should just do (with my current and probably wrong
>> understanding):
>>
>> if (slave < factor || master < factor)
>>     return 0;
>>
>
> Actually I think both are wrong, but I need Mike to weigh in.  In my example
> above we'd return 0, because the 'producer' will definitely have a wakee_flip of
> ridiculous values, but the 'consumer' could essentially have a wakee_flip of 1,
> just the master to tell it that it's done.  I _suppose_ in practice you have a
> lock or something so the wakee_flip isn't going to be strictly 1, but some
> significantly lower value than master.  I'm skeptical of the slave < factor
> test, I think it's too high of a bar in the case where cache locality doesn't
> really matter, but the master < slave * factor makes sense, as slave is going to
> be orders of magnitude lower than master.

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). I know slave's flips are probably low and need to be
higher, but why its multiplied with llc_size than some other number
(in other words - why we are tying the size of a NUMA node or a
cluster size with the number of wake-ups that the slave made)? Is this
because of an assumption that a master is expected to evenly
distribute work amongs CPUs within its node or something like that?

More over, this case is only for when slave wakeups are far lower than
the master. But, what about the case where slave wakes up are greater
than the factor but approximately equal or around the same as the
masters'. Then, it sounds like (master < slave * factor) can return
true. In that case wake_wide() will be = 0. That sounds like a bad
thing to do I think - pull a busy slave onto a busy master.

>> Basically, I didn't follow why we multiply the slave's flips with
>> llc_size. That makes it sound like the master has to have way more
>> flips than the slave to return 0 from wake_wide. Could you maybe give
>> an example to clarify? Thanks a lot for your help,
>>
>
> It may be worth to try with schedbench and trace it to see how this turns out in
> practice, as that's the workload that generated all this discussion before.  I
> imagine generally speaking this works out properly.  The small regression I

I see. I will try to find some time to play with this tool. Thanks for
the pointer.

> reported before was at low RPS, so we wouldn't be waking up as many tasks as
> often, so we would be returning 0 from wake_wide() and we'd get screwed.  This
> is where I think possibly dropping the slave < factor part of the test would
> address that, but I'd have to trace it to say for sure.

Ah, I see your problem. I guess its a conflicting case/requirement? I
guess somehow to handle your case, it has to be embedded into this
condition that cache locality doesn't matter as that seems to be the
assumption of slave < factor as you pointed.

Thanks,
Joel

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

#1678879

On Thu, Jun 29, 2017 at 08:04:59PM -0700, Joel Fernandes wrote:
> Hi Josef,
> 
> Thanks a lot for your reply, :-)
> 
> On Thu, Jun 29, 2017 at 5:49 PM, Josef Bacik <josef@toxicpanda.com> wrote:
> > Because we are trying to detect the case that the master is waking many
> > different processes, and the 'slave' processes are only waking up the
> > master/some other specific processes to determine if we don't care about cache
> > locality.
> >
> >>
> >> The code here is written as:
> >>
> >> if (slave < factor || master < slave * factor)
> >>    return 0;
> >>
> >> However I think we should just do (with my current and probably wrong
> >> understanding):
> >>
> >> if (slave < factor || master < factor)
> >>     return 0;
> >>
> >
> > Actually I think both are wrong, but I need Mike to weigh in.  In my example
> > above we'd return 0, because the 'producer' will definitely have a wakee_flip of
> > ridiculous values, but the 'consumer' could essentially have a wakee_flip of 1,
> > just the master to tell it that it's done.  I _suppose_ in practice you have a
> > lock or something so the wakee_flip isn't going to be strictly 1, but some
> > significantly lower value than master.  I'm skeptical of the slave < factor
> > test, I think it's too high of a bar in the case where cache locality doesn't
> > really matter, but the master < slave * factor makes sense, as slave is going to
> > be orders of magnitude lower than master.
> 
> 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). I know slave's flips are probably low and need to be
> higher, but why its multiplied with llc_size than some other number
> (in other words - why we are tying the size of a NUMA node or a
> cluster size with the number of wake-ups that the slave made)? Is this
> because of an assumption that a master is expected to evenly
> distribute work amongs CPUs within its node or something like that?
> 

Yeah I don't know why llc_size was chosen, but I've been thinking about this on
and off since last night and I don't really know what the right thing to use
would be.  We need some arbitrary number, and any arbitrary number is going to
be wrong for one workload when its fine for another workload.

What we really want is to know how many different tasks we could potentially
wake up to compare against, and that's kind of impossible.  If we did it based
soley on actual wakee_flips values we could end up with the case that 1 tasks
that has 2 worker tasks always being wake_wide, and that may not be as helpful.
With processes that are threaded then sure we have a readily available number to
use, but for things that are discrete processes that talk over say a pipe or
shared memory that's going to be unpossible to tease out.  I haven't had my Mt.
Dew this morning so if you have a better idea for a factor I'm all ears.

> More over, this case is only for when slave wakeups are far lower than
> the master. But, what about the case where slave wakes up are greater
> than the factor but approximately equal or around the same as the
> masters'. Then, it sounds like (master < slave * factor) can return
> true. In that case wake_wide() will be = 0. That sounds like a bad
> thing to do I think - pull a busy slave onto a busy master.
> 

This I think is a flaw in our load balancing assumptions.  I've been drowning in
this code recently because of a cgroups imbalance problem.  We don't really
propagate load well for processes that are on the rq but haven't run yet, so I
feel this plays into this problem where we think the cpu we're pulling to has
plenty of capacity when in reality it doesnt.

I'm going to tool around with this logic some this morning and see if I can make
it a little bit smarter, I'll let you know how it goes.  Thanks,

Josef

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

#1679001

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

	-Mike

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

#1679045

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

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,

Josef

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

#1678425

On Thu, 2017-06-29 at 20:49 -0400, Josef Bacik wrote:
> On Thu, Jun 29, 2017 at 05:19:14PM -0700, Joel Fernandes wrote:
> 
> > Why are wanting the master's flip frequency to be higher than the
> > slaves by the factor?
> 
> (Responding from my personal email as my work email is outlook shit and
> impossible to use)
> 
> Because we are trying to detect the case that the master is waking many
> different processes, and the 'slave' processes are only waking up the
> master/some other specific processes to determine if we don't care about cache
> locality.

Yes, the heuristic (large delta implies waker/wakee are NOT 1:1, ie
filter out high frequency communication where eating misses doesn't
merely sting, it hurts like hell) just became bidirectional.

> Actually I think both are wrong, but I need Mike to weigh in.

My weigh in is this: if you have ideas to improve or replace that
heuristic, by all means go for it, just make damn sure it's dirt cheap.
 Heuristics all suck one way or another, problem is that nasty old
"perfect is the enemy of good" adage.  Make it perfect, it'll hurt.

	-Mike

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

#1678816

On Thu, 29 Jun, at 08:49:13PM, Josef Bacik wrote:
> 
> It may be worth to try with schedbench and trace it to see how this turns out in
> practice, as that's the workload that generated all this discussion before.  I
> imagine generally speaking this works out properly.  The small regression I
> reported before was at low RPS, so we wouldn't be waking up as many tasks as
> often, so we would be returning 0 from wake_wide() and we'd get screwed.  This
> is where I think possibly dropping the slave < factor part of the test would
> address that, but I'd have to trace it to say for sure.  Thanks,

Just 2 weeks ago I was poking at wake_wide() because it's impacting
hackbench times now we're better at balancing on fork() (see commit
6b94780e45c1 ("sched/core: Use load_avg for selecting idlest group")).

What's happening is that occasionally the hackbench times will be
pretty large because the hackbench tasks are being pulled back and
forth across NUMA domains due to the wake_wide() logic.

Reproducing this issue does require a NUMA box with more CPUs than
hackbench tasks. I was using an 80-cpu 2 NUMA node box with 1
hackbench group (20 readers, 20 writers).

I did the following very quick hack,

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a1f5efa51dc7..c1bc1b0434bd 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5055,7 +5055,7 @@ static int wake_wide(struct task_struct *p)

        if (master < slave)
                swap(master, slave);
-       if (slave < factor || master < slave * factor)
+       if (master < slave * factor)
                return 0;
        return 1;
 }

Which produces the following results for the 1 group (40 tasks) on one
of SUSE's enterprise kernels:

hackbench-process-pipes
                            4.4.71                4.4.71
                          patched+patched+-wake-wide-fix
Min      1        0.7000 (  0.00%)      0.8480 (-21.14%)
Amean    1        1.0343 (  0.00%)      0.9073 ( 12.28%)
Stddev   1        0.2373 (  0.00%)      0.0447 ( 81.15%)
CoeffVar 1       22.9447 (  0.00%)      4.9300 ( 78.51%)
Max      1        1.2270 (  0.00%)      0.9560 ( 22.09%)

You'll see that the minimum value is worse with my change, but the
maximum is much better.

So the current wake_wide() code does help sometimes, but it also hurts
sometimes too.

I'm happy to gather performance data for any code suggestions.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web