[v3,07/24] sched/fair: Compute IPC class scores for load balancing

Commit Message

Ricardo Neri Feb. 7, 2023, 5:10 a.m. UTC

Compute the joint total (both current and prospective) IPC class score of
a scheduling group and the local scheduling group.

These IPCC statistics are used during idle load balancing. The candidate
scheduling group will have one fewer busy CPU after load balancing. This
observation is important for cores with SMT support.

The IPCC score of scheduling groups composed of SMT siblings needs to
consider that the siblings share CPU resources. When computing the total
IPCC score of the scheduling group, divide score of each sibling by the
number of busy siblings.

Collect IPCC statistics for asym_packing and fully_busy scheduling groups.
When picking a busiest group, they are used to break ties between otherwise
identical groups.

Cc: Ben Segall <[e-mail]>
Cc: Daniel Bristot de Oliveira <[e-mail]>
Cc: Dietmar Eggemann <[e-mail]>
Cc: Ionela Voinescu <[e-mail]>
Cc: Joel Fernandes (Google) <[e-mail]>
Cc: Len Brown <[e-mail]>
Cc: Lukasz Luba <[e-mail]>
Cc: Mel Gorman <[e-mail]>
Cc: Rafael J. Wysocki <[e-mail]>
Cc: Srinivas Pandruvada <[e-mail]>
Cc: Steven Rostedt <[e-mail]>
Cc: Tim C. Chen <[e-mail]>
Cc: Valentin Schneider <[e-mail]>
Cc: [e-mail]
Cc: [e-mail]
Cc: [e-mail]
Signed-off-by: Ricardo Neri <[e-mail]>
---
Changes since v2:
 * Also collect IPCC stats for fully_busy sched groups.
 * Restrict use of IPCC stats to SD_ASYM_PACKING. (Ionela)
 * Handle errors of arch_get_ipcc_score(). (Ionela)

Changes since v1:
 * Implemented cleanups and reworks from PeterZ. I took all his
   suggestions, except the computation of the  IPC score before and after
   load balancing. We are computing not the average score, but the *total*.
 * Check for the SD_SHARE_CPUCAPACITY to compute the throughput of the SMT
   siblings of a physical core.
 * Used the new interface names.
 * Reworded commit message for clarity.
---
 kernel/sched/fair.c | 68 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 68 insertions(+)

Comments

Vincent Guittot March 28, 2023, 10 a.m. UTC | #1

On Tue, 7 Feb 2023 at 06:01, Ricardo Neri
<[e-mail]> wrote:
>
> Compute the joint total (both current and prospective) IPC class score of
> a scheduling group and the local scheduling group.
>
> These IPCC statistics are used during idle load balancing. The candidate
> scheduling group will have one fewer busy CPU after load balancing. This
> observation is important for cores with SMT support.
>
> The IPCC score of scheduling groups composed of SMT siblings needs to
> consider that the siblings share CPU resources. When computing the total
> IPCC score of the scheduling group, divide score of each sibling by the
> number of busy siblings.
>
> Collect IPCC statistics for asym_packing and fully_busy scheduling groups.

IPCC statistics collect scores of current tasks, so they are
meaningful only when trying to migrate one of those running tasks.
Using such score when pulling other tasks is just meaningless. And I
don't see how you ensure such correct use of ipcc score

> When picking a busiest group, they are used to break ties between otherwise
> identical groups.
>
> Cc: Ben Segall <[e-mail]>
> Cc: Daniel Bristot de Oliveira <[e-mail]>
> Cc: Dietmar Eggemann <[e-mail]>
> Cc: Ionela Voinescu <[e-mail]>
> Cc: Joel Fernandes (Google) <[e-mail]>
> Cc: Len Brown <[e-mail]>
> Cc: Lukasz Luba <[e-mail]>
> Cc: Mel Gorman <[e-mail]>
> Cc: Rafael J. Wysocki <[e-mail]>
> Cc: Srinivas Pandruvada <[e-mail]>
> Cc: Steven Rostedt <[e-mail]>
> Cc: Tim C. Chen <[e-mail]>
> Cc: Valentin Schneider <[e-mail]>
> Cc: [e-mail]
> Cc: [e-mail]
> Cc: [e-mail]
> Signed-off-by: Ricardo Neri <[e-mail]>
> ---
> Changes since v2:
>  * Also collect IPCC stats for fully_busy sched groups.

Why have you added fully_busy case ? it's worth explaining the
rational because there is a lot of change to use the ipcc score of the
wrong task to take the decision

