Skip to contentSkip to conversation

Some improvements to the cpuidle menu governor

PATCH In review Arjan van de Ven 3 participants 10 messages May 9, 2010 – May 22, 2010 CPU idle time management framework

lore
Share & tools
lore
#0 lore raw

cover Some improvements to the cpuidle menu governor

Hi,

two patches to the menu governor that, together, boost the quality of the decisions it makes significantly (results below).
The first patch is basically a bugfix, while the second patch adds some smarts to the algorithm.

Both patches only impact the idle-duration predictor (for those unfamiliar with the menu governor, the menu governor first tries to predict the idle duration, and then uses a set of heuristics to pick a suitable idle state based on this prediction. The better the prediction the better the decision ends up being)

To show the quality of the predictor, I added some instrumentation where I had perf report out the result of the current, after patch 1 and after patch 2 prediction value as well as the actual idle duration as measured at the end of the idle period. The test run I give below had 69854 samples (other runs had pretty much the same result).

The quality indicator I use is the percentage of samples for which the prediction is within a certain factor of the actual duration.

Factor         before patches       patch 1          patch 1+2
1.5x            29.1%               30.4%            34.1%
2x              33.6%               49.3%            52.9%
4x              43.6%               73.6%            75.2%
10x             56.9%               86.1%            86.5%
100x            78.4%               97.0%            97.2%
Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#1 lore raw

PATCH 1/2 cpuidle: Fix incorrect optimziation

Quoted 2 lines

From 8fd01c156227a2c14e6c4cf46fc421ee1c8d9946 Mon Sep 17 00:00:00 2001

From: Arjan van de Ven <[email protected]>
Date: Sat, 8 May 2010 15:47:37 -0700
Subject: [PATCH 1/2] cpuidle: Fix incorrect optimziation

commit 672917dcc781ead7652a8b11b1fba14e38ac15b8 added an optimization, where the analysis on the past idle period moved from the end of idle, to the beginning of the new idle.

Unfortunately, this optimization had a bug where it zeroed one key variable for new use, that is needed for the analysis. The fix is simple, zero the variable after doing the work from the previous idle.

During the audit of the code that found this issue, another issue was also found; the ->measured_us data structure member is never set, a local variable is always used instead.

Cc Corrado Zoccolo <[email protected]>
---
 drivers/cpuidle/governors/menu.c |    9 ++++-----
 1 files changed, 4 insertions(+), 5 deletions(-)
