[v6,2/2] cpuidle: teo: Introduce util-awareness

  Modern interactive systems, such as recent Android phones, tend to have power
efficient shallow idle states. Selecting deeper idle states on a device while a
latency-sensitive workload is running can adversely impact performance due to
increased latency. Additionally, if the CPU wakes up from a deeper sleep before
its target residency as is often the case, it results in a waste of energy on
top of that.

At the moment, none of the available idle governors take any scheduling
information into account. They also tend to overestimate the idle
duration quite often, which causes them to select excessively deep idle
states, thus leading to increased wakeup latency and lower performance with no
power saving. For 'menu' while web browsing on Android for instance, those
types of wakeups ('too deep') account for over 24% of all wakeups.

At the same time, on some platforms idle state 0 can be power efficient
enough to warrant wanting to prefer it over idle state 1. This is because
the power usage of the two states can be so close that sufficient amounts
of too deep state 1 sleeps can completely offset the state 1 power saving to the
point where it would've been more power efficient to just use state 0 instead.
This is of course for systems where state 0 is not a polling state, such as
arm-based devices.

Sleeps that happened in state 0 while they could have used state 1 ('too shallow') only
save less power than they otherwise could have. Too deep sleeps, on the other
hand, harm performance and nullify the potential power saving from using state 1 in
the first place. While taking this into account, it is clear that on balance it
is preferable for an idle governor to have more too shallow sleeps instead of
more too deep sleeps on those kinds of platforms.

This patch specifically tunes TEO to prefer shallower idle states in
order to reduce wakeup latency and achieve better performance.
To this end, before selecting the next idle state it uses the avg_util signal
of a CPU's runqueue in order to determine to what extent the CPU is being utilized.
This util value is then compared to a threshold defined as a percentage of the
cpu's capacity (capacity >> 6 ie. ~1.5% in the current implementation). If the
util is above the threshold, the idle state selected by TEO metrics will be
reduced by 1, thus selecting a shallower state. If the util is below the threshold,
the governor defaults to the TEO metrics mechanism to try to select the deepest
available idle state based on the closest timer event and its own correctness.

The main goal of this is to reduce latency and increase performance for some
workloads. Under some workloads it will result in an increase in power usage
(Geekbench 5) while for other workloads it will also result in a decrease in
power usage compared to TEO (PCMark Web, Jankbench, Speedometer).

It can provide drastically decreased latency and performance benefits in certain
types of workloads that are sensitive to latency.

Example test results:

1. GB5 (better score, latency & more power usage)

| metric                                | menu           | teo               | teo-util-aware    |
| ------------------------------------- | -------------- | ----------------- | ----------------- |
| gmean score                           | 2826.5 (0.0%)  | 2764.8 (-2.18%)   | 2865 (1.36%)      |
| gmean power usage [mW]                | 2551.4 (0.0%)  | 2606.8 (2.17%)    | 2722.3 (6.7%)     |
| gmean too deep %                      | 14.99%         | 9.65%             | 4.02%             |
| gmean too shallow %                   | 2.5%           | 5.96%             | 14.59%            |
| gmean task wakeup latency (asynctask) | 78.16μs (0.0%) | 61.60μs (-21.19%) | 54.45μs (-30.34%) |

2. Jankbench (better score, latency & less power usage)

| metric                                | menu           | teo               | teo-util-aware    |
| ------------------------------------- | -------------- | ----------------- | ----------------- |
| gmean frame duration                  | 13.9 (0.0%)    | 14.7 (6.0%)       | 12.6 (-9.0%)      |
| gmean jank percentage                 | 1.5 (0.0%)     | 2.1 (36.99%)      | 1.3 (-17.37%)     |
| gmean power usage [mW]                | 144.6 (0.0%)   | 136.9 (-5.27%)    | 121.3 (-16.08%)   |
| gmean too deep %                      | 26.00%         | 11.00%            | 2.54%             |
| gmean too shallow %                   | 4.74%          | 11.89%            | 21.93%            |
| gmean wakeup latency (RenderThread)   | 139.5μs (0.0%) | 116.5μs (-16.49%) | 91.11μs (-34.7%)  |
| gmean wakeup latency (surfaceflinger) | 124.0μs (0.0%) | 151.9μs (22.47%)  | 87.65μs (-29.33%) |

Signed-off-by: Kajetan Puchalski <kajetan.puchalski@arm.com>
---
 drivers/cpuidle/governors/teo.c | 92 ++++++++++++++++++++++++++++++++-
 1 file changed, 91 insertions(+), 1 deletion(-)
  

On Thu, Jan 5, 2023 at 3:52 PM Kajetan Puchalski
<kajetan.puchalski@arm.com> wrote:
>
> Modern interactive systems, such as recent Android phones, tend to have power
> efficient shallow idle states. Selecting deeper idle states on a device while a
> latency-sensitive workload is running can adversely impact performance due to
> increased latency. Additionally, if the CPU wakes up from a deeper sleep before
> its target residency as is often the case, it results in a waste of energy on
> top of that.
>
> At the moment, none of the available idle governors take any scheduling
> information into account. They also tend to overestimate the idle
> duration quite often, which causes them to select excessively deep idle
> states, thus leading to increased wakeup latency and lower performance with no
> power saving. For 'menu' while web browsing on Android for instance, those
> types of wakeups ('too deep') account for over 24% of all wakeups.
>
> At the same time, on some platforms idle state 0 can be power efficient
> enough to warrant wanting to prefer it over idle state 1. This is because
> the power usage of the two states can be so close that sufficient amounts
> of too deep state 1 sleeps can completely offset the state 1 power saving to the
> point where it would've been more power efficient to just use state 0 instead.
> This is of course for systems where state 0 is not a polling state, such as
> arm-based devices.
>
> Sleeps that happened in state 0 while they could have used state 1 ('too shallow') only
> save less power than they otherwise could have. Too deep sleeps, on the other
> hand, harm performance and nullify the potential power saving from using state 1 in
> the first place. While taking this into account, it is clear that on balance it
> is preferable for an idle governor to have more too shallow sleeps instead of
> more too deep sleeps on those kinds of platforms.
>
> This patch specifically tunes TEO to prefer shallower idle states in
> order to reduce wakeup latency and achieve better performance.
> To this end, before selecting the next idle state it uses the avg_util signal
> of a CPU's runqueue in order to determine to what extent the CPU is being utilized.
> This util value is then compared to a threshold defined as a percentage of the
> cpu's capacity (capacity >> 6 ie. ~1.5% in the current implementation). If the
> util is above the threshold, the idle state selected by TEO metrics will be
> reduced by 1, thus selecting a shallower state. If the util is below the threshold,
> the governor defaults to the TEO metrics mechanism to try to select the deepest
> available idle state based on the closest timer event and its own correctness.
>
> The main goal of this is to reduce latency and increase performance for some
> workloads. Under some workloads it will result in an increase in power usage
> (Geekbench 5) while for other workloads it will also result in a decrease in
> power usage compared to TEO (PCMark Web, Jankbench, Speedometer).
>
> It can provide drastically decreased latency and performance benefits in certain
> types of workloads that are sensitive to latency.
>
> Example test results:
>
> 1. GB5 (better score, latency & more power usage)
>
> | metric                                | menu           | teo               | teo-util-aware    |
> | ------------------------------------- | -------------- | ----------------- | ----------------- |
> | gmean score                           | 2826.5 (0.0%)  | 2764.8 (-2.18%)   | 2865 (1.36%)      |
> | gmean power usage [mW]                | 2551.4 (0.0%)  | 2606.8 (2.17%)    | 2722.3 (6.7%)     |
> | gmean too deep %                      | 14.99%         | 9.65%             | 4.02%             |
> | gmean too shallow %                   | 2.5%           | 5.96%             | 14.59%            |
> | gmean task wakeup latency (asynctask) | 78.16μs (0.0%) | 61.60μs (-21.19%) | 54.45μs (-30.34%) |
>
> 2. Jankbench (better score, latency & less power usage)
>
> | metric                                | menu           | teo               | teo-util-aware    |
> | ------------------------------------- | -------------- | ----------------- | ----------------- |
> | gmean frame duration                  | 13.9 (0.0%)    | 14.7 (6.0%)       | 12.6 (-9.0%)      |
> | gmean jank percentage                 | 1.5 (0.0%)     | 2.1 (36.99%)      | 1.3 (-17.37%)     |
> | gmean power usage [mW]                | 144.6 (0.0%)   | 136.9 (-5.27%)    | 121.3 (-16.08%)   |
> | gmean too deep %                      | 26.00%         | 11.00%            | 2.54%             |
> | gmean too shallow %                   | 4.74%          | 11.89%            | 21.93%            |
> | gmean wakeup latency (RenderThread)   | 139.5μs (0.0%) | 116.5μs (-16.49%) | 91.11μs (-34.7%)  |
> | gmean wakeup latency (surfaceflinger) | 124.0μs (0.0%) | 151.9μs (22.47%)  | 87.65μs (-29.33%) |
>
> Signed-off-by: Kajetan Puchalski <kajetan.puchalski@arm.com>

This looks good enough for me.

There are still a couple of things I would change in it, but I may as
well do that when applying it, so never mind.

The most important question for now is what the scheduler people think
about calling sched_cpu_util() from a CPU idle governor.  Peter,
Vincent?