>  * Restrict use of IPCC stats to SD_ASYM_PACKING. (Ionela)
>  * Handle errors of arch_get_ipcc_score(). (Ionela)
>
> Changes since v1:
>  * Implemented cleanups and reworks from PeterZ. I took all his
>    suggestions, except the computation of the  IPC score before and after
>    load balancing. We are computing not the average score, but the *total*.
>  * Check for the SD_SHARE_CPUCAPACITY to compute the throughput of the SMT
>    siblings of a physical core.
>  * Used the new interface names.
>  * Reworded commit message for clarity.
> ---
>  kernel/sched/fair.c | 68 +++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 68 insertions(+)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index d773380a95b3..b6165aa8a376 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8901,6 +8901,8 @@ struct sg_lb_stats {
>         unsigned long min_score; /* Min(score(rq->curr->ipcc)) */
>         unsigned short min_ipcc; /* Class of the task with the minimum IPCC score in the rq */
>         unsigned long sum_score; /* Sum(score(rq->curr->ipcc)) */
> +       long ipcc_score_after; /* Prospective IPCC score after load balancing */
> +       unsigned long ipcc_score_before; /* IPCC score before load balancing */
>  #endif
>  };
>
> @@ -9287,6 +9289,62 @@ static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
>         }
>  }
>
> +static void update_sg_lb_stats_scores(struct sg_lb_stats *sgs,
> +                                     struct sched_group *sg,
> +                                     struct lb_env *env)
> +{
> +       unsigned long score_on_dst_cpu, before;
> +       int busy_cpus;
> +       long after;
> +
> +       if (!sched_ipcc_enabled())
> +               return;
> +
> +       /*
> +        * IPCC scores are only useful during idle load balancing. For now,
> +        * only asym_packing uses IPCC scores.
> +        */
> +       if (!(env->sd->flags & SD_ASYM_PACKING) ||
> +           env->idle == CPU_NOT_IDLE)
> +               return;
> +
> +       /*
> +        * IPCC scores are used to break ties only between these types of
> +        * groups.
> +        */
> +       if (sgs->group_type != group_fully_busy &&
> +           sgs->group_type != group_asym_packing)
> +               return;
> +
> +       busy_cpus = sgs->group_weight - sgs->idle_cpus;
> +
> +       /* No busy CPUs in the group. No tasks to move. */
> +       if (!busy_cpus)
> +               return;
> +
> +       score_on_dst_cpu = arch_get_ipcc_score(sgs->min_ipcc, env->dst_cpu);
> +
> +       /*
> +        * Do not use IPC scores. sgs::ipcc_score_{after, before} will be zero
> +        * and not used.
> +        */
> +       if (IS_ERR_VALUE(score_on_dst_cpu))
> +               return;
> +
> +       before = sgs->sum_score;
> +       after = before - sgs->min_score;

IIUC, you assume that you will select the cpu with the min score.
How do you ensure this ? otherwise all your comparisong are useless

> +
> +       /* SMT siblings share throughput. */
> +       if (busy_cpus > 1 && sg->flags & SD_SHARE_CPUCAPACITY) {
> +               before /= busy_cpus;
> +               /* One sibling will become idle after load balance. */
> +               after /= busy_cpus - 1;
> +       }
> +
> +       sgs->ipcc_score_after = after + score_on_dst_cpu;
> +       sgs->ipcc_score_before = before;

I'm not sure to understand why you are computing the sum_score,
ipcc_score_before and ipcc_score_after ?
Why is it not sufficient to check if score_on_dst_cpu will be higher
than current min_score ?

> +}
> +
>  #else /* CONFIG_IPC_CLASSES */
>  static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
>                                     struct rq *rq)
> @@ -9296,6 +9354,13 @@ static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
>  static void init_rq_ipcc_stats(struct sg_lb_stats *sgs)
>  {
>  }
> +
> +static void update_sg_lb_stats_scores(struct sg_lb_stats *sgs,
> +                                     struct sched_group *sg,
> +                                     struct lb_env *env)
> +{
> +}
> +
>  #endif /* CONFIG_IPC_CLASSES */
>
>  /**
> @@ -9457,6 +9522,9 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>
>         sgs->group_type = group_classify(env->sd->imbalance_pct, group, sgs);
>
> +       if (!local_group)
> +               update_sg_lb_stats_scores(sgs, group, env);
> +
>         /* Computing avg_load makes sense only when group is overloaded */
>         if (sgs->group_type == group_overloaded)
>                 sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
> --
> 2.25.1
>

