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@xxxxxxxxxx>
> ---
>  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...