Re: [PATCH 1/2] cpuidle : auto-promotion for cpuidle states

[Abhishek]

On 04/04/2019 03:51 PM, Daniel Lezcano wrote:

Hi Abhishek,

thanks for taking the time to test the different scenario and give us
the numbers.

On 01/04/2019 07:11, Abhishek wrote:


On 03/22/2019 06:56 PM, Daniel Lezcano wrote:

On 22/03/2019 10:45, Rafael J. Wysocki wrote:

On Fri, Mar 22, 2019 at 8:31 AM Abhishek Goel
 wrote:

Currently, the cpuidle governors (menu /ladder) determine what idle
state
an idling CPU should enter into based on heuristics that depend on the
idle history on that CPU. Given that no predictive heuristic is
perfect,
there are cases where the governor predicts a shallow idle state,
hoping
that the CPU will be busy soon. However, if no new workload is
scheduled
on that CPU in the near future, the CPU will end up in the shallow
state.

In case of POWER, this is problematic, when the predicted state in the
aforementioned scenario is a lite stop state, as such lite states will
inhibit SMT folding, thereby depriving the other threads in the core
from
using the core resources.

I can understand an idle state can prevent other threads to use the core
resources. But why a deeper idle state does not prevent this also?



To address this, such lite states need to be autopromoted. The cpuidle-
core can queue timer to correspond with the residency value of the next
available state. Thus leading to auto-promotion to a deeper idle
state as
soon as possible.

Isn't the tick stopping avoidance sufficient for that?

I was about to ask the same :)





Thanks for the review.
I performed experiments for three scenarios to collect some data.

case 1 :
Without this patch and without tick retained, i.e. in a upstream kernel,
It would spend more than even a second to get out of stop0_lite.

case 2 : With tick retained(as suggested) -

Generally, we have a sched tick at 4ms(CONF_HZ = 250). Ideally I expected
it to take 8 sched tick to get out of stop0_lite. Experimentally,
observation was

===
min            max            99percentile
4ms            12ms          4ms
===
*ms = milliseconds

It would take atleast one sched tick to get out of stop0_lite.

case 2 :  With this patch (not stopping tick, but explicitly queuing a
timer)

min            max              99.5percentile
===
144us       192us              144us
===
*us = microseconds

In this patch, we queue a timer just before entering into a stop0_lite
state. The timer fires at (residency of next available state + exit
latency of next available state * 2).

So for the context, we have a similar issue but from the power
management point of view where a CPU can stay in a shallow state for a
long period, thus consuming a lot of energy.

The window was reduced by preventing stopping the tick when a shallow
state is selected. Unfortunately, if the tick is stopped and we
exit/enter again and we select a shallow state, the situation is the same.

A solution was previously proposed with a timer some years ago, like
this patch does, and merged but there were complains about bad
performance impact, so it has been reverted.


Let's say if next state(stop0) is available which has residency of 20us, it
should get out in as low as (20+2*2)*8 [Based on the forumla (residency +
2xlatency)*history length] microseconds = 192us. Ideally we would expect 8
iterations, it was observed to get out in 6-7 iterations.

Can you explain the formula? I don't get the rational. Why using the
exit latency and why multiply it by 2?

Why the timer is not set to the next state's target residency value ?

The idea behind multiplying by 2 is, entry latency + exit latency = 2* 
exit latency, i.e.,

using exit latency = entry latency
So in effect, we are using target residency + 2 * exit latency for 
timeout of timer.
Latency is generally <=10% of residency. I have tried to be conservative 
by including latency
factor in computation for timeout. Thus, this formula will give slightly 
greater value compared

to directly using residency of target state.

--Abhishek

Re: [PATCH 1/2] cpuidle : auto-promotion for cpuidle states

[Gautham R Shenoy]

Hello Daniel,

On Thu, Apr 4, 2019 at 3:52 PM Daniel Lezcano  wrote:
>
>
> Hi Abhishek,
>
> thanks for taking the time to test the different scenario and give us
> the numbers.
>
> On 01/04/2019 07:11, Abhishek wrote:
> >

[.. snip..]

>
>  In case of POWER, this is problematic, when the predicted state in the
>  aforementioned scenario is a lite stop state, as such lite states will
>  inhibit SMT folding, thereby depriving the other threads in the core
>  from
>  using the core resources.
>
> I can understand an idle state can prevent other threads to use the core
> resources. But why a deeper idle state does not prevent this also?

On POWER9, we have the following classes of platform idle states
(called stop states)