Ricardo Neri March 30, 2023, 2:07 a.m. UTC | #2

On Tue, Mar 28, 2023 at 12:00:58PM +0200, Vincent Guittot wrote:
> On Tue, 7 Feb 2023 at 06:01, Ricardo Neri
> <[e-mail]> wrote:
> >
> > Compute the joint total (both current and prospective) IPC class score of
> > a scheduling group and the local scheduling group.
> >
> > These IPCC statistics are used during idle load balancing. The candidate
> > scheduling group will have one fewer busy CPU after load balancing. This
> > observation is important for cores with SMT support.
> >
> > The IPCC score of scheduling groups composed of SMT siblings needs to
> > consider that the siblings share CPU resources. When computing the total
> > IPCC score of the scheduling group, divide score of each sibling by the
> > number of busy siblings.
> >
> > Collect IPCC statistics for asym_packing and fully_busy scheduling groups.
> 
> IPCC statistics collect scores of current tasks, so they are
> meaningful only when trying to migrate one of those running tasks.
> Using such score when pulling other tasks is just meaningless. And I
> don't see how you ensure such correct use of ipcc score

Thank you very much for your feedback Vincent!

It is true that the task that is current when collecting statistics may be
different from the task that is current when we are ready to pluck tasks.

Using IPCC scores for load balancing benefits large, long-running tasks
the most. For these tasks, the current task is likely to remain the same
at the two mentioned points in time.

My patchset proposes to use IPCC clases to break ties between otherwise
identical sched groups in update_sd_pick_busiest(). Its use is limited to
asym_packing and fully_busy types. For these types, it is likely that there
will not be tasks wanting to run other than current. need_active_balance()
will return true and we will migrate the current task.

You are correct, by only looking at the current tasks we risk overlooking
other tasks in the queue and the statistics becoming meaningless. A fully
correct solution would need to keep track of the the types of tasks in
all runqueues as they come and go. IMO, the increased complexity of such
approach does not justify the benefit. We give the load balancer extra
information to decide between otherwise identical sched groups using the
IPCC statistics of big tasks.

> 
> > When picking a busiest group, they are used to break ties between otherwise
> > identical groups.
> >
> > Cc: Ben Segall <[e-mail]>
> > Cc: Daniel Bristot de Oliveira <[e-mail]>
> > Cc: Dietmar Eggemann <[e-mail]>
> > Cc: Ionela Voinescu <[e-mail]>
> > Cc: Joel Fernandes (Google) <[e-mail]>
> > Cc: Len Brown <[e-mail]>
> > Cc: Lukasz Luba <[e-mail]>
> > Cc: Mel Gorman <[e-mail]>
> > Cc: Rafael J. Wysocki <[e-mail]>
> > Cc: Srinivas Pandruvada <[e-mail]>
> > Cc: Steven Rostedt <[e-mail]>
> > Cc: Tim C. Chen <[e-mail]>
> > Cc: Valentin Schneider <[e-mail]>
> > Cc: [e-mail]
> > Cc: [e-mail]
> > Cc: [e-mail]
> > Signed-off-by: Ricardo Neri <[e-mail]>
> > ---
> > Changes since v2:
> >  * Also collect IPCC stats for fully_busy sched groups.
> 
> Why have you added fully_busy case ? it's worth explaining the
> rational because there is a lot of change to use the ipcc score of the
> wrong task to take the decision

When deciding between two fully_busy sched groups, update_sd_pick_busiest()
unconditionally selects the given candidate @sg as busiest. With IPCC
scores, what is running a scheduling group becomes important. We now have
extra information to select either of the fully_busy groups. This is done
in patch 9.

(Also note that in [1] I tweak the logic to select fully_busy SMT cores vs
fully_busy non-SMT cores).

