Re: [PATCH] sched: Avoid side-effect of tickless idle on update_cpu_load (v2)

[Venkatesh Pallipadi]

On Mon, May 17, 2010 at 10:35 AM, Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
> On Mon, 2010-05-17 at 09:52 -0700, Venkatesh Pallipadi wrote:
>
>> >  load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * load_(i-1)
>
>> > So because we're in no_hz, current load == 0 and we could approximate
>> > the thing by:
>> >
>> >  load_i = ((2^i)-1)/(2^i) * load_i
>> >
>> > Because for i ~ 1, there is no new input, and for i >> 1 the fraction is
>> > small.
>>
>> Something like that. But, with total_updates = n and missed_updates = n - 1
>> We do this for (n - 1)
>> load_i = ((2^i)-1)/(2^i) * load_i
>> And do this once.
>> load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * cur_load
>
>> That way we do not differentiate between whether we are in tickless or
>> not and we use the same code path.
>
> But by the above, that's not the same as without, because that does
>
> load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * load_(i-1)
>
> not
>
> load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * cur_load

Hmm. I assumed you meant
load_(i-1) is same as cur_load when you said
>> >Where load_-1 == current load.

No? Or did I miss something?

For the updates done every tick, it is
load = degrade * load + (1-degrade) * cur_load
For updates done with missed ticks
load = degrade^(missed-1) * load
load = degrade * load + (1-degrade) * cur_load

So, cur_load is only accounted for the last tick, and zero load
assumed for all the missed ticks.

>> > But why then do we precalculate these factors? It seems to me
>> > ((2^i)-1)/(2^i) is something that is trivial to compute and doesn't
>> > warrant a lookup table?
>> >
>>
>> Yes. Initially I had a for loop running for missed_updates to calculate
>>  ((2^i)-1)/(2^i) * load_i
>> in a loop.
>
> Ah, right! So you want to calculate:
>
>  (((2^i)-1)/(2^i))^n
>
> Which ends up being a nasty binomial sum: 1/(2^ni) * \Sum_k^n (n choose
> k) * 2^k, so yeah, I don't see a fancy way to quickly compute that.
>
>
> OK, could you summarize our discussion into that comment?
>

OK. Will do.

Thanks,
Venki
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/