On Thu, Apr 28, 2011 at 11:51 AM, Paul Turner <[email protected]> wrote:
> On Thu, Apr 28, 2011 at 11:33 AM, Nikhil Rao <[email protected]> wrote:
>> On Thu, Apr 28, 2011 at 5:12 AM, Srivatsa Vaddagiri
>> <[email protected]> wrote:
>>> On Thu, Apr 28, 2011 at 05:18:27PM +0530, Nikunj A. Dadhania wrote:
>>>> --- kernel/sched.c.orig 2011-04-28 16:34:24.000000000 +0530
>>>> +++ kernel/sched.c 2011-04-28 16:36:29.000000000 +0530
>>>> @@ -1336,7 +1336,7 @@ calc_delta_mine(unsigned long delta_exec
>>>> lw->inv_weight = 1 + (WMULT_CONST - w/2) / (w + 1);
>>>> }
>>>>
>>>> - tmp = (u64)delta_exec * weight;
>>>> + tmp = (u64)delta_exec * (weight >> SCHED_LOAD_RESOLUTION);
>>>
>>> Should we be fixing inv_weight rather to account for SCHED_LOAD_RESOLUTION here?
>>>
>>
>> Yes, I have been looking into fixing inv_weight and calc_delta_mine()
>> calculations based on the assumption that we have u64 weights. IMO the
>> function is complicated because the return value needs to be
>> calculated to fit into unsigned long. I would like to update users of
>> calc_delta_mine() to use u64 instead of unsigned longs and I think
>> this can be easily done (quick inspection of the code shows two call
>> sites that need to be updated - update_curr() and wakeup_gran()).
>> Without the restriction to fit into unsigned long, I think we can make
>> calc_delta_mine() and the inv_weight calculations simpler.
>>
>
> I don't think you have much room to maneuver here, the calculations in
> c_d_m() are already u64 based, even on 32bit. Changing the external
> load factors to 64 bit doesn't change this.
>
> We lose fairness in cdm beyond 32 bits, at the old LOAD_SCALE=10
> you've got 22 bits with which you can maintain fairness. This gives
> total accuracy in total curr on any delta <= ~4ms (for a NICE_0 task).
> If you bump this up (and don't downshift before computing the inverse
> as you are) then you start introducing rounding errors beyond ~4us.
>
> This would also be further exacerbated in sched_period() since that's
> using the total cfs_rq weight.
>

Hmm... yeah, I think you have nicely explained the problem at hand. As
you said, we can't bump up inv_weight without losing accuracy. We want
to keep the 32-bit bound because it avoids the division. I was
exploring other optimizations in this functions, but I think what Paul
pointed out is key here.

-Thanks
Nikhil

>> -Thanks,
>> Nikhil
>>
>

2011-04-29 16:56:17

by Paul Turner

[permalink] [raw]

Subject: Re: [RFC][PATCH 00/18] Increase resolution of load weights

On Thu, Apr 28, 2011 at 2:27 PM, Nikhil Rao <[email protected]> wrote:
> On Thu, Apr 28, 2011 at 11:51 AM, Paul Turner <[email protected]> wrote:
>> On Thu, Apr 28, 2011 at 11:33 AM, Nikhil Rao <[email protected]> wrote:
>>> On Thu, Apr 28, 2011 at 5:12 AM, Srivatsa Vaddagiri
>>> <[email protected]> wrote:
>>>> On Thu, Apr 28, 2011 at 05:18:27PM +0530, Nikunj A. Dadhania wrote:
>>>>> --- kernel/sched.c.orig ? ? ? 2011-04-28 16:34:24.000000000 +0530
>>>>> +++ kernel/sched.c ? ?2011-04-28 16:36:29.000000000 +0530
>>>>> @@ -1336,7 +1336,7 @@ calc_delta_mine(unsigned long delta_exec
>>>>> ? ? ? ? ? ? ? ? ? ? ? lw->inv_weight = 1 + (WMULT_CONST - w/2) / (w + 1);
>>>>> ? ? ? }
>>>>>
>>>>> - ? ? tmp = (u64)delta_exec * weight;
>>>>> + ? ? tmp = (u64)delta_exec * (weight >> SCHED_LOAD_RESOLUTION);
>>>>
>>>> Should we be fixing inv_weight rather to account for SCHED_LOAD_RESOLUTION here?
>>>>
>>>
>>> Yes, I have been looking into fixing inv_weight and calc_delta_mine()
>>> calculations based on the assumption that we have u64 weights. IMO the
>>> function is complicated because the return value needs to be
>>> calculated to fit into unsigned long. I would like to update users of
>>> calc_delta_mine() to use u64 instead of unsigned longs and I think
>>> this can be easily done (quick inspection of the code shows two call
>>> sites that need to be updated - update_curr() and wakeup_gran()).
>>> Without the restriction to fit into unsigned long, I think we can make
>>> calc_delta_mine() and the inv_weight calculations simpler.
>>>
>>
>> I don't think you have much room to maneuver here, the calculations in
>> c_d_m() are already u64 based, even on 32bit. ?Changing the external
>> load factors to 64 bit doesn't change this.
>>
>> We lose fairness in cdm beyond 32 bits, at the old LOAD_SCALE=10
>> you've got 22 bits with which you can maintain fairness. This gives
>> total accuracy in total curr on any delta <= ~4ms (for a NICE_0 task).
>> ?If you bump this up (and don't downshift before computing the inverse
>> as you are) then you start introducing rounding errors beyond ~4us.
>>
>> This would also be further exacerbated in sched_period() since that's
>> using the total cfs_rq weight.
>>
>
> Hmm... yeah, I think you have nicely explained the problem at hand. As
> you said, we can't bump up inv_weight without losing accuracy. We want
> to keep the 32-bit bound because it avoids the division. I was
> exploring other optimizations in this functions, but I think what Paul
> pointed out is key here.
>

Correcting myself a tiny bit here: the 32 bit inverse covers the load
weight, at 28 bit load weights it's this (the inverse) that goes to
hell not the numerator (time). The end effect of mushy fairness is
the same.

> -Thanks
> Nikhil
>
>>> -Thanks,
>>> Nikhil
>>>
>>
>