Re: wake_wide mechanism clarification

From: Brendan Jackman
Date: Thu Aug 03 2017 - 11:05:22 EST


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