drivers/cpuidle/governors/menu.c +4 -5
index 1aea715..f8e57c6 100644
@@ -100,7 +100,6 @@ struct menu_device {
 	int             needs_update;
 
 	unsigned int	expected_us;
-	unsigned int	measured_us;
 	u64		predicted_us;
 	unsigned int	exit_us;
 	unsigned int	bucket;
@@ -187,14 +186,14 @@ static int menu_select(struct cpuidle_device *dev)
 	int i;
 	int multiplier;
 
-	data->last_state_idx = 0;
-	data->exit_us = 0;
-
 	if (data->needs_update) {
 		menu_update(dev);
 		data->needs_update = 0;
 	}
 
+	data->last_state_idx = 0;
+	data->exit_us = 0;
+
 	/* Special case when user has set very strict latency requirement */
 	if (unlikely(latency_req == 0))
 		return 0;
@@ -294,7 +293,7 @@ static void menu_update(struct cpuidle_device *dev)
 	new_factor = data->correction_factor[data->bucket]
 			* (DECAY - 1) / DECAY;
 
-	if (data->expected_us > 0 && data->measured_us < MAX_INTERESTING)
+	if (data->expected_us > 0 && measured_us < MAX_INTERESTING)
 		new_factor += RESOLUTION * measured_us / data->expected_us;
 	else
 		/*
Signature · 7 lines
1.6.2.5


-- 
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#2 lore raw

PATCH 2/2 cpuidle: Add a repeating pattern detector to the menu governor

In reply to Arjan van de Ven

From: Arjan van de Ven <[email protected]>
Date: Sun, 9 May 2010 15:49:43 -0700
Subject: [PATCH 2/2] cpuidle: Add a repeating pattern detector to the menu governor

Currently, the menu governor uses the (corrected) next timer as key item for predicting the idle duration.

It turns out that there are specific cases where this breaks down:
There are cases where we have a very repetitive pattern of idle durations, where the idle period is pretty much the same, for reasons completely unrelated to the next timer event. Examples of such repeating patterns are network loads with irq mitigation, the mouse moving but in theory also the wifi beacons.

This patch adds a relatively simple detector for such repeating patterns, where the standard deviation of the last 8 idle periods is compared to a threshold.

With this extra predictor in place, measurements show that the DECAY factor can now be increased (the decaying average will now decay slower) to get an even more stable result.

---
 drivers/cpuidle/governors/menu.c |   60 +++++++++++++++++++++++++++++++++++++-
 1 files changed, 59 insertions(+), 1 deletions(-)
drivers/cpuidle/governors/menu.c +59 -1
index f8e57c6..4eeef00 100644
@@ -21,9 +21,12 @@
 #include <linux/math64.h>
 
 #define BUCKETS 12
+#define INTERVALS 8
 #define RESOLUTION 1024
-#define DECAY 4
+#define DECAY 8
 #define MAX_INTERESTING 50000
+#define STDDEV_THRESH 400
+
 
 /*
  * Concepts and ideas behind the menu governor
@@ -64,6 +67,16 @@
  * indexed based on the magnitude of the expected duration as well as the
  * "is IO outstanding" property.
  *
+ * Repeatable-interval-detector
+ * ----------------------------
+ * There are some cases where "next timer" is a completely unusable predictor:
+ * Those cases where the interval is fixed, for example due to hardware
+ * interrupt mitigation, but also due to fixed transfer rate devices such as
+ * mice.
+ * For this, we use a different predictor: We track the duration of the last 8
+ * intervals and if the stand deviation of these 8 intervals is below a
+ * threshold value, we use the average of these intervals as prediction.
+ *
  * Limiting Performance Impact
  * ---------------------------
  * C states, especially those with large exit latencies, can have a real
@@ -104,6 +117,8 @@ struct menu_device {
 	unsigned int	exit_us;
 	unsigned int	bucket;
 	u64		correction_factor[BUCKETS];
+	u32		intervals[INTERVALS];
+	int		interval_ptr;
 };
 
 
@@ -175,6 +190,42 @@ static u64 div_round64(u64 dividend, u32 divisor)
 	return div_u64(dividend + (divisor / 2), divisor);
 }
 
+/*
+ * Try detecting repeating patterns by keeping track of the last 8
+ * intervals, and checking if the standard deviation of that set
+ * of points is below a threshold. If it is... then use the
+ * average of these 8 points as the estimated value.
+ */
+static void detect_repeating_patterns(struct menu_device *data)
+{
+	int i;
+	uint64_t avg = 0;
+	uint64_t stddev = 0; /* contains the square of the std deviation */
+
+	/* first calculate average and standard deviation of the past */
+	for (i = 0; i < INTERVALS; i++)
+		avg += data->intervals[i];
+
+	/* if the avg is beyond the known next tick, it's worthless */
+	if (avg > data->expected_us)
+		return;
+
+	avg = avg / INTERVALS;
+	for (i = 0; i < INTERVALS; i++)
+		stddev += (data->intervals[i] - avg) *
+			  (data->intervals[i] - avg);
+
+	stddev = stddev / INTERVALS;
+
+	/*
+	 * now.. if stddev is small.. then assume we have a
+	 * repeating pattern and predict we keep doing this.
+	 */
+
+	if (avg && stddev < STDDEV_THRESH)
+		data->predicted_us = avg;
+}
+
 /**
  * menu_select - selects the next idle state to enter
  * @dev: the CPU
@@ -218,6 +269,8 @@ static int menu_select(struct cpuidle_device *dev)
 	data->predicted_us = div_round64(data->expected_us * data->correction_factor[data->bucket],
 					 RESOLUTION * DECAY);
 
+	detect_repeating_patterns(data);
+
 	/*
 	 * We want to default to C1 (hlt), not to busy polling
 	 * unless the timer is happening really really soon.
@@ -310,6 +363,11 @@ static void menu_update(struct cpuidle_device *dev)
 		new_factor = 1;
 
 	data->correction_factor[data->bucket] = new_factor;
+
+	/* update the repeating-pattern data */
+	data->intervals[data->interval_ptr++] = last_idle_us;
+	if (data->interval_ptr >= INTERVALS)
+		data->interval_ptr = 0;
 }
 
 /**
Signature · 8 lines
1.6.2.5



-- 
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#3 lore raw

Re: [PATCH 2/2] cpuidle: Add a repeating pattern detector to the menu governor

Quoted 19 lines · On Sun, 9 May 2010 16:04:44 -0700 Arjan van de Ven <[email protected]> wrote:
drivers/cpuidle/governors/menu.c +19 -0
+static void detect_repeating_patterns(struct menu_device *data)
+{
+	int i;
+	uint64_t avg = 0;
+	uint64_t stddev = 0; /* contains the square of the std deviation */
+
+	/* first calculate average and standard deviation of the past */
+	for (i = 0; i < INTERVALS; i++)
+		avg += data->intervals[i];
+
+	/* if the avg is beyond the known next tick, it's worthless */
+	if (avg > data->expected_us)
+		return;
+
+	avg = avg / INTERVALS;
+	for (i = 0; i < INTERVALS; i++)
+		stddev += (data->intervals[i] - avg) *
+			  (data->intervals[i] - avg);
+

