[PATCH v2] cpuidle: menu: find the typical interval by a heuristic classification method

[PATCH v2] cpuidle: menu: find the typical interval by a heuristic classification method

[朱恺乾]

Menu governor relies on get_typical_interval() to find the repeating
idle interval from the history, but it can not handle the case when
there're two or more repeating patterns. The calculation of deviation
always leads to a single closely connected intervals.

In order to find all the possible repeating intervals and choose the
most promising one for the next idle. This algorithm is classifying
the idle histories heuristically by the state it is in. It changes
the behavior of the function to look for the repeating state actually,
but it still meets the goal of choosing an idle state.

The occurrence of each state is counted and their average is calculated.
The average value of each state would be taken as a repeating pattern.
To find the one most likely to happen, weights are added to the
histories by the order of time, so the state has the highest weight, or
occurs most often in the recent history, is selected, and it's average
is returned as the typical interval.

Considering the fact that some idle intervals may be very close to another
state, the algorithm calculates the distance to each average, and do the
re-classification once by putting the history into the state closer to it.
It makes the state average possible to derive an average under or above the
state residency.

Comparing with the deviation calculation, this method
1) can find multiple patterns from the history and choose from them
2) can be more sensitive to the changing workload as the threshold is
lowered
3) puts time into consideration, so prediction won't stuck in the stale
histories

Signed-off-by: Kaiqian Zhu <zhukaiqian@xiaomi.com>
---
 drivers/cpuidle/governors/menu.c | 172 ++++++++++++++++---------------
 1 file changed, 89 insertions(+), 83 deletions(-)