lite: These do not lose any context including the user context. In
this state
   GPRs are also preserved (stop0_lite)

shallow : These lose user context,but not the hypervisor context. So
GPRs are lost but
   not SPRs. (stop0, stop1, stop2)

deep: These lose hypervisor context. (stop4, stop5)

In the case of lite stop state, only instruction dispatch on the CPU thread
is paused. The thread does not  give up its registers set in this state for the
use of its busy sibling threads in the core.  Hence, SMT folding does not
happen in this state.

With respect to shallow and deep states, not only is the instruction dispatch
paused, it also gives up its registers set for the other siblings to use
These stop states are beneficial for SMT folding.

Hence, if a CPU thread remains in a lite state for too long,
its siblings in the core would not be able to utilize the full resources
of the core for that duration, thereby inhibiting single
thread performance. This is not the case with non-lite states.

-- 
Thanks and Regards
gautham.

Re: [PATCH 1/2] cpuidle : auto-promotion for cpuidle states

[Daniel Lezcano]

Hi Abhishek,

thanks for taking the time to test the different scenario and give us
the numbers.

On 01/04/2019 07:11, Abhishek wrote:
> 
> 
> On 03/22/2019 06:56 PM, Daniel Lezcano wrote:
>> On 22/03/2019 10:45, Rafael J. Wysocki wrote:
>>> On Fri, Mar 22, 2019 at 8:31 AM Abhishek Goel
>>>  wrote:
 Currently, the cpuidle governors (menu /ladder) determine what idle
 state
 an idling CPU should enter into based on heuristics that depend on the
 idle history on that CPU. Given that no predictive heuristic is
 perfect,
 there are cases where the governor predicts a shallow idle state,
 hoping
 that the CPU will be busy soon. However, if no new workload is
 scheduled
 on that CPU in the near future, the CPU will end up in the shallow
 state.

 In case of POWER, this is problematic, when the predicted state in the
 aforementioned scenario is a lite stop state, as such lite states will
 inhibit SMT folding, thereby depriving the other threads in the core
 from
 using the core resources.

I can understand an idle state can prevent other threads to use the core
resources. But why a deeper idle state does not prevent this also?


 To address this, such lite states need to be autopromoted. The cpuidle-
 core can queue timer to correspond with the residency value of the next
 available state. Thus leading to auto-promotion to a deeper idle
 state as
 soon as possible.
>>> Isn't the tick stopping avoidance sufficient for that?
>> I was about to ask the same :)
>>
>>
>>
>>
> Thanks for the review.
> I performed experiments for three scenarios to collect some data.
> 
> case 1 :
> Without this patch and without tick retained, i.e. in a upstream kernel,
> It would spend more than even a second to get out of stop0_lite.
> 
> case 2 : With tick retained(as suggested) -
> 
> Generally, we have a sched tick at 4ms(CONF_HZ = 250). Ideally I expected
> it to take 8 sched tick to get out of stop0_lite. Experimentally,
> observation was
> 
> ===
> min            max            99percentile
> 4ms            12ms          4ms
> ===
> *ms = milliseconds
> 
> It would take atleast one sched tick to get out of stop0_lite.
> 
> case 2 :  With this patch (not stopping tick, but explicitly queuing a
> timer)
> 
> min            max              99.5percentile
> ===
> 144us       192us              144us
> ===
> *us = microseconds
> 
> In this patch, we queue a timer just before entering into a stop0_lite
> state. The timer fires at (residency of next available state + exit
> latency of next available state * 2).

So for the context, we have a similar issue but from the power
management point of view where a CPU can stay in a shallow state for a
long period, thus consuming a lot of energy.

The window was reduced by preventing stopping the tick when a shallow
state is selected. Unfortunately, if the tick is stopped and we
exit/enter again and we select a shallow state, the situation is the same.

A solution was previously proposed with a timer some years ago, like
this patch does, and merged but there were complains about bad
performance impact, so it has been reverted.

> Let's say if next state(stop0) is available which has residency of 20us, it
> should get out in as low as (20+2*2)*8 [Based on the forumla (residency +
> 2xlatency)*history length] microseconds = 192us. Ideally we would expect 8
> iterations, it was observed to get out in 6-7 iterations.

Can you explain the formula? I don't get the rational. Why using the
exit latency and why multiply it by 2?

Why the timer is not set to the next state's target residency value ?