drivers/cpuidle/governors/menu.c static u64 div_round64(u64 dividend, u32 divisor) · line 227

Quoted 10 lines
drivers/cpuidle/governors/menu.c +10 -0
+	stddev = stddev / INTERVALS;
+
+	/*
+	 * now.. if stddev is small.. then assume we have a
+	 * repeating pattern and predict we keep doing this.
+	 */
+
+	if (avg && stddev < STDDEV_THRESH)
+		data->predicted_us = avg;
+}

You got lucky there, because INTERVALS is a power of two. If someone changes INTERVALS to 7, this code will ask for __udivdi3 and won't link on i364.

#4 lore raw

Re: [PATCH 2/2] cpuidle: Add a repeating pattern detector to the menu governor

Quoted 7 lines · On Mon, 10 May 2010 14:38:50 -0700 Andrew Morton <[email protected]>…

drivers/cpuidle/governors/menu.c static u64 div_round64(u64 dividend, u32 divisor) · line 227

Quoted 3 lines
drivers/cpuidle/governors/menu.c +3 -0
+	if (avg && stddev < STDDEV_THRESH)
+		data->predicted_us = avg;
+}

You got lucky there, because INTERVALS is a power of two. If someone changes INTERVALS to 7, this code will ask for __udivdi3 and won't link on i364.

yeah you'd think it almost isn't an accident ;-)

Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#5 lore raw

Re: [PATCH 2/2] cpuidle: Add a repeating pattern detector to the menu governor

Quoted 11 lines · On Mon, 10 May 2010 18:27:46 -0700 Arjan van de Ven <[email protected]> wrote:
Quoted 7 lines · On Mon, 10 May 2010 14:38:50 -0700 Andrew Morton <[email protected]>…

drivers/cpuidle/governors/menu.c static u64 div_round64(u64 dividend, u32 divisor) · line 227

Quoted 3 lines
drivers/cpuidle/governors/menu.c +3 -0
+	if (avg && stddev < STDDEV_THRESH)
+		data->predicted_us = avg;
+}

You got lucky there, because INTERVALS is a power of two. If someone changes INTERVALS to 7, this code will ask for __udivdi3 and won't link on i364.

Quoted 1 line

yeah you'd think it almost isn't an accident ;-)

If it was deliberate the code would read

	avg >>= INTERVALS_SHIFT;

:-p

#6 lore raw

Re: [PATCH 2/2] cpuidle: Add a repeating pattern detector to the menu governor

In reply to Arjan van de Ven

Aplogies if this is a duplicate, my outgoing email seems to have not been working.