diff --git a/drivers/cpuidle/governors/menu.c b/drivers/cpuidle/governors/menu.c
index 81306612a5c6..5b279ae07b16 100644
--- a/drivers/cpuidle/governors/menu.c
+++ b/drivers/cpuidle/governors/menu.c
@@ -107,109 +107,115 @@ static void menu_update_intervals(struct menu_device *data, unsigned int interva

 static void menu_update(struct cpuidle_driver *drv, struct cpuidle_device *dev);

+static int get_actual_state(struct cpuidle_driver *drv,
+    struct cpuidle_device *dev,
+    int duration_us)
+{
+int actual;
+
+for (int i = 0; i < drv->state_count; i++) {
+if (duration_us < drv->states[i].target_residency)
+break;
+
+actual = i;
+}
+
+return actual;
+}
+
 /*
- * 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.
+ * Find a typical interval by analyzing the sleep times and their
+ * corresponding states. The state that contains the recent idle
+ * and frequently hit in the history is considered most likely to
+ * happen in the future, and the average interval for that state
+ * is returned.
+ *
+ * For the cases that a sleep time is close to another state's
+ * residency, it is reclassified once during the process based on
+ * its proximity to the average of each state.
  */
-static unsigned int get_typical_interval(struct menu_device *data)
+static unsigned int get_typical_interval(struct cpuidle_driver *drv,
+ struct cpuidle_device *dev,
+ struct menu_device *data)
 {
-s64 value, min_thresh = -1, max_thresh = UINT_MAX;
-unsigned int max, min, divisor;
-u64 avg, variance, avg_sq;
-int i;
+int cnt = 0;

-again:
-/* Compute the average and variance of past intervals. */
-max = 0;
-min = UINT_MAX;
-avg = 0;
-variance = 0;
-divisor = 0;
-for (i = 0; i < INTERVALS; i++) {
-value = data->intervals[i];
-/*
- * Discard the samples outside the interval between the min and
- * max thresholds.
- */
-if (value <= min_thresh || value >= max_thresh)
-continue;
+int state_hit[CPUIDLE_STATE_MAX];
+int state_avg[CPUIDLE_STATE_MAX];
+int adj_weight[CPUIDLE_STATE_MAX];
+int adj_avg[CPUIDLE_STATE_MAX];
+int adj_hit[CPUIDLE_STATE_MAX];
+int hit_thres = max(3, INTERVALS / drv->state_count);
+int weights[INTERVALS] = {5, 3, 2, 1};
+int weight = 0;
+int high_state = -1;

-divisor++;

-avg += value;
-variance += value * value;
+/* Going through the history, and divide them by the actual state */
+for (int i = 0; i < INTERVALS; i++) {
+int actual = get_actual_state(drv, dev, data->intervals[i]);

-if (value > max)
-max = value;
+/* Count the idle states hit in the history */
+state_avg[actual] += data->intervals[i];
+state_hit[actual]++;

-if (value < min)
-min = value;
+cnt++;
 }

-if (!max)
+if (cnt < hit_thres)
 return UINT_MAX;

-if (divisor == INTERVALS) {
-avg >>= INTERVAL_SHIFT;
-variance >>= INTERVAL_SHIFT;
-} else {
-do_div(avg, divisor);
-do_div(variance, divisor);
+/* Calculate the average of each state */
+for (int i = 0; i < drv->state_count; i++) {
+if (state_hit[i] > 1)
+state_avg[i] /= state_hit[i];
 }

-avg_sq = avg * avg;
-variance -= avg_sq;
+/* Try to re-assign the data points by the closeness */
+for (int i = 0; i < INTERVALS; i++) {
+/* Starting from the recent history */
+int idx = ((data->interval_ptr - i - 1) + INTERVALS) % INTERVALS;
+unsigned int diff;
+unsigned int best_diff = UINT_MAX;
+unsigned int best_state;
+unsigned int value = data->intervals[idx];
+
+for (int state = 0; state < drv->state_count; state++) {
+diff = abs(state_avg[state] - value);
+if (diff < best_diff) {
+best_diff = diff;
+best_state = state;
+}
+}

-/*
- * The typical interval is obtained when standard deviation is
- * small (stddev <= 20 us, variance <= 400 us^2) or standard
- * deviation is small compared to the average interval (avg >
- * 6*stddev, avg^2 > 36*variance). The average is smaller than
- * UINT_MAX aka U32_MAX, so computing its square does not
- * overflow a u64. We simply reject this candidate average if
- * the standard deviation is greater than 715 s (which is
- * rather unlikely).
- *
- * Use this result only if there is no timer to wake us up sooner.
- */
-if (likely(variance <= U64_MAX/36)) {
-if ((avg_sq > variance * 36 && divisor * 4 >= INTERVALS * 3) ||
-    variance <= 400)
-return avg;
+adj_weight[best_state] += weights[i];
+adj_avg[best_state] += value;
+adj_hit[best_state]++;
 }

-/*
- * If there are outliers, discard them by setting thresholds to exclude
- * data points at a large enough distance from the average, then
- * calculate the average and standard deviation again. Once we get
- * down to the last 3/4 of our samples, stop excluding samples.
- *
- * This can deal with workloads that have long pauses interspersed
- * with sporadic activity with a bunch of short pauses.
+/* We've adjusted the hit status by the closeness, if one state is still
+ * hit more often and selected recently, we can assume that state is more
+ * likely to happen in the future
  */
-if (divisor * 4 <= INTERVALS * 3) {
-/*
- * If there are sufficiently many data points still under
- * consideration after the outliers have been eliminated,
- * returning without a prediction would be a mistake because it
- * is likely that the next interval will not exceed the current
- * maximum, so return the latter in that case.
- */
-if (divisor >= INTERVALS / 2)
-return max;
-
-return UINT_MAX;
+for (int state = 0; state < drv->state_count; state++) {
+if (adj_weight[state] > 1 && adj_hit[state] >= hit_thres) {
+adj_avg[state] /= adj_hit[state];
+
+if (adj_weight[state] > weight) {
+weight = adj_weight[state];
+high_state = state;
+} else if (adj_weight[state] == weight) {
+if (adj_hit[state] > adj_hit[high_state])
+high_state = state;
+}
+}
 }

-/* Update the thresholds for the next round. */
-if (avg - min > max - avg)
-min_thresh = min;
-else
-max_thresh = max;
+/* Return the average of the re-classifed state */
+if (weight)
+return adj_avg[high_state];

-goto again;
+return UINT_MAX;
 }

 /**
@@ -241,7 +247,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
 }

 /* Find the shortest expected idle interval. */
-predicted_ns = get_typical_interval(data) * NSEC_PER_USEC;
+predicted_ns = get_typical_interval(drv, dev, data) * NSEC_PER_USEC;
 if (predicted_ns > RESIDENCY_THRESHOLD_NS) {
 unsigned int timer_us;

--
2.34.1

#/******本邮件及其附件含有小米公司的保密信息，仅限于发送给上面地址中列出的个人或群组。禁止任何其他人以任何形式使用（包括但不限于全部或部分地泄露、复制、或散发）本邮件中的信息。如果您错收了本邮件，请您立即电话或邮件通知发件人并删除本邮件！ This e-mail and its attachments contain confidential information from XIAOMI, which is intended only for the person or entity whose address is listed above. Any use of the information contained herein in any way (including, but not limited to, total or partial disclosure, reproduction, or dissemination) by persons other than the intended recipient(s) is prohibited. If you receive this e-mail in error, please notify the sender by phone or email immediately and delete it!******/#

Re: [PATCH v2] cpuidle: menu: find the typical interval by a heuristic classification method

[Christian Loehle]

On 8/21/25 02:54, 朱恺乾 wrote:
> Menu governor relies on get_typical_interval() to find the repeating
> idle interval from the history, but it can not handle the case when
> there're two or more repeating patterns. The calculation of deviation
> always leads to a single closely connected intervals.
> 
> In order to find all the possible repeating intervals and choose the
> most promising one for the next idle. This algorithm is classifying
> the idle histories heuristically by the state it is in. It changes
> the behavior of the function to look for the repeating state actually,
> but it still meets the goal of choosing an idle state.
> 
> The occurrence of each state is counted and their average is calculated.
> The average value of each state would be taken as a repeating pattern.
> To find the one most likely to happen, weights are added to the
> histories by the order of time, so the state has the highest weight, or
> occurs most often in the recent history, is selected, and it's average
> is returned as the typical interval.
> 
> Considering the fact that some idle intervals may be very close to another
> state, the algorithm calculates the distance to each average, and do the
> re-classification once by putting the history into the state closer to it.
> It makes the state average possible to derive an average under or above the
> state residency.
> 
> Comparing with the deviation calculation, this method
> 1) can find multiple patterns from the history and choose from them
> 2) can be more sensitive to the changing workload as the threshold is
> lowered
> 3) puts time into consideration, so prediction won't stuck in the stale
> histories
> 
> Signed-off-by: Kaiqian Zhu <zhukaiqian@xiaomi.com>
> ---
>  drivers/cpuidle/governors/menu.c | 172 ++++++++++++++++---------------
>  1 file changed, 89 insertions(+), 83 deletions(-)
> 
> diff --git a/drivers/cpuidle/governors/menu.c b/drivers/cpuidle/governors/menu.c
> index 81306612a5c6..5b279ae07b16 100644
> --- a/drivers/cpuidle/governors/menu.c
> +++ b/drivers/cpuidle/governors/menu.c
> @@ -107,109 +107,115 @@ static void menu_update_intervals(struct menu_device *data, unsigned int interva
> 
>  static void menu_update(struct cpuidle_driver *drv, struct cpuidle_device *dev);
> 
> +static int get_actual_state(struct cpuidle_driver *drv,
> +    struct cpuidle_device *dev,
> +    int duration_us)
> +{
> +int actual;
> +
> +for (int i = 0; i < drv->state_count; i++) {
> +if (duration_us < drv->states[i].target_residency)
> +break;
> +
> +actual = i;
> +}
> +
> +return actual;
> +}
> +

FYI Something went wrong witch the patch here...