[PATCH] Add decaying history logic to cpuidle menu idle predictor

[PATCH] Add decaying history logic to cpuidle menu idle predictor

[Pallipadi, Venkatesh]

Add decaying history of predicted idle time, instead of using the last early
wakeup. This logic helps menu governor do better job of predicting idle time.

With this change, we also measured noticable (~8%) power savings on
a DP server system with CPUs supporting deep C states, when system
was lightly loaded. There was no change to power or perf on other load
conditions.

Signed-off-by: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>

---
 drivers/cpuidle/governors/menu.c |   10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

Index: linux-2.6/drivers/cpuidle/governors/menu.c
===================================================================
--- linux-2.6.orig/drivers/cpuidle/governors/menu.c	2008-11-10 15:27:13.000000000 -0800
+++ linux-2.6/drivers/cpuidle/governors/menu.c	2008-12-30 14:39:15.000000000 -0800
@@ -15,12 +15,14 @@
 #include <linux/tick.h>
 
 #define BREAK_FUZZ	4	/* 4 us */
+#define PRED_HISTORY_PCT	50
 
 struct menu_device {
 	int		last_state_idx;
 
 	unsigned int	expected_us;
 	unsigned int	predicted_us;
+	unsigned int    current_predicted_us;
 	unsigned int	last_measured_us;
 	unsigned int	elapsed_us;
 };