Quoted 10 lines · Arjan van de Ven
drivers/cpuidle/governors/menu.c +10 -0
+/*
+ * Try detecting repeating patterns by keeping track of the last 8
+ * intervals, and checking if the standard deviation of that set
+ * of points is below a threshold. If it is... then use the
+ * average of these 8 points as the estimated value.
+ */
+static void detect_repeating_patterns(struct menu_device *data)
+{
+	int i;
+	uint64_t avg = 0;

drivers/cpuidle/governors/menu.c static u64 div_round64(u64 dividend, u32 divisor) · line 212

Quoted 10 lines
drivers/cpuidle/governors/menu.c +10 -0
+	uint64_t stddev = 0; /* contains the square of the std deviation */
+
+	/* first calculate average and standard deviation of the past */
+	for (i = 0; i < INTERVALS; i++)
+		avg += data->intervals[i];
+
+	/* if the avg is beyond the known next tick, it's worthless */
+	if (avg > data->expected_us)
+		return;
+

Should the following division by INTERVALS be moved up 6 lines to before "if (avg > data->expected_us)"?

Quoted 15 lines
drivers/cpuidle/governors/menu.c +15 -0
+	avg = avg / INTERVALS;
+	for (i = 0; i < INTERVALS; i++)
+		stddev += (data->intervals[i] - avg) *
+			  (data->intervals[i] - avg);
+
+	stddev = stddev / INTERVALS;
+
+	/*
+	 * now.. if stddev is small.. then assume we have a
+	 * repeating pattern and predict we keep doing this.
+	 */
+
+	if (avg && stddev < STDDEV_THRESH)
+		data->predicted_us = avg;
+}
#7 lore raw

Re: [PATCH 2/2] cpuidle: Add a repeating pattern detector to the menu governor

Quoted 20 lines · On Wed, 19 May 2010 12:51:50 -0700 Frank Rowand <[email protected]>…

Aplogies if this is a duplicate, my outgoing email seems to have not been working.

Quoted 15 lines · Arjan van de Ven
drivers/cpuidle/governors/menu.c +15 -0
+/*
+ * Try detecting repeating patterns by keeping track of the last 8
+ * intervals, and checking if the standard deviation of that set
+ * of points is below a threshold. If it is... then use the
+ * average of these 8 points as the estimated value.
+ */
+static void detect_repeating_patterns(struct menu_device *data)
+{
+	int i;
+	uint64_t avg = 0;
+	uint64_t stddev = 0; /* contains the square of the std deviation */
+
+	/* first calculate average and standard deviation of the past */
+	for (i = 0; i < INTERVALS; i++)
+		avg += data->intervals[i];
Quoted 8 lines

drivers/cpuidle/governors/menu.c static u64 div_round64(u64 dividend, u32 divisor) · line 212

Quoted 5 lines
drivers/cpuidle/governors/menu.c +5 -0
+
+	/* if the avg is beyond the known next tick, it's worthless */
+	if (avg > data->expected_us)
+		return;
+

Should the following division by INTERVALS be moved up 6 lines to before "if (avg > data->expected_us)"?

Quite possibly.

Quoted 7 lines
Quoted 7 lines
drivers/cpuidle/governors/menu.c +7 -0
+	avg = avg / INTERVALS;
+	for (i = 0; i < INTERVALS; i++)
+		stddev += (data->intervals[i] - avg) *
+			  (data->intervals[i] - avg);
+
+	stddev = stddev / INTERVALS;
+
Quoted 8 lines

drivers/cpuidle/governors/menu.c static u64 div_round64(u64 dividend, u32 divisor) · line 227

Quoted 8 lines
drivers/cpuidle/governors/menu.c +8 -0
+	/*
+	 * now.. if stddev is small.. then assume we have a
+	 * repeating pattern and predict we keep doing this.
+	 */
+
+	if (avg && stddev < STDDEV_THRESH)
+		data->predicted_us = avg;
+}

wakey wakey, Arjan.

Also, expected_us is 32-bit and predicted_us is 64-bit. Was that rational?

#8 lore raw

Re: [PATCH 2/2] cpuidle: Add a repeating pattern detector to the menu governor

Quoted 35 lines · On Fri, 21 May 2010 12:43:09 -0700 Andrew Morton <[email protected]>…
Quoted 23 lines · On Wed, 19 May 2010 12:51:50 -0700 Frank Rowand <[email protected]>…

Aplogies if this is a duplicate, my outgoing email seems to have not been working.

