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

[Vincent Guittot <vincent.guittot@linaro.org>]

Hi Mel,

Thanks for looking at this NUMA locality vs spreading tasks point.

Le Wednesday 18 Dec 2019 à 15:44:02 (+0000), Mel Gorman a écrit :
> The CPU load balancer balances between different domains to spread load
> and strives to have equal balance everywhere. Communicating tasks can
> migrate so they are topologically close to each other but these decisions
> are independent. On a lightly loaded NUMA machine, two communicating tasks
> pulled together at wakeup time can be pushed apart by the load balancer.
> In isolation, the load balancer decision is fine but it ignores the tasks
> data locality and the wakeup/LB paths continually conflict. NUMA balancing
> is also a factor but it also simply conflicts with the load balancer.
> 

[snip]

> There is some impact but there is a degree of variability and the ones
> showing impact are mainly workloads that are mostly parallelised
> and communicate infrequently between tests. It's a corner case where
> the workload benefits heavily from spreading wide and early which is
> not common. This is intended to illustrate the worst case measured.
> 
> In general, the patch simply seeks to avoid unnecessarily cross-node
> migrations when a machine is lightly loaded but shows benefits for other
> workloads. While tests are still running, so far it seems to benefit
> light-utilisation smaller workloads on large machines and does not appear
> to do any harm to larger or parallelised workloads.
> 
> Signed-off-by: Mel Gorman <mgorman@techsingularity.net>
> ---
>  kernel/sched/fair.c | 38 +++++++++++++++++++++++++++++++++-----
>  1 file changed, 33 insertions(+), 5 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 08a233e97a01..1dc8c7800fc0 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8637,10 +8637,6 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
>  	/*
>  	 * Try to use spare capacity of local group without overloading it or
>  	 * emptying busiest.
> -	 * XXX Spreading tasks across NUMA nodes is not always the best policy
> -	 * and special care should be taken for SD_NUMA domain level before
> -	 * spreading the tasks. For now, load_balance() fully relies on
> -	 * NUMA_BALANCING and fbq_classify_group/rq to override the decision.
>  	 */
>  	if (local->group_type == group_has_spare) {
>  		if (busiest->group_type > group_fully_busy) {
> @@ -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.

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


>
>  		}
>  
>  		/*
> @@ -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 ?

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

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.

In fact i was hoping that we could use the numa_preferred_nid ? During the
detach of tasks, we don't detach the task if busiest has spare capacity and
preferred_nid of the task is busiest.

I'm going to run some tests to see the impact on my platform 

Regards,
Vincent
}


> +				env->imbalance = 0;
> +			}
> +		}
>  		return;
>  	}
>  
> 
> -- 
> Mel Gorman
> SUSE Labs