> Even if let's say stop2 is next available state(stop0 and stop1 both are
> unavailable), it would take (100+2*10)*8 = 960us to get into stop2.
> 
> So, We are able to get out of stop0_lite generally in 150us(with this
> patch) as
> compared to 4ms(with tick retained). As stated earlier, we do not want
> to get
> stuck into stop0_lite as it inhibits SMT folding for other sibling
> threads, depriving
> them of core resources. Current patch is using auto-promotion only for
> stop0_lite,
> as it gives performance benefit(primary reason) along with lowering down
> power
> consumption. We may extend this model for other states in future.
> 
> --Abhishek
> 


-- 
  Linaro.org │ Open source software for ARM SoCs

Follow Linaro:   Facebook |
 Twitter |
 Blog

Re: [PATCH 1/2] cpuidle : auto-promotion for cpuidle states

[Abhishek]

On 03/22/2019 06:56 PM, Daniel Lezcano wrote:

On 22/03/2019 10:45, Rafael J. Wysocki wrote:

On Fri, Mar 22, 2019 at 8:31 AM Abhishek Goel
 wrote:

Currently, the cpuidle governors (menu /ladder) determine what idle state
an idling CPU should enter into based on heuristics that depend on the
idle history on that CPU. Given that no predictive heuristic is perfect,
there are cases where the governor predicts a shallow idle state, hoping
that the CPU will be busy soon. However, if no new workload is scheduled
on that CPU in the near future, the CPU will end up in the shallow state.

In case of POWER, this is problematic, when the predicted state in the
aforementioned scenario is a lite stop state, as such lite states will
inhibit SMT folding, thereby depriving the other threads in the core from
using the core resources.

To address this, such lite states need to be autopromoted. The cpuidle-
core can queue timer to correspond with the residency value of the next
available state. Thus leading to auto-promotion to a deeper idle state as
soon as possible.

Isn't the tick stopping avoidance sufficient for that?

I was about to ask the same :)





Thanks for the review.
I performed experiments for three scenarios to collect some data.

case 1 :
Without this patch and without tick retained, i.e. in a upstream kernel,
It would spend more than even a second to get out of stop0_lite.

case 2 : With tick retained(as suggested) -

Generally, we have a sched tick at 4ms(CONF_HZ = 250). Ideally I expected
it to take 8 sched tick to get out of stop0_lite. Experimentally, 
observation was


===
min            max            99percentile
4ms            12ms          4ms
===
*ms = milliseconds

It would take atleast one sched tick to get out of stop0_lite.

case 2 :  With this patch (not stopping tick, but explicitly queuing a 
timer)


min            max              99.5percentile
===
144us       192us              144us
===
*us = microseconds

In this patch, we queue a timer just before entering into a stop0_lite
state. The timer fires at (residency of next available state + exit
latency of next available state * 2).
Let's say if next state(stop0) is available which has residency of 20us, it
should get out in as low as (20+2*2)*8 [Based on the forumla (residency +
2xlatency)*history length] microseconds = 192us. Ideally we would expect 8
iterations, it was observed to get out in 6-7 iterations.
Even if let's say stop2 is next available state(stop0 and stop1 both are
unavailable), it would take (100+2*10)*8 = 960us to get into stop2.

So, We are able to get out of stop0_lite generally in 150us(with this 
patch) as
compared to 4ms(with tick retained). As stated earlier, we do not want 
to get
stuck into stop0_lite as it inhibits SMT folding for other sibling 
threads, depriving
them of core resources. Current patch is using auto-promotion only for 
stop0_lite,
as it gives performance benefit(primary reason) along with lowering down 
power

consumption. We may extend this model for other states in future.

--Abhishek

Re: [PATCH 1/2] cpuidle : auto-promotion for cpuidle states

[Daniel Lezcano]

On 22/03/2019 10:45, Rafael J. Wysocki wrote:
> On Fri, Mar 22, 2019 at 8:31 AM Abhishek Goel
>  wrote:
>>
>> Currently, the cpuidle governors (menu /ladder) determine what idle state
>> an idling CPU should enter into based on heuristics that depend on the
>> idle history on that CPU. Given that no predictive heuristic is perfect,
>> there are cases where the governor predicts a shallow idle state, hoping
>> that the CPU will be busy soon. However, if no new workload is scheduled
>> on that CPU in the near future, the CPU will end up in the shallow state.
>>
>> In case of POWER, this is problematic, when the predicted state in the
>> aforementioned scenario is a lite stop state, as such lite states will
>> inhibit SMT folding, thereby depriving the other threads in the core from
>> using the core resources.
>>
>> To address this, such lite states need to be autopromoted. The cpuidle-
>> core can queue timer to correspond with the residency value of the next
>> available state. Thus leading to auto-promotion to a deeper idle state as
>> soon as possible.
> 
> Isn't the tick stopping avoidance sufficient for that?