Quoted 18 lines · Arjan van de Ven

+/*
+ * Try detecting repeating patterns by keeping track of the last 8
+ * intervals, and checking if the standard deviation of that set
+ * of points is below a threshold. If it is... then use the
+ * average of these 8 points as the estimated value.
+ */

drivers/cpuidle/governors/menu.c +5 -0
+static void detect_repeating_patterns(struct menu_device *data)
+{
+	int i;
+	uint64_t avg = 0;
+	uint64_t stddev = 0; /* contains the square of the std

deviation */ +

(quoted diff) +1 -0
+	/* first calculate average and standard deviation of the

past */

drivers/cpuidle/governors/menu.c +3 -0
+	for (i = 0; i < INTERVALS; i++)
+		avg += data->intervals[i];
+
Quoted 8 lines

drivers/cpuidle/governors/menu.c static u64 div_round64(u64 dividend, u32 divisor) · line 212

Quoted 5 lines
(quoted diff) +1 -0
+	/* if the avg is beyond the known next tick, it's

worthless */

drivers/cpuidle/governors/menu.c +3 -0
+	if (avg > data->expected_us)
+		return;
+

Should the following division by INTERVALS be moved up 6 lines to before "if (avg > data->expected_us)"?

Quoted 1 line

Quite possibly.

yeah that's a bug; I'll make a patch to fix it

Quoted 10 lines
Quoted 10 lines
Quoted 10 lines
drivers/cpuidle/governors/menu.c +9 -0
+	avg = avg / INTERVALS;
+	for (i = 0; i < INTERVALS; i++)
+		stddev += (data->intervals[i] - avg) *
+			  (data->intervals[i] - avg);
+
+	stddev = stddev / INTERVALS;
+
+	/*
+	 * now.. if stddev is small.. then assume we have a
Quoted 8 lines
Quoted 6 lines

drivers/cpuidle/governors/menu.c static u64 div_round64(u64 dividend, u32 divisor) · line 227

Quoted 6 lines
drivers/cpuidle/governors/menu.c +6 -0
+	 * repeating pattern and predict we keep doing this.
+	 */
+
+	if (avg && stddev < STDDEV_THRESH)
+		data->predicted_us = avg;
+}

wakey wakey, Arjan.

sorry, seems this email got lost in 400 "Suspend block API" emails ;(

Quoted 4 lines

Also, expected_us is 32-bit and predicted_us is 64-bit. Was that rational?

predicted holds intermediate results of some calculations.. and those overflow 32 bit...

Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#9 lore raw

Re: [PATCH 2/2] cpuidle: Add a repeating pattern detector to the menu governor

In reply to Andrew Morton
Quoted 6 lines · On Fri, 21 May 2010 12:43:09 -0700 Andrew Morton <[email protected]>…
Quoted 2 lines

Should the following division by INTERVALS be moved up 6 lines to before "if (avg > data->expected_us)"?

Quite possibly.

From 7350a9007eee802eaa9e4c1878dd5a2ea4d6f7f9 Mon Sep 17 00:00:00 2001

From: Arjan van de Ven <[email protected]>
Date: Sat, 22 May 2010 09:29:29 -0700
Subject: [PATCH] cpuidle: fix bug in the pattern detector as reported by Frank Rowand

Frank Rowand found a bug in the new pattern detector code where the average value was looked at before the sum of values got divided by the number of samples.

---
 drivers/cpuidle/governors/menu.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
drivers/cpuidle/governors/menu.c +1 -1
index f3d4783..52ff8aa 100644
@@ -205,12 +205,12 @@ static void detect_repeating_patterns(struct menu_device *data)
 	/* first calculate average and standard deviation of the past */
 	for (i = 0; i < INTERVALS; i++)
 		avg += data->intervals[i];
+	avg = avg / INTERVALS;
 
 	/* if the avg is beyond the known next tick, it's worthless */
 	if (avg > data->expected_us)
 		return;
 
-	avg = avg / INTERVALS;
 	for (i = 0; i < INTERVALS; i++)
 		stddev += (data->intervals[i] - avg) *
 			  (data->intervals[i] - avg);
Signature · 1 line
1.6.2.5