[PATCH v2 0/2] sched/fair: find_energy_efficient_cpu() enhancements

[PATCH v2 0/2] sched/fair: find_energy_efficient_cpu() enhancements

[Pierre.Gondois]

From: Pierre Gondois <Pierre.Gondois@arm.com>

V2:
 - Split the patch in 2. [Quentin]
 - Add testing results to the cover-letter. [Dietmar]
 - Put back 'rcu_read_unlock()' to unlock the rcu
   earlier. [Dietmar]
 - Various comments. [Dietmar/Quentin]

This patchset prevents underflows in find_energy_efficient_cpu().
This is done in the second patch:
sched/fair: Fix negative energy delta in find_energy_efficient_cpu()

The first patch:
sched/fair: Only compute base_energy_pd if necessary
prevents an unnecessary call to compute_energy() if no CPU is available
in a performance domain (pd).
When looping over the pds, it also allows to gather the calls
to compute_energy(), reducing the chances of having utilization signals
being concurrently updated and having a 'negative delta'.

The energy tests of the initial EAS enablement at:
https://lkml.kernel.org/r/20181203095628.11858-1-quentin.perret@arm.com
have been executed using LISA on a Juno-r2 (2xA57 + 4xA53).

To recall the test:
"10 iterations of between 10 and 50 periodic rt-app tasks (16ms period, 
5% duty-cycle) for 30 seconds with energy measurement. Unit is Joules. 
The goal is to save energy, so lower is better."
"Energy is measured with the onboard energy meter. Numbers include 
consumption of big and little CPUs."

+----------+-----------------+-------------------------+
|          | Without patches | With patches            |
+----------+--------+--------+------------------+------+
| Tasks nb |  Mean  |    CI* | Mean             |  CI* |
+----------+--------+--------+------------------+------+
|       10 |   6.57 |   0.24 |   6.46 (-1.63%)  | 0.27 |
|       20 |  12.44 |   0.21 |  12.44 (-0.01%)  | 0.14 |
|       30 |  19.10 |   0.78 |  18.75 (-1.85%)  | 0.15 |
|       40 |  27.27 |   0.53 |  27.35 (+0.31%)  | 0.33 |
|       50 |  36.55 |   0.42 |  36.28 (-0.74%)  | 0.42 |
+----------+-----------------+-------------------------+
CI: confidence interval

For each line, the intervals of values w/ w/o the patches are 
overlapping (consider Mean +/- CI). Thus, the energy results shouldn't 
have been impacted.

Pierre Gondois (2):
  sched/fair: Only compute base_energy_pd if necessary
  sched/fair: Fix negative energy delta in find_energy_efficient_cpu()

 kernel/sched/fair.c | 66 ++++++++++++++++++++++++++-------------------
 1 file changed, 38 insertions(+), 28 deletions(-)

-- 
2.17.1

[PATCH v2 1/2] sched/fair: Only compute base_energy_pd if necessary

[Pierre.Gondois]

From: Pierre Gondois <Pierre.Gondois@arm.com>

find_energy_efficient_cpu() searches the best energy CPU
to place a task on. To do so, the energy of each performance domain
(pd) is computed w/ and w/o the task placed in each pd.

The energy of a pd w/o the task (base_energy_pd) is computed prior
knowing whether a CPU is available in the pd.

Move the base_energy_pd computation after looping through the CPUs
of a pd and only computes it if at least one CPU is available.