@@ -47,6 +49,12 @@ static int menu_select(struct cpuidle_de
 	data->expected_us =
 		(u32) ktime_to_ns(tick_nohz_get_sleep_length()) / 1000;
 
+	/* Recalculate predicted_us based on prediction_history_pct */
+	data->predicted_us *= PRED_HISTORY_PCT;
+	data->predicted_us += (100 - PRED_HISTORY_PCT) *
+				data->current_predicted_us;
+	data->predicted_us /= 100;
+
 	/* find the deepest idle state that satisfies our constraints */
 	for (i = CPUIDLE_DRIVER_STATE_START + 1; i < dev->state_count; i++) {
 		struct cpuidle_state *s = &dev->states[i];
@@ -97,7 +105,7 @@ static void menu_reflect(struct cpuidle_
 		measured_us = -1;
 
 	/* Predict time until next break event */
-	data->predicted_us = max(measured_us, data->last_measured_us);
+	data->current_predicted_us = max(measured_us, data->last_measured_us);
 
 	if (last_idle_us + BREAK_FUZZ <
 	    data->expected_us - target->exit_latency) {

Re: [PATCH] Add decaying history logic to cpuidle menu idle predictor

[Len Brown]

applied

-- Len Brown, Intel Open Source Technology Center

On Tue, 30 Dec 2008, Pallipadi, Venkatesh wrote:

> 
> Add decaying history of predicted idle time, instead of using the last early
> wakeup. This logic helps menu governor do better job of predicting idle time.
> 
> With this change, we also measured noticable (~8%) power savings on
> a DP server system with CPUs supporting deep C states, when system
> was lightly loaded. There was no change to power or perf on other load
> conditions.
> 
> Signed-off-by: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>
> 
> ---
>  drivers/cpuidle/governors/menu.c |   10 +++++++++-
>  1 file changed, 9 insertions(+), 1 deletion(-)
> 
> Index: linux-2.6/drivers/cpuidle/governors/menu.c
> ===================================================================
> --- linux-2.6.orig/drivers/cpuidle/governors/menu.c	2008-11-10 15:27:13.000000000 -0800
> +++ linux-2.6/drivers/cpuidle/governors/menu.c	2008-12-30 14:39:15.000000000 -0800
> @@ -15,12 +15,14 @@
>  #include <linux/tick.h>
>  
>  #define BREAK_FUZZ	4	/* 4 us */
> +#define PRED_HISTORY_PCT	50
>  
>  struct menu_device {
>  	int		last_state_idx;
>  
>  	unsigned int	expected_us;
>  	unsigned int	predicted_us;
> +	unsigned int    current_predicted_us;
>  	unsigned int	last_measured_us;
>  	unsigned int	elapsed_us;
>  };
> @@ -47,6 +49,12 @@ static int menu_select(struct cpuidle_de
>  	data->expected_us =
>  		(u32) ktime_to_ns(tick_nohz_get_sleep_length()) / 1000;
>  
> +	/* Recalculate predicted_us based on prediction_history_pct */
> +	data->predicted_us *= PRED_HISTORY_PCT;
> +	data->predicted_us += (100 - PRED_HISTORY_PCT) *
> +				data->current_predicted_us;
> +	data->predicted_us /= 100;
> +
>  	/* find the deepest idle state that satisfies our constraints */
>  	for (i = CPUIDLE_DRIVER_STATE_START + 1; i < dev->state_count; i++) {
>  		struct cpuidle_state *s = &dev->states[i];
> @@ -97,7 +105,7 @@ static void menu_reflect(struct cpuidle_
>  		measured_us = -1;
>  
>  	/* Predict time until next break event */
> -	data->predicted_us = max(measured_us, data->last_measured_us);
> +	data->current_predicted_us = max(measured_us, data->last_measured_us);
>  
>  	if (last_idle_us + BREAK_FUZZ <
>  	    data->expected_us - target->exit_latency) {
> --
> To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH] Add decaying history logic to cpuidle menu idle predictor

[Zhao Yakui]

On Wed, 2008-12-31 at 06:46 +0800, Pallipadi, Venkatesh wrote:
> Add decaying history of predicted idle time, instead of using the last early
> wakeup. This logic helps menu governor do better job of predicting idle time.
> 
> With this change, we also measured noticable (~8%) power savings on
> a DP server system with CPUs supporting deep C states, when system
> was lightly loaded. There was no change to power or perf on other load
> conditions.
> 
> Signed-off-by: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>
> 
> ---
>  drivers/cpuidle/governors/menu.c |   10 +++++++++-
>  1 file changed, 9 insertions(+), 1 deletion(-)
> 
> Index: linux-2.6/drivers/cpuidle/governors/menu.c
> ===================================================================
> --- linux-2.6.orig/drivers/cpuidle/governors/menu.c	2008-11-10 15:27:13.000000000 -0800
> +++ linux-2.6/drivers/cpuidle/governors/menu.c	2008-12-30 14:39:15.000000000 -0800
> @@ -15,12 +15,14 @@
>  #include <linux/tick.h>
>  
>  #define BREAK_FUZZ	4	/* 4 us */
> +#define PRED_HISTORY_PCT	50
Hi, Venki
   It seems that the history factor is fixed to 50%. 
   How about adding an interface to change the history factor?

Thanks.
>  
>  struct menu_device {
>  	int		last_state_idx;
>  
>  	unsigned int	expected_us;
>  	unsigned int	predicted_us;
> +	unsigned int    current_predicted_us;
>  	unsigned int	last_measured_us;
>  	unsigned int	elapsed_us;
>  };
> @@ -47,6 +49,12 @@ static int menu_select(struct cpuidle_de
>  	data->expected_us =
>  		(u32) ktime_to_ns(tick_nohz_get_sleep_length()) / 1000;
>  
> +	/* Recalculate predicted_us based on prediction_history_pct */
> +	data->predicted_us *= PRED_HISTORY_PCT;
> +	data->predicted_us += (100 - PRED_HISTORY_PCT) *
> +				data->current_predicted_us;
> +	data->predicted_us /= 100;
> +
>  	/* find the deepest idle state that satisfies our constraints */
>  	for (i = CPUIDLE_DRIVER_STATE_START + 1; i < dev->state_count; i++) {
>  		struct cpuidle_state *s = &dev->states[i];
> @@ -97,7 +105,7 @@ static void menu_reflect(struct cpuidle_
>  		measured_us = -1;
>  
>  	/* Predict time until next break event */
> -	data->predicted_us = max(measured_us, data->last_measured_us);
> +	data->current_predicted_us = max(measured_us, data->last_measured_us);
>  
>  	if (last_idle_us + BREAK_FUZZ <
>  	    data->expected_us - target->exit_latency) {

RE: [PATCH] Add decaying history logic to cpuidle menu idle predictor

[Pallipadi, Venkatesh]

>-----Original Message-----
>From: Zhao, Yakui 
>Sent: Tuesday, December 30, 2008 5:28 PM
>To: Pallipadi, Venkatesh
>Cc: Len Brown; linux-acpi@vger.kernel.org
>Subject: Re: [PATCH] Add decaying history logic to cpuidle 
>menu idle predictor
>
>On Wed, 2008-12-31 at 06:46 +0800, Pallipadi, Venkatesh wrote:
>> Add decaying history of predicted idle time, instead of 
>using the last early
>> wakeup. This logic helps menu governor do better job of 
>predicting idle time.
>> 
>> With this change, we also measured noticable (~8%) power savings on
>> a DP server system with CPUs supporting deep C states, when system
>> was lightly loaded. There was no change to power or perf on 
>other load
>> conditions.
>> 
>> Signed-off-by: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>
>> 
>> ---
>>  drivers/cpuidle/governors/menu.c |   10 +++++++++-
>>  1 file changed, 9 insertions(+), 1 deletion(-)
>> 
>> Index: linux-2.6/drivers/cpuidle/governors/menu.c
>> ===================================================================
>> --- linux-2.6.orig/drivers/cpuidle/governors/menu.c	
>2008-11-10 15:27:13.000000000 -0800
>> +++ linux-2.6/drivers/cpuidle/governors/menu.c	
>2008-12-30 14:39:15.000000000 -0800
>> @@ -15,12 +15,14 @@
>>  #include <linux/tick.h>
>>  
>>  #define BREAK_FUZZ	4	/* 4 us */
>> +#define PRED_HISTORY_PCT	50
>Hi, Venki
>   It seems that the history factor is fixed to 50%. 
>   How about adding an interface to change the history factor?
>

Yakui,

50% seems to be reasonable default across all platforms we have checked. We still
have to get some more data to see 25% works better on all platforms.

I considered adding a boot parameter or /sysfs tunable for this. Even though
such options are good for developers, most of the time, any option like that
will get misused at the end user/distro level.

So, this is the simple patch that helps in most cases. Going forward, we have
options like
1 One single constant factor for all platforms
2 Different factor for different platforms, based on CPU type (HT, multi-core, etc)
3 History factor that varies over time, based on right or wrong predictions

My gut feeling is that we may end up with 3 in future. But, I wanted to get the
basic code in now with options to optimize in future.

Thanks,
Venki

RE: [PATCH] Add decaying history logic to cpuidle menu idle predictor

[Len Brown]

On Wed, 31 Dec 2008, Pallipadi, Venkatesh wrote:

> 
> >-----Original Message-----
> >From: Zhao, Yakui 
> >Sent: Tuesday, December 30, 2008 5:28 PM
> >To: Pallipadi, Venkatesh
> >Cc: Len Brown; linux-acpi@vger.kernel.org
> >Subject: Re: [PATCH] Add decaying history logic to cpuidle 
> >menu idle predictor
> >
> >On Wed, 2008-12-31 at 06:46 +0800, Pallipadi, Venkatesh wrote:
> >> Add decaying history of predicted idle time, instead of 
> >using the last early
> >> wakeup. This logic helps menu governor do better job of 
> >predicting idle time.
> >> 
> >> With this change, we also measured noticable (~8%) power savings on
> >> a DP server system with CPUs supporting deep C states, when system
> >> was lightly loaded. There was no change to power or perf on 
> >other load
> >> conditions.
> >> 
> >> Signed-off-by: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com>
> >> 
> >> ---
> >>  drivers/cpuidle/governors/menu.c |   10 +++++++++-
> >>  1 file changed, 9 insertions(+), 1 deletion(-)
> >> 
> >> Index: linux-2.6/drivers/cpuidle/governors/menu.c
> >> ===================================================================
> >> --- linux-2.6.orig/drivers/cpuidle/governors/menu.c	
> >2008-11-10 15:27:13.000000000 -0800
> >> +++ linux-2.6/drivers/cpuidle/governors/menu.c	
> >2008-12-30 14:39:15.000000000 -0800
> >> @@ -15,12 +15,14 @@
> >>  #include <linux/tick.h>
> >>  
> >>  #define BREAK_FUZZ	4	/* 4 us */
> >> +#define PRED_HISTORY_PCT	50
> >Hi, Venki
> >   It seems that the history factor is fixed to 50%. 
> >   How about adding an interface to change the history factor?
> >
> 
> Yakui,
> 
> 50% seems to be reasonable default across all platforms we have checked. We still
> have to get some more data to see 25% works better on all platforms.
> 
> I considered adding a boot parameter or /sysfs tunable for this. Even though
> such options are good for developers, most of the time, any option like that
> will get misused at the end user/distro level.
> 
> So, this is the simple patch that helps in most cases. Going forward, we have
> options like
> 1 One single constant factor for all platforms
> 2 Different factor for different platforms, based on CPU type (HT, multi-core, etc)
> 3 History factor that varies over time, based on right or wrong predictions
> 
> My gut feeling is that we may end up with 3 in future. But, I wanted to get the
> basic code in now with options to optimize in future.

Agreed.
While I can see it would be possible for this to be platform dependent,
I would think that the difference between workloads would be
an even larger factor.

So far, the code reflects all of the measurements we've done,
so that is the best we can do at this point.

-- Len Brown, Intel Open Source Technology Center