> 
> >  * Restrict use of IPCC stats to SD_ASYM_PACKING. (Ionela)
> >  * Handle errors of arch_get_ipcc_score(). (Ionela)
> >
> > Changes since v1:
> >  * Implemented cleanups and reworks from PeterZ. I took all his
> >    suggestions, except the computation of the  IPC score before and after
> >    load balancing. We are computing not the average score, but the *total*.
> >  * Check for the SD_SHARE_CPUCAPACITY to compute the throughput of the SMT
> >    siblings of a physical core.
> >  * Used the new interface names.
> >  * Reworded commit message for clarity.
> > ---
> >  kernel/sched/fair.c | 68 +++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 68 insertions(+)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index d773380a95b3..b6165aa8a376 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -8901,6 +8901,8 @@ struct sg_lb_stats {
> >         unsigned long min_score; /* Min(score(rq->curr->ipcc)) */
> >         unsigned short min_ipcc; /* Class of the task with the minimum IPCC score in the rq */
> >         unsigned long sum_score; /* Sum(score(rq->curr->ipcc)) */
> > +       long ipcc_score_after; /* Prospective IPCC score after load balancing */
> > +       unsigned long ipcc_score_before; /* IPCC score before load balancing */
> >  #endif
> >  };
> >
> > @@ -9287,6 +9289,62 @@ static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
> >         }
> >  }
> >
> > +static void update_sg_lb_stats_scores(struct sg_lb_stats *sgs,
> > +                                     struct sched_group *sg,
> > +                                     struct lb_env *env)
> > +{
> > +       unsigned long score_on_dst_cpu, before;
> > +       int busy_cpus;
> > +       long after;
> > +
> > +       if (!sched_ipcc_enabled())
> > +               return;
> > +
> > +       /*
> > +        * IPCC scores are only useful during idle load balancing. For now,
> > +        * only asym_packing uses IPCC scores.
> > +        */
> > +       if (!(env->sd->flags & SD_ASYM_PACKING) ||
> > +           env->idle == CPU_NOT_IDLE)
> > +               return;
> > +
> > +       /*
> > +        * IPCC scores are used to break ties only between these types of
> > +        * groups.
> > +        */
> > +       if (sgs->group_type != group_fully_busy &&
> > +           sgs->group_type != group_asym_packing)
> > +               return;
> > +
> > +       busy_cpus = sgs->group_weight - sgs->idle_cpus;
> > +
> > +       /* No busy CPUs in the group. No tasks to move. */
> > +       if (!busy_cpus)
> > +               return;
> > +
> > +       score_on_dst_cpu = arch_get_ipcc_score(sgs->min_ipcc, env->dst_cpu);
> > +
> > +       /*
> > +        * Do not use IPC scores. sgs::ipcc_score_{after, before} will be zero
> > +        * and not used.
> > +        */
> > +       if (IS_ERR_VALUE(score_on_dst_cpu))
> > +               return;
> > +
> > +       before = sgs->sum_score;
> > +       after = before - sgs->min_score;
> 
> IIUC, you assume that you will select the cpu with the min score.
> How do you ensure this ? otherwise all your comparisong are useless

This is relevant for SMT cores. A smaller idle core will help a fully_busy
SMT core by pulling low-IPC work, leaving the full core for high-IPC
work.

We ensure (or anticipate if you will) this because find_busiest_queue()
will select the queue whose current task gets the biggest IPC boost. When
done from big to small cores the IPC boost is negative.

> 
> > +
> > +       /* SMT siblings share throughput. */
> > +       if (busy_cpus > 1 && sg->flags & SD_SHARE_CPUCAPACITY) {
> > +               before /= busy_cpus;
> > +               /* One sibling will become idle after load balance. */
> > +               after /= busy_cpus - 1;
> > +       }
> > +
> > +       sgs->ipcc_score_after = after + score_on_dst_cpu;
> > +       sgs->ipcc_score_before = before;
> 
> I'm not sure to understand why you are computing the sum_score,
> ipcc_score_before and ipcc_score_after ?
> Why is it not sufficient to check if score_on_dst_cpu will be higher
> than current min_score ?

You are right. As the source core becomes idle after load balancing, it is
sufficient to look for the highest score_on_dst_cpu. However, we must also
handle SMT cores.

If the source sched group is a fully_busy SMT core, one of the siblings
will become idle after load balance (my patchset uses IPCC scores for
asym_packing and when balancing the number of idle CPUs from fully_busy).
The remaining non-idle siblings will benefit from the extra throughput.

We calculate ipcc_score_after to find the sched group that would benefit
the most. We calculate ipcc_score_before to break ties of two groups of
identical ipcc_score_after.

Thanks and BR,
Ricardo

[1]. https://lore.kernel.org/lkml/[e-mail]/

Vincent Guittot March 31, 2023, 12:20 p.m. UTC | #3

On Thu, 30 Mar 2023 at 03:56, Ricardo Neri
<[e-mail]> wrote:
>
> On Tue, Mar 28, 2023 at 12:00:58PM +0200, Vincent Guittot wrote:
> > On Tue, 7 Feb 2023 at 06:01, Ricardo Neri
> > <[e-mail]> wrote:
> > >
> > > Compute the joint total (both current and prospective) IPC class score of
> > > a scheduling group and the local scheduling group.
> > >
> > > These IPCC statistics are used during idle load balancing. The candidate
> > > scheduling group will have one fewer busy CPU after load balancing. This
> > > observation is important for cores with SMT support.
> > >
> > > The IPCC score of scheduling groups composed of SMT siblings needs to
> > > consider that the siblings share CPU resources. When computing the total
> > > IPCC score of the scheduling group, divide score of each sibling by the
> > > number of busy siblings.
> > >
> > > Collect IPCC statistics for asym_packing and fully_busy scheduling groups.
> >
> > IPCC statistics collect scores of current tasks, so they are
> > meaningful only when trying to migrate one of those running tasks.
> > Using such score when pulling other tasks is just meaningless. And I
> > don't see how you ensure such correct use of ipcc score
>
> Thank you very much for your feedback Vincent!
>
> It is true that the task that is current when collecting statistics may be
> different from the task that is current when we are ready to pluck tasks.
>
> Using IPCC scores for load balancing benefits large, long-running tasks
> the most. For these tasks, the current task is likely to remain the same
> at the two mentioned points in time.

My point was mainly about the fact that the current running task is
the last one to be pulled. And this happens only when no other task
was pulled otherwise.

>
> My patchset proposes to use IPCC clases to break ties between otherwise
> identical sched groups in update_sd_pick_busiest(). Its use is limited to
> asym_packing and fully_busy types. For these types, it is likely that there
> will not be tasks wanting to run other than current. need_active_balance()
> will return true and we will migrate the current task.

I disagree with your assumption above, asym_packing and fully_busy
types doesn't put any mean on the number of running tasks

>
> You are correct, by only looking at the current tasks we risk overlooking
> other tasks in the queue and the statistics becoming meaningless. A fully
> correct solution would need to keep track of the the types of tasks in
> all runqueues as they come and go. IMO, the increased complexity of such
> approach does not justify the benefit. We give the load balancer extra
> information to decide between otherwise identical sched groups using the
> IPCC statistics of big tasks.

because IPCC are meaningful only when there is only 1 running task and
during active migration, you should collect them only for such
situation

>
> >
> > > When picking a busiest group, they are used to break ties between otherwise
> > > identical groups.
> > >
> > > Cc: Ben Segall <[e-mail]>
> > > Cc: Daniel Bristot de Oliveira <[e-mail]>
> > > Cc: Dietmar Eggemann <[e-mail]>
> > > Cc: Ionela Voinescu <[e-mail]>
> > > Cc: Joel Fernandes (Google) <[e-mail]>
> > > Cc: Len Brown <[e-mail]>
> > > Cc: Lukasz Luba <[e-mail]>
> > > Cc: Mel Gorman <[e-mail]>
> > > Cc: Rafael J. Wysocki <[e-mail]>
> > > Cc: Srinivas Pandruvada <[e-mail]>
> > > Cc: Steven Rostedt <[e-mail]>
> > > Cc: Tim C. Chen <[e-mail]>
> > > Cc: Valentin Schneider <[e-mail]>
> > > Cc: [e-mail]
> > > Cc: [e-mail]
> > > Cc: [e-mail]
> > > Signed-off-by: Ricardo Neri <[e-mail]>
> > > ---
> > > Changes since v2:
> > >  * Also collect IPCC stats for fully_busy sched groups.
> >
> > Why have you added fully_busy case ? it's worth explaining the
> > rational because there is a lot of change to use the ipcc score of the
> > wrong task to take the decision
>
> When deciding between two fully_busy sched groups, update_sd_pick_busiest()
> unconditionally selects the given candidate @sg as busiest. With IPCC
> scores, what is running a scheduling group becomes important. We now have
> extra information to select either of the fully_busy groups. This is done
> in patch 9.
>
> (Also note that in [1] I tweak the logic to select fully_busy SMT cores vs
> fully_busy non-SMT cores).
>
> >
> > >  * Restrict use of IPCC stats to SD_ASYM_PACKING. (Ionela)
> > >  * Handle errors of arch_get_ipcc_score(). (Ionela)
> > >
> > > Changes since v1:
> > >  * Implemented cleanups and reworks from PeterZ. I took all his
> > >    suggestions, except the computation of the  IPC score before and after
> > >    load balancing. We are computing not the average score, but the *total*.
> > >  * Check for the SD_SHARE_CPUCAPACITY to compute the throughput of the SMT
> > >    siblings of a physical core.
> > >  * Used the new interface names.
> > >  * Reworded commit message for clarity.
> > > ---
> > >  kernel/sched/fair.c | 68 +++++++++++++++++++++++++++++++++++++++++++++
> > >  1 file changed, 68 insertions(+)
> > >
> > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > > index d773380a95b3..b6165aa8a376 100644
> > > --- a/kernel/sched/fair.c
> > > +++ b/kernel/sched/fair.c
> > > @@ -8901,6 +8901,8 @@ struct sg_lb_stats {
> > >         unsigned long min_score; /* Min(score(rq->curr->ipcc)) */
> > >         unsigned short min_ipcc; /* Class of the task with the minimum IPCC score in the rq */
> > >         unsigned long sum_score; /* Sum(score(rq->curr->ipcc)) */
> > > +       long ipcc_score_after; /* Prospective IPCC score after load balancing */
> > > +       unsigned long ipcc_score_before; /* IPCC score before load balancing */
> > >  #endif
> > >  };
> > >
> > > @@ -9287,6 +9289,62 @@ static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
> > >         }
> > >  }
> > >
> > > +static void update_sg_lb_stats_scores(struct sg_lb_stats *sgs,
> > > +                                     struct sched_group *sg,
> > > +                                     struct lb_env *env)
> > > +{
> > > +       unsigned long score_on_dst_cpu, before;
> > > +       int busy_cpus;
> > > +       long after;
> > > +
> > > +       if (!sched_ipcc_enabled())
> > > +               return;
> > > +
> > > +       /*
> > > +        * IPCC scores are only useful during idle load balancing. For now,
> > > +        * only asym_packing uses IPCC scores.
> > > +        */
> > > +       if (!(env->sd->flags & SD_ASYM_PACKING) ||
> > > +           env->idle == CPU_NOT_IDLE)
> > > +               return;
> > > +
> > > +       /*
> > > +        * IPCC scores are used to break ties only between these types of
> > > +        * groups.
> > > +        */
> > > +       if (sgs->group_type != group_fully_busy &&
> > > +           sgs->group_type != group_asym_packing)
> > > +               return;
> > > +
> > > +       busy_cpus = sgs->group_weight - sgs->idle_cpus;
> > > +
> > > +       /* No busy CPUs in the group. No tasks to move. */
> > > +       if (!busy_cpus)
> > > +               return;
> > > +
> > > +       score_on_dst_cpu = arch_get_ipcc_score(sgs->min_ipcc, env->dst_cpu);
> > > +
> > > +       /*
> > > +        * Do not use IPC scores. sgs::ipcc_score_{after, before} will be zero
> > > +        * and not used.
> > > +        */
> > > +       if (IS_ERR_VALUE(score_on_dst_cpu))
> > > +               return;
> > > +
> > > +       before = sgs->sum_score;
> > > +       after = before - sgs->min_score;
> >
> > IIUC, you assume that you will select the cpu with the min score.
> > How do you ensure this ? otherwise all your comparisong are useless
>
> This is relevant for SMT cores. A smaller idle core will help a fully_busy
> SMT core by pulling low-IPC work, leaving the full core for high-IPC
> work.
>
> We ensure (or anticipate if you will) this because find_busiest_queue()
> will select the queue whose current task gets the biggest IPC boost. When
> done from big to small cores the IPC boost is negative.
>
> >
> > > +
> > > +       /* SMT siblings share throughput. */
> > > +       if (busy_cpus > 1 && sg->flags & SD_SHARE_CPUCAPACITY) {
> > > +               before /= busy_cpus;
> > > +               /* One sibling will become idle after load balance. */
> > > +               after /= busy_cpus - 1;
> > > +       }
> > > +
> > > +       sgs->ipcc_score_after = after + score_on_dst_cpu;
> > > +       sgs->ipcc_score_before = before;
> >
> > I'm not sure to understand why you are computing the sum_score,
> > ipcc_score_before and ipcc_score_after ?
> > Why is it not sufficient to check if score_on_dst_cpu will be higher
> > than current min_score ?
>
> You are right. As the source core becomes idle after load balancing, it is
> sufficient to look for the highest score_on_dst_cpu. However, we must also
> handle SMT cores.
>
> If the source sched group is a fully_busy SMT core, one of the siblings
> will become idle after load balance (my patchset uses IPCC scores for
> asym_packing and when balancing the number of idle CPUs from fully_busy).
> The remaining non-idle siblings will benefit from the extra throughput.
>
> We calculate ipcc_score_after to find the sched group that would benefit
> the most. We calculate ipcc_score_before to break ties of two groups of
> identical ipcc_score_after.
>
> Thanks and BR,
> Ricardo
>
> [1]. https://lore.kernel.org/lkml/[e-mail]/

Ricardo Neri April 17, 2023, 10:52 p.m. UTC | #4

On Fri, Mar 31, 2023 at 02:20:11PM +0200, Vincent Guittot wrote:
> On Thu, 30 Mar 2023 at 03:56, Ricardo Neri
> <[e-mail]> wrote:
> >
> > On Tue, Mar 28, 2023 at 12:00:58PM +0200, Vincent Guittot wrote:
> > > On Tue, 7 Feb 2023 at 06:01, Ricardo Neri
> > > <[e-mail]> wrote:
> > > >
> > > > Compute the joint total (both current and prospective) IPC class score of
> > > > a scheduling group and the local scheduling group.
> > > >
> > > > These IPCC statistics are used during idle load balancing. The candidate
> > > > scheduling group will have one fewer busy CPU after load balancing. This
> > > > observation is important for cores with SMT support.
> > > >
> > > > The IPCC score of scheduling groups composed of SMT siblings needs to
> > > > consider that the siblings share CPU resources. When computing the total
> > > > IPCC score of the scheduling group, divide score of each sibling by the
> > > > number of busy siblings.
> > > >
> > > > Collect IPCC statistics for asym_packing and fully_busy scheduling groups.
> > >
> > > IPCC statistics collect scores of current tasks, so they are
> > > meaningful only when trying to migrate one of those running tasks.
> > > Using such score when pulling other tasks is just meaningless. And I
> > > don't see how you ensure such correct use of ipcc score
> >
> > Thank you very much for your feedback Vincent!
> >
> > It is true that the task that is current when collecting statistics may be
> > different from the task that is current when we are ready to pluck tasks.
> >
> > Using IPCC scores for load balancing benefits large, long-running tasks
> > the most. For these tasks, the current task is likely to remain the same
> > at the two mentioned points in time.
> 
> My point was mainly about the fact that the current running task is
> the last one to be pulled. And this happens only when no other task
> was pulled otherwise.

(Thanks again for your feedback, Vincent. I am sorry for the late reply. I
needed some more time to think about it.)

Good point! It is smarter to compare and pull from the back of the queue,
rather than comparing curr and pulling from the back. We are more likely
to break the tie correctly without being too complex.

Here is an incremental patch with the update. I'll include this change in
my next version.

@@ -9281,24 +9281,42 @@ static void init_rq_ipcc_stats(struct sg_lb_stats *sgs)
 	sgs->min_score = ULONG_MAX;
 }
 