> ---
>  drivers/cpuidle/governors/teo.c | 92 ++++++++++++++++++++++++++++++++-
>  1 file changed, 91 insertions(+), 1 deletion(-)
>
> diff --git a/drivers/cpuidle/governors/teo.c b/drivers/cpuidle/governors/teo.c
> index e2864474a98d..2a2be4f45b70 100644
> --- a/drivers/cpuidle/governors/teo.c
> +++ b/drivers/cpuidle/governors/teo.c
> @@ -2,8 +2,13 @@
>  /*
>   * Timer events oriented CPU idle governor
>   *
> + * TEO governor:
>   * Copyright (C) 2018 - 2021 Intel Corporation
>   * Author: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> + *
> + * Util-awareness mechanism:
> + * Copyright (C) 2022 Arm Ltd.
> + * Author: Kajetan Puchalski <kajetan.puchalski@arm.com>
>   */
>
>  /**
> @@ -99,14 +104,55 @@
>   *      select the given idle state instead of the candidate one.
>   *
>   * 3. By default, select the candidate state.
> + *
> + * Util-awareness mechanism:
> + *
> + * The idea behind the util-awareness extension is that there are two distinct
> + * scenarios for the CPU which should result in two different approaches to idle
> + * state selection - utilized and not utilized.
> + *
> + * In this case, 'utilized' means that the average runqueue util of the CPU is
> + * above a certain threshold.
> + *
> + * When the CPU is utilized while going into idle, more likely than not it will
> + * be woken up to do more work soon and so a shallower idle state should be
> + * selected to minimise latency and maximise performance. When the CPU is not
> + * being utilized, the usual metrics-based approach to selecting the deepest
> + * available idle state should be preferred to take advantage of the power
> + * saving.
> + *
> + * In order to achieve this, the governor uses a utilization threshold.
> + * The threshold is computed per-cpu as a percentage of the CPU's capacity
> + * by bit shifting the capacity value. Based on testing, the shift of 6 (~1.56%)
> + * seems to be getting the best results.
> + *
> + * Before selecting the next idle state, the governor compares the current CPU
> + * util to the precomputed util threshold. If it's below, it defaults to the
> + * TEO metrics mechanism. If it's above, the idle state will be reduced to C0
> + * as long as C0 is not a polling state.
>   */
>
>  #include <linux/cpuidle.h>
>  #include <linux/jiffies.h>
>  #include <linux/kernel.h>
> +#include <linux/sched.h>
>  #include <linux/sched/clock.h>
> +#include <linux/sched/topology.h>
>  #include <linux/tick.h>
>
> +/*
> + * The number of bits to shift the cpu's capacity by in order to determine
> + * the utilized threshold.
> + *
> + * 6 was chosen based on testing as the number that achieved the best balance
> + * of power and performance on average.
> + *
> + * The resulting threshold is high enough to not be triggered by background
> + * noise and low enough to react quickly when activity starts to ramp up.
> + */
> +#define UTIL_THRESHOLD_SHIFT 6
> +
> +
>  /*
>   * The PULSE value is added to metrics when they grow and the DECAY_SHIFT value
>   * is used for decreasing metrics on a regular basis.
> @@ -137,9 +183,11 @@ struct teo_bin {
>   * @time_span_ns: Time between idle state selection and post-wakeup update.
>   * @sleep_length_ns: Time till the closest timer event (at the selection time).
>   * @state_bins: Idle state data bins for this CPU.
> - * @total: Grand total of the "intercepts" and "hits" mertics for all bins.
> + * @total: Grand total of the "intercepts" and "hits" metrics for all bins.
>   * @next_recent_idx: Index of the next @recent_idx entry to update.
>   * @recent_idx: Indices of bins corresponding to recent "intercepts".
> + * @util_threshold: Threshold above which the CPU is considered utilized
> + * @utilized: Whether the last sleep on the CPU happened while utilized
>   */
>  struct teo_cpu {
>         s64 time_span_ns;
> @@ -148,10 +196,29 @@ struct teo_cpu {
>         unsigned int total;
>         int next_recent_idx;
>         int recent_idx[NR_RECENT];
> +       unsigned long util_threshold;
> +       bool utilized;
>  };
>
>  static DEFINE_PER_CPU(struct teo_cpu, teo_cpus);
>
> +/**
> + * teo_cpu_is_utilized - Check if the CPU's util is above the threshold
> + * @cpu: Target CPU
> + * @cpu_data: Governor CPU data for the target CPU
> + */
> +#ifdef CONFIG_SMP
> +static bool teo_cpu_is_utilized(int cpu, struct teo_cpu *cpu_data)
> +{
> +       return sched_cpu_util(cpu) > cpu_data->util_threshold;
> +}
> +#else
> +static bool teo_cpu_is_utilized(int cpu, struct teo_cpu *cpu_data)
> +{
> +       return false;
> +}
> +#endif
> +
>  /**
>   * teo_update - Update CPU metrics after wakeup.
>   * @drv: cpuidle driver containing state data.
> @@ -323,6 +390,20 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
>                         goto end;
>         }
>
> +       cpu_data->utilized = teo_cpu_is_utilized(dev->cpu, cpu_data);
> +       /*
> +        * The cpu is being utilized over the threshold there are only 2 states to choose from.
> +        * No need to consider metrics, choose the shallowest non-polling state and exit.
> +        */
> +       if (drv->state_count < 3 && cpu_data->utilized) {
> +               for (i = 0; i < drv->state_count; ++i) {
> +                       if (!dev->states_usage[i].disable && !(drv->states[i].flags & CPUIDLE_FLAG_POLLING)) {
> +                               idx = i;
> +                               goto end;
> +                       }
> +               }
> +       }
> +
>         /*
>          * Find the deepest idle state whose target residency does not exceed
>          * the current sleep length and the deepest idle state not deeper than
> @@ -454,6 +535,13 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
>         if (idx > constraint_idx)
>                 idx = constraint_idx;
>
> +       /*
> +        * If the CPU is being utilized over the threshold,
> +        * choose a shallower non-polling state to improve latency
> +        */
> +       if (cpu_data->utilized)
> +               idx = teo_find_shallower_state(drv, dev, idx, duration_ns, true);
> +
>  end:
>         /*
>          * Don't stop the tick if the selected state is a polling one or if the
> @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
>                              struct cpuidle_device *dev)
>  {
>         struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> +       unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
>         int i;
>
>         memset(cpu_data, 0, sizeof(*cpu_data));
> +       cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
>
>         for (i = 0; i < NR_RECENT; i++)
>                 cpu_data->recent_idx[i] = -1;
> --
> 2.37.1
>
  

On 1/5/23 15:07, Rafael J. Wysocki wrote:
> On Thu, Jan 5, 2023 at 3:52 PM Kajetan Puchalski
> <kajetan.puchalski@arm.com> wrote:
>>
>> Modern interactive systems, such as recent Android phones, tend to have power
>> efficient shallow idle states. Selecting deeper idle states on a device while a
>> latency-sensitive workload is running can adversely impact performance due to
>> increased latency. Additionally, if the CPU wakes up from a deeper sleep before
>> its target residency as is often the case, it results in a waste of energy on
>> top of that.
>>
>> At the moment, none of the available idle governors take any scheduling
>> information into account. They also tend to overestimate the idle
>> duration quite often, which causes them to select excessively deep idle
>> states, thus leading to increased wakeup latency and lower performance with no
>> power saving. For 'menu' while web browsing on Android for instance, those
>> types of wakeups ('too deep') account for over 24% of all wakeups.
>>
>> At the same time, on some platforms idle state 0 can be power efficient
>> enough to warrant wanting to prefer it over idle state 1. This is because
>> the power usage of the two states can be so close that sufficient amounts
>> of too deep state 1 sleeps can completely offset the state 1 power saving to the
>> point where it would've been more power efficient to just use state 0 instead.
>> This is of course for systems where state 0 is not a polling state, such as
>> arm-based devices.
>>
>> Sleeps that happened in state 0 while they could have used state 1 ('too shallow') only
>> save less power than they otherwise could have. Too deep sleeps, on the other
>> hand, harm performance and nullify the potential power saving from using state 1 in
>> the first place. While taking this into account, it is clear that on balance it
>> is preferable for an idle governor to have more too shallow sleeps instead of
>> more too deep sleeps on those kinds of platforms.
>>
>> This patch specifically tunes TEO to prefer shallower idle states in
>> order to reduce wakeup latency and achieve better performance.
>> To this end, before selecting the next idle state it uses the avg_util signal
>> of a CPU's runqueue in order to determine to what extent the CPU is being utilized.
>> This util value is then compared to a threshold defined as a percentage of the
>> cpu's capacity (capacity >> 6 ie. ~1.5% in the current implementation). If the
>> util is above the threshold, the idle state selected by TEO metrics will be
>> reduced by 1, thus selecting a shallower state. If the util is below the threshold,
>> the governor defaults to the TEO metrics mechanism to try to select the deepest
>> available idle state based on the closest timer event and its own correctness.
>>
>> The main goal of this is to reduce latency and increase performance for some
>> workloads. Under some workloads it will result in an increase in power usage
>> (Geekbench 5) while for other workloads it will also result in a decrease in
>> power usage compared to TEO (PCMark Web, Jankbench, Speedometer).
>>
>> It can provide drastically decreased latency and performance benefits in certain
>> types of workloads that are sensitive to latency.
>>
>> Example test results:
>>
>> 1. GB5 (better score, latency & more power usage)
>>
>> | metric                                | menu           | teo               | teo-util-aware    |
>> | ------------------------------------- | -------------- | ----------------- | ----------------- |
>> | gmean score                           | 2826.5 (0.0%)  | 2764.8 (-2.18%)   | 2865 (1.36%)      |
>> | gmean power usage [mW]                | 2551.4 (0.0%)  | 2606.8 (2.17%)    | 2722.3 (6.7%)     |
>> | gmean too deep %                      | 14.99%         | 9.65%             | 4.02%             |
>> | gmean too shallow %                   | 2.5%           | 5.96%             | 14.59%            |
>> | gmean task wakeup latency (asynctask) | 78.16μs (0.0%) | 61.60μs (-21.19%) | 54.45μs (-30.34%) |
>>
>> 2. Jankbench (better score, latency & less power usage)
>>
>> | metric                                | menu           | teo               | teo-util-aware    |
>> | ------------------------------------- | -------------- | ----------------- | ----------------- |
>> | gmean frame duration                  | 13.9 (0.0%)    | 14.7 (6.0%)       | 12.6 (-9.0%)      |
>> | gmean jank percentage                 | 1.5 (0.0%)     | 2.1 (36.99%)      | 1.3 (-17.37%)     |
>> | gmean power usage [mW]                | 144.6 (0.0%)   | 136.9 (-5.27%)    | 121.3 (-16.08%)   |
>> | gmean too deep %                      | 26.00%         | 11.00%            | 2.54%             |
>> | gmean too shallow %                   | 4.74%          | 11.89%            | 21.93%            |
>> | gmean wakeup latency (RenderThread)   | 139.5μs (0.0%) | 116.5μs (-16.49%) | 91.11μs (-34.7%)  |
>> | gmean wakeup latency (surfaceflinger) | 124.0μs (0.0%) | 151.9μs (22.47%)  | 87.65μs (-29.33%) |
>>
>> Signed-off-by: Kajetan Puchalski <kajetan.puchalski@arm.com>
> 
> This looks good enough for me.
> 
> There are still a couple of things I would change in it, but I may as
> well do that when applying it, so never mind.
> 
> The most important question for now is what the scheduler people think
> about calling sched_cpu_util() from a CPU idle governor.  Peter,
> Vincent?
> 

We have a precedence in thermal framework for purpose of thermal
governor - IPA. It's been there for a while to estimate the power
of CPUs in the frequency domain for cpufreq_cooling device [1].
That's how this API sched_cpu_util() got created. Then it was also
adopted to PowerCap DTPM [2] (for the same power estimation purpose).

It's a function available with form include/linux/sched.h so I don't
see reasons why to not use it.

[1] 
https://elixir.bootlin.com/linux/latest/source/drivers/thermal/cpufreq_cooling.c#L151
[2] 
https://elixir.bootlin.com/linux/latest/source/drivers/powercap/dtpm_cpu.c#L83
  

On Thu, 5 Jan 2023 at 16:07, Rafael J. Wysocki <rafael@kernel.org> wrote:
>
> On Thu, Jan 5, 2023 at 3:52 PM Kajetan Puchalski
> <kajetan.puchalski@arm.com> wrote:
> >
> > Modern interactive systems, such as recent Android phones, tend to have power
> > efficient shallow idle states. Selecting deeper idle states on a device while a
> > latency-sensitive workload is running can adversely impact performance due to
> > increased latency. Additionally, if the CPU wakes up from a deeper sleep before
> > its target residency as is often the case, it results in a waste of energy on
> > top of that.
> >
> > At the moment, none of the available idle governors take any scheduling
> > information into account. They also tend to overestimate the idle
> > duration quite often, which causes them to select excessively deep idle
> > states, thus leading to increased wakeup latency and lower performance with no
> > power saving. For 'menu' while web browsing on Android for instance, those
> > types of wakeups ('too deep') account for over 24% of all wakeups.
> >
> > At the same time, on some platforms idle state 0 can be power efficient
> > enough to warrant wanting to prefer it over idle state 1. This is because
> > the power usage of the two states can be so close that sufficient amounts
> > of too deep state 1 sleeps can completely offset the state 1 power saving to the
> > point where it would've been more power efficient to just use state 0 instead.
> > This is of course for systems where state 0 is not a polling state, such as
> > arm-based devices.
> >
> > Sleeps that happened in state 0 while they could have used state 1 ('too shallow') only
> > save less power than they otherwise could have. Too deep sleeps, on the other
> > hand, harm performance and nullify the potential power saving from using state 1 in
> > the first place. While taking this into account, it is clear that on balance it
> > is preferable for an idle governor to have more too shallow sleeps instead of
> > more too deep sleeps on those kinds of platforms.
> >
> > This patch specifically tunes TEO to prefer shallower idle states in
> > order to reduce wakeup latency and achieve better performance.
> > To this end, before selecting the next idle state it uses the avg_util signal
> > of a CPU's runqueue in order to determine to what extent the CPU is being utilized.
> > This util value is then compared to a threshold defined as a percentage of the
> > cpu's capacity (capacity >> 6 ie. ~1.5% in the current implementation). If the
> > util is above the threshold, the idle state selected by TEO metrics will be
> > reduced by 1, thus selecting a shallower state. If the util is below the threshold,
> > the governor defaults to the TEO metrics mechanism to try to select the deepest
> > available idle state based on the closest timer event and its own correctness.
> >
> > The main goal of this is to reduce latency and increase performance for some
> > workloads. Under some workloads it will result in an increase in power usage
> > (Geekbench 5) while for other workloads it will also result in a decrease in
> > power usage compared to TEO (PCMark Web, Jankbench, Speedometer).
> >
> > It can provide drastically decreased latency and performance benefits in certain
> > types of workloads that are sensitive to latency.
> >
> > Example test results:
> >
> > 1. GB5 (better score, latency & more power usage)
> >
> > | metric                                | menu           | teo               | teo-util-aware    |
> > | ------------------------------------- | -------------- | ----------------- | ----------------- |
> > | gmean score                           | 2826.5 (0.0%)  | 2764.8 (-2.18%)   | 2865 (1.36%)      |
> > | gmean power usage [mW]                | 2551.4 (0.0%)  | 2606.8 (2.17%)    | 2722.3 (6.7%)     |
> > | gmean too deep %                      | 14.99%         | 9.65%             | 4.02%             |
> > | gmean too shallow %                   | 2.5%           | 5.96%             | 14.59%            |
> > | gmean task wakeup latency (asynctask) | 78.16μs (0.0%) | 61.60μs (-21.19%) | 54.45μs (-30.34%) |
> >
> > 2. Jankbench (better score, latency & less power usage)
> >
> > | metric                                | menu           | teo               | teo-util-aware    |
> > | ------------------------------------- | -------------- | ----------------- | ----------------- |
> > | gmean frame duration                  | 13.9 (0.0%)    | 14.7 (6.0%)       | 12.6 (-9.0%)      |
> > | gmean jank percentage                 | 1.5 (0.0%)     | 2.1 (36.99%)      | 1.3 (-17.37%)     |
> > | gmean power usage [mW]                | 144.6 (0.0%)   | 136.9 (-5.27%)    | 121.3 (-16.08%)   |
> > | gmean too deep %                      | 26.00%         | 11.00%            | 2.54%             |
> > | gmean too shallow %                   | 4.74%          | 11.89%            | 21.93%            |
> > | gmean wakeup latency (RenderThread)   | 139.5μs (0.0%) | 116.5μs (-16.49%) | 91.11μs (-34.7%)  |
> > | gmean wakeup latency (surfaceflinger) | 124.0μs (0.0%) | 151.9μs (22.47%)  | 87.65μs (-29.33%) |
> >
> > Signed-off-by: Kajetan Puchalski <kajetan.puchalski@arm.com>
>
> This looks good enough for me.
>
> There are still a couple of things I would change in it, but I may as
> well do that when applying it, so never mind.
>
> The most important question for now is what the scheduler people think
> about calling sched_cpu_util() from a CPU idle governor.  Peter,
> Vincent?

I don't see a problem with using sched_cpu_util() outside the
scheduler as it's already used in thermal and dtpm to get cpu
utilization.

>
> > ---
> >  drivers/cpuidle/governors/teo.c | 92 ++++++++++++++++++++++++++++++++-
> >  1 file changed, 91 insertions(+), 1 deletion(-)
> >
> > diff --git a/drivers/cpuidle/governors/teo.c b/drivers/cpuidle/governors/teo.c
> > index e2864474a98d..2a2be4f45b70 100644
> > --- a/drivers/cpuidle/governors/teo.c
> > +++ b/drivers/cpuidle/governors/teo.c
> > @@ -2,8 +2,13 @@
> >  /*
> >   * Timer events oriented CPU idle governor
> >   *
> > + * TEO governor:
> >   * Copyright (C) 2018 - 2021 Intel Corporation
> >   * Author: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > + *
> > + * Util-awareness mechanism:
> > + * Copyright (C) 2022 Arm Ltd.
> > + * Author: Kajetan Puchalski <kajetan.puchalski@arm.com>
> >   */
> >
> >  /**
> > @@ -99,14 +104,55 @@
> >   *      select the given idle state instead of the candidate one.
> >   *
> >   * 3. By default, select the candidate state.
> > + *
> > + * Util-awareness mechanism:
> > + *
> > + * The idea behind the util-awareness extension is that there are two distinct
> > + * scenarios for the CPU which should result in two different approaches to idle
> > + * state selection - utilized and not utilized.
> > + *
> > + * In this case, 'utilized' means that the average runqueue util of the CPU is
> > + * above a certain threshold.
> > + *
> > + * When the CPU is utilized while going into idle, more likely than not it will
> > + * be woken up to do more work soon and so a shallower idle state should be
> > + * selected to minimise latency and maximise performance. When the CPU is not
> > + * being utilized, the usual metrics-based approach to selecting the deepest
> > + * available idle state should be preferred to take advantage of the power
> > + * saving.
> > + *
> > + * In order to achieve this, the governor uses a utilization threshold.
> > + * The threshold is computed per-cpu as a percentage of the CPU's capacity
> > + * by bit shifting the capacity value. Based on testing, the shift of 6 (~1.56%)
> > + * seems to be getting the best results.
> > + *
> > + * Before selecting the next idle state, the governor compares the current CPU
> > + * util to the precomputed util threshold. If it's below, it defaults to the
> > + * TEO metrics mechanism. If it's above, the idle state will be reduced to C0
> > + * as long as C0 is not a polling state.
> >   */
> >
> >  #include <linux/cpuidle.h>
> >  #include <linux/jiffies.h>
> >  #include <linux/kernel.h>
> > +#include <linux/sched.h>
> >  #include <linux/sched/clock.h>
> > +#include <linux/sched/topology.h>
> >  #include <linux/tick.h>
> >
> > +/*
> > + * The number of bits to shift the cpu's capacity by in order to determine
> > + * the utilized threshold.
> > + *
> > + * 6 was chosen based on testing as the number that achieved the best balance
> > + * of power and performance on average.
> > + *
> > + * The resulting threshold is high enough to not be triggered by background
> > + * noise and low enough to react quickly when activity starts to ramp up.
> > + */
> > +#define UTIL_THRESHOLD_SHIFT 6
> > +
> > +
> >  /*
> >   * The PULSE value is added to metrics when they grow and the DECAY_SHIFT value
> >   * is used for decreasing metrics on a regular basis.
> > @@ -137,9 +183,11 @@ struct teo_bin {
> >   * @time_span_ns: Time between idle state selection and post-wakeup update.
> >   * @sleep_length_ns: Time till the closest timer event (at the selection time).
> >   * @state_bins: Idle state data bins for this CPU.
> > - * @total: Grand total of the "intercepts" and "hits" mertics for all bins.
> > + * @total: Grand total of the "intercepts" and "hits" metrics for all bins.
> >   * @next_recent_idx: Index of the next @recent_idx entry to update.
> >   * @recent_idx: Indices of bins corresponding to recent "intercepts".
> > + * @util_threshold: Threshold above which the CPU is considered utilized
> > + * @utilized: Whether the last sleep on the CPU happened while utilized
> >   */
> >  struct teo_cpu {
> >         s64 time_span_ns;
> > @@ -148,10 +196,29 @@ struct teo_cpu {
> >         unsigned int total;
> >         int next_recent_idx;
> >         int recent_idx[NR_RECENT];
> > +       unsigned long util_threshold;
> > +       bool utilized;
> >  };
> >
> >  static DEFINE_PER_CPU(struct teo_cpu, teo_cpus);
> >
> > +/**
> > + * teo_cpu_is_utilized - Check if the CPU's util is above the threshold
> > + * @cpu: Target CPU
> > + * @cpu_data: Governor CPU data for the target CPU
> > + */
> > +#ifdef CONFIG_SMP
> > +static bool teo_cpu_is_utilized(int cpu, struct teo_cpu *cpu_data)
> > +{
> > +       return sched_cpu_util(cpu) > cpu_data->util_threshold;
> > +}
> > +#else
> > +static bool teo_cpu_is_utilized(int cpu, struct teo_cpu *cpu_data)
> > +{
> > +       return false;
> > +}
> > +#endif
> > +
> >  /**
> >   * teo_update - Update CPU metrics after wakeup.
> >   * @drv: cpuidle driver containing state data.
> > @@ -323,6 +390,20 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
> >                         goto end;
> >         }
> >
> > +       cpu_data->utilized = teo_cpu_is_utilized(dev->cpu, cpu_data);
> > +       /*
> > +        * The cpu is being utilized over the threshold there are only 2 states to choose from.
> > +        * No need to consider metrics, choose the shallowest non-polling state and exit.
> > +        */
> > +       if (drv->state_count < 3 && cpu_data->utilized) {
> > +               for (i = 0; i < drv->state_count; ++i) {
> > +                       if (!dev->states_usage[i].disable && !(drv->states[i].flags & CPUIDLE_FLAG_POLLING)) {
> > +                               idx = i;
> > +                               goto end;
> > +                       }
> > +               }
> > +       }
> > +
> >         /*
> >          * Find the deepest idle state whose target residency does not exceed
> >          * the current sleep length and the deepest idle state not deeper than
> > @@ -454,6 +535,13 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
> >         if (idx > constraint_idx)
> >                 idx = constraint_idx;
> >
> > +       /*
> > +        * If the CPU is being utilized over the threshold,
> > +        * choose a shallower non-polling state to improve latency
> > +        */
> > +       if (cpu_data->utilized)
> > +               idx = teo_find_shallower_state(drv, dev, idx, duration_ns, true);
> > +
> >  end:
> >         /*
> >          * Don't stop the tick if the selected state is a polling one or if the
> > @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
> >                              struct cpuidle_device *dev)
> >  {
> >         struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> > +       unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
> >         int i;
> >
> >         memset(cpu_data, 0, sizeof(*cpu_data));
> > +       cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
> >
> >         for (i = 0; i < NR_RECENT; i++)
> >                 cpu_data->recent_idx[i] = -1;
> > --
> > 2.37.1
> >
  

On Thu, Jan 5, 2023 at 4:34 PM Vincent Guittot
<vincent.guittot@linaro.org> wrote:
>
> On Thu, 5 Jan 2023 at 16:07, Rafael J. Wysocki <rafael@kernel.org> wrote:
> >
> > On Thu, Jan 5, 2023 at 3:52 PM Kajetan Puchalski
> > <kajetan.puchalski@arm.com> wrote:
> > >
> > > Modern interactive systems, such as recent Android phones, tend to have power
> > > efficient shallow idle states. Selecting deeper idle states on a device while a
> > > latency-sensitive workload is running can adversely impact performance due to
> > > increased latency. Additionally, if the CPU wakes up from a deeper sleep before
> > > its target residency as is often the case, it results in a waste of energy on
> > > top of that.
> > >
> > > At the moment, none of the available idle governors take any scheduling
> > > information into account. They also tend to overestimate the idle
> > > duration quite often, which causes them to select excessively deep idle
> > > states, thus leading to increased wakeup latency and lower performance with no
> > > power saving. For 'menu' while web browsing on Android for instance, those
> > > types of wakeups ('too deep') account for over 24% of all wakeups.
> > >
> > > At the same time, on some platforms idle state 0 can be power efficient
> > > enough to warrant wanting to prefer it over idle state 1. This is because
> > > the power usage of the two states can be so close that sufficient amounts
> > > of too deep state 1 sleeps can completely offset the state 1 power saving to the
> > > point where it would've been more power efficient to just use state 0 instead.
> > > This is of course for systems where state 0 is not a polling state, such as
> > > arm-based devices.
> > >
> > > Sleeps that happened in state 0 while they could have used state 1 ('too shallow') only
> > > save less power than they otherwise could have. Too deep sleeps, on the other
> > > hand, harm performance and nullify the potential power saving from using state 1 in
> > > the first place. While taking this into account, it is clear that on balance it
> > > is preferable for an idle governor to have more too shallow sleeps instead of
> > > more too deep sleeps on those kinds of platforms.
> > >
> > > This patch specifically tunes TEO to prefer shallower idle states in
> > > order to reduce wakeup latency and achieve better performance.
> > > To this end, before selecting the next idle state it uses the avg_util signal
> > > of a CPU's runqueue in order to determine to what extent the CPU is being utilized.
> > > This util value is then compared to a threshold defined as a percentage of the
> > > cpu's capacity (capacity >> 6 ie. ~1.5% in the current implementation). If the
> > > util is above the threshold, the idle state selected by TEO metrics will be
> > > reduced by 1, thus selecting a shallower state. If the util is below the threshold,
> > > the governor defaults to the TEO metrics mechanism to try to select the deepest
> > > available idle state based on the closest timer event and its own correctness.
> > >
> > > The main goal of this is to reduce latency and increase performance for some
> > > workloads. Under some workloads it will result in an increase in power usage
> > > (Geekbench 5) while for other workloads it will also result in a decrease in
> > > power usage compared to TEO (PCMark Web, Jankbench, Speedometer).
> > >
> > > It can provide drastically decreased latency and performance benefits in certain
> > > types of workloads that are sensitive to latency.
> > >
> > > Example test results:
> > >
> > > 1. GB5 (better score, latency & more power usage)
> > >
> > > | metric                                | menu           | teo               | teo-util-aware    |
> > > | ------------------------------------- | -------------- | ----------------- | ----------------- |
> > > | gmean score                           | 2826.5 (0.0%)  | 2764.8 (-2.18%)   | 2865 (1.36%)      |
> > > | gmean power usage [mW]                | 2551.4 (0.0%)  | 2606.8 (2.17%)    | 2722.3 (6.7%)     |
> > > | gmean too deep %                      | 14.99%         | 9.65%             | 4.02%             |
> > > | gmean too shallow %                   | 2.5%           | 5.96%             | 14.59%            |
> > > | gmean task wakeup latency (asynctask) | 78.16μs (0.0%) | 61.60μs (-21.19%) | 54.45μs (-30.34%) |
> > >
> > > 2. Jankbench (better score, latency & less power usage)
> > >
> > > | metric                                | menu           | teo               | teo-util-aware    |
> > > | ------------------------------------- | -------------- | ----------------- | ----------------- |
> > > | gmean frame duration                  | 13.9 (0.0%)    | 14.7 (6.0%)       | 12.6 (-9.0%)      |
> > > | gmean jank percentage                 | 1.5 (0.0%)     | 2.1 (36.99%)      | 1.3 (-17.37%)     |
> > > | gmean power usage [mW]                | 144.6 (0.0%)   | 136.9 (-5.27%)    | 121.3 (-16.08%)   |
> > > | gmean too deep %                      | 26.00%         | 11.00%            | 2.54%             |
> > > | gmean too shallow %                   | 4.74%          | 11.89%            | 21.93%            |
> > > | gmean wakeup latency (RenderThread)   | 139.5μs (0.0%) | 116.5μs (-16.49%) | 91.11μs (-34.7%)  |
> > > | gmean wakeup latency (surfaceflinger) | 124.0μs (0.0%) | 151.9μs (22.47%)  | 87.65μs (-29.33%) |
> > >
> > > Signed-off-by: Kajetan Puchalski <kajetan.puchalski@arm.com>
> >
> > This looks good enough for me.
> >
> > There are still a couple of things I would change in it, but I may as
> > well do that when applying it, so never mind.
> >
> > The most important question for now is what the scheduler people think
> > about calling sched_cpu_util() from a CPU idle governor.  Peter,
> > Vincent?
>
> I don't see a problem with using sched_cpu_util() outside the
> scheduler as it's already used in thermal and dtpm to get cpu
> utilization.

OK, thanks!

> >
> > > ---
> > >  drivers/cpuidle/governors/teo.c | 92 ++++++++++++++++++++++++++++++++-
> > >  1 file changed, 91 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/drivers/cpuidle/governors/teo.c b/drivers/cpuidle/governors/teo.c
> > > index e2864474a98d..2a2be4f45b70 100644
> > > --- a/drivers/cpuidle/governors/teo.c
> > > +++ b/drivers/cpuidle/governors/teo.c
> > > @@ -2,8 +2,13 @@
> > >  /*
> > >   * Timer events oriented CPU idle governor
> > >   *
> > > + * TEO governor:
> > >   * Copyright (C) 2018 - 2021 Intel Corporation
> > >   * Author: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > > + *
> > > + * Util-awareness mechanism:
> > > + * Copyright (C) 2022 Arm Ltd.
> > > + * Author: Kajetan Puchalski <kajetan.puchalski@arm.com>
> > >   */
> > >
> > >  /**
> > > @@ -99,14 +104,55 @@
> > >   *      select the given idle state instead of the candidate one.
> > >   *
> > >   * 3. By default, select the candidate state.
> > > + *
> > > + * Util-awareness mechanism:
> > > + *
> > > + * The idea behind the util-awareness extension is that there are two distinct
> > > + * scenarios for the CPU which should result in two different approaches to idle
> > > + * state selection - utilized and not utilized.
> > > + *
> > > + * In this case, 'utilized' means that the average runqueue util of the CPU is
> > > + * above a certain threshold.
> > > + *
> > > + * When the CPU is utilized while going into idle, more likely than not it will
> > > + * be woken up to do more work soon and so a shallower idle state should be
> > > + * selected to minimise latency and maximise performance. When the CPU is not
> > > + * being utilized, the usual metrics-based approach to selecting the deepest
> > > + * available idle state should be preferred to take advantage of the power
> > > + * saving.
> > > + *
> > > + * In order to achieve this, the governor uses a utilization threshold.
> > > + * The threshold is computed per-cpu as a percentage of the CPU's capacity
> > > + * by bit shifting the capacity value. Based on testing, the shift of 6 (~1.56%)
> > > + * seems to be getting the best results.
> > > + *
> > > + * Before selecting the next idle state, the governor compares the current CPU
> > > + * util to the precomputed util threshold. If it's below, it defaults to the
> > > + * TEO metrics mechanism. If it's above, the idle state will be reduced to C0
> > > + * as long as C0 is not a polling state.
> > >   */
> > >
> > >  #include <linux/cpuidle.h>
> > >  #include <linux/jiffies.h>
> > >  #include <linux/kernel.h>
> > > +#include <linux/sched.h>
> > >  #include <linux/sched/clock.h>
> > > +#include <linux/sched/topology.h>
> > >  #include <linux/tick.h>
> > >
> > > +/*
> > > + * The number of bits to shift the cpu's capacity by in order to determine
> > > + * the utilized threshold.
> > > + *
> > > + * 6 was chosen based on testing as the number that achieved the best balance
> > > + * of power and performance on average.
> > > + *
> > > + * The resulting threshold is high enough to not be triggered by background
> > > + * noise and low enough to react quickly when activity starts to ramp up.
> > > + */
> > > +#define UTIL_THRESHOLD_SHIFT 6
> > > +
> > > +
> > >  /*
> > >   * The PULSE value is added to metrics when they grow and the DECAY_SHIFT value
> > >   * is used for decreasing metrics on a regular basis.
> > > @@ -137,9 +183,11 @@ struct teo_bin {
> > >   * @time_span_ns: Time between idle state selection and post-wakeup update.
> > >   * @sleep_length_ns: Time till the closest timer event (at the selection time).
> > >   * @state_bins: Idle state data bins for this CPU.
> > > - * @total: Grand total of the "intercepts" and "hits" mertics for all bins.
> > > + * @total: Grand total of the "intercepts" and "hits" metrics for all bins.
> > >   * @next_recent_idx: Index of the next @recent_idx entry to update.
> > >   * @recent_idx: Indices of bins corresponding to recent "intercepts".
> > > + * @util_threshold: Threshold above which the CPU is considered utilized
> > > + * @utilized: Whether the last sleep on the CPU happened while utilized
> > >   */
> > >  struct teo_cpu {
> > >         s64 time_span_ns;
> > > @@ -148,10 +196,29 @@ struct teo_cpu {
> > >         unsigned int total;
> > >         int next_recent_idx;
> > >         int recent_idx[NR_RECENT];
> > > +       unsigned long util_threshold;
> > > +       bool utilized;
> > >  };
> > >
> > >  static DEFINE_PER_CPU(struct teo_cpu, teo_cpus);
> > >
> > > +/**
> > > + * teo_cpu_is_utilized - Check if the CPU's util is above the threshold
> > > + * @cpu: Target CPU
> > > + * @cpu_data: Governor CPU data for the target CPU
> > > + */
> > > +#ifdef CONFIG_SMP
> > > +static bool teo_cpu_is_utilized(int cpu, struct teo_cpu *cpu_data)
> > > +{
> > > +       return sched_cpu_util(cpu) > cpu_data->util_threshold;
> > > +}
> > > +#else
> > > +static bool teo_cpu_is_utilized(int cpu, struct teo_cpu *cpu_data)
> > > +{
> > > +       return false;
> > > +}
> > > +#endif
> > > +
> > >  /**
> > >   * teo_update - Update CPU metrics after wakeup.
> > >   * @drv: cpuidle driver containing state data.
> > > @@ -323,6 +390,20 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
> > >                         goto end;
> > >         }
> > >
> > > +       cpu_data->utilized = teo_cpu_is_utilized(dev->cpu, cpu_data);
> > > +       /*
> > > +        * The cpu is being utilized over the threshold there are only 2 states to choose from.
> > > +        * No need to consider metrics, choose the shallowest non-polling state and exit.
> > > +        */
> > > +       if (drv->state_count < 3 && cpu_data->utilized) {
> > > +               for (i = 0; i < drv->state_count; ++i) {
> > > +                       if (!dev->states_usage[i].disable && !(drv->states[i].flags & CPUIDLE_FLAG_POLLING)) {
> > > +                               idx = i;
> > > +                               goto end;
> > > +                       }
> > > +               }
> > > +       }
> > > +
> > >         /*
> > >          * Find the deepest idle state whose target residency does not exceed
> > >          * the current sleep length and the deepest idle state not deeper than
> > > @@ -454,6 +535,13 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
> > >         if (idx > constraint_idx)
> > >                 idx = constraint_idx;
> > >
> > > +       /*
> > > +        * If the CPU is being utilized over the threshold,
> > > +        * choose a shallower non-polling state to improve latency
> > > +        */
> > > +       if (cpu_data->utilized)
> > > +               idx = teo_find_shallower_state(drv, dev, idx, duration_ns, true);
> > > +
> > >  end:
> > >         /*
> > >          * Don't stop the tick if the selected state is a polling one or if the
> > > @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
> > >                              struct cpuidle_device *dev)
> > >  {
> > >         struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> > > +       unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
> > >         int i;
> > >
> > >         memset(cpu_data, 0, sizeof(*cpu_data));
> > > +       cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
> > >
> > >         for (i = 0; i < NR_RECENT; i++)
> > >                 cpu_data->recent_idx[i] = -1;
> > > --
> > > 2.37.1
> > >
  

Hi Kajetan

On 01/05/23 14:51, Kajetan Puchalski wrote:

[...]

> @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
>  			     struct cpuidle_device *dev)
>  {
>  	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> +	unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
>  	int i;
>  
>  	memset(cpu_data, 0, sizeof(*cpu_data));
> +	cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;

Given that utilization is invariant, why do we set the threshold based on
cpu capacity?

I'm not sure if this is a problem, but on little cores this threshold would be
too low. Given that util is invariant - I wondered if we need to have a single
threshold for all type of CPUs instead. Have you tried something like that
while developing the patch?


Thanks

--
Qais Yousef
  

Hi Qais,

The rule is 'one size doesn't fit all', please see below.

On 7/11/23 18:58, Qais Yousef wrote:
> Hi Kajetan
> 
> On 01/05/23 14:51, Kajetan Puchalski wrote:
> 
> [...]
> 
>> @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
>>   			     struct cpuidle_device *dev)
>>   {
>>   	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
>> +	unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
>>   	int i;
>>   
>>   	memset(cpu_data, 0, sizeof(*cpu_data));
>> +	cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
> 
> Given that utilization is invariant, why do we set the threshold based on
> cpu capacity?


To treat CPUs differently, not with the same policy.


> 
> I'm not sure if this is a problem, but on little cores this threshold would be
> too low. Given that util is invariant - I wondered if we need to have a single
> threshold for all type of CPUs instead. Have you tried something like that

A single threshold for all CPUs might be biased towards some CPUs. Let's
pick the value 15 - which was tested to work really good in benchmarks
for the big CPUs. On the other hand when you set that value to little
CPUs, with max_capacity = 124, than you have 15/124 ~= 13% threshold.
That means you prefer to enter deeper idle state ~9x times (at max
freq). What if the Little's freq is set to e.g. < ~20% fmax, which
corresponds to capacity < ~25? Let's try to simulate such scenario.

In a situation we could have utilization 14 on Little CPU, than CPU 
capacity (effectively frequency) voting based on utilization would be
1.2 * 14 = ~17 so let's pick OPP corresponding to 17 capacity.
In such condition the little CPU would run the 14-util-periodic-task for
14/17= ~82% of wall-clock time. That's a lot, and not suited for
entering deeper idle state on that CPU, isn't it?

Apart from that, the little CPUs are tiny in terms of silicon area
and are less leaky in WFI than big cores. Therefore, they don't need
aggressive entries into deeper idle state. At the same time, they
are often used for serving interrupts, where the latency is important
factor.

> while developing the patch?

We have tried different threshold values in terms of %, but for all CPUs
(at the same time) not per-cluster. The reason was to treat those CPUs
differently as described above.

Regards,
Lukasz
  

+CC Vincent and Peter

On 07/17/23 14:47, Lukasz Luba wrote:
> Hi Qais,
> 
> The rule is 'one size doesn't fit all', please see below.
> 
> On 7/11/23 18:58, Qais Yousef wrote:
> > Hi Kajetan
> > 
> > On 01/05/23 14:51, Kajetan Puchalski wrote:
> > 
> > [...]
> > 
> > > @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
> > >   			     struct cpuidle_device *dev)
> > >   {
> > >   	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> > > +	unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
> > >   	int i;
> > >   	memset(cpu_data, 0, sizeof(*cpu_data));
> > > +	cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
> > 
> > Given that utilization is invariant, why do we set the threshold based on
> > cpu capacity?
> 
> 
> To treat CPUs differently, not with the same policy.
> 
> 
> > 
> > I'm not sure if this is a problem, but on little cores this threshold would be
> > too low. Given that util is invariant - I wondered if we need to have a single
> > threshold for all type of CPUs instead. Have you tried something like that
> 
> A single threshold for all CPUs might be biased towards some CPUs. Let's
> pick the value 15 - which was tested to work really good in benchmarks
> for the big CPUs. On the other hand when you set that value to little
> CPUs, with max_capacity = 124, than you have 15/124 ~= 13% threshold.
> That means you prefer to enter deeper idle state ~9x times (at max
> freq). What if the Little's freq is set to e.g. < ~20% fmax, which
> corresponds to capacity < ~25? Let's try to simulate such scenario.

Hmm what I'm struggling with is that PELT is invariant. So the time it takes to
rise and decay to threshold of 15 should be the same for all CPUs, no?

> 
> In a situation we could have utilization 14 on Little CPU, than CPU capacity
> (effectively frequency) voting based on utilization would be
> 1.2 * 14 = ~17 so let's pick OPP corresponding to 17 capacity.
> In such condition the little CPU would run the 14-util-periodic-task for
> 14/17= ~82% of wall-clock time. That's a lot, and not suited for
> entering deeper idle state on that CPU, isn't it?

Yes runtime is stretched. But we counter this at utilization level by making
PELT invariant. I thought that any CPU in the system will now take the same
amount of time to ramp-up and decay to the same util level. No?

But maybe what you're saying is that we don't need to take the invariance into
account?

My concern (that is not backed by real problem yet) is that the threshold is
near 0, and since PELT is invariant, the time to gain few points is constant
irrespective of any CPU/capacity/freq and this means the little CPUs has to be
absolutely idle with no activity almost at all, IIUC.

> 
> Apart from that, the little CPUs are tiny in terms of silicon area
> and are less leaky in WFI than big cores. Therefore, they don't need
> aggressive entries into deeper idle state. At the same time, they
> are often used for serving interrupts, where the latency is important
> factor.

On Pixel 6 this threshold will translate to util_threshold of 2. Which looks
too low to me. Can't TEO do a good job before we reach such extremely low level
of inactivity?


Thanks

--
Qais Yousef

> 
> > while developing the patch?
> 
> We have tried different threshold values in terms of %, but for all CPUs
> (at the same time) not per-cluster. The reason was to treat those CPUs
> differently as described above.
> 
> Regards,
> Lukasz
  

On 7/17/23 19:21, Qais Yousef wrote:
> +CC Vincent and Peter
> 
> On 07/17/23 14:47, Lukasz Luba wrote:
>> Hi Qais,
>>
>> The rule is 'one size doesn't fit all', please see below.
>>
>> On 7/11/23 18:58, Qais Yousef wrote:
>>> Hi Kajetan
>>>
>>> On 01/05/23 14:51, Kajetan Puchalski wrote:
>>>
>>> [...]
>>>
>>>> @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
>>>>    			     struct cpuidle_device *dev)
>>>>    {
>>>>    	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
>>>> +	unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
>>>>    	int i;
>>>>    	memset(cpu_data, 0, sizeof(*cpu_data));
>>>> +	cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
>>>
>>> Given that utilization is invariant, why do we set the threshold based on
>>> cpu capacity?
>>
>>
>> To treat CPUs differently, not with the same policy.
>>
>>
>>>
>>> I'm not sure if this is a problem, but on little cores this threshold would be
>>> too low. Given that util is invariant - I wondered if we need to have a single
>>> threshold for all type of CPUs instead. Have you tried something like that
>>
>> A single threshold for all CPUs might be biased towards some CPUs. Let's
>> pick the value 15 - which was tested to work really good in benchmarks
>> for the big CPUs. On the other hand when you set that value to little
>> CPUs, with max_capacity = 124, than you have 15/124 ~= 13% threshold.
>> That means you prefer to enter deeper idle state ~9x times (at max
>> freq). What if the Little's freq is set to e.g. < ~20% fmax, which
>> corresponds to capacity < ~25? Let's try to simulate such scenario.
> 
> Hmm what I'm struggling with is that PELT is invariant. So the time it takes to
> rise and decay to threshold of 15 should be the same for all CPUs, no?

Yes, but that's not an issue. The idea is to have a threshold value
set to a level which corresponds to a long enough slip time (in
wall-clock). Then you don't waste the energy for turning on/off the
core too often.

> 
>>
>> In a situation we could have utilization 14 on Little CPU, than CPU capacity
>> (effectively frequency) voting based on utilization would be
>> 1.2 * 14 = ~17 so let's pick OPP corresponding to 17 capacity.
>> In such condition the little CPU would run the 14-util-periodic-task for
>> 14/17= ~82% of wall-clock time. That's a lot, and not suited for
>> entering deeper idle state on that CPU, isn't it?
> 
> Yes runtime is stretched. But we counter this at utilization level by making
> PELT invariant. I thought that any CPU in the system will now take the same
> amount of time to ramp-up and decay to the same util level. No?

The stretched runtime is what we want to derived out of rq util
information, mostly after task migration to some next cpu.

> 
> But maybe what you're saying is that we don't need to take the invariance into
> account?

Invariance is OK, since is the common ground when we migrate those tasks
across cores and we still can conclude based on util the sleeping
cpu time.

> 
> My concern (that is not backed by real problem yet) is that the threshold is
> near 0, and since PELT is invariant, the time to gain few points is constant
> irrespective of any CPU/capacity/freq and this means the little CPUs has to be
> absolutely idle with no activity almost at all, IIUC.

As I said, that is good for those Little CPU in term of better latency
for the tasks they serve and also doesn't harm the energy. The
deeper idle state for those tiny silicon area cores (and low-power
cells) doesn't bring much in avg for real workloads.
This is the trade-off: you don't want to sacrifice the latency factor,
you would rather pay a bit more energy not entering deep idle
on Little cores, but get better latency there.
For the big cores, which occupy bigger silicon area and are made from
High-Performance (HP) cells (and low V-threshold) leaking more, that
trade-off is set differently. That's why a similar small util task on
big core might be facing larger latency do to facing the need to
wake-up cpu from deeper idle state.

> 
>>
>> Apart from that, the little CPUs are tiny in terms of silicon area
>> and are less leaky in WFI than big cores. Therefore, they don't need
>> aggressive entries into deeper idle state. At the same time, they
>> are often used for serving interrupts, where the latency is important
>> factor.
> 
> On Pixel 6 this threshold will translate to util_threshold of 2. Which looks
> too low to me. Can't TEO do a good job before we reach such extremely low level
> of inactivity?

Kajetan has introduced a new trace event 'cpu_idle_miss' which was
helping us to say how to set the trade-off in different thresholds.
It appeared that we would rather prefer to miss-predict and be wrong
about missing opportunity to enter deeper idle. The opposite was more
harmful. You can enable that trace event on your platform and analyze
your use cases.

Regards,
Lukasz
  

Hi Qais,

On Tue, Jul 11, 2023 at 06:58:14PM +0100, Qais Yousef wrote:
> Hi Kajetan
> 
> On 01/05/23 14:51, Kajetan Puchalski wrote:
> 
> [...]
> 
> > @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
> >  			     struct cpuidle_device *dev)
> >  {
> >  	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> > +	unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
> >  	int i;
> >  
> >  	memset(cpu_data, 0, sizeof(*cpu_data));
> > +	cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
> 
> Given that utilization is invariant, why do we set the threshold based on
> cpu capacity?

Conceptually, the threshold is meant to represent a level at which the
core is considered 'utilized'. I appreciate the definitions here can get
a little fuzzy but I think of it as "generally doing a non-insignificant
amount of work" even if there are currently no tasks scheduled on the core.
This comes in handy in real-world workloads where the core will go
through multiple cycles of busy-idle-busy-idle within each second.
The intention here is to be able to distinguish a scenario of "going
into idle for a few us because of the nature of the workload" from
"going into idle for longer because there is no workload".

I set the threshold based on capacity because I think conceptually it
makes more sense to say "every CPU is consireded to be utilized if the
util is above X% of its capacity" than to effectively have a varying
percentage based on the size of the core. 60 util is not that
much work for a 1024-util big core but it's almost half the capacity of
a little one, using a percentage/shift on capacity lets us account for that
while using a raw value would not.

There's also very practical issues but I'll describe those below.

> I'm not sure if this is a problem, but on little cores this threshold would be
> too low. Given that util is invariant - I wondered if we need to have a single
> threshold for all type of CPUs instead. Have you tried something like that
> while developing the patch?

Yes, the problem there is that it's very difficult to define what "too low"
actually means :)
Namely, do we define 'too low' based on the effects it has on
performance in terms of latency, on the resulting power usage or on the
prediction accuracy? In terms of the prediction accuracy, how do we
weigh the two possible types of mispredictions? I'll just try to explain
my thinking and how I got to my conclusions.

Based on my tests, on the types of platforms we both work with our
state0/wfi is very power efficient to stay in, very power efficient
to enter/exit and also very fast so it has very little impact on
latency. On the other hand, state1 is power efficient to *stay in* but
very costly to enter/exit in terms of *both* power and latency. The
effect this has is that there's many cases where going through a cycle
of busy-state1-busy-state1-busy and so on will actually use up more
power than if you only kept the core in wfi.

I had some tests done with effectively making the governor do "return 0"
in state selection, never using any state1 and the results were still
pretty good, only slightly worse than e.g. menu. The problem there was
that not using state1 on big cores would not leave them time to cool
down and we'd burn through the thermal budget too quickly then tank the
performance.

I don't have the numbers on hand but even completely disabling state1 on
the entire little cluster will work perfectly fine - your latency for
tasks that run on littles will improve and the thermal budget/power
won't take a particularly noticeable hit because of how small they are
in the first place.

This is why the governor is intentionally skewed towards shallower
states, they just work better most of the time. If you try to skew it
the other way the results just come out much worse because even a
relatively small amount of mispredicted state1 entries can completely
nullify any benefits that selecting state1 could bring.

The percentage approach does make the threshold for littles pretty small
but as desccribed above that's perfectly fine, could say a feature not a
bug :) If we tried setting a fixed one across all CPUs then we'd need to
pick one high enough for the big cores which would end up being too high
for the littles, lead to excessive state1 entries and all the issues
I've just described. TLDR: there's just more downsides on the other side.

In development I just had a sysctl to set the threshold shift and iirc I
tested values from 3 to 10-12 eventually arriving at 6 being the one
with best results across different metrics and benchmarks. If you're
backporting the patch somewhere and have a specific platform feel free
to test it with different shift values, it's possible that different
platforms will behave differently with this. I doubt there's any
appetite to make the shift tweakable at runtime rather than a
compile-time constant but if you'd like to push for that I'm happy to
sign off on it, would work just as well as it does now.


> Thanks
> 
> --
> Qais Yousef
  

On 07/18/23 11:23, Lukasz Luba wrote:
> 
> 
> On 7/17/23 19:21, Qais Yousef wrote:
> > +CC Vincent and Peter
> > 
> > On 07/17/23 14:47, Lukasz Luba wrote:
> > > Hi Qais,
> > > 
> > > The rule is 'one size doesn't fit all', please see below.
> > > 
> > > On 7/11/23 18:58, Qais Yousef wrote:
> > > > Hi Kajetan
> > > > 
> > > > On 01/05/23 14:51, Kajetan Puchalski wrote:
> > > > 
> > > > [...]
> > > > 
> > > > > @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
> > > > >    			     struct cpuidle_device *dev)
> > > > >    {
> > > > >    	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> > > > > +	unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
> > > > >    	int i;
> > > > >    	memset(cpu_data, 0, sizeof(*cpu_data));
> > > > > +	cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
> > > > 
> > > > Given that utilization is invariant, why do we set the threshold based on
> > > > cpu capacity?
> > > 
> > > 
> > > To treat CPUs differently, not with the same policy.
> > > 
> > > 
> > > > 
> > > > I'm not sure if this is a problem, but on little cores this threshold would be
> > > > too low. Given that util is invariant - I wondered if we need to have a single
> > > > threshold for all type of CPUs instead. Have you tried something like that
> > > 
> > > A single threshold for all CPUs might be biased towards some CPUs. Let's
> > > pick the value 15 - which was tested to work really good in benchmarks
> > > for the big CPUs. On the other hand when you set that value to little
> > > CPUs, with max_capacity = 124, than you have 15/124 ~= 13% threshold.
> > > That means you prefer to enter deeper idle state ~9x times (at max
> > > freq). What if the Little's freq is set to e.g. < ~20% fmax, which
> > > corresponds to capacity < ~25? Let's try to simulate such scenario.
> > 
> > Hmm what I'm struggling with is that PELT is invariant. So the time it takes to
> > rise and decay to threshold of 15 should be the same for all CPUs, no?
> 
> Yes, but that's not an issue. The idea is to have a threshold value
> set to a level which corresponds to a long enough slip time (in
> wall-clock). Then you don't waste the energy for turning on/off the
> core too often.
> 
> > 
> > > 
> > > In a situation we could have utilization 14 on Little CPU, than CPU capacity
> > > (effectively frequency) voting based on utilization would be
> > > 1.2 * 14 = ~17 so let's pick OPP corresponding to 17 capacity.
> > > In such condition the little CPU would run the 14-util-periodic-task for
> > > 14/17= ~82% of wall-clock time. That's a lot, and not suited for
> > > entering deeper idle state on that CPU, isn't it?
> > 
> > Yes runtime is stretched. But we counter this at utilization level by making
> > PELT invariant. I thought that any CPU in the system will now take the same
> > amount of time to ramp-up and decay to the same util level. No?
> 
> The stretched runtime is what we want to derived out of rq util
> information, mostly after task migration to some next cpu.
> 
> > 
> > But maybe what you're saying is that we don't need to take the invariance into
> > account?
> 
> Invariance is OK, since is the common ground when we migrate those tasks
> across cores and we still can conclude based on util the sleeping
> cpu time.
> 
> > 
> > My concern (that is not backed by real problem yet) is that the threshold is
> > near 0, and since PELT is invariant, the time to gain few points is constant
> > irrespective of any CPU/capacity/freq and this means the little CPUs has to be
> > absolutely idle with no activity almost at all, IIUC.
> 
> As I said, that is good for those Little CPU in term of better latency
> for the tasks they serve and also doesn't harm the energy. The
> deeper idle state for those tiny silicon area cores (and low-power
> cells) doesn't bring much in avg for real workloads.
> This is the trade-off: you don't want to sacrifice the latency factor,
> you would rather pay a bit more energy not entering deep idle
> on Little cores, but get better latency there.

I can follow this argument much better than the time stretch one for sure.

I sort of agree, but feel cautious still this is too aggressive. I guess time
will let us know how suitable this is or we'll need to evolve :-)

FWIW, these patches are now in GKI, so we should get complaints if it is
a real problem.

> For the big cores, which occupy bigger silicon area and are made from
> High-Performance (HP) cells (and low V-threshold) leaking more, that
> trade-off is set differently. That's why a similar small util task on
> big core might be facing larger latency do to facing the need to
> wake-up cpu from deeper idle state.
> 
> > 
> > > 
> > > Apart from that, the little CPUs are tiny in terms of silicon area
> > > and are less leaky in WFI than big cores. Therefore, they don't need
> > > aggressive entries into deeper idle state. At the same time, they
> > > are often used for serving interrupts, where the latency is important
> > > factor.
> > 
> > On Pixel 6 this threshold will translate to util_threshold of 2. Which looks
> > too low to me. Can't TEO do a good job before we reach such extremely low level
> > of inactivity?
> 
> Kajetan has introduced a new trace event 'cpu_idle_miss' which was
> helping us to say how to set the trade-off in different thresholds.
> It appeared that we would rather prefer to miss-predict and be wrong
> about missing opportunity to enter deeper idle. The opposite was more
> harmful. You can enable that trace event on your platform and analyze
> your use cases.

Okay, thanks for the info.


Cheers

--
Qais Yousef
  

On 07/18/23 13:02, Kajetan Puchalski wrote:
> Hi Qais,
> 
> On Tue, Jul 11, 2023 at 06:58:14PM +0100, Qais Yousef wrote:
> > Hi Kajetan
> > 
> > On 01/05/23 14:51, Kajetan Puchalski wrote:
> > 
> > [...]
> > 
> > > @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
> > >  			     struct cpuidle_device *dev)
> > >  {
> > >  	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> > > +	unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
> > >  	int i;
> > >  
> > >  	memset(cpu_data, 0, sizeof(*cpu_data));
> > > +	cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
> > 
> > Given that utilization is invariant, why do we set the threshold based on
> > cpu capacity?
> 
> Conceptually, the threshold is meant to represent a level at which the
> core is considered 'utilized'. I appreciate the definitions here can get
> a little fuzzy but I think of it as "generally doing a non-insignificant
> amount of work" even if there are currently no tasks scheduled on the core.
> This comes in handy in real-world workloads where the core will go
> through multiple cycles of busy-idle-busy-idle within each second.
> The intention here is to be able to distinguish a scenario of "going
> into idle for a few us because of the nature of the workload" from
> "going into idle for longer because there is no workload".
> 
> I set the threshold based on capacity because I think conceptually it
> makes more sense to say "every CPU is consireded to be utilized if the
> util is above X% of its capacity" than to effectively have a varying
> percentage based on the size of the core. 60 util is not that
> much work for a 1024-util big core but it's almost half the capacity of
> a little one, using a percentage/shift on capacity lets us account for that
> while using a raw value would not.

Thanks for the explanation.

I did try the busy perspective, but I think I still view this as 60util means
we've are running on average for X ms. which I think what matters more than how
much this is of a work to the big core. I look at this; we still have few ms
worth of runtime on the CPU and it's not worth going to deeper idle state
yet.

I can appreciate you think that this percentage of runtime should be lower for
smaller cores. My doubt (which again is not backed by real problem - so I'm not
questioning but rather trying to understand :)) is that if this becomes too low
is it better than letting usual TEO logic to operate. The series in its current
shape is great and offers good improvement already, no doubt :)

By the way, by default big will get a threshold of 16, the little will get
a threshold of around 2. I think the latter will translate to few hundreds of
us of activity (haven't done proper measurement to be honest, so this could be
off but I don't think  by much).

> 
> There's also very practical issues but I'll describe those below.
> 
> > I'm not sure if this is a problem, but on little cores this threshold would be
> > too low. Given that util is invariant - I wondered if we need to have a single
> > threshold for all type of CPUs instead. Have you tried something like that
> > while developing the patch?
> 
> Yes, the problem there is that it's very difficult to define what "too low"
> actually means :)

target residency maybe?

> Namely, do we define 'too low' based on the effects it has on
> performance in terms of latency, on the resulting power usage or on the
> prediction accuracy? In terms of the prediction accuracy, how do we
> weigh the two possible types of mispredictions? I'll just try to explain
> my thinking and how I got to my conclusions.
> 
> Based on my tests, on the types of platforms we both work with our
> state0/wfi is very power efficient to stay in, very power efficient
> to enter/exit and also very fast so it has very little impact on
> latency. On the other hand, state1 is power efficient to *stay in* but
> very costly to enter/exit in terms of *both* power and latency. The
> effect this has is that there's many cases where going through a cycle
> of busy-state1-busy-state1-busy and so on will actually use up more
> power than if you only kept the core in wfi.
> 
> I had some tests done with effectively making the governor do "return 0"
> in state selection, never using any state1 and the results were still
> pretty good, only slightly worse than e.g. menu. The problem there was
> that not using state1 on big cores would not leave them time to cool
> down and we'd burn through the thermal budget too quickly then tank the
> performance.
> 
> I don't have the numbers on hand but even completely disabling state1 on
> the entire little cluster will work perfectly fine - your latency for
> tasks that run on littles will improve and the thermal budget/power
> won't take a particularly noticeable hit because of how small they are
> in the first place.
> 
> This is why the governor is intentionally skewed towards shallower
> states, they just work better most of the time. If you try to skew it
> the other way the results just come out much worse because even a
> relatively small amount of mispredicted state1 entries can completely
> nullify any benefits that selecting state1 could bring.
> 
> The percentage approach does make the threshold for littles pretty small
> but as desccribed above that's perfectly fine, could say a feature not a
> bug :) If we tried setting a fixed one across all CPUs then we'd need to

I didn't think it's a bug. But it seemed too low, hence the question.
I actually thought a single value is enough for all CPUs since util is
invariant and the tipping point where TEO normal predictions should work should
be the same.

Thanks for the detailed explanation :)

> pick one high enough for the big cores which would end up being too high
> for the littles, lead to excessive state1 entries and all the issues
> I've just described. TLDR: there's just more downsides on the other side.

This is an artifact of the shifting algorithm you used to derive it. It is not
a real restriction. But I appreciate that simple approach proved to be good
enough, and I have nothing against it.

> 
> In development I just had a sysctl to set the threshold shift and iirc I
> tested values from 3 to 10-12 eventually arriving at 6 being the one
> with best results across different metrics and benchmarks. If you're
> backporting the patch somewhere and have a specific platform feel free
> to test it with different shift values, it's possible that different
> platforms will behave differently with this. I doubt there's any
> appetite to make the shift tweakable at runtime rather than a
> compile-time constant but if you'd like to push for that I'm happy to
> sign off on it, would work just as well as it does now.

These patches are in GKI. So we'll if there are uncaught problems I guess :)

No appetite for a knob, but the very low value for littles did strike me and
thought I better ask at least. Today's littles are too tiny for their own good
and it seemed the threshold could end up being too aggressive especially in low
activity state. You effectively are saying that if we have few 100us of
activity, normal TEO predictions based on timers are no good and better to stay
shallower anyway.

Note that due to NOHZ, if we go to idle for an extended period the util value
might not decay for a while and miss some opportunities. Especially that when
it next wakes up, it's enough for this wake up to run for few 100s us to block
a deeper state before going back to sleep for extended period of time.

But we shall see. I got the answer I was looking for for now.


Thanks for the help!

--
Qais Yousef
  

On Tue, Jul 18, 2023 at 02:24:32PM +0100, Qais Yousef wrote:
> On 07/18/23 13:02, Kajetan Puchalski wrote:
> > Hi Qais,
> > 
> > On Tue, Jul 11, 2023 at 06:58:14PM +0100, Qais Yousef wrote:
> > > Hi Kajetan
> > > 
> > > On 01/05/23 14:51, Kajetan Puchalski wrote:
> > > 
> > > [...]
> > > 
> > > > @@ -510,9 +598,11 @@ static int teo_enable_device(struct cpuidle_driver *drv,
> > > >  			     struct cpuidle_device *dev)
> > > >  {
> > > >  	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
> > > > +	unsigned long max_capacity = arch_scale_cpu_capacity(dev->cpu);
> > > >  	int i;
> > > >  
> > > >  	memset(cpu_data, 0, sizeof(*cpu_data));
> > > > +	cpu_data->util_threshold = max_capacity >> UTIL_THRESHOLD_SHIFT;
> > > 
> > > Given that utilization is invariant, why do we set the threshold based on
> > > cpu capacity?
> > 
> > Conceptually, the threshold is meant to represent a level at which the
> > core is considered 'utilized'. I appreciate the definitions here can get
> > a little fuzzy but I think of it as "generally doing a non-insignificant
> > amount of work" even if there are currently no tasks scheduled on the core.
> > This comes in handy in real-world workloads where the core will go
> > through multiple cycles of busy-idle-busy-idle within each second.
> > The intention here is to be able to distinguish a scenario of "going
> > into idle for a few us because of the nature of the workload" from
> > "going into idle for longer because there is no workload".
> > 
> > I set the threshold based on capacity because I think conceptually it
> > makes more sense to say "every CPU is consireded to be utilized if the
> > util is above X% of its capacity" than to effectively have a varying
> > percentage based on the size of the core. 60 util is not that
> > much work for a 1024-util big core but it's almost half the capacity of
> > a little one, using a percentage/shift on capacity lets us account for that
> > while using a raw value would not.
> 
> Thanks for the explanation.
> 
> I did try the busy perspective, but I think I still view this as 60util means
> we've are running on average for X ms. which I think what matters more than how
> much this is of a work to the big core. I look at this; we still have few ms
> worth of runtime on the CPU and it's not worth going to deeper idle state
> yet.
> 
> I can appreciate you think that this percentage of runtime should be lower for
> smaller cores. My doubt (which again is not backed by real problem - so I'm not
> questioning but rather trying to understand :)) is that if this becomes too low
> is it better than letting usual TEO logic to operate. The series in its current
> shape is great and offers good improvement already, no doubt :)

No worries! In my experience it does tend to be better than just letting
the metrics logic operate as the metrics logic is pretty much just
reasonably good maths-based guessing and it relies on making mistakes
before adjusting - the util approach tries to just not make those
mistakes. Again, too shallow decisions most of the time are perfectly
fine, too deep decisions are an actual problem for both power and
performance.

> By the way, by default big will get a threshold of 16, the little will get
> a threshold of around 2. I think the latter will translate to few hundreds of
> us of activity (haven't done proper measurement to be honest, so this could be
> off but I don't think  by much).

Yeah that sounds about right but I don't think that's really an issue -
I'm pretty sure a case could be made to just never use deep idle on
littles anyway. Having some threshold above 0 at least accounts for the
"the phone is in your pocket" scenario. Because littles tend to run
many small background tasks over time in my testing they end up getting
tons of too deep decisions that mess things up so avoiding it tends
to be more beneficial. Especially I saw better results in UI benchmarks
like Jankbench that mainly run on littles.

> > 
> > There's also very practical issues but I'll describe those below.
> > 
> > > I'm not sure if this is a problem, but on little cores this threshold would be
> > > too low. Given that util is invariant - I wondered if we need to have a single
> > > threshold for all type of CPUs instead. Have you tried something like that
> > > while developing the patch?
> > 
> > Yes, the problem there is that it's very difficult to define what "too low"
> > actually means :)
> 
> target residency maybe?

Target residency refers to how long the cpu stays in idle, we're talking
about a threshold determining the avg util at which we allow deeper
idle in the first place. I don't think one really impacts the other? I
don't think we can really extrapolate from avg util the precise amount
of time we have until the next wakeup on the CPU apart from the
"probably soon" that the threshold is meant to determine.

> > Namely, do we define 'too low' based on the effects it has on
> > performance in terms of latency, on the resulting power usage or on the
> > prediction accuracy? In terms of the prediction accuracy, how do we
> > weigh the two possible types of mispredictions? I'll just try to explain
> > my thinking and how I got to my conclusions.
> > 
> > Based on my tests, on the types of platforms we both work with our
> > state0/wfi is very power efficient to stay in, very power efficient
> > to enter/exit and also very fast so it has very little impact on
> > latency. On the other hand, state1 is power efficient to *stay in* but
> > very costly to enter/exit in terms of *both* power and latency. The
> > effect this has is that there's many cases where going through a cycle
> > of busy-state1-busy-state1-busy and so on will actually use up more
> > power than if you only kept the core in wfi.
> > 
> > I had some tests done with effectively making the governor do "return 0"
> > in state selection, never using any state1 and the results were still
> > pretty good, only slightly worse than e.g. menu. The problem there was
> > that not using state1 on big cores would not leave them time to cool
> > down and we'd burn through the thermal budget too quickly then tank the
> > performance.
> > 
> > I don't have the numbers on hand but even completely disabling state1 on
> > the entire little cluster will work perfectly fine - your latency for
> > tasks that run on littles will improve and the thermal budget/power
> > won't take a particularly noticeable hit because of how small they are
> > in the first place.
> > 
> > This is why the governor is intentionally skewed towards shallower
> > states, they just work better most of the time. If you try to skew it
> > the other way the results just come out much worse because even a
> > relatively small amount of mispredicted state1 entries can completely
> > nullify any benefits that selecting state1 could bring.
> > 
> > The percentage approach does make the threshold for littles pretty small
> > but as desccribed above that's perfectly fine, could say a feature not a
> > bug :) If we tried setting a fixed one across all CPUs then we'd need to
> 
> I didn't think it's a bug. But it seemed too low, hence the question.
> I actually thought a single value is enough for all CPUs since util is
> invariant and the tipping point where TEO normal predictions should work should
> be the same.

Makes sense of course, I was saying it in the sense of "yes it's
intentionally that low" :)
From what I recall when I was testing it higher thresholds just didn't
work as well for the activity on the littles but could be
platform-specifc, always worth testing I suppose.

> Thanks for the detailed explanation :)
> 
> > pick one high enough for the big cores which would end up being too high
> > for the littles, lead to excessive state1 entries and all the issues
> > I've just described. TLDR: there's just more downsides on the other side.
> 
> This is an artifact of the shifting algorithm you used to derive it. It is not
> a real restriction. But I appreciate that simple approach proved to be good
> enough, and I have nothing against it.

True but even without the shifting just putting in a fixed number across
all clusters would have the same effect I'm pretty sure. E.g. if we go
with 16 that's fine for the big cluster but will let through a big chunk
of the too deep sleeps on the littles. If we pick 5 it's better for the
littles but suddenly the big cores which tend to get bigger-util tasks
will almost never go into deep idle.

> > 
> > In development I just had a sysctl to set the threshold shift and iirc I
> > tested values from 3 to 10-12 eventually arriving at 6 being the one
> > with best results across different metrics and benchmarks. If you're
> > backporting the patch somewhere and have a specific platform feel free
> > to test it with different shift values, it's possible that different
> > platforms will behave differently with this. I doubt there's any
> > appetite to make the shift tweakable at runtime rather than a
> > compile-time constant but if you'd like to push for that I'm happy to
> > sign off on it, would work just as well as it does now.
> 
> These patches are in GKI. So we'll if there are uncaught problems I guess :)

More testing platform is always a good idea, maybe we'll find some new
things out :)

> 
> No appetite for a knob, but the very low value for littles did strike me and
> thought I better ask at least. Today's littles are too tiny for their own good
> and it seemed the threshold could end up being too aggressive especially in low
> activity state. You effectively are saying that if we have few 100us of
> activity, normal TEO predictions based on timers are no good and better to stay
> shallower anyway.

It probably would be too aggressive if our state0 was a polling state
like on Intel cores, here we're very much leveraging the fact that arm
wfi is already very efficient. This makes it possible to afford multiple
'too shallow' sleeps that give us better latency + not a big power
difference as opposed to the 'too deep' ones that seriously harm both.

> Note that due to NOHZ, if we go to idle for an extended period the util value
> might not decay for a while and miss some opportunities. Especially that when
> it next wakes up, it's enough for this wake up to run for few 100s us to block
> a deeper state before going back to sleep for extended period of time.

That's true, again a tradeoff that usually comes out better - it's much
better overall to miss a deep sleep opportunity than to go into deep
idle and then not hit the residency.

> But we shall see. I got the answer I was looking for for now.

You're welcome, good luck!

> 
> Thanks for the help!
> 
> --
> Qais Yousef
  

Hi Kajetan

On 07/18/23 14:24, Qais Yousef wrote:

> These patches are in GKI. So we'll if there are uncaught problems I guess :)
> 
> No appetite for a knob, but the very low value for littles did strike me and
> thought I better ask at least. Today's littles are too tiny for their own good
> and it seemed the threshold could end up being too aggressive especially in low
> activity state. You effectively are saying that if we have few 100us of
> activity, normal TEO predictions based on timers are no good and better to stay
> shallower anyway.
> 
> Note that due to NOHZ, if we go to idle for an extended period the util value
> might not decay for a while and miss some opportunities. Especially that when
> it next wakes up, it's enough for this wake up to run for few 100s us to block
> a deeper state before going back to sleep for extended period of time.
> 
> But we shall see. I got the answer I was looking for for now.

Unfortunately not too long after the patches got merged I got regression report
of worse power. As you know on Android things are not as mainline, so I need to
untangle this to make sure it's not a red herring. But if you want to take my
word for it, I think the chances of it being a true regression is high. I had
to introduce knobs to allow controlling the thresholds for now, so the good
news they do help and it's not a total revert. I don't have a lot of info to
share, but it's the low activity use cases that seem to got impacted. Like
video playback for instance.

Generally, I'm trying to remove some hardcoded values from the scheduler that
enforces a behavior that is not universally desired on all systems/workloads.
And I think the way the util awareness threshold are done today fall into the
same category.

As I tried to highlight before, it is easy to trick the threshold by a task
that runs for a short time then goes back to sleep for a long time.

And when the system runs full throttle for a while, it'll take around 150+ms
for the util to decay to the threshold value. That's a long time to block
entering deeper idle states for. I'm not sure how NOHZ and blocked averaged
updates can make this potentially worse.

In my view, the absolute comparison against util can be misleading. Even when
util is 512 for example, we still have 50% of idle time. How this time is
distributed can't be known from util alone. It could be one task waking up and
sleeping. It could be multiple tasks at many combination of patterns all
leading to the same outcome of CPU util being 512.

IIUC the idea is that if we have even small activity, then erring on the
shallow side is better. But given that target-residency is usually in few ms
range, do we really need to be that quite? With a target-residency of 3ms for
example, even at util of 900 there can be opportunities to enter it.

Can't we instead sample util at entry to idle loop and see if it is on a rising
or falling trend? When rising it makes sense to say there's demand, let's block
deeper idle state. But if it is falling, then if the decay time is longer than
target-residency we can say it's okay to permit the deeper idle states?

I need to think more about this; but I think it's worth trying to make these
thresholds more deterministic and quantifiable. There are too many workloads
and system variations. I'm not sure if a knob to control these thresholds is
good for anything but a workaround like I had to do. These hardcoded values
can be improved IMHO. Happy to help to find alternatives.


Cheers

--
Qais Yousef
  

Hi,

On Sun, Sep 17, 2023 at 02:05:16AM +0100, Qais Yousef wrote:
> Hi Kajetan
> 
> On 07/18/23 14:24, Qais Yousef wrote:
> 
> > These patches are in GKI. So we'll if there are uncaught problems I guess :)
> > 
> > No appetite for a knob, but the very low value for littles did strike me and
> > thought I better ask at least. Today's littles are too tiny for their own good
> > and it seemed the threshold could end up being too aggressive especially in low
> > activity state. You effectively are saying that if we have few 100us of
> > activity, normal TEO predictions based on timers are no good and better to stay
> > shallower anyway.
> > 
> > Note that due to NOHZ, if we go to idle for an extended period the util value
> > might not decay for a while and miss some opportunities. Especially that when
> > it next wakes up, it's enough for this wake up to run for few 100s us to block
> > a deeper state before going back to sleep for extended period of time.
> > 
> > But we shall see. I got the answer I was looking for for now.
> 
> Unfortunately not too long after the patches got merged I got regression report
> of worse power. As you know on Android things are not as mainline, so I need to
> untangle this to make sure it's not a red herring. But if you want to take my
> word for it, I think the chances of it being a true regression is high. I had
> to introduce knobs to allow controlling the thresholds for now, so the good
> news they do help and it's not a total revert. I don't have a lot of info to
> share, but it's the low activity use cases that seem to got impacted. Like
> video playback for instance.

Ah that's pretty unfortunate indeed. I definitely see how that could
happen, especially given that as you said it seems to be tied to
low activity use cases. When I was testing it out with UI benchmarks
(e.g. jankbench) the power numbers usually came out better. I suppose
video playback could be falling just over the currently set threshold
where it does not benefit from it in the same way as other workloads.

> Generally, I'm trying to remove some hardcoded values from the scheduler that
> enforces a behavior that is not universally desired on all systems/workloads.
> And I think the way the util awareness threshold are done today fall into the
> same category.
> 
> As I tried to highlight before, it is easy to trick the threshold by a task
> that runs for a short time then goes back to sleep for a long time.

I do agree, the way I view this topic is just that using util as a proxy
for idle correctness gives us another dimension that cpuidle otherwise
does not have. I'm not very invested in the hardcoded threshold, it was
giving reasonable results in my testing so I stuck with it to not
overcomplicate the patchset but I see it more as "step 1" rather than
the end goal. There's definitely improvements to be had there and a
better way to do this, I'm just not sure what it is at the moment.

> And when the system runs full throttle for a while, it'll take around 150+ms
> for the util to decay to the threshold value. That's a long time to block
> entering deeper idle states for. I'm not sure how NOHZ and blocked averaged
> updates can make this potentially worse.
> 
> In my view, the absolute comparison against util can be misleading. Even when
> util is 512 for example, we still have 50% of idle time. How this time is
> distributed can't be known from util alone. It could be one task waking up and
> sleeping. It could be multiple tasks at many combination of patterns all
> leading to the same outcome of CPU util being 512.

> IIUC the idea is that if we have even small activity, then erring on the
> shallow side is better. But given that target-residency is usually in few ms
> range, do we really need to be that quite? With a target-residency of 3ms for
> example, even at util of 900 there can be opportunities to enter it.
 
It could be misleading, the question then is which scenario happens more
often - the one where we have enough time for deeper idle but are
missing it because of the util or the one where the wakeups are erratic
enough that the util check saves us from incorrectly entering deep idle.
In most workloads I saw it was the latter hence the improvements but I
imagine the actual answer is very workload dependent so I'm not very
surprised that some cases go the other way.

> Can't we instead sample util at entry to idle loop and see if it is on a rising
> or falling trend? When rising it makes sense to say there's demand, let's block
> deeper idle state. But if it is falling, then if the decay time is longer than
> target-residency we can say it's okay to permit the deeper idle states?

Sounds like a pretty good idea to explore - I've not tried it myself at
this point so I have no idea how it'd work in practice but at least
conceptually this could make sense imo.

> I need to think more about this; but I think it's worth trying to make these
> thresholds more deterministic and quantifiable. There are too many workloads
> and system variations. I'm not sure if a knob to control these thresholds is
> good for anything but a workaround like I had to do. These hardcoded values
> can be improved IMHO. Happy to help to find alternatives.

Yes very much agreed on this part, they definitely can be improved. I'm
currently exploring some other approaches to this issue as well but
that's more of a long-term thing so it'll likely take a couple of months
to see whether they're workable or not.

The role I think the util bits are supposed to play here is mainly to
give us a view from a bit higher up than the metrics themselves do
because of how quickly those decay. Another way to do it would be some
way to make the threshold self-adjusting in the same way the metrics
are, e.g. increase the threshold if we're suddenly hitting too many too
shallow sleeps and decrease when we're hitting too many deep sleeps as a
result of the util checks. This would take care of the edge cases
currently falling through the cracks of their util being right around the
threshold, the mechanism would adjust within a few seconds of a workload
like video playback running. Could be a step in the right direction at least.

> 
> Cheers
> 
> --
> Qais Yousef
  

On 09/18/23 12:41, Kajetan Puchalski wrote:

> Yes very much agreed on this part, they definitely can be improved. I'm
> currently exploring some other approaches to this issue as well but
> that's more of a long-term thing so it'll likely take a couple of months
> to see whether they're workable or not.

Sounds good :)

> The role I think the util bits are supposed to play here is mainly to
> give us a view from a bit higher up than the metrics themselves do
> because of how quickly those decay. Another way to do it would be some
> way to make the threshold self-adjusting in the same way the metrics
> are, e.g. increase the threshold if we're suddenly hitting too many too
> shallow sleeps and decrease when we're hitting too many deep sleeps as a
> result of the util checks. This would take care of the edge cases
> currently falling through the cracks of their util being right around the
> threshold, the mechanism would adjust within a few seconds of a workload
> like video playback running. Could be a step in the right direction at least.

I'm not keen on the 'too many' part personally. It does feel finger in the air
to me. But maybe it can work.

Beside timers, tasks wake up on synchronization mechanisms and IPC, we can
potentially gather more info from there. For example, if a task is blocked on
a kernel lock, then chances its in kernel contention and it supposed to wake up
soon for the kernel to finish servicing the operation (ie: finish the syscall
and return to user mode).

Android has the notion of cpus being in deeper idle states in EAS. I think we
could benefit from such thing in upstream too. Not all idle cpus are equal when
idle states are taken into account, for both power and latency reasons. So
there's room to improve on the wake up side to help keep CPUs in deeper idle
states too.

Load balancer state can give indications too. It'll try to spread to idle CPUs
first. Its activity is a good indication on the demand for an idle CPU to be
ready to run something soon.

Generally maybe scheduler and idle governor can coordinate better to
provide/request some low latency idle CPUs, but allow the rest to go into
deeper idle states, per TEO's rule of course.

On HMP systems this will be trickier for us as not all CPUs are equal. And
cluster idle can complicate things further. So the nomination of a low latency
CPU needs to consider more things into account compared to other systems
(except NUMA maybe) where any idle CPU is as good as any other.


Thanks!

--
Qais Yousef