Sorry about that, my bad.
I know this is an RFC patch, not meant for inclusion, but it is good
practice to have your Signed-off-by.
+ /*
+ * Rearrange the weight distribution of the state, increase the weight
+ * by the LEARNING RATE % for the idle state that was supposed to be
+ * chosen and reduce by the same amount for rest of the states
+ *
+ * If the weights are greater than (100 - LEARNING_RATE) % or lesser
+ * than LEARNING_RATE %, do not increase or decrease the confidence
+ * respectively
+ */
+ for (i = 0; i < drv->state_count; i++) {
+ unsigned int delta;
+
+ if (idx == -1)
+ break;
+ if (i == idx) {
+ delta = (LEARNING_RATE * cpu_data->state_mat[last_idx][i]) / 100;
+ if (cpu_data->state_mat[last_idx][i] + delta >=
+ (100 - LEARNING_RATE) * 100)
+ continue;
+ cpu_data->state_mat[last_idx][i] += delta;
+ continue;
+ }
+ delta = (LEARNING_RATE * cpu_data->state_mat[last_idx][i]) /
+ ((drv->state_count - 1) * 100);
What happens when drv->state_count == 1?
+ if (cpu_data->state_mat[last_idx][i] - delta <=So, even update takes O(n) time, since we have to increase the weight
+ LEARNING_RATE * 100)
+ continue;
+ cpu_data->state_mat[last_idx][i] -= delta;
for one state, and correspondingly decrease the state for all the
other states.
+ }
+
/*
* Save idle duration values corresponding to non-timer wakeups for
* pattern detection.
@@ -244,7 +288,7 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
s64 latency_req = cpuidle_governor_latency_req(dev->cpu);
u64 duration_ns;
unsigned int hits, misses, early_hits;
- int max_early_idx, prev_max_early_idx, constraint_idx, idx, i;
+ int max_early_idx, prev_max_early_idx, constraint_idx, idx, i, og_idx;
ktime_t delta_tick;
if (dev->last_state_idx >= 0) {
@@ -374,10 +418,13 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
if (constraint_idx < idx)
idx = constraint_idx;
+ og_idx = idx;
+
if (idx < 0) {
idx = 0; /* No states enabled. Must use 0. */
} else if (idx > 0) {
- unsigned int count = 0;
+ unsigned int count = 0, sum_weights = 0, weights_list[CPUIDLE_STATE_MAX];
+ int i, j = 0, rnd_wt, rnd_num = 0;
u64 sum = 0;
/*
@@ -412,6 +459,29 @@ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
idx, avg_ns);
}
}
+ /*
+ * In case, the recent history yields a shallower state, then
+ * the probability distribution is looked at.
+ * The weighted random number generator uses the weights as a
+ * bias to choose the next idle state
+ */
+ if (og_idx != idx) {
+ for (i = 0; i <= idx; i++) {
So it seems like we are restricting our choice to states no deeper
than the selected state.
Is it not possible that cpu_data->state_mat[idx][j] has the
maximum weight when j > idx ? If yes, why are we leaving those states
out ?
+ if (dev->states_usage[i].disable)Assume that cpu_data->stat_mat[idx] = {4, 5, 6, 9}
+ continue;
+ sum_weights += cpu_data->state_mat[idx][i];
+ weights_list[j++] = sum_weights;
+ }
weight_list[] = {4, 9, 15, 24}
+ get_random_bytes(&rnd_num, sizeof(rnd_num));Assume rnd_num = 50.
+ rnd_num = rnd_num % 100;
+ rnd_wt = (rnd_num * sum_weights) / 100;
Then, rnd_wt = 12.
From the logic, below, it appears that you want to pick the shallowest
state i at which rnd_wt < weights_list[i]. In which case it would be
the state corresponding to the weight 6 (as the cumulative weight at
that point is 15).
+ for (i = 0; i < j; i++) {
+ if (rnd_wt < weights_list[i])
+ break;
+ rnd_wt -= weights_list[i];
And yet, because of this additional subtraction, after the first
iteration of this loop, rnd_wt = 12 - 4 = 8, which means that you will
end up picking the state corresponding to weight 5 (cumulative weight
being 9 at this point).
This doesn't seem right.
---+ }
+ idx = i;
+ }
}
/*
@@ -468,13 +538,28 @@ static int teo_enable_device(struct cpuidle_driver *drv,
struct cpuidle_device *dev)
{
struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
- int i;
+ int i, j;
memset(cpu_data, 0, sizeof(*cpu_data));
for (i = 0; i < INTERVALS; i++)
cpu_data->intervals[i] = U64_MAX;
+ /*
+ * Populate initial weights for each state
+ * The stop state is initially more biased for itself.
+ *
+ * Currently the initial distribution of probabilities are 70%-30%.
+ * The trailing 0s are for increased resolution.
+ */
+ for (i = 0; i < drv->state_count; i++) {
+ for (j = 0; j < drv->state_count; j++) {
+ if (i == j)
+ cpu_data->state_mat[i][j] = 7000;
+ else
+ cpu_data->state_mat[i][j] = 3000 / (drv->state_count - 1);
+ }
+ }
return 0;
}
--
2.17.1