+static int rq_last_task_ipcc(int dst_cpu, struct rq *rq, unsigned short *ipcc)
+{
+	struct list_head *tasks = &rq->cfs_tasks;
+	struct task_struct *p;
+	struct rq_flags rf;
+	int ret = -EINVAL;
+
+	rq_lock_irqsave(rq, &rf);
+	if (list_empty(tasks))
+		goto out;
+
+	p = list_last_entry(tasks, struct task_struct, se.group_node);
+	if (p->flags & PF_EXITING || is_idle_task(p) ||
+	    !cpumask_test_cpu(dst_cpu, p->cpus_ptr))
+		goto out;
+
+	ret = 0;
+	*ipcc = p->ipcc;
+out:
+	rq_unlock(rq, &rf);
+	return ret;
+}
+
 /* Called only if cpu_of(@rq) is not idle and has tasks running. */
 static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
 				    struct rq *rq)
 {
-	struct task_struct *curr;
 	unsigned short ipcc;
 	unsigned long score;
 
 	if (!sched_ipcc_enabled())
 		return;
 
-	curr = rcu_dereference(rq->curr);
-	if (!curr || (curr->flags & PF_EXITING) || is_idle_task(curr) ||
-	    task_is_realtime(curr) ||
-	    !cpumask_test_cpu(dst_cpu, curr->cpus_ptr))
+	if (rq_last_task_ipcc(dst_cpu, rq, &ipcc))
 		return;
 
-	ipcc = curr->ipcc;
 	score = arch_get_ipcc_score(ipcc, cpu_of(rq));
 
> 
> >
> > My patchset proposes to use IPCC clases to break ties between otherwise
> > identical sched groups in update_sd_pick_busiest(). Its use is limited to
> > asym_packing and fully_busy types. For these types, it is likely that there
> > will not be tasks wanting to run other than current. need_active_balance()
> > will return true and we will migrate the current task.
> 
> I disagree with your assumption above, asym_packing and fully_busy
> types doesn't put any mean on the number of running tasks

Agreed. What I stated was not correct.

o> 
> >
> > You are correct, by only looking at the current tasks we risk overlooking
> > other tasks in the queue and the statistics becoming meaningless. A fully
> > correct solution would need to keep track of the the types of tasks in
> > all runqueues as they come and go. IMO, the increased complexity of such
> > approach does not justify the benefit. We give the load balancer extra
> > information to decide between otherwise identical sched groups using the
> > IPCC statistics of big tasks.
> 
> because IPCC are meaningful only when there is only 1 running task and
> during active migration, you should collect them only for such
> situation

I think that if we compute the IPCC statistics using the tasks at the back
of the runqueue, then IPCC statistics remain meaningful for nr_running >= 1.

Patch

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index d773380a95b3..b6165aa8a376 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8901,6 +8901,8 @@  struct sg_lb_stats {
 	unsigned long min_score; /* Min(score(rq->curr->ipcc)) */
 	unsigned short min_ipcc; /* Class of the task with the minimum IPCC score in the rq */
 	unsigned long sum_score; /* Sum(score(rq->curr->ipcc)) */
+	long ipcc_score_after; /* Prospective IPCC score after load balancing */
+	unsigned long ipcc_score_before; /* IPCC score before load balancing */
 #endif
 };
 
@@ -9287,6 +9289,62 @@  static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
 	}
 }
 
+static void update_sg_lb_stats_scores(struct sg_lb_stats *sgs,
+				      struct sched_group *sg,
+				      struct lb_env *env)
+{
+	unsigned long score_on_dst_cpu, before;
+	int busy_cpus;
+	long after;
+
+	if (!sched_ipcc_enabled())
+		return;
+
+	/*
+	 * IPCC scores are only useful during idle load balancing. For now,
+	 * only asym_packing uses IPCC scores.
+	 */
+	if (!(env->sd->flags & SD_ASYM_PACKING) ||
+	    env->idle == CPU_NOT_IDLE)
+		return;
+
+	/*
+	 * IPCC scores are used to break ties only between these types of
+	 * groups.
+	 */
+	if (sgs->group_type != group_fully_busy &&
+	    sgs->group_type != group_asym_packing)
+		return;
+
+	busy_cpus = sgs->group_weight - sgs->idle_cpus;
+
+	/* No busy CPUs in the group. No tasks to move. */
+	if (!busy_cpus)
+		return;
+
+	score_on_dst_cpu = arch_get_ipcc_score(sgs->min_ipcc, env->dst_cpu);
+
+	/*
+	 * Do not use IPC scores. sgs::ipcc_score_{after, before} will be zero
+	 * and not used.
+	 */
+	if (IS_ERR_VALUE(score_on_dst_cpu))
+		return;
+
+	before = sgs->sum_score;
+	after = before - sgs->min_score;
+
+	/* SMT siblings share throughput. */
+	if (busy_cpus > 1 && sg->flags & SD_SHARE_CPUCAPACITY) {
+		before /= busy_cpus;
+		/* One sibling will become idle after load balance. */
+		after /= busy_cpus - 1;
+	}
+
+	sgs->ipcc_score_after = after + score_on_dst_cpu;
+	sgs->ipcc_score_before = before;
+}
+
 #else /* CONFIG_IPC_CLASSES */
 static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
 				    struct rq *rq)
@@ -9296,6 +9354,13 @@  static void update_sg_lb_ipcc_stats(int dst_cpu, struct sg_lb_stats *sgs,
 static void init_rq_ipcc_stats(struct sg_lb_stats *sgs)
 {
 }
+
+static void update_sg_lb_stats_scores(struct sg_lb_stats *sgs,
+				      struct sched_group *sg,
+				      struct lb_env *env)
+{
+}
+
 #endif /* CONFIG_IPC_CLASSES */
 
 /**
@@ -9457,6 +9522,9 @@  static inline void update_sg_lb_stats(struct lb_env *env,
 
 	sgs->group_type = group_classify(env->sd->imbalance_pct, group, sgs);
 
+	if (!local_group)
+		update_sg_lb_stats_scores(sgs, group, env);
+
 	/* Computing avg_load makes sense only when group is overloaded */
 	if (sgs->group_type == group_overloaded)
 		sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /