On Thu, Sep 25, 2014 at 06:23:43PM +0100, Morten Rasmussen wrote:
> > Why haven't you used arch_scale_freq_capacity which has a similar
> > purpose in scaling the CPU capacity except the additional sched_domain
> > pointer argument ?
>
> To be honest I'm not happy with introducing another arch-function
> either and I'm happy to change that. It wasn't really clear to me which
> functions that would remain after your cpu_capacity rework patches, so I
> added this one. Now that we have most of the patches for capacity
> scaling and scale-invariant load-tracking on the table I think we have a
> better chance of figuring out which ones are needed and exactly how they
> are supposed to work.
>
> arch_scale_load_capacity() compensates for both frequency scaling and
> micro-architectural differences, while arch_scale_freq_capacity() only
> for frequency. As long as we can use arch_scale_cpu_capacity() to
> provide the micro-architecture scaling we can just do the scaling in two
> operations rather than one similar to how it is done for capacity in
> update_cpu_capacity(). I can fix that in the next version. It will cost
> an extra function call and multiplication though.
>
> To make sure that runnable_avg_{sum, period} are still bounded by
> LOAD_AVG_MAX, arch_scale_{cpu,freq}_capacity() must both return a factor
> in the range 0..SCHED_CAPACITY_SCALE.
I would certainly like some words in the Changelog on how and that the
math is still free of overflows. Clearly you've thought about it, so
please feel free to elucidate the rest of us :-)
> > If we take the example of an always running task, its runnable_avg_sum
> > should stay at the LOAD_AVG_MAX value whatever the frequency of the
> > CPU on which it runs. But your change links the max value of
> > runnable_avg_sum with the current frequency of the CPU so an always
> > running task will have a load contribution of 25%
> > your proposed scaling is fine with usage_avg_sum which reflects the
> > effective running time on the CPU but the runnable_avg_sum should be
> > able to reach LOAD_AVG_MAX whatever the current frequency is
>
> I don't think it makes sense to scale one metric and not the other. You
> will end up with two very different (potentially opposite) views of the
> cpu load/utilization situation in many scenarios. As I see it,
> scale-invariance and load-balancing with scale-invariance present can be
> done in two ways:
>
> 1. Leave runnable_avg_sum unscaled and scale running_avg_sum.
> se->avg.load_avg_contrib will remain unscaled and so will
> cfs_rq->runnable_load_avg, cfs_rq->blocked_load_avg, and
> weighted_cpuload(). Essentially all the existing load-balancing code
> will continue to use unscaled load. When we want to improve cpu
> utilization and energy-awareness we will have to bypass most of this
> code as it is likely to lead us on the wrong direction since it has a
> potentially wrong view of the cpu load due to the lack of
> scale-invariance.
>
> 2. Scale both runnable_avg_sum and running_avg_sum. All existing load
> metrics including weighted_cpuload() are scaled and thus more accurate.
> The difference between se->avg.load_avg_contrib and
> se->avg.usage_avg_contrib is the priority scaling and whether or not
> runqueue waiting time is counted. se->avg.load_avg_contrib can only
> reach se->load.weight when running on the fastest cpu at the highest
> frequency, but it is now scale-invariant so we have much better idea
> about how much load we are pulling when load-balancing two cpus running
> at different frequencies. The load-balance code-path still has to be
> audited to see if anything blows up due to the scaling. I haven't
> finished doing that yet. This patch set doesn't include patches to
> address such issues (yet). IMHO, by scaling runnable_avg_sum we can more
> easily make the existing load-balancing code do the right thing.
>
> For both options we have to go through the existing load-balancing code
> to either change it to use the scale-invariant metric (running_avg_sum)
> when appropriate or to fix bits that don't work properly with a
> scale-invariant runnable_avg_sum and reuse the existing code. I think
> the latter is less intrusive, but I might be wrong.
>
> Opinions?
/me votes #2, I think the example in the reply is a false one, an always
running task will/should ramp up the cpufreq and get us at full speed
(and yes I'm aware of the case where you're memory bound and raising the
cpu freq isn't going to actually improve performance, but I'm not sure
we want to get/be that smart, esp. at this stage).
On Thu, Oct 02, 2014 at 09:34:28PM +0100, Peter Zijlstra wrote:
> On Thu, Sep 25, 2014 at 06:23:43PM +0100, Morten Rasmussen wrote:
>
> > > Why haven't you used arch_scale_freq_capacity which has a similar
> > > purpose in scaling the CPU capacity except the additional sched_domain
> > > pointer argument ?
> >
> > To be honest I'm not happy with introducing another arch-function
> > either and I'm happy to change that. It wasn't really clear to me which
> > functions that would remain after your cpu_capacity rework patches, so I
> > added this one. Now that we have most of the patches for capacity
> > scaling and scale-invariant load-tracking on the table I think we have a
> > better chance of figuring out which ones are needed and exactly how they
> > are supposed to work.
> >
> > arch_scale_load_capacity() compensates for both frequency scaling and
> > micro-architectural differences, while arch_scale_freq_capacity() only
> > for frequency. As long as we can use arch_scale_cpu_capacity() to
> > provide the micro-architecture scaling we can just do the scaling in two
> > operations rather than one similar to how it is done for capacity in
> > update_cpu_capacity(). I can fix that in the next version. It will cost
> > an extra function call and multiplication though.
> >
> > To make sure that runnable_avg_{sum, period} are still bounded by
> > LOAD_AVG_MAX, arch_scale_{cpu,freq}_capacity() must both return a factor
> > in the range 0..SCHED_CAPACITY_SCALE.
>
> I would certainly like some words in the Changelog on how and that the
> math is still free of overflows. Clearly you've thought about it, so
> please feel free to elucidate the rest of us :-)
Sure. The easiest way to avoid introducing overflows is to ensure that
we always scale by a factor >= 1.0. That should be true as long as
arch_scale_{cpu,freq}_capacity() never returns anything greater than
SCHED_CAPACITY_SCALE (= 1024 = 1.0).
If we take big.LITTLE is an example, the max cpu capacity of a big cpu
would be 1024 and since we multiply the scaling factors (as in
update_cpu_capacity()) the max frequency scaling capacity factor would
be 1024. The result is a 1.0 (1.0 * 1.0) scaling factor when a task is
running on a big cpu at the highest frequency. At 50% frequency, the
scaling factor is 0.5 (1.0 * 0.5).
For a little cpu arch_scale_cpu_capacity() would return something less
than 1024, 512 for example. The max frequency scaling capacity factor is
1024. A task running on a little cpu at max frequency would have its
load scaled by 0.5 (0.5 * 1.0). At 50% frequency, it would be 0.25 (0.5
* 0.5).
However, as said earlier (below), we have to go through the load-balance
code to ensure that it doesn't blow up when cpu capacities get small
(huge.TINY), but the load-tracking code itself should be fine I think.
>
> > > If we take the example of an always running task, its runnable_avg_sum
> > > should stay at the LOAD_AVG_MAX value whatever the frequency of the
> > > CPU on which it runs. But your change links the max value of
> > > runnable_avg_sum with the current frequency of the CPU so an always
> > > running task will have a load contribution of 25%
> > > your proposed scaling is fine with usage_avg_sum which reflects the
> > > effective running time on the CPU but the runnable_avg_sum should be
> > > able to reach LOAD_AVG_MAX whatever the current frequency is
> >
> > I don't think it makes sense to scale one metric and not the other. You
> > will end up with two very different (potentially opposite) views of the
> > cpu load/utilization situation in many scenarios. As I see it,
> > scale-invariance and load-balancing with scale-invariance present can be
> > done in two ways:
> >
> > 1. Leave runnable_avg_sum unscaled and scale running_avg_sum.
> > se->avg.load_avg_contrib will remain unscaled and so will
> > cfs_rq->runnable_load_avg, cfs_rq->blocked_load_avg, and
> > weighted_cpuload(). Essentially all the existing load-balancing code
> > will continue to use unscaled load. When we want to improve cpu
> > utilization and energy-awareness we will have to bypass most of this
> > code as it is likely to lead us on the wrong direction since it has a
> > potentially wrong view of the cpu load due to the lack of
> > scale-invariance.
> >
> > 2. Scale both runnable_avg_sum and running_avg_sum. All existing load
> > metrics including weighted_cpuload() are scaled and thus more accurate.
> > The difference between se->avg.load_avg_contrib and
> > se->avg.usage_avg_contrib is the priority scaling and whether or not
> > runqueue waiting time is counted. se->avg.load_avg_contrib can only
> > reach se->load.weight when running on the fastest cpu at the highest
> > frequency, but it is now scale-invariant so we have much better idea
> > about how much load we are pulling when load-balancing two cpus running
> > at different frequencies. The load-balance code-path still has to be
> > audited to see if anything blows up due to the scaling. I haven't
> > finished doing that yet. This patch set doesn't include patches to
> > address such issues (yet). IMHO, by scaling runnable_avg_sum we can more
> > easily make the existing load-balancing code do the right thing.
> >
> > For both options we have to go through the existing load-balancing code
> > to either change it to use the scale-invariant metric (running_avg_sum)
> > when appropriate or to fix bits that don't work properly with a
> > scale-invariant runnable_avg_sum and reuse the existing code. I think
> > the latter is less intrusive, but I might be wrong.
> >
> > Opinions?
>
> /me votes #2, I think the example in the reply is a false one, an always
> running task will/should ramp up the cpufreq and get us at full speed
> (and yes I'm aware of the case where you're memory bound and raising the
> cpu freq isn't going to actually improve performance, but I'm not sure
> we want to get/be that smart, esp. at this stage).
Okay, and agreed that memory bound task smarts are out of scope for the
time being.
On 8 October 2014 13:00, Morten Rasmussen <[email protected]> wrote:
> On Thu, Oct 02, 2014 at 09:34:28PM +0100, Peter Zijlstra wrote:
>> On Thu, Sep 25, 2014 at 06:23:43PM +0100, Morten Rasmussen wrote:
>>
>> > > Why haven't you used arch_scale_freq_capacity which has a similar
>> > > purpose in scaling the CPU capacity except the additional sched_domain
>> > > pointer argument ?
>> >
>> > To be honest I'm not happy with introducing another arch-function
>> > either and I'm happy to change that. It wasn't really clear to me which
>> > functions that would remain after your cpu_capacity rework patches, so I
>> > added this one. Now that we have most of the patches for capacity
>> > scaling and scale-invariant load-tracking on the table I think we have a
>> > better chance of figuring out which ones are needed and exactly how they
>> > are supposed to work.
>> >
>> > arch_scale_load_capacity() compensates for both frequency scaling and
>> > micro-architectural differences, while arch_scale_freq_capacity() only
>> > for frequency. As long as we can use arch_scale_cpu_capacity() to
>> > provide the micro-architecture scaling we can just do the scaling in two
>> > operations rather than one similar to how it is done for capacity in
>> > update_cpu_capacity(). I can fix that in the next version. It will cost
>> > an extra function call and multiplication though.
>> >
>> > To make sure that runnable_avg_{sum, period} are still bounded by
>> > LOAD_AVG_MAX, arch_scale_{cpu,freq}_capacity() must both return a factor
>> > in the range 0..SCHED_CAPACITY_SCALE.
>>
>> I would certainly like some words in the Changelog on how and that the
>> math is still free of overflows. Clearly you've thought about it, so
>> please feel free to elucidate the rest of us :-)
>
> Sure. The easiest way to avoid introducing overflows is to ensure that
> we always scale by a factor >= 1.0. That should be true as long as
> arch_scale_{cpu,freq}_capacity() never returns anything greater than
> SCHED_CAPACITY_SCALE (= 1024 = 1.0).
the current ARM arch_scale_cpu is in the range [1536..0] which is free
of overflow AFAICT
>
> If we take big.LITTLE is an example, the max cpu capacity of a big cpu
> would be 1024 and since we multiply the scaling factors (as in
> update_cpu_capacity()) the max frequency scaling capacity factor would
> be 1024. The result is a 1.0 (1.0 * 1.0) scaling factor when a task is
> running on a big cpu at the highest frequency. At 50% frequency, the
> scaling factor is 0.5 (1.0 * 0.5).
>
> For a little cpu arch_scale_cpu_capacity() would return something less
> than 1024, 512 for example. The max frequency scaling capacity factor is
> 1024. A task running on a little cpu at max frequency would have its
> load scaled by 0.5 (0.5 * 1.0). At 50% frequency, it would be 0.25 (0.5
> * 0.5).
>
> However, as said earlier (below), we have to go through the load-balance
> code to ensure that it doesn't blow up when cpu capacities get small
> (huge.TINY), but the load-tracking code itself should be fine I think.
>
>>
>> > > If we take the example of an always running task, its runnable_avg_sum
>> > > should stay at the LOAD_AVG_MAX value whatever the frequency of the
>> > > CPU on which it runs. But your change links the max value of
>> > > runnable_avg_sum with the current frequency of the CPU so an always
>> > > running task will have a load contribution of 25%
>> > > your proposed scaling is fine with usage_avg_sum which reflects the
>> > > effective running time on the CPU but the runnable_avg_sum should be
>> > > able to reach LOAD_AVG_MAX whatever the current frequency is
>> >
>> > I don't think it makes sense to scale one metric and not the other. You
>> > will end up with two very different (potentially opposite) views of the
>> > cpu load/utilization situation in many scenarios. As I see it,
>> > scale-invariance and load-balancing with scale-invariance present can be
>> > done in two ways:
>> >
>> > 1. Leave runnable_avg_sum unscaled and scale running_avg_sum.
>> > se->avg.load_avg_contrib will remain unscaled and so will
>> > cfs_rq->runnable_load_avg, cfs_rq->blocked_load_avg, and
>> > weighted_cpuload(). Essentially all the existing load-balancing code
>> > will continue to use unscaled load. When we want to improve cpu
>> > utilization and energy-awareness we will have to bypass most of this
>> > code as it is likely to lead us on the wrong direction since it has a
>> > potentially wrong view of the cpu load due to the lack of
>> > scale-invariance.
>> >
>> > 2. Scale both runnable_avg_sum and running_avg_sum. All existing load
>> > metrics including weighted_cpuload() are scaled and thus more accurate.
>> > The difference between se->avg.load_avg_contrib and
>> > se->avg.usage_avg_contrib is the priority scaling and whether or not
>> > runqueue waiting time is counted. se->avg.load_avg_contrib can only
>> > reach se->load.weight when running on the fastest cpu at the highest
>> > frequency, but it is now scale-invariant so we have much better idea
>> > about how much load we are pulling when load-balancing two cpus running
>> > at different frequencies. The load-balance code-path still has to be
>> > audited to see if anything blows up due to the scaling. I haven't
>> > finished doing that yet. This patch set doesn't include patches to
>> > address such issues (yet). IMHO, by scaling runnable_avg_sum we can more
>> > easily make the existing load-balancing code do the right thing.
>> >
>> > For both options we have to go through the existing load-balancing code
>> > to either change it to use the scale-invariant metric (running_avg_sum)
>> > when appropriate or to fix bits that don't work properly with a
>> > scale-invariant runnable_avg_sum and reuse the existing code. I think
>> > the latter is less intrusive, but I might be wrong.
>> >
>> > Opinions?
>>
>> /me votes #2, I think the example in the reply is a false one, an always
>> running task will/should ramp up the cpufreq and get us at full speed
>> (and yes I'm aware of the case where you're memory bound and raising the
>> cpu freq isn't going to actually improve performance, but I'm not sure
>> we want to get/be that smart, esp. at this stage).
>
> Okay, and agreed that memory bound task smarts are out of scope for the
> time being.
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
On 2 October 2014 22:34, Peter Zijlstra <[email protected]> wrote:
> On Thu, Sep 25, 2014 at 06:23:43PM +0100, Morten Rasmussen wrote:
>
>> > Why haven't you used arch_scale_freq_capacity which has a similar
>> > purpose in scaling the CPU capacity except the additional sched_domain
>> > pointer argument ?
>>
>> To be honest I'm not happy with introducing another arch-function
>> either and I'm happy to change that. It wasn't really clear to me which
>> functions that would remain after your cpu_capacity rework patches, so I
>> added this one. Now that we have most of the patches for capacity
>> scaling and scale-invariant load-tracking on the table I think we have a
>> better chance of figuring out which ones are needed and exactly how they
>> are supposed to work.
>>
>> arch_scale_load_capacity() compensates for both frequency scaling and
>> micro-architectural differences, while arch_scale_freq_capacity() only
>> for frequency. As long as we can use arch_scale_cpu_capacity() to
>> provide the micro-architecture scaling we can just do the scaling in two
>> operations rather than one similar to how it is done for capacity in
>> update_cpu_capacity(). I can fix that in the next version. It will cost
>> an extra function call and multiplication though.
>>
>> To make sure that runnable_avg_{sum, period} are still bounded by
>> LOAD_AVG_MAX, arch_scale_{cpu,freq}_capacity() must both return a factor
>> in the range 0..SCHED_CAPACITY_SCALE.
>
> I would certainly like some words in the Changelog on how and that the
> math is still free of overflows. Clearly you've thought about it, so
> please feel free to elucidate the rest of us :-)
>
>> > If we take the example of an always running task, its runnable_avg_sum
>> > should stay at the LOAD_AVG_MAX value whatever the frequency of the
>> > CPU on which it runs. But your change links the max value of
>> > runnable_avg_sum with the current frequency of the CPU so an always
>> > running task will have a load contribution of 25%
>> > your proposed scaling is fine with usage_avg_sum which reflects the
>> > effective running time on the CPU but the runnable_avg_sum should be
>> > able to reach LOAD_AVG_MAX whatever the current frequency is
>>
>> I don't think it makes sense to scale one metric and not the other. You
>> will end up with two very different (potentially opposite) views of the
>> cpu load/utilization situation in many scenarios. As I see it,
>> scale-invariance and load-balancing with scale-invariance present can be
>> done in two ways:
>>
>> 1. Leave runnable_avg_sum unscaled and scale running_avg_sum.
>> se->avg.load_avg_contrib will remain unscaled and so will
>> cfs_rq->runnable_load_avg, cfs_rq->blocked_load_avg, and
>> weighted_cpuload(). Essentially all the existing load-balancing code
>> will continue to use unscaled load. When we want to improve cpu
>> utilization and energy-awareness we will have to bypass most of this
>> code as it is likely to lead us on the wrong direction since it has a
>> potentially wrong view of the cpu load due to the lack of
>> scale-invariance.
>>
>> 2. Scale both runnable_avg_sum and running_avg_sum. All existing load
>> metrics including weighted_cpuload() are scaled and thus more accurate.
>> The difference between se->avg.load_avg_contrib and
>> se->avg.usage_avg_contrib is the priority scaling and whether or not
>> runqueue waiting time is counted. se->avg.load_avg_contrib can only
>> reach se->load.weight when running on the fastest cpu at the highest
>> frequency, but it is now scale-invariant so we have much better idea
>> about how much load we are pulling when load-balancing two cpus running
>> at different frequencies. The load-balance code-path still has to be
>> audited to see if anything blows up due to the scaling. I haven't
>> finished doing that yet. This patch set doesn't include patches to
>> address such issues (yet). IMHO, by scaling runnable_avg_sum we can more
>> easily make the existing load-balancing code do the right thing.
>>
>> For both options we have to go through the existing load-balancing code
>> to either change it to use the scale-invariant metric (running_avg_sum)
>> when appropriate or to fix bits that don't work properly with a
>> scale-invariant runnable_avg_sum and reuse the existing code. I think
>> the latter is less intrusive, but I might be wrong.
>>
>> Opinions?
>
> /me votes #2, I think the example in the reply is a false one, an always
> running task will/should ramp up the cpufreq and get us at full speed
I have in mind some system where the max achievable freq of a core
depends of how many cores are running simultaneously because of some
HW constraint like max current. In this case, the CPU might not reach
max frequency even with an always running task.
Then, beside frequency scaling, their is the uarch invariance that is
introduced by patch 4 that will generate similar behavior of the load.
> (and yes I'm aware of the case where you're memory bound and raising the
> cpu freq isn't going to actually improve performance, but I'm not sure
> we want to get/be that smart, esp. at this stage).
On Wed, Oct 08, 2014 at 12:21:45PM +0100, Vincent Guittot wrote:
> On 8 October 2014 13:00, Morten Rasmussen <[email protected]> wrote:
> > On Thu, Oct 02, 2014 at 09:34:28PM +0100, Peter Zijlstra wrote:
> >> On Thu, Sep 25, 2014 at 06:23:43PM +0100, Morten Rasmussen wrote:
> >>
> >> > > Why haven't you used arch_scale_freq_capacity which has a similar
> >> > > purpose in scaling the CPU capacity except the additional sched_domain
> >> > > pointer argument ?
> >> >
> >> > To be honest I'm not happy with introducing another arch-function
> >> > either and I'm happy to change that. It wasn't really clear to me which
> >> > functions that would remain after your cpu_capacity rework patches, so I
> >> > added this one. Now that we have most of the patches for capacity
> >> > scaling and scale-invariant load-tracking on the table I think we have a
> >> > better chance of figuring out which ones are needed and exactly how they
> >> > are supposed to work.
> >> >
> >> > arch_scale_load_capacity() compensates for both frequency scaling and
> >> > micro-architectural differences, while arch_scale_freq_capacity() only
> >> > for frequency. As long as we can use arch_scale_cpu_capacity() to
> >> > provide the micro-architecture scaling we can just do the scaling in two
> >> > operations rather than one similar to how it is done for capacity in
> >> > update_cpu_capacity(). I can fix that in the next version. It will cost
> >> > an extra function call and multiplication though.
> >> >
> >> > To make sure that runnable_avg_{sum, period} are still bounded by
> >> > LOAD_AVG_MAX, arch_scale_{cpu,freq}_capacity() must both return a factor
> >> > in the range 0..SCHED_CAPACITY_SCALE.
> >>
> >> I would certainly like some words in the Changelog on how and that the
> >> math is still free of overflows. Clearly you've thought about it, so
> >> please feel free to elucidate the rest of us :-)
> >
> > Sure. The easiest way to avoid introducing overflows is to ensure that
> > we always scale by a factor >= 1.0. That should be true as long as
> > arch_scale_{cpu,freq}_capacity() never returns anything greater than
> > SCHED_CAPACITY_SCALE (= 1024 = 1.0).
>
> the current ARM arch_scale_cpu is in the range [1536..0] which is free
> of overflow AFAICT
If I'm not mistaken, that will cause an overflow in
__update_task_entity_contrib():
static inline void __update_task_entity_contrib(struct sched_entity *se)
{
u32 contrib;
/* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
contrib /= (se->avg.avg_period + 1);
se->avg.load_avg_contrib = scale_load(contrib);
}
With arch_scale_cpu_capacity() > 1024 se->avg.runnable_avg_sum is no
longer bounded by LOAD_AVG_MAX = 47742. scale_load_down(se->load.weight)
== se->load.weight =< 88761.
47742 * 88761 = 4237627662 (2^32 = 4294967296)
To avoid overflow se->avg.runnable_avg_sum must be less than 2^32/88761
= 48388, which means that arch_scale_cpu_capacity() must be in the range
0..48388*1024/47742 = 0..1037.
I also think it is easier to have a fixed defined max scaling factor,
but that might just be me.
Regarding the ARM arch_scale_cpu_capacity() implementation, I think that
can be changed to fit the 0..1024 range easily. Currently, it will only
report a non-default (1024) capacity for big.LITTLE systems and actually
enabling it (requires a certain property to be set in device tree) leads
to broken load-balancing decisions. We have discussed that several times
in the past. I wouldn't recommend enabling it until the load-balance
code can deal with big.LITTLE compute capacities correctly. This is also
why it isn't implemented by ARM64.
On Wed, Oct 08, 2014 at 12:38:40PM +0100, Vincent Guittot wrote:
> On 2 October 2014 22:34, Peter Zijlstra <[email protected]> wrote:
> > On Thu, Sep 25, 2014 at 06:23:43PM +0100, Morten Rasmussen wrote:
> >
> >> > Why haven't you used arch_scale_freq_capacity which has a similar
> >> > purpose in scaling the CPU capacity except the additional sched_domain
> >> > pointer argument ?
> >>
> >> To be honest I'm not happy with introducing another arch-function
> >> either and I'm happy to change that. It wasn't really clear to me which
> >> functions that would remain after your cpu_capacity rework patches, so I
> >> added this one. Now that we have most of the patches for capacity
> >> scaling and scale-invariant load-tracking on the table I think we have a
> >> better chance of figuring out which ones are needed and exactly how they
> >> are supposed to work.
> >>
> >> arch_scale_load_capacity() compensates for both frequency scaling and
> >> micro-architectural differences, while arch_scale_freq_capacity() only
> >> for frequency. As long as we can use arch_scale_cpu_capacity() to
> >> provide the micro-architecture scaling we can just do the scaling in two
> >> operations rather than one similar to how it is done for capacity in
> >> update_cpu_capacity(). I can fix that in the next version. It will cost
> >> an extra function call and multiplication though.
> >>
> >> To make sure that runnable_avg_{sum, period} are still bounded by
> >> LOAD_AVG_MAX, arch_scale_{cpu,freq}_capacity() must both return a factor
> >> in the range 0..SCHED_CAPACITY_SCALE.
> >
> > I would certainly like some words in the Changelog on how and that the
> > math is still free of overflows. Clearly you've thought about it, so
> > please feel free to elucidate the rest of us :-)
> >
> >> > If we take the example of an always running task, its runnable_avg_sum
> >> > should stay at the LOAD_AVG_MAX value whatever the frequency of the
> >> > CPU on which it runs. But your change links the max value of
> >> > runnable_avg_sum with the current frequency of the CPU so an always
> >> > running task will have a load contribution of 25%
> >> > your proposed scaling is fine with usage_avg_sum which reflects the
> >> > effective running time on the CPU but the runnable_avg_sum should be
> >> > able to reach LOAD_AVG_MAX whatever the current frequency is
> >>
> >> I don't think it makes sense to scale one metric and not the other. You
> >> will end up with two very different (potentially opposite) views of the
> >> cpu load/utilization situation in many scenarios. As I see it,
> >> scale-invariance and load-balancing with scale-invariance present can be
> >> done in two ways:
> >>
> >> 1. Leave runnable_avg_sum unscaled and scale running_avg_sum.
> >> se->avg.load_avg_contrib will remain unscaled and so will
> >> cfs_rq->runnable_load_avg, cfs_rq->blocked_load_avg, and
> >> weighted_cpuload(). Essentially all the existing load-balancing code
> >> will continue to use unscaled load. When we want to improve cpu
> >> utilization and energy-awareness we will have to bypass most of this
> >> code as it is likely to lead us on the wrong direction since it has a
> >> potentially wrong view of the cpu load due to the lack of
> >> scale-invariance.
> >>
> >> 2. Scale both runnable_avg_sum and running_avg_sum. All existing load
> >> metrics including weighted_cpuload() are scaled and thus more accurate.
> >> The difference between se->avg.load_avg_contrib and
> >> se->avg.usage_avg_contrib is the priority scaling and whether or not
> >> runqueue waiting time is counted. se->avg.load_avg_contrib can only
> >> reach se->load.weight when running on the fastest cpu at the highest
> >> frequency, but it is now scale-invariant so we have much better idea
> >> about how much load we are pulling when load-balancing two cpus running
> >> at different frequencies. The load-balance code-path still has to be
> >> audited to see if anything blows up due to the scaling. I haven't
> >> finished doing that yet. This patch set doesn't include patches to
> >> address such issues (yet). IMHO, by scaling runnable_avg_sum we can more
> >> easily make the existing load-balancing code do the right thing.
> >>
> >> For both options we have to go through the existing load-balancing code
> >> to either change it to use the scale-invariant metric (running_avg_sum)
> >> when appropriate or to fix bits that don't work properly with a
> >> scale-invariant runnable_avg_sum and reuse the existing code. I think
> >> the latter is less intrusive, but I might be wrong.
> >>
> >> Opinions?
> >
> > /me votes #2, I think the example in the reply is a false one, an always
> > running task will/should ramp up the cpufreq and get us at full speed
>
> I have in mind some system where the max achievable freq of a core
> depends of how many cores are running simultaneously because of some
> HW constraint like max current. In this case, the CPU might not reach
> max frequency even with an always running task.
If we compare scale-invariant task load to the current frequency scaled
compute capacity of the cpu when making load-balancing decisions as I
described in my other reply that shouldn't be a problem.
> Then, beside frequency scaling, their is the uarch invariance that is
> introduced by patch 4 that will generate similar behavior of the load.
I don't quite follow. When we make task load frequency and uarch
invariant, we must scale compute capacity accordingly. So compute
capacity is bigger for big cores and smaller for little cores.
On 8 October 2014 15:53, Morten Rasmussen <[email protected]> wrote:
> On Wed, Oct 08, 2014 at 12:21:45PM +0100, Vincent Guittot wrote:
>> On 8 October 2014 13:00, Morten Rasmussen <[email protected]> wrote:
>> >
>> > Sure. The easiest way to avoid introducing overflows is to ensure that
>> > we always scale by a factor >= 1.0. That should be true as long as
>> > arch_scale_{cpu,freq}_capacity() never returns anything greater than
>> > SCHED_CAPACITY_SCALE (= 1024 = 1.0).
>>
>> the current ARM arch_scale_cpu is in the range [1536..0] which is free
>> of overflow AFAICT
>
> If I'm not mistaken, that will cause an overflow in
> __update_task_entity_contrib():
>
> static inline void __update_task_entity_contrib(struct sched_entity *se)
> {
> u32 contrib;
> /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
> contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
> contrib /= (se->avg.avg_period + 1);
> se->avg.load_avg_contrib = scale_load(contrib);
> }
>
> With arch_scale_cpu_capacity() > 1024 se->avg.runnable_avg_sum is no
> longer bounded by LOAD_AVG_MAX = 47742. scale_load_down(se->load.weight)
> == se->load.weight =< 88761.
>
> 47742 * 88761 = 4237627662 (2^32 = 4294967296)
>
> To avoid overflow se->avg.runnable_avg_sum must be less than 2^32/88761
> = 48388, which means that arch_scale_cpu_capacity() must be in the range
> 0..48388*1024/47742 = 0..1037.
>
> I also think it is easier to have a fixed defined max scaling factor,
> but that might just be me.
OK, overflow comes with adding uarch invariance into runnable load average
>
> Regarding the ARM arch_scale_cpu_capacity() implementation, I think that
> can be changed to fit the 0..1024 range easily. Currently, it will only
> report a non-default (1024) capacity for big.LITTLE systems and actually
> enabling it (requires a certain property to be set in device tree) leads
> to broken load-balancing decisions. We have discussed that several times
Only the 1 task per CPU is broken but in the other hand, it better
handles the overload use case where we have more tasks than CPU and
other middle range use case by putting more task on big cluster.
> in the past. I wouldn't recommend enabling it until the load-balance
> code can deal with big.LITTLE compute capacities correctly. This is also
> why it isn't implemented by ARM64.
On Wed, Oct 08, 2014 at 03:08:04PM +0100, Vincent Guittot wrote:
> On 8 October 2014 15:53, Morten Rasmussen <[email protected]> wrote:
> > On Wed, Oct 08, 2014 at 12:21:45PM +0100, Vincent Guittot wrote:
> >> On 8 October 2014 13:00, Morten Rasmussen <[email protected]> wrote:
>
> >> >
> >> > Sure. The easiest way to avoid introducing overflows is to ensure that
> >> > we always scale by a factor >= 1.0. That should be true as long as
> >> > arch_scale_{cpu,freq}_capacity() never returns anything greater than
> >> > SCHED_CAPACITY_SCALE (= 1024 = 1.0).
> >>
> >> the current ARM arch_scale_cpu is in the range [1536..0] which is free
> >> of overflow AFAICT
> >
> > If I'm not mistaken, that will cause an overflow in
> > __update_task_entity_contrib():
> >
> > static inline void __update_task_entity_contrib(struct sched_entity *se)
> > {
> > u32 contrib;
> > /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
> > contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
> > contrib /= (se->avg.avg_period + 1);
> > se->avg.load_avg_contrib = scale_load(contrib);
> > }
> >
> > With arch_scale_cpu_capacity() > 1024 se->avg.runnable_avg_sum is no
> > longer bounded by LOAD_AVG_MAX = 47742. scale_load_down(se->load.weight)
> > == se->load.weight =< 88761.
> >
> > 47742 * 88761 = 4237627662 (2^32 = 4294967296)
> >
> > To avoid overflow se->avg.runnable_avg_sum must be less than 2^32/88761
> > = 48388, which means that arch_scale_cpu_capacity() must be in the range
> > 0..48388*1024/47742 = 0..1037.
> >
> > I also think it is easier to have a fixed defined max scaling factor,
> > but that might just be me.
>
> OK, overflow comes with adding uarch invariance into runnable load average
>
> >
> > Regarding the ARM arch_scale_cpu_capacity() implementation, I think that
> > can be changed to fit the 0..1024 range easily. Currently, it will only
> > report a non-default (1024) capacity for big.LITTLE systems and actually
> > enabling it (requires a certain property to be set in device tree) leads
> > to broken load-balancing decisions. We have discussed that several times
>
> Only the 1 task per CPU is broken but in the other hand, it better
> handles the overload use case where we have more tasks than CPU and
> other middle range use case by putting more task on big cluster.
Yes, agreed. My point was just to say that it shouldn't cause a lot of
harm changing the range of arch_scale_cpu_capacity() for ARM. We need to
fix things anyway.
On Wed, Oct 08, 2014 at 01:38:40PM +0200, Vincent Guittot wrote:
> I have in mind some system where the max achievable freq of a core
> depends of how many cores are running simultaneously because of some
> HW constraint like max current. In this case, the CPU might not reach
> max frequency even with an always running task.
> Then, beside frequency scaling, their is the uarch invariance that is
> introduced by patch 4 that will generate similar behavior of the load.
This is a 'common' issue. x86 and powerpc also suffer this. It can be
the result of either thermal or power thresholds.