I was about to ask the same :)




-- 
  Linaro.org │ Open source software for ARM SoCs

Follow Linaro:   Facebook |
 Twitter |
 Blog

Re: [PATCH 1/2] cpuidle : auto-promotion for cpuidle states

[Rafael J. Wysocki]

On Fri, Mar 22, 2019 at 8:31 AM Abhishek Goel
 wrote:
>
> Currently, the cpuidle governors (menu /ladder) determine what idle state
> an idling CPU should enter into based on heuristics that depend on the
> idle history on that CPU. Given that no predictive heuristic is perfect,
> there are cases where the governor predicts a shallow idle state, hoping
> that the CPU will be busy soon. However, if no new workload is scheduled
> on that CPU in the near future, the CPU will end up in the shallow state.
>
> In case of POWER, this is problematic, when the predicted state in the
> aforementioned scenario is a lite stop state, as such lite states will
> inhibit SMT folding, thereby depriving the other threads in the core from
> using the core resources.
>
> To address this, such lite states need to be autopromoted. The cpuidle-
> core can queue timer to correspond with the residency value of the next
> available state. Thus leading to auto-promotion to a deeper idle state as
> soon as possible.

Isn't the tick stopping avoidance sufficient for that?

[PATCH 1/2] cpuidle : auto-promotion for cpuidle states

[Abhishek Goel]

Currently, the cpuidle governors (menu /ladder) determine what idle state
an idling CPU should enter into based on heuristics that depend on the
idle history on that CPU. Given that no predictive heuristic is perfect,
there are cases where the governor predicts a shallow idle state, hoping
that the CPU will be busy soon. However, if no new workload is scheduled
on that CPU in the near future, the CPU will end up in the shallow state.

In case of POWER, this is problematic, when the predicted state in the
aforementioned scenario is a lite stop state, as such lite states will
inhibit SMT folding, thereby depriving the other threads in the core from
using the core resources.

To address this, such lite states need to be autopromoted. The cpuidle-
core can queue timer to correspond with the residency value of the next
available state. Thus leading to auto-promotion to a deeper idle state as
soon as possible.

Signed-off-by: Abhishek Goel 
---
 drivers/cpuidle/cpuidle.c  | 79 +-
 drivers/cpuidle/governors/ladder.c |  3 +-
 drivers/cpuidle/governors/menu.c   | 23 -
 include/linux/cpuidle.h| 12 +++--
 4 files changed, 111 insertions(+), 6 deletions(-)

diff --git a/drivers/cpuidle/cpuidle.c b/drivers/cpuidle/cpuidle.c
index 7f108309e..c4d1c1b38 100644
--- a/drivers/cpuidle/cpuidle.c
+++ b/drivers/cpuidle/cpuidle.c
@@ -36,6 +36,12 @@ static int enabled_devices;
 static int off __read_mostly;
 static int initialized __read_mostly;
 
+struct auto_promotion {
+   struct hrtimer  hrtimer;
+   int timeout;
+   booltimeout_needed;
+};
+
 int cpuidle_disabled(void)
 {
return off;
@@ -188,6 +194,64 @@ int cpuidle_enter_s2idle(struct cpuidle_driver *drv, 
struct cpuidle_device *dev)
 }
 #endif /* CONFIG_SUSPEND */
 