Suggested-by: Xuewen Yan <xuewen.yan@unisoc.com>
Signed-off-by: Pierre Gondois <Pierre.Gondois@arm.com>
---
 kernel/sched/fair.c | 38 ++++++++++++++++++++++----------------
 1 file changed, 22 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 0dba0ebc3657..c5351366fb93 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6620,13 +6620,10 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 
 	for (; pd; pd = pd->next) {
 		unsigned long cur_delta, spare_cap, max_spare_cap = 0;
+		bool compute_prev_delta = false;
 		unsigned long base_energy_pd;
 		int max_spare_cap_cpu = -1;
 
-		/* Compute the 'base' energy of the pd, without @p */
-		base_energy_pd = compute_energy(p, -1, pd);
-		base_energy += base_energy_pd;
-
 		for_each_cpu_and(cpu, perf_domain_span(pd), sched_domain_span(sd)) {
 			if (!cpumask_test_cpu(cpu, p->cpus_ptr))
 				continue;
@@ -6647,25 +6644,34 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 			if (!fits_capacity(util, cpu_cap))
 				continue;
 
-			/* Always use prev_cpu as a candidate. */
 			if (cpu == prev_cpu) {
-				prev_delta = compute_energy(p, prev_cpu, pd);
-				prev_delta -= base_energy_pd;
-				best_delta = min(best_delta, prev_delta);
-			}
-
-			/*
-			 * Find the CPU with the maximum spare capacity in
-			 * the performance domain
-			 */
-			if (spare_cap > max_spare_cap) {
+				/* Always use prev_cpu as a candidate. */
+				compute_prev_delta = true;
+			} else if (spare_cap > max_spare_cap) {
+				/*
+				 * Find the CPU with the maximum spare capacity
+				 * in the performance domain.
+				 */
 				max_spare_cap = spare_cap;
 				max_spare_cap_cpu = cpu;
 			}
 		}
 
+		if (max_spare_cap_cpu < 0 && !compute_prev_delta)
+			continue;
+
+		/* Compute the 'base' energy of the pd, without @p */
+		base_energy_pd = compute_energy(p, -1, pd);
+		base_energy += base_energy_pd;
+
+		if (compute_prev_delta) {
+			prev_delta = compute_energy(p, prev_cpu, pd);
+			prev_delta -= base_energy_pd;
+			best_delta = min(best_delta, prev_delta);
+		}
+
 		/* Evaluate the energy impact of using this CPU. */
-		if (max_spare_cap_cpu >= 0 && max_spare_cap_cpu != prev_cpu) {
+		if (max_spare_cap_cpu >= 0) {
 			cur_delta = compute_energy(p, max_spare_cap_cpu, pd);
 			cur_delta -= base_energy_pd;
 			if (cur_delta < best_delta) {
-- 
2.17.1

[PATCH v2 2/2] sched/fair: Fix negative energy delta in find_energy_efficient_cpu()

[Pierre.Gondois]

From: Pierre Gondois <Pierre.Gondois@arm.com>

find_energy_efficient_cpu() (feec()) searches the best energy CPU
to place a task on. To do so, compute_energy() estimates the energy
impact of placing the task on a CPU, based on CPU and task utilization
signals.

Utilization signals can be concurrently updated while evaluating a
performance domain (pd). In some cases, this leads to having a
'negative delta', i.e. placing the task in the pd is seen as an
energy gain. Thus, any further energy comparison is biased.

In case of a 'negative delta', return prev_cpu since:
1. a 'negative delta' happens in less than 0.5% of feec() calls,
   on a Juno with 6 CPUs (4 little, 2 big)
2. it is unlikely to have two consecutive 'negative delta' for
   a task, so if the first call fails, feec() will correctly
   place the task in the next feec() call
3. EAS current behavior tends to select prev_cpu if the task
   doesn't raise the OPP of its current pd. prev_cpu is EAS's
   generic decision
4. prev_cpu should be preferred to returning an error code.
   In the latter case, select_idle_sibling() would do the placement,
   selecting a big (and not energy efficient) CPU. As 3., the task
   would potentially reside on the big CPU for a long time

Reported-by: Xuewen Yan <xuewen.yan@unisoc.com>
Suggested-by: Xuewen Yan <xuewen.yan@unisoc.com>
Signed-off-by: Pierre Gondois <Pierre.Gondois@arm.com>
---
 kernel/sched/fair.c | 28 ++++++++++++++++------------
 1 file changed, 16 insertions(+), 12 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c5351366fb93..935f1ea267a9 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6594,15 +6594,15 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 {
 	unsigned long prev_delta = ULONG_MAX, best_delta = ULONG_MAX;
 	struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
+	int cpu, best_energy_cpu = prev_cpu, target = -1;
 	unsigned long cpu_cap, util, base_energy = 0;
-	int cpu, best_energy_cpu = prev_cpu;
 	struct sched_domain *sd;
 	struct perf_domain *pd;
 
 	rcu_read_lock();
 	pd = rcu_dereference(rd->pd);
 	if (!pd || READ_ONCE(rd->overutilized))
-		goto fail;
+		goto unlock;
 
 	/*
 	 * Energy-aware wake-up happens on the lowest sched_domain starting
@@ -6612,7 +6612,9 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 	while (sd && !cpumask_test_cpu(prev_cpu, sched_domain_span(sd)))
 		sd = sd->parent;
 	if (!sd)
-		goto fail;
+		goto unlock;
+
+	target = prev_cpu;
 
 	sync_entity_load_avg(&p->se);
 	if (!task_util_est(p))
@@ -6666,6 +6668,8 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 
 		if (compute_prev_delta) {
 			prev_delta = compute_energy(p, prev_cpu, pd);
+			if (prev_delta < base_energy_pd)
+				goto unlock;
 			prev_delta -= base_energy_pd;
 			best_delta = min(best_delta, prev_delta);
 		}
@@ -6673,6 +6677,8 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 		/* Evaluate the energy impact of using this CPU. */
 		if (max_spare_cap_cpu >= 0) {
 			cur_delta = compute_energy(p, max_spare_cap_cpu, pd);
+			if (cur_delta < base_energy_pd)
+				goto unlock;
 			cur_delta -= base_energy_pd;
 			if (cur_delta < best_delta) {
 				best_delta = cur_delta;
@@ -6680,25 +6686,23 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 			}
 		}
 	}
-unlock:
+
 	rcu_read_unlock();
 
 	/*
 	 * Pick the best CPU if prev_cpu cannot be used, or if it saves at
 	 * least 6% of the energy used by prev_cpu.
 	 */
-	if (prev_delta == ULONG_MAX)
-		return best_energy_cpu;
-
-	if ((prev_delta - best_delta) > ((prev_delta + base_energy) >> 4))
-		return best_energy_cpu;
+	if ((prev_delta == ULONG_MAX) ||
+		(prev_delta - best_delta) > ((prev_delta + base_energy) >> 4))
+		target = best_energy_cpu;
 
-	return prev_cpu;
+	return target;
 
-fail:
+unlock:
 	rcu_read_unlock();
 
-	return -1;
+	return target;
 }
 
 /*
-- 
2.17.1

Re: [PATCH v2 1/2] sched/fair: Only compute base_energy_pd if necessary

[Lukasz Luba]

Hi Pierre,

On 4/29/21 11:19 AM, Pierre.Gondois@arm.com wrote:
> From: Pierre Gondois <Pierre.Gondois@arm.com>
> 
> find_energy_efficient_cpu() searches the best energy CPU
> to place a task on. To do so, the energy of each performance domain
> (pd) is computed w/ and w/o the task placed in each pd.
> 
> The energy of a pd w/o the task (base_energy_pd) is computed prior
> knowing whether a CPU is available in the pd.
> 
> Move the base_energy_pd computation after looping through the CPUs
> of a pd and only computes it if at least one CPU is available.
> 
> Suggested-by: Xuewen Yan <xuewen.yan@unisoc.com>
> Signed-off-by: Pierre Gondois <Pierre.Gondois@arm.com>
> ---
>   kernel/sched/fair.c | 38 ++++++++++++++++++++++----------------
>   1 file changed, 22 insertions(+), 16 deletions(-)
> 

Make sense. I will speed-up feec() on Android devices for tasks
being moved into 'background' cgroup (limited to subset of CPUs,
e.g. to only Little cores). LGTM.

Reviewed-by: Lukasz Luba <lukasz.luba@arm.com>

Regards,
Lukasz

Re: [PATCH v2 2/2] sched/fair: Fix negative energy delta in find_energy_efficient_cpu()

[Lukasz Luba]

On 4/29/21 11:19 AM, Pierre.Gondois@arm.com wrote:
> From: Pierre Gondois <Pierre.Gondois@arm.com>
> 
> find_energy_efficient_cpu() (feec()) searches the best energy CPU
> to place a task on. To do so, compute_energy() estimates the energy
> impact of placing the task on a CPU, based on CPU and task utilization
> signals.
> 
> Utilization signals can be concurrently updated while evaluating a
> performance domain (pd). In some cases, this leads to having a
> 'negative delta', i.e. placing the task in the pd is seen as an
> energy gain. Thus, any further energy comparison is biased.
> 
> In case of a 'negative delta', return prev_cpu since:
> 1. a 'negative delta' happens in less than 0.5% of feec() calls,
>     on a Juno with 6 CPUs (4 little, 2 big)
> 2. it is unlikely to have two consecutive 'negative delta' for
>     a task, so if the first call fails, feec() will correctly
>     place the task in the next feec() call
> 3. EAS current behavior tends to select prev_cpu if the task
>     doesn't raise the OPP of its current pd. prev_cpu is EAS's
>     generic decision
> 4. prev_cpu should be preferred to returning an error code.
>     In the latter case, select_idle_sibling() would do the placement,
>     selecting a big (and not energy efficient) CPU. As 3., the task
>     would potentially reside on the big CPU for a long time
> 
> Reported-by: Xuewen Yan <xuewen.yan@unisoc.com>
> Suggested-by: Xuewen Yan <xuewen.yan@unisoc.com>
> Signed-off-by: Pierre Gondois <Pierre.Gondois@arm.com>
> ---
>   kernel/sched/fair.c | 28 ++++++++++++++++------------
>   1 file changed, 16 insertions(+), 12 deletions(-)
> 


Reviewed-by: Lukasz Luba <lukasz.luba@arm.com>

Regards,
Lukasz

Re: [PATCH v2 1/2] sched/fair: Only compute base_energy_pd if necessary

[Dietmar Eggemann]

On 29/04/2021 12:19, Pierre.Gondois@arm.com wrote:
> From: Pierre Gondois <Pierre.Gondois@arm.com>
> 
> find_energy_efficient_cpu() searches the best energy CPU
> to place a task on. To do so, the energy of each performance domain
> (pd) is computed w/ and w/o the task placed in each pd.

s/in each pd/on it ?

> 
> The energy of a pd w/o the task (base_energy_pd) is computed prior
> knowing whether a CPU is available in the pd.
> 
> Move the base_energy_pd computation after looping through the CPUs
> of a pd and only computes it if at least one CPU is available.

s/computes/compute

[...]

> +		if (max_spare_cap_cpu < 0 && !compute_prev_delta)
> +			continue;
> +
> +		/* Compute the 'base' energy of the pd, without @p */
> +		base_energy_pd = compute_energy(p, -1, pd);
> +		base_energy += base_energy_pd;
> +

                /* Evaluate the energy impact of using prev_cpu. */

You agreed on this one during v1 review ;-)

> +		if (compute_prev_delta) {
> +			prev_delta = compute_energy(p, prev_cpu, pd);
> +			prev_delta -= base_energy_pd;
> +			best_delta = min(best_delta, prev_delta);
> +		}
> +
>  		/* Evaluate the energy impact of using this CPU. */

better:

            /* Evaluate the energy impact of using max_spare_cap_cpu. */

'this' has lost its context and people might read it as 'this_cpu' or
smp_processor_id().


> -		if (max_spare_cap_cpu >= 0 && max_spare_cap_cpu != prev_cpu) {
> +		if (max_spare_cap_cpu >= 0) {
>  			cur_delta = compute_energy(p, max_spare_cap_cpu, pd);
>  			cur_delta -= base_energy_pd;
>  			if (cur_delta < best_delta) {
> 

With these minor things sorted:

Reviewed-by: Dietmar Eggemann <dietmar.eggemann@arm.com>

Re: [PATCH v2 2/2] sched/fair: Fix negative energy delta in find_energy_efficient_cpu()

[Dietmar Eggemann]

On 29/04/2021 12:19, Pierre.Gondois@arm.com wrote:
> From: Pierre Gondois <Pierre.Gondois@arm.com>

[...]

> @@ -6680,25 +6686,23 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
>  			}
>  		}
>  	}
> -unlock:
> +

No need for empty line.

>  	rcu_read_unlock();
>  
>  	/*
>  	 * Pick the best CPU if prev_cpu cannot be used, or if it saves at
>  	 * least 6% of the energy used by prev_cpu.
>  	 */
> -	if (prev_delta == ULONG_MAX)
> -		return best_energy_cpu;
> -
> -	if ((prev_delta - best_delta) > ((prev_delta + base_energy) >> 4))
> -		return best_energy_cpu;
> +	if ((prev_delta == ULONG_MAX) ||
> +		(prev_delta - best_delta) > ((prev_delta + base_energy) >> 4))
> +		target = best_energy_cpu;

       if ((prev_delta == ULONG_MAX) ||
-               (prev_delta - best_delta) > ((prev_delta + base_energy) >> 4))
+           (prev_delta - best_delta) > ((prev_delta + base_energy) >> 4))
                target = best_energy_cpu;

IMHO, using whitespaces to align both sub-conditions here makes it more
readable. Especially since braces aren't required around single
statements with a condition spanning over multiple lines.

[...]

With these minor things sorted:

Reviewed-by: Dietmar Eggemann <dietmar.eggemann@arm.com>

Re: [PATCH v2 2/2] sched/fair: Fix negative energy delta in find_energy_efficient_cpu()

[Vincent Donnefort]

On Thu, Apr 29, 2021 at 11:19:48AM +0100, Pierre.Gondois@arm.com wrote:
> From: Pierre Gondois <Pierre.Gondois@arm.com>
> 
> find_energy_efficient_cpu() (feec()) searches the best energy CPU
> to place a task on. To do so, compute_energy() estimates the energy
> impact of placing the task on a CPU, based on CPU and task utilization
> signals.
> 
> Utilization signals can be concurrently updated while evaluating a
> performance domain (pd). In some cases, this leads to having a
> 'negative delta', i.e. placing the task in the pd is seen as an
> energy gain. Thus, any further energy comparison is biased.
> 
> In case of a 'negative delta', return prev_cpu since:
> 1. a 'negative delta' happens in less than 0.5% of feec() calls,
>    on a Juno with 6 CPUs (4 little, 2 big)
> 2. it is unlikely to have two consecutive 'negative delta' for
>    a task, so if the first call fails, feec() will correctly
>    place the task in the next feec() call
> 3. EAS current behavior tends to select prev_cpu if the task
>    doesn't raise the OPP of its current pd. prev_cpu is EAS's
>    generic decision
> 4. prev_cpu should be preferred to returning an error code.
>    In the latter case, select_idle_sibling() would do the placement,
>    selecting a big (and not energy efficient) CPU. As 3., the task
>    would potentially reside on the big CPU for a long time
> 
> Reported-by: Xuewen Yan <xuewen.yan@unisoc.com>
> Suggested-by: Xuewen Yan <xuewen.yan@unisoc.com>
> Signed-off-by: Pierre Gondois <Pierre.Gondois@arm.com>
> ---

I've been testing this patch on the Google's Pixel4, with a modified kernel that
we are using to evalute mailine performance and energy consumption for a
"real-life" mobile usage.

As always, I ran the Work2.0 workload from PCMark on Android. With that setup I
haven't observed any statistically significant performance change neither any CPU
Idle residency modification. Nevertheless, this code protected against ~600 bad
computations (and by extent bad placements) during a single PCMark iteration
and by looking at the traces, this is saving from spurious wake-ups that would
otherwise happen on the biggest CPUs of the system.

+ Reviewed-by: Vincent Donnefort <vincent.donnefort@arm.com>