Re: [PATCH] sched, fair: Allow a small degree of load imbalance between SD_NUMA domains

Vincent Guittot
2019-12-19T15:41:28Z

Le Thursday 19 Dec 2019 à 15:18:24 (+0000), Mel Gorman a écrit :
> On Thu, Dec 19, 2019 at 03:45:39PM +0100, Vincent Guittot wrote:
> > Hi Mel,
> >
> > Thanks for looking at this NUMA locality vs spreading tasks point.
> >
>
> No problem.
>
> > > @@ -8680,7 +8676,7 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
> > > env->migration_type = migrate_task;
> > > lsub_positive(&nr_diff, local->sum_nr_running);
> > > env->imbalance = nr_diff >> 1;
> > > - return;
> > > + goto out_spare;
> >
> > Why are you doing this only for prefer_sibling case ? That's probably the default case of most of numa system but you should also consider others case too.
> >
>
> It's the common case for NUMA machines I'm aware of and from the
> perspective of allowing a slight imbalance when there are spare CPUs, I
> felt it was the same whether we were considering idle CPUs or the number
> of tasks running.
>
> The prefer_sibling case applies to the children and the corner case is
> that balancing NUMA domains takes into account whether the MC domain
> prefers siblings which is a bit odd. I believe, but don't know, that the
> reasoning may have been to spread load for memory bandwidth usage.
>
> > So you should probably add your
> >
> > > +                * Whether balancing the number of running tasks or the number
> > > +                * of idle CPUs, consider allowing some degree of imbalance if
> > > +                * migrating between NUMA domains.
> > > +                */
> > > +               if (env->sd->flags & SD_NUMA) {
> > > +                       unsigned int imbalance_adj, imbalance_max;
> >
> > ...
> >
> > > +               }
> >
> > before the prefer_sibling case :
> >
> > if (busiest->group_weight == 1 || sds->prefer_sibling) {
> > unsigned int nr_diff = busiest->sum_nr_running;
> > /*
> > * When prefer sibling, evenly spread running tasks on
> > * groups.
> > */
> >
>
> I don't understand. If I move SD_NUMA checks above the imbalance
> calculation, how do I know whether the imbalance should be ignored?

You are only clearing env->imbalance before returning if the condition
between sum_nr_running with weight doesn't match so you don't care about
what will be the value of env->imbalance in the other case so you can have

if ((env->sd->flags & SD_NUMA) &&
( allow some degrees of imbalance )) {
env->imbalance = 0
return;
}

if (busiest->group_weight == 1 || sds->prefer_sibling) {
unsigned int nr_diff = busiest->sum_nr_running;
/*
* When prefer sibling, evenly spread running tasks on
* groups.
*/
env->migration_type = migrate_task;
lsub_positive(&nr_diff, local->sum_nr_running);
env->imbalance = nr_diff >> 1;
return;
}

/*
* If there is no overload, we just want to even the number of
* idle cpus.
*/
env->migration_type = migrate_task;
env->imbalance = max_t(long, 0, (local->idle_cpus -
busiest->idle_cpus) >> 1);
return;
}

>
> >
> > >
> > > }
> > >
> > > /*
> > > @@ -8690,6 +8686,38 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
> > > env->migration_type = migrate_task;
> > > env->imbalance = max_t(long, 0, (local->idle_cpus -
> > > busiest->idle_cpus) >> 1);
> > > +
> > > +out_spare:
> > > + /*
> > > + * Whether balancing the number of running tasks or the number
> > > + * of idle CPUs, consider allowing some degree of imbalance if
> > > + * migrating between NUMA domains.
> > > + */
> > > + if (env->sd->flags & SD_NUMA) {
> > > + unsigned int imbalance_adj, imbalance_max;
> > > +
> > > + /*
> > > + * imbalance_adj is the allowable degree of imbalance
> > > + * to exist between two NUMA domains. It's calculated
> > > + * relative to imbalance_pct with a minimum of two
> > > + * tasks or idle CPUs.
> > > + */
> > > + imbalance_adj = (busiest->group_weight *
> > > + (env->sd->imbalance_pct - 100) / 100) >> 1;
> > > + imbalance_adj = max(imbalance_adj, 2U);
> > > +
> > > + /*
> > > + * Ignore imbalance unless busiest sd is close to 50%
> > > + * utilisation. At that point balancing for memory
> > > + * bandwidth and potentially avoiding unnecessary use
> > > + * of HT siblings is as relevant as memory locality.
> > > + */
> > > + imbalance_max = (busiest->group_weight >> 1) - imbalance_adj;
> > > + if (env->imbalance <= imbalance_adj &&
> > > + busiest->sum_nr_running < imbalance_max) {i
> >
> > Shouldn't you consider the number of busiest->idle_cpus instead of the busiest->sum_nr_running ?
> >
>
> Why? CPU affinity could have stacked multiple tasks on one CPU where
> as I'm looking for a proxy hint on the amount of bandwidth required.
> sum_nr_running does not give me an accurate estimate but it's better than
> idle cpus.

Because even if you have multiple tasks on one CPU, only one will run at a
time on the CPU and others will wait so the bandwidth is effectively link to
the number of running CPUs more than number of runnable tasks

>
> > and you could simplify by
> >
> >
> > if ((env->sd->flags & SD_NUMA) &&
> > ((100 * busiest->group_weight) <= (env->sd->imbalance_pct * (busiest->idle_cpus << 1)))) {
> > env->imbalance = 0;
> > return;
> > }
> >
> > And otherwise it will continue with the current path
> >
>
> I ended up doing something similar to this in v2 but it's a bit more
> expanded so I can put in comments on why the comparisons are the way
> they are. The multiplications are in the slow path.
>
> > Also I'm a bit worry about using a 50% threshold that look a bit like a
> > heuristic which can change depending of platform and the UCs that run of the
> > system.
> >
>
> UCs?

Use Cases

>
> And yes, it's a heuristic. In this case, I'm as concerned about memory
> bandwidth availability as I am about improper locality due to agressive
> balancing. We do not know the available memory bandwidth and we do not
> know how much bandwidth the tasks required so 50% was as good as threshold
> as any. I do not know of any way that can cheaply measure either bandwidth
> usage (PMUs are not cheap) or available bandwidth (theoretical bandwidth !=
> actual bandwidth).
>
> In an earlier version that I never posted, I had no cutoff at all and
> NAS took a roughly 30% performance penalty across all computational
> kernels. Debug tracing led me to this cutoff and running a battery
> of workloads led me to believe that it was a reasonable cutoff. It's
> important.
>
> > In fact i was hoping that we could use the numa_preferred_nid ?
>
> Unfortunately not. For some tasks, they are not long-lived enough for NUMA
> balancing to make a decision. For longer-lived tasks, if load balancing is
> spreading the load across nodes and wakeups are pulling tasks together,
> NUMA balancing will get a mix of remote/local samples and will be unable
> to pick a node properly.
>
> In the netperf figures I put in the changelog, I pointed out that NUMA
> balancing sampled roughly 50% of accesses were remote. With the patch,
> 100% of the samples are local.
>
> > During the
> > detach of tasks, we don't detach the task if busiest has spare capacity and
> > preferred_nid of the task is busiest.
> >
>
> Sure, but again if load balancing and waker/wakees are fighting each
> other, NUMA balancing gets caught in the crossfire and cannot make a
> sensible decision.
>
> --
> Mel Gorman
> SUSE Labs