+enum hrtimer_restart auto_promotion_hrtimer_callback(struct hrtimer *hrtimer)
+{
+   return HRTIMER_NORESTART;
+}
+
+#ifdef CONFIG_CPU_IDLE_AUTO_PROMOTION
+DEFINE_PER_CPU(struct auto_promotion, ap);
+
+static void cpuidle_auto_promotion_start(struct cpuidle_state *state, int cpu)
+{
+   struct auto_promotion *this_ap = &per_cpu(ap, cpu);
+
+   if (this_ap->timeout_needed && (state->flags &
+   CPUIDLE_FLAG_AUTO_PROMOTION))
+   hrtimer_start(&this_ap->hrtimer, ns_to_ktime(this_ap->timeout
+   * 1000), HRTIMER_MODE_REL_PINNED);
+}
+
+static void cpuidle_auto_promotion_cancel(int cpu)
+{
+   struct hrtimer *hrtimer;
+
+   hrtimer = &per_cpu(ap, cpu).hrtimer;
+   if (hrtimer_is_queued(hrtimer))
+   hrtimer_cancel(hrtimer);
+}
+
+static void cpuidle_auto_promotion_update(int time, int cpu)
+{
+   per_cpu(ap, cpu).timeout = time;
+}
+
+static void cpuidle_auto_promotion_init(struct cpuidle_driver *drv, int cpu)
+{
+   int i;
+   struct auto_promotion *this_ap = &per_cpu(ap, cpu);
+
+   this_ap->timeout_needed = 0;
+
+   for (i = 0; i < drv->state_count; i++) {
+   if (drv->states[i].flags & CPUIDLE_FLAG_AUTO_PROMOTION) {
+   this_ap->timeout_needed = 1;
+   break;
+   }
+   }
+
+   hrtimer_init(&this_ap->hrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+   this_ap->hrtimer.function = auto_promotion_hrtimer_callback;
+}
+#else
+static inline void cpuidle_auto_promotion_start(struct cpuidle_state *state,
+   int cpu) { }
+static inline void cpuidle_auto_promotion_cancel(int cpu) { }
+static inline void cpuidle_auto_promotion_update(int timeout, int cpu) { }
+static inline void cpuidle_auto_promotion_init(struct cpuidle_driver *drv,
+   int cpu) { }
+#endif
+
 /**
  * cpuidle_enter_state - enter the state and update stats
  * @dev: cpuidle device for this cpu
@@ -225,12 +289,17 @@ int cpuidle_enter_state(struct cpuidle_device *dev, 
struct cpuidle_driver *drv,
trace_cpu_idle_rcuidle(index, dev->cpu);
time_start = ns_to_ktime(local_clock());
 
+   cpuidle_auto_promotion_start(target_state, dev->cpu);
+
stop_critical_timings();
entered_state = target_state->enter(dev, drv, index);
start_critical_timings();
 
sched_clock_idle_wakeup_event();
time_end = ns_to_ktime(local_clock());
+
+   cpuidle_auto_promotion_cancel(dev->cpu);
+
trace_cpu_idle_rcuidle(PWR_EVENT_EXIT, dev->cpu);
 
/* The cpu is no longer idle or about to enter idle. */
@@ -312,7 +381,13 @@ int cpuidle_enter_state(struct cpuidle_device *dev, struct 
cpuidle_driver *drv,
 int cpuidle_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
   bool *stop_tick)
 {
-   return cpuidle_curr_governor->select(drv, dev, stop_tick);
+   int timeout, ret;
+
+   timeout = INT_MAX;
+   ret = cpuidle_curr_governor->select(drv, dev, stop_tick, &timeout);
+   cpuidle_au

[PATCH 1/2] cpuidle : auto-promotion for cpuidle states

[Abhishek Goel]

Currently, the cpuidle governors (menu /ladder) determine what idle state
an idling CPU should enter into based on heuristics that depend on the
idle history on that CPU. Given that no predictive heuristic is perfect,
there are cases where the governor predicts a shallow idle state, hoping
that the CPU will be busy soon. However, if no new workload is scheduled
on that CPU in the near future, the CPU will end up in the shallow state.

In case of POWER, this is problematic, when the predicted state in the
aforementioned scenario is a lite stop state, as such lite states will
inhibit SMT folding, thereby depriving the other threads in the core from
using the core resources.

To address this, such lite states need to be autopromoted. The cpuidle-
core can queue timer to correspond with the residency value of the next
available state. Thus leading to auto-promotion to a deeper idle state as
soon as possible.

Signed-off-by: Abhishek Goel 
---
 drivers/cpuidle/cpuidle.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/drivers/cpuidle/cpuidle.c b/drivers/cpuidle/cpuidle.c
index 2406e2655..c4d1c1b38 100644
--- a/drivers/cpuidle/cpuidle.c
+++ b/drivers/cpuidle/cpuidle.c
@@ -584,11 +584,8 @@ static void __cpuidle_unregister_device(struct 
cpuidle_device *dev)
 
 static void __cpuidle_device_init(struct cpuidle_device *dev)
 {
-   int i;
memset(dev->states_usage, 0, sizeof(dev->states_usage));
dev->last_residency = 0;
-   for (i = 0; i < CPUIDLE_STATE_MAX; i++)
-   dev->states_usage[i].disable = true;
 }
 
 /**
-- 
2.17.1