Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1220267 > unrolled thread

Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Dietmar Eggemann <dietmar.eggemann@arm.com> - 2015-09-07 17:40 +0200
    Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Vincent Guittot <vincent.guittot@linaro.org> - 2015-09-07 18:30 +0200
      Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Dietmar Eggemann <dietmar.eggemann@arm.com> - 2015-09-07 21:00 +0200
        Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-07 21:50 +0200
          Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Dietmar Eggemann <dietmar.eggemann@arm.com> - 2015-09-08 14:50 +0200
        Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Vincent Guittot <vincent.guittot@linaro.org> - 2015-09-08 09:30 +0200
          Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-08 14:30 +0200
            Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-08 15:00 +0200
              Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Vincent Guittot <vincent.guittot@linaro.org> - 2015-09-08 16:10 +0200
                Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-08 16:40 +0200
                  Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Vincent Guittot <vincent.guittot@linaro.org> - 2015-09-08 16:50 +0200
              Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-08 16:30 +0200
                Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-08 17:40 +0200
                  Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig bsegall@google.com - 2015-09-10 00:30 +0200
                    Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-10 13:10 +0200
                      Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Vincent Guittot <vincent.guittot@linaro.org> - 2015-09-10 13:20 +0200
                        Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-10 14:10 +0200
                          Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-11 10:40 +0200
                      Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig bsegall@google.com - 2015-09-10 19:30 +0200
                Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-08 18:50 +0200
                  Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-09 11:50 +0200
                  Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-09 11:50 +0200
                    Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-09 13:10 +0200
                      Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-11 19:20 +0200
                        Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-17 12:00 +0200
                        Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-17 12:50 +0200
                          Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-21 11:10 +0200
                            Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig bsegall@google.com - 2015-09-21 19:40 +0200
                              Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-22 09:30 +0200
                  Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Leo Yan <leo.yan@linaro.org> - 2015-09-11 09:50 +0200
                    Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-11 12:00 +0200
                      Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Leo Yan <leo.yan@linaro.org> - 2015-09-11 16:20 +0200
              Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-10 05:00 +0200
                Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-10 12:10 +0200
            Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Vincent Guittot <vincent.guittot@linaro.org> - 2015-09-08 15:50 +0200
              Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-08 16:20 +0200
                Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Vincent Guittot <vincent.guittot@linaro.org> - 2015-09-08 17:20 +0200
          Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Dietmar Eggemann <dietmar.eggemann@arm.com> - 2015-09-08 15:00 +0200
            Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig Vincent Guittot <vincent.guittot@linaro.org> - 2015-09-08 16:10 +0200
              Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Dietmar Eggemann <dietmar.eggemann@arm.com> - 2015-09-08 16:30 +0200
            Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-10 06:10 +0200
              Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-10 12:10 +0200
                Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-11 10:20 +0200
                  Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-11 12:30 +0200
                    Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig bsegall@google.com - 2015-09-11 19:10 +0200
                      Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-12 04:20 +0200
                        Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig bsegall@google.com - 2015-09-14 19:40 +0200
                      Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-14 15:00 +0200
                        Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig bsegall@google.com - 2015-09-14 19:40 +0200
                          Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-15 08:50 +0200
                            Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig bsegall@google.com - 2015-09-15 19:20 +0200
                              Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-16 04:30 +0200
                                Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig bsegall@google.com - 2015-09-16 19:10 +0200
                                  Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Yuyang Du <yuyang.du@intel.com> - 2015-09-17 12:30 +0200
                          Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Morten Rasmussen <morten.rasmussen@arm.com> - 2015-09-15 10:40 +0200
                          Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-16 17:50 +0200
        Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by  capacity_orig Peter Zijlstra <peterz@infradead.org> - 2015-09-08 13:50 +0200
    [tip:sched/core] sched/fair:   Get rid of scaling utilization by capacity_orig tip-bot for Dietmar Eggemann <tipbot@zytor.com> - 2015-09-13 13:10 +0200

Page 1 of 3  [1] 2 3  Next page →

#1220267 — Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

On 04/09/15 00:51, Steve Muckle wrote:
> Hi Morten, Dietmar,
> 
> On 08/14/2015 09:23 AM, Morten Rasmussen wrote:
> ...
>> + * cfs_rq.avg.util_avg is the sum of running time of runnable tasks plus the
>> + * recent utilization of currently non-runnable tasks on a CPU. It represents
>> + * the amount of utilization of a CPU in the range [0..capacity_orig] where
> 
> I see util_sum is scaled by SCHED_LOAD_SHIFT at the end of
> __update_load_avg(). If there is now an assumption that util_avg may be
> used directly as a capacity value, should it be changed to
> SCHED_CAPACITY_SHIFT? These are equal right now, not sure if they will
> always be or if they can be combined.

You're referring to the code line

2647   sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;

in __update_load_avg()?

Here we actually scale by 'SCHED_LOAD_SCALE/LOAD_AVG_MAX' so both values are
load related.

LOAD (UTIL) and CAPACITY have the same SCALE and SHIFT values because
SCHED_LOAD_RESOLUTION is always defined to 0. scale_load() and
scale_load_down() are also NOPs so this area is probably 
worth a separate clean-up.
Beyond that, I'm not sure if the current functionality is
broken if we use different SCALE and SHIFT values for LOAD and CAPACITY?

> 
>> + * capacity_orig is the cpu_capacity available at * the highest frequency
> 
> spurious *
> 
> thanks,
> Steve
> 

Fixed.

Thanks, 

-- Dietmar

-- >8 --

From: Dietmar Eggemann <dietmar.eggemann@arm.com>
Date: Fri, 14 Aug 2015 17:23:13 +0100
Subject: [PATCH] sched/fair: Get rid of scaling utilization by capacity_orig

Utilization is currently scaled by capacity_orig, but since we now have
frequency and cpu invariant cfs_rq.avg.util_avg, frequency and cpu scaling
now happens as part of the utilization tracking itself.
So cfs_rq.avg.util_avg should no longer be scaled in cpu_util().

Cc: Ingo Molnar <mingo@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
---
 kernel/sched/fair.c | 38 ++++++++++++++++++++++----------------
 1 file changed, 22 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 2074d45a67c2..a73ece2372f5 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4824,33 +4824,39 @@ static int select_idle_sibling(struct task_struct *p, int target)
 done:
 	return target;
 }
+
 /*
  * cpu_util returns the amount of capacity of a CPU that is used by CFS
  * tasks. The unit of the return value must be the one of capacity so we can
  * compare the utilization with the capacity of the CPU that is available for
  * CFS task (ie cpu_capacity).
- * cfs.avg.util_avg is the sum of running time of runnable tasks on a
- * CPU. It represents the amount of utilization of a CPU in the range
- * [0..SCHED_LOAD_SCALE]. The utilization of a CPU can't be higher than the
- * full capacity of the CPU because it's about the running time on this CPU.
- * Nevertheless, cfs.avg.util_avg can be higher than SCHED_LOAD_SCALE
- * because of unfortunate rounding in util_avg or just
- * after migrating tasks until the average stabilizes with the new running
- * time. So we need to check that the utilization stays into the range
- * [0..cpu_capacity_orig] and cap if necessary.
- * Without capping the utilization, a group could be seen as overloaded (CPU0
- * utilization at 121% + CPU1 utilization at 80%) whereas CPU1 has 20% of
- * available capacity.
+ *
+ * cfs_rq.avg.util_avg is the sum of running time of runnable tasks plus the
+ * recent utilization of currently non-runnable tasks on a CPU. It represents
+ * the amount of utilization of a CPU in the range [0..capacity_orig] where
+ * capacity_orig is the cpu_capacity available at the highest frequency
+ * (arch_scale_freq_capacity()).
+ * The utilization of a CPU converges towards a sum equal to or less than the
+ * current capacity (capacity_curr <= capacity_orig) of the CPU because it is
+ * the running time on this CPU scaled by capacity_curr.
+ *
+ * Nevertheless, cfs_rq.avg.util_avg can be higher than capacity_curr or even
+ * higher than capacity_orig because of unfortunate rounding in
+ * cfs.avg.util_avg or just after migrating tasks and new task wakeups until
+ * the average stabilizes with the new running time. We need to check that the
+ * utilization stays within the range of [0..capacity_orig] and cap it if
+ * necessary. Without utilization capping, a group could be seen as overloaded
+ * (CPU0 utilization at 121% + CPU1 utilization at 80%) whereas CPU1 has 20% of
+ * available capacity. We allow utilization to overshoot capacity_curr (but not
+ * capacity_orig) as it useful for predicting the capacity required after task
+ * migrations (scheduler-driven DVFS).
  */
 static int cpu_util(int cpu)
 {
 	unsigned long util = cpu_rq(cpu)->cfs.avg.util_avg;
 	unsigned long capacity = capacity_orig_of(cpu);
 
-	if (util >= SCHED_LOAD_SCALE)
-		return capacity;
-
-	return (util * capacity) >> SCHED_LOAD_SHIFT;
+	return (util >= capacity) ? capacity : util;
 }
 
 /*
-- 
1.9.1

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

[toc] | [next] | [standalone]

#1220324 — Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

On 7 September 2015 at 17:37, Dietmar Eggemann <dietmar.eggemann@arm.com> wrote:
> On 04/09/15 00:51, Steve Muckle wrote:
>> Hi Morten, Dietmar,
>>
>> On 08/14/2015 09:23 AM, Morten Rasmussen wrote:
>> ...
>>> + * cfs_rq.avg.util_avg is the sum of running time of runnable tasks plus the
>>> + * recent utilization of currently non-runnable tasks on a CPU. It represents
>>> + * the amount of utilization of a CPU in the range [0..capacity_orig] where
>>
>> I see util_sum is scaled by SCHED_LOAD_SHIFT at the end of
>> __update_load_avg(). If there is now an assumption that util_avg may be
>> used directly as a capacity value, should it be changed to
>> SCHED_CAPACITY_SHIFT? These are equal right now, not sure if they will
>> always be or if they can be combined.
>
> You're referring to the code line
>
> 2647   sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
>
> in __update_load_avg()?
>
> Here we actually scale by 'SCHED_LOAD_SCALE/LOAD_AVG_MAX' so both values are
> load related.

I agree with Steve that there is an issue from a unit point of view

sa->util_sum and LOAD_AVG_MAX have the same unit so sa->util_avg is a
load because of << SCHED_LOAD_SHIFT)

Before this patch , the translation from load to capacity unit was
done in get_cpu_usage with "* capacity) >> SCHED_LOAD_SHIFT"

So you still have to change the unit from load to capacity with a "/
SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE" somewhere.

sa->util_avg = ((sa->util_sum << SCHED_LOAD_SHIFT) /SCHED_LOAD_SCALE *
SCHED_CAPACITY_SCALE / LOAD_AVG_MAX = (sa->util_sum <<
SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;


Regards,
Vincent


>
> LOAD (UTIL) and CAPACITY have the same SCALE and SHIFT values because
> SCHED_LOAD_RESOLUTION is always defined to 0. scale_load() and
> scale_load_down() are also NOPs so this area is probably
> worth a separate clean-up.
> Beyond that, I'm not sure if the current functionality is
> broken if we use different SCALE and SHIFT values for LOAD and CAPACITY?
>
>>
>>> + * capacity_orig is the cpu_capacity available at * the highest frequency
>>
>> spurious *
>>
>> thanks,
>> Steve
>>
>
> Fixed.
>
> Thanks,
>
> -- Dietmar
>
> -- >8 --
>
> From: Dietmar Eggemann <dietmar.eggemann@arm.com>
> Date: Fri, 14 Aug 2015 17:23:13 +0100
> Subject: [PATCH] sched/fair: Get rid of scaling utilization by capacity_orig
>
> Utilization is currently scaled by capacity_orig, but since we now have
> frequency and cpu invariant cfs_rq.avg.util_avg, frequency and cpu scaling
> now happens as part of the utilization tracking itself.
> So cfs_rq.avg.util_avg should no longer be scaled in cpu_util().
>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Signed-off-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
> Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
> ---
>  kernel/sched/fair.c | 38 ++++++++++++++++++++++----------------
>  1 file changed, 22 insertions(+), 16 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 2074d45a67c2..a73ece2372f5 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4824,33 +4824,39 @@ static int select_idle_sibling(struct task_struct *p, int target)
>  done:
>         return target;
>  }
> +
>  /*
>   * cpu_util returns the amount of capacity of a CPU that is used by CFS
>   * tasks. The unit of the return value must be the one of capacity so we can
>   * compare the utilization with the capacity of the CPU that is available for
>   * CFS task (ie cpu_capacity).
> - * cfs.avg.util_avg is the sum of running time of runnable tasks on a
> - * CPU. It represents the amount of utilization of a CPU in the range
> - * [0..SCHED_LOAD_SCALE]. The utilization of a CPU can't be higher than the
> - * full capacity of the CPU because it's about the running time on this CPU.
> - * Nevertheless, cfs.avg.util_avg can be higher than SCHED_LOAD_SCALE
> - * because of unfortunate rounding in util_avg or just
> - * after migrating tasks until the average stabilizes with the new running
> - * time. So we need to check that the utilization stays into the range
> - * [0..cpu_capacity_orig] and cap if necessary.
> - * Without capping the utilization, a group could be seen as overloaded (CPU0
> - * utilization at 121% + CPU1 utilization at 80%) whereas CPU1 has 20% of
> - * available capacity.
> + *
> + * cfs_rq.avg.util_avg is the sum of running time of runnable tasks plus the
> + * recent utilization of currently non-runnable tasks on a CPU. It represents
> + * the amount of utilization of a CPU in the range [0..capacity_orig] where
> + * capacity_orig is the cpu_capacity available at the highest frequency
> + * (arch_scale_freq_capacity()).
> + * The utilization of a CPU converges towards a sum equal to or less than the
> + * current capacity (capacity_curr <= capacity_orig) of the CPU because it is
> + * the running time on this CPU scaled by capacity_curr.
> + *
> + * Nevertheless, cfs_rq.avg.util_avg can be higher than capacity_curr or even
> + * higher than capacity_orig because of unfortunate rounding in
> + * cfs.avg.util_avg or just after migrating tasks and new task wakeups until
> + * the average stabilizes with the new running time. We need to check that the
> + * utilization stays within the range of [0..capacity_orig] and cap it if
> + * necessary. Without utilization capping, a group could be seen as overloaded
> + * (CPU0 utilization at 121% + CPU1 utilization at 80%) whereas CPU1 has 20% of
> + * available capacity. We allow utilization to overshoot capacity_curr (but not
> + * capacity_orig) as it useful for predicting the capacity required after task
> + * migrations (scheduler-driven DVFS).
>   */
>  static int cpu_util(int cpu)
>  {
>         unsigned long util = cpu_rq(cpu)->cfs.avg.util_avg;
>         unsigned long capacity = capacity_orig_of(cpu);
>
> -       if (util >= SCHED_LOAD_SCALE)
> -               return capacity;
> -
> -       return (util * capacity) >> SCHED_LOAD_SHIFT;
> +       return (util >= capacity) ? capacity : util;
>  }
>
>  /*
> --
> 1.9.1
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220360

On 07/09/15 17:21, Vincent Guittot wrote:
> On 7 September 2015 at 17:37, Dietmar Eggemann <dietmar.eggemann@arm.com> wrote:
>> On 04/09/15 00:51, Steve Muckle wrote:
>>> Hi Morten, Dietmar,
>>>
>>> On 08/14/2015 09:23 AM, Morten Rasmussen wrote:
>>> ...
>>>> + * cfs_rq.avg.util_avg is the sum of running time of runnable tasks plus the
>>>> + * recent utilization of currently non-runnable tasks on a CPU. It represents
>>>> + * the amount of utilization of a CPU in the range [0..capacity_orig] where
>>>
>>> I see util_sum is scaled by SCHED_LOAD_SHIFT at the end of
>>> __update_load_avg(). If there is now an assumption that util_avg may be
>>> used directly as a capacity value, should it be changed to
>>> SCHED_CAPACITY_SHIFT? These are equal right now, not sure if they will
>>> always be or if they can be combined.
>>
>> You're referring to the code line
>>
>> 2647   sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
>>
>> in __update_load_avg()?
>>
>> Here we actually scale by 'SCHED_LOAD_SCALE/LOAD_AVG_MAX' so both values are
>> load related.
> 
> I agree with Steve that there is an issue from a unit point of view
> 
> sa->util_sum and LOAD_AVG_MAX have the same unit so sa->util_avg is a
> load because of << SCHED_LOAD_SHIFT)
> 
> Before this patch , the translation from load to capacity unit was
> done in get_cpu_usage with "* capacity) >> SCHED_LOAD_SHIFT"
> 
> So you still have to change the unit from load to capacity with a "/
> SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE" somewhere.
> 
> sa->util_avg = ((sa->util_sum << SCHED_LOAD_SHIFT) /SCHED_LOAD_SCALE *
> SCHED_CAPACITY_SCALE / LOAD_AVG_MAX = (sa->util_sum <<
> SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;

I see the point but IMHO this will only be necessary if the SCHED_LOAD_RESOLUTION
stuff gets re-enabled again.

It's not really about utilization or capacity units but rather about using the same
SCALE/SHIFT values for both sides, right?

I always thought that scale_load_down() takes care of that.

So shouldn't:

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 3445d2fb38f4..b80f799aface 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2644,7 +2644,7 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
                        cfs_rq->runnable_load_avg =
                                div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
                }
-               sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
+               sa->util_avg = (sa->util_sum * scale_load_down(SCHED_LOAD_SCALE)) / LOAD_AVG_MAX;
        }
 
        return decayed;

fix that issue in case SCHED_LOAD_RESOLUTION != 0 ?

I would vote for removing this SCHED_LOAD_RESOLUTION thing completely so that we can
assume that load/util and capacity are always using 1024/10.

Cheers,

-- Dietmar

> 
> 
> Regards,
> Vincent
> 
> 
>>
>> LOAD (UTIL) and CAPACITY have the same SCALE and SHIFT values because
>> SCHED_LOAD_RESOLUTION is always defined to 0. scale_load() and
>> scale_load_down() are also NOPs so this area is probably
>> worth a separate clean-up.
>> Beyond that, I'm not sure if the current functionality is
>> broken if we use different SCALE and SHIFT values for LOAD and CAPACITY?
>>

[...]

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

[toc] | [prev] | [next] | [standalone]

#1220366

On Mon, Sep 07, 2015 at 07:54:18PM +0100, Dietmar Eggemann wrote:
> I would vote for removing this SCHED_LOAD_RESOLUTION thing completely so that we can
> assume that load/util and capacity are always using 1024/10.

Ha!, I just requested Google look into moving it to 20 again ;-)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220756

On 07/09/15 20:47, Peter Zijlstra wrote:
> On Mon, Sep 07, 2015 at 07:54:18PM +0100, Dietmar Eggemann wrote:
>> I would vote for removing this SCHED_LOAD_RESOLUTION thing completely so that we can
>> assume that load/util and capacity are always using 1024/10.
> 
> Ha!, I just requested Google look into moving it to 20 again ;-)
> 

In this case Steve and Vincent have a point here.

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

[toc] | [prev] | [next] | [standalone]

#1220545 — Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

On 7 September 2015 at 20:54, Dietmar Eggemann <dietmar.eggemann@arm.com> wrote:
> On 07/09/15 17:21, Vincent Guittot wrote:
>> On 7 September 2015 at 17:37, Dietmar Eggemann <dietmar.eggemann@arm.com> wrote:
>>> On 04/09/15 00:51, Steve Muckle wrote:
>>>> Hi Morten, Dietmar,
>>>>
>>>> On 08/14/2015 09:23 AM, Morten Rasmussen wrote:
>>>> ...
>>>>> + * cfs_rq.avg.util_avg is the sum of running time of runnable tasks plus the
>>>>> + * recent utilization of currently non-runnable tasks on a CPU. It represents
>>>>> + * the amount of utilization of a CPU in the range [0..capacity_orig] where
>>>>
>>>> I see util_sum is scaled by SCHED_LOAD_SHIFT at the end of
>>>> __update_load_avg(). If there is now an assumption that util_avg may be
>>>> used directly as a capacity value, should it be changed to
>>>> SCHED_CAPACITY_SHIFT? These are equal right now, not sure if they will
>>>> always be or if they can be combined.
>>>
>>> You're referring to the code line
>>>
>>> 2647   sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
>>>
>>> in __update_load_avg()?
>>>
>>> Here we actually scale by 'SCHED_LOAD_SCALE/LOAD_AVG_MAX' so both values are
>>> load related.
>>
>> I agree with Steve that there is an issue from a unit point of view
>>
>> sa->util_sum and LOAD_AVG_MAX have the same unit so sa->util_avg is a
>> load because of << SCHED_LOAD_SHIFT)
>>
>> Before this patch , the translation from load to capacity unit was
>> done in get_cpu_usage with "* capacity) >> SCHED_LOAD_SHIFT"
>>
>> So you still have to change the unit from load to capacity with a "/
>> SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE" somewhere.
>>
>> sa->util_avg = ((sa->util_sum << SCHED_LOAD_SHIFT) /SCHED_LOAD_SCALE *
>> SCHED_CAPACITY_SCALE / LOAD_AVG_MAX = (sa->util_sum <<
>> SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
>
> I see the point but IMHO this will only be necessary if the SCHED_LOAD_RESOLUTION
> stuff gets re-enabled again.
>
> It's not really about utilization or capacity units but rather about using the same
> SCALE/SHIFT values for both sides, right?

It's both a unit and a SCALE/SHIFT problem, SCHED_LOAD_SHIFT and
SCHED_CAPACITY_SHIFT are defined separately so we must be sure to
scale the value in the right range. In the case of cpu_usage which
returns sa->util_avg , it's the capacity range not the load range.

>
> I always thought that scale_load_down() takes care of that.

AFAIU, scale_load_down is a way to increase the resolution  of the
load not to move from load to capacity

>
> So shouldn't:
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 3445d2fb38f4..b80f799aface 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -2644,7 +2644,7 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
>                         cfs_rq->runnable_load_avg =
>                                 div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
>                 }
> -               sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
> +               sa->util_avg = (sa->util_sum * scale_load_down(SCHED_LOAD_SCALE)) / LOAD_AVG_MAX;
>         }
>
>         return decayed;
>
> fix that issue in case SCHED_LOAD_RESOLUTION != 0 ?


No, but
sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
will fix the unit issue.
I agree that i don't change the result because both SCHED_LOAD_SHIFT
and SCHED_CAPACITY_SHIFT are set to 10 but as mentioned above, they
are set separately so it can make the difference if someone change one
SHIFT value.

Regards,
Vincent

>
> I would vote for removing this SCHED_LOAD_RESOLUTION thing completely so that we can
> assume that load/util and capacity are always using 1024/10.
>
> Cheers,
>
> -- Dietmar
>
>>
>>
>> Regards,
>> Vincent
>>
>>
>>>
>>> LOAD (UTIL) and CAPACITY have the same SCALE and SHIFT values because
>>> SCHED_LOAD_RESOLUTION is always defined to 0. scale_load() and
>>> scale_load_down() are also NOPs so this area is probably
>>> worth a separate clean-up.
>>> Beyond that, I'm not sure if the current functionality is
>>> broken if we use different SCALE and SHIFT values for LOAD and CAPACITY?
>>>
>
> [...]
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220741

On Tue, Sep 08, 2015 at 09:22:05AM +0200, Vincent Guittot wrote:
> No, but
> sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
> will fix the unit issue.

Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.

And where load_sum already gets a factor 1024 from the weight
multiplication, util_sum does not get such a factor, and all the scaling
we do on it loose bits.

So at the moment we go compute the util_avg value, we need to inflate
util_sum with an extra factor 1024 in order to make it work.

And seeing that we do the shift up on sa->util_sum without consideration
of overflow, would it not make sense to add that factor before the
scaling and into the addition?

Now, given all that, units are a complete mess here, and I'd not mind
something like:

#if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != SCHED_CAPACITY_SHIFT
#error "something usefull"
#endif

somewhere near here.


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

[toc] | [prev] | [next] | [standalone]

#1220762

On Tue, Sep 08, 2015 at 02:26:06PM +0200, Peter Zijlstra wrote:
> On Tue, Sep 08, 2015 at 09:22:05AM +0200, Vincent Guittot wrote:
> > No, but
> > sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
> > will fix the unit issue.
> 
> Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
> 
> And where load_sum already gets a factor 1024 from the weight
> multiplication, util_sum does not get such a factor, and all the scaling
> we do on it loose bits.
> 
> So at the moment we go compute the util_avg value, we need to inflate
> util_sum with an extra factor 1024 in order to make it work.
> 
> And seeing that we do the shift up on sa->util_sum without consideration
> of overflow, would it not make sense to add that factor before the
> scaling and into the addition?
> 
> Now, given all that, units are a complete mess here, and I'd not mind
> something like:
> 
> #if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != SCHED_CAPACITY_SHIFT
> #error "something usefull"
> #endif
> 
> somewhere near here.

Something like teh below..

Another thing to ponder; the downside of scaled_delta_w is that its
fairly likely delta is small and you loose all bits, whereas the weight
is likely to be large can could loose a fwe bits without issue.

That is, in fixed point scaling like this, you want to start with the
biggest numbers, not the smallest, otherwise you loose too much.

The flip side is of course that now you can share a multiplcation.

--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -682,7 +682,7 @@ void init_entity_runnable_average(struct
 	sa->load_avg = scale_load_down(se->load.weight);
 	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
 	sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
-	sa->util_sum = LOAD_AVG_MAX;
+	sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
 	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
 }
 
@@ -2515,6 +2515,10 @@ static u32 __compute_runnable_contrib(u6
 	return contrib + runnable_avg_yN_sum[n];
 }
 
+#if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != 10 || SCHED_CAPACITY_SHIFT != 10
+#error "load tracking assumes 2^10 as unit"
+#endif
+
 #define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
 
 /*
@@ -2599,7 +2603,7 @@ __update_load_avg(u64 now, int cpu, stru
 			}
 		}
 		if (running)
-			sa->util_sum += cap_scale(scaled_delta_w, scale_cpu);
+			sa->util_sum += scaled_delta_w * scale_cpu;
 
 		delta -= delta_w;
 
@@ -2623,7 +2627,7 @@ __update_load_avg(u64 now, int cpu, stru
 				cfs_rq->runnable_load_sum += weight * contrib;
 		}
 		if (running)
-			sa->util_sum += cap_scale(contrib, scale_cpu);
+			sa->util_sum += contrib * scale_cpu;
 	}
 
 	/* Remainder of delta accrued against u_0` */
@@ -2634,7 +2638,7 @@ __update_load_avg(u64 now, int cpu, stru
 			cfs_rq->runnable_load_sum += weight * scaled_delta;
 	}
 	if (running)
-		sa->util_sum += cap_scale(scaled_delta, scale_cpu);
+		sa->util_sum += scaled_delta * scale_cpu;
 
 	sa->period_contrib += delta;
 
@@ -2644,7 +2648,7 @@ __update_load_avg(u64 now, int cpu, stru
 			cfs_rq->runnable_load_avg =
 				div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
 		}
-		sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
+		sa->util_avg = sa->util_sum / LOAD_AVG_MAX;
 	}
 
 	return decayed;
@@ -2686,8 +2690,7 @@ static inline int update_cfs_rq_load_avg
 	if (atomic_long_read(&cfs_rq->removed_util_avg)) {
 		long r = atomic_long_xchg(&cfs_rq->removed_util_avg, 0);
 		sa->util_avg = max_t(long, sa->util_avg - r, 0);
-		sa->util_sum = max_t(s32, sa->util_sum -
-			((r * LOAD_AVG_MAX) >> SCHED_LOAD_SHIFT), 0);
+		sa->util_sum = max_t(s32, sa->util_sum - r * LOAD_AVG_MAX, 0);
 	}
 
 	decayed = __update_load_avg(now, cpu_of(rq_of(cfs_rq)), sa,
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220820 — Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

On 8 September 2015 at 14:52, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Sep 08, 2015 at 02:26:06PM +0200, Peter Zijlstra wrote:
>> On Tue, Sep 08, 2015 at 09:22:05AM +0200, Vincent Guittot wrote:
>> > No, but
>> > sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
>> > will fix the unit issue.
>>
>> Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
>>
>> And where load_sum already gets a factor 1024 from the weight
>> multiplication, util_sum does not get such a factor, and all the scaling
>> we do on it loose bits.
>>
>> So at the moment we go compute the util_avg value, we need to inflate
>> util_sum with an extra factor 1024 in order to make it work.
>>
>> And seeing that we do the shift up on sa->util_sum without consideration
>> of overflow, would it not make sense to add that factor before the
>> scaling and into the addition?
>>
>> Now, given all that, units are a complete mess here, and I'd not mind
>> something like:
>>
>> #if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != SCHED_CAPACITY_SHIFT
>> #error "something usefull"
>> #endif
>>
>> somewhere near here.
>
> Something like teh below..
>
> Another thing to ponder; the downside of scaled_delta_w is that its
> fairly likely delta is small and you loose all bits, whereas the weight
> is likely to be large can could loose a fwe bits without issue.
>
> That is, in fixed point scaling like this, you want to start with the
> biggest numbers, not the smallest, otherwise you loose too much.
>
> The flip side is of course that now you can share a multiplcation.
>
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -682,7 +682,7 @@ void init_entity_runnable_average(struct
>         sa->load_avg = scale_load_down(se->load.weight);
>         sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
>         sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
> -       sa->util_sum = LOAD_AVG_MAX;
> +       sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
>         /* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
>  }
>
> @@ -2515,6 +2515,10 @@ static u32 __compute_runnable_contrib(u6
>         return contrib + runnable_avg_yN_sum[n];
>  }
>
> +#if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != 10 || SCHED_CAPACITY_SHIFT != 10
> +#error "load tracking assumes 2^10 as unit"
> +#endif

so why don't we set SCHED_CAPACITY_SHIFT to SCHED_LOAD_SHIFT ?

> +
>  #define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
>
>  /*
> @@ -2599,7 +2603,7 @@ __update_load_avg(u64 now, int cpu, stru
>                         }
>                 }
>                 if (running)
> -                       sa->util_sum += cap_scale(scaled_delta_w, scale_cpu);
> +                       sa->util_sum += scaled_delta_w * scale_cpu;
>
>                 delta -= delta_w;
>
> @@ -2623,7 +2627,7 @@ __update_load_avg(u64 now, int cpu, stru
>                                 cfs_rq->runnable_load_sum += weight * contrib;
>                 }
>                 if (running)
> -                       sa->util_sum += cap_scale(contrib, scale_cpu);
> +                       sa->util_sum += contrib * scale_cpu;
>         }
>
>         /* Remainder of delta accrued against u_0` */
> @@ -2634,7 +2638,7 @@ __update_load_avg(u64 now, int cpu, stru
>                         cfs_rq->runnable_load_sum += weight * scaled_delta;
>         }
>         if (running)
> -               sa->util_sum += cap_scale(scaled_delta, scale_cpu);
> +               sa->util_sum += scaled_delta * scale_cpu;
>
>         sa->period_contrib += delta;
>
> @@ -2644,7 +2648,7 @@ __update_load_avg(u64 now, int cpu, stru
>                         cfs_rq->runnable_load_avg =
>                                 div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
>                 }
> -               sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
> +               sa->util_avg = sa->util_sum / LOAD_AVG_MAX;
>         }
>
>         return decayed;
> @@ -2686,8 +2690,7 @@ static inline int update_cfs_rq_load_avg
>         if (atomic_long_read(&cfs_rq->removed_util_avg)) {
>                 long r = atomic_long_xchg(&cfs_rq->removed_util_avg, 0);
>                 sa->util_avg = max_t(long, sa->util_avg - r, 0);
> -               sa->util_sum = max_t(s32, sa->util_sum -
> -                       ((r * LOAD_AVG_MAX) >> SCHED_LOAD_SHIFT), 0);
> +               sa->util_sum = max_t(s32, sa->util_sum - r * LOAD_AVG_MAX, 0);

looks good to me

>         }
>
>         decayed = __update_load_avg(now, cpu_of(rq_of(cfs_rq)), sa,
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220866

On Tue, Sep 08, 2015 at 04:06:36PM +0200, Vincent Guittot wrote:
> On 8 September 2015 at 14:52, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Tue, Sep 08, 2015 at 02:26:06PM +0200, Peter Zijlstra wrote:
> >> On Tue, Sep 08, 2015 at 09:22:05AM +0200, Vincent Guittot wrote:
> >> > No, but
> >> > sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
> >> > will fix the unit issue.
> >>
> >> Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
> >>
> >> And where load_sum already gets a factor 1024 from the weight
> >> multiplication, util_sum does not get such a factor, and all the scaling
> >> we do on it loose bits.
> >>
> >> So at the moment we go compute the util_avg value, we need to inflate
> >> util_sum with an extra factor 1024 in order to make it work.
> >>
> >> And seeing that we do the shift up on sa->util_sum without consideration
> >> of overflow, would it not make sense to add that factor before the
> >> scaling and into the addition?
> >>
> >> Now, given all that, units are a complete mess here, and I'd not mind
> >> something like:
> >>
> >> #if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != SCHED_CAPACITY_SHIFT
> >> #error "something usefull"
> >> #endif
> >>
> >> somewhere near here.
> >
> > Something like teh below..
> >
> > Another thing to ponder; the downside of scaled_delta_w is that its
> > fairly likely delta is small and you loose all bits, whereas the weight
> > is likely to be large can could loose a fwe bits without issue.
> >
> > That is, in fixed point scaling like this, you want to start with the
> > biggest numbers, not the smallest, otherwise you loose too much.
> >
> > The flip side is of course that now you can share a multiplcation.
> >
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -682,7 +682,7 @@ void init_entity_runnable_average(struct
> >         sa->load_avg = scale_load_down(se->load.weight);
> >         sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
> >         sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
> > -       sa->util_sum = LOAD_AVG_MAX;
> > +       sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
> >         /* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
> >  }
> >
> > @@ -2515,6 +2515,10 @@ static u32 __compute_runnable_contrib(u6
> >         return contrib + runnable_avg_yN_sum[n];
> >  }
> >
> > +#if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != 10 || SCHED_CAPACITY_SHIFT != 10
> > +#error "load tracking assumes 2^10 as unit"
> > +#endif
> 
> so why don't we set SCHED_CAPACITY_SHIFT to SCHED_LOAD_SHIFT ?

Don't you mean:

#define SCHED_LOAD_SHIFT (SCHED_CAPACITY_SHIFT + SCHED_LOAD_RESOLUTION)

?

Or do you want to increase the capacity resolution as well if you
increase the load resolution?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220901 — Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

On 8 September 2015 at 16:35, Morten Rasmussen <morten.rasmussen@arm.com> wrote:
> On Tue, Sep 08, 2015 at 04:06:36PM +0200, Vincent Guittot wrote:
>> On 8 September 2015 at 14:52, Peter Zijlstra <peterz@infradead.org> wrote:
>> > On Tue, Sep 08, 2015 at 02:26:06PM +0200, Peter Zijlstra wrote:
>> >> On Tue, Sep 08, 2015 at 09:22:05AM +0200, Vincent Guittot wrote:
>> >> > No, but
>> >> > sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
>> >> > will fix the unit issue.
>> >>
>> >> Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
>> >>
>> >> And where load_sum already gets a factor 1024 from the weight
>> >> multiplication, util_sum does not get such a factor, and all the scaling
>> >> we do on it loose bits.
>> >>
>> >> So at the moment we go compute the util_avg value, we need to inflate
>> >> util_sum with an extra factor 1024 in order to make it work.
>> >>
>> >> And seeing that we do the shift up on sa->util_sum without consideration
>> >> of overflow, would it not make sense to add that factor before the
>> >> scaling and into the addition?
>> >>
>> >> Now, given all that, units are a complete mess here, and I'd not mind
>> >> something like:
>> >>
>> >> #if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != SCHED_CAPACITY_SHIFT
>> >> #error "something usefull"
>> >> #endif
>> >>
>> >> somewhere near here.
>> >
>> > Something like teh below..
>> >
>> > Another thing to ponder; the downside of scaled_delta_w is that its
>> > fairly likely delta is small and you loose all bits, whereas the weight
>> > is likely to be large can could loose a fwe bits without issue.
>> >
>> > That is, in fixed point scaling like this, you want to start with the
>> > biggest numbers, not the smallest, otherwise you loose too much.
>> >
>> > The flip side is of course that now you can share a multiplcation.
>> >
>> > --- a/kernel/sched/fair.c
>> > +++ b/kernel/sched/fair.c
>> > @@ -682,7 +682,7 @@ void init_entity_runnable_average(struct
>> >         sa->load_avg = scale_load_down(se->load.weight);
>> >         sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
>> >         sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
>> > -       sa->util_sum = LOAD_AVG_MAX;
>> > +       sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
>> >         /* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
>> >  }
>> >
>> > @@ -2515,6 +2515,10 @@ static u32 __compute_runnable_contrib(u6
>> >         return contrib + runnable_avg_yN_sum[n];
>> >  }
>> >
>> > +#if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != 10 || SCHED_CAPACITY_SHIFT != 10
>> > +#error "load tracking assumes 2^10 as unit"
>> > +#endif
>>
>> so why don't we set SCHED_CAPACITY_SHIFT to SCHED_LOAD_SHIFT ?
>
> Don't you mean:
>
> #define SCHED_LOAD_SHIFT (SCHED_CAPACITY_SHIFT + SCHED_LOAD_RESOLUTION)

yes you're right

>
> ?
>
> Or do you want to increase the capacity resolution as well if you
> increase the load resolution?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220842

On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote:
> On Tue, Sep 08, 2015 at 02:26:06PM +0200, Peter Zijlstra wrote:
> > On Tue, Sep 08, 2015 at 09:22:05AM +0200, Vincent Guittot wrote:
> > > No, but
> > > sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
> > > will fix the unit issue.
> > 
> > Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.

I don't get why LOAD_AVG_MAX relies on the util_avg shifting being
1<<10, it is just the sum of the geometric series and the upper bound of
util_sum?

> > And where load_sum already gets a factor 1024 from the weight
> > multiplication, util_sum does not get such a factor, and all the scaling
> > we do on it loose bits.
> > 
> > So at the moment we go compute the util_avg value, we need to inflate
> > util_sum with an extra factor 1024 in order to make it work.

Agreed. Inflating the util_sum instead of util_avg like you do below
makes more sense. The load_sum/util_sum assymmetry is somewhat confusing.

> > And seeing that we do the shift up on sa->util_sum without consideration
> > of overflow, would it not make sense to add that factor before the
> > scaling and into the addition?

I don't think util_sum can overflow as it is bounded by LOAD_AVG_MAX
unless you shift it a lot, like << 20. The << SCHED_LOAD_SHIFT in the
existing code is wrong I think. Looking at the initialization of
util_avg = scale_load_down(SCHED_LOAD_SCALE) it is not using using high
resolution load.

> > Now, given all that, units are a complete mess here, and I'd not mind
> > something like:
> > 
> > #if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != SCHED_CAPACITY_SHIFT
> > #error "something usefull"
> > #endif
> > 
> > somewhere near here.

Yes. As I see it, it all falls completely if that isn't true. 

> 
> Something like teh below..
> 
> Another thing to ponder; the downside of scaled_delta_w is that its
> fairly likely delta is small and you loose all bits, whereas the weight
> is likely to be large can could loose a fwe bits without issue.

That issue applies both to load and util.

> 
> That is, in fixed point scaling like this, you want to start with the
> biggest numbers, not the smallest, otherwise you loose too much.
> 
> The flip side is of course that now you can share a multiplcation.

But if we apply the scaling to the weight instead of time, we would only
have to apply it once and not three times like it is now? So maybe we
can end up with almost the same number of multiplications.

We might be loosing bits for low priority task running on cpus at a low
frequency though.

> 
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -682,7 +682,7 @@ void init_entity_runnable_average(struct
>  	sa->load_avg = scale_load_down(se->load.weight);
>  	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
>  	sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
> -	sa->util_sum = LOAD_AVG_MAX;
> +	sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
>  	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
>  }
>  
> @@ -2515,6 +2515,10 @@ static u32 __compute_runnable_contrib(u6
>  	return contrib + runnable_avg_yN_sum[n];
>  }
>  
> +#if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != 10 || SCHED_CAPACITY_SHIFT != 10
> +#error "load tracking assumes 2^10 as unit"
> +#endif

As mentioned above. Does it have to be 10?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220935

On Tue, Sep 08, 2015 at 03:31:58PM +0100, Morten Rasmussen wrote:
> On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote:
> > > Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
> 
> I don't get why LOAD_AVG_MAX relies on the util_avg shifting being
> 1<<10, it is just the sum of the geometric series and the upper bound of
> util_sum?

It needs a 1024, it might just have been the 1024 ns we use a period
instead of the scale unit though.

The LOAD_AVG_MAX is the number where adding a next element to the series
doesn't change the result anymore, so scaling it up will allow more
significant elements to the series before we bottom out, which is the _N
thing.


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

[toc] | [prev] | [next] | [standalone]

#1221773 — Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

Peter Zijlstra <peterz@infradead.org> writes:

> On Tue, Sep 08, 2015 at 03:31:58PM +0100, Morten Rasmussen wrote:
>> On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote:
>> > > Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
>> 
>> I don't get why LOAD_AVG_MAX relies on the util_avg shifting being
>> 1<<10, it is just the sum of the geometric series and the upper bound of
>> util_sum?
>
> It needs a 1024, it might just have been the 1024 ns we use a period
> instead of the scale unit though.
>
> The LOAD_AVG_MAX is the number where adding a next element to the series
> doesn't change the result anymore, so scaling it up will allow more
> significant elements to the series before we bottom out, which is the _N
> thing.
>

Yes, as the comments say, the 1024ns unit is arbitrary (and is an
average of not-quite-microseconds instead of just nanoseconds to allow
more bits to load.weight when we multiply load.weight by this number).
In fact there are two arbitrary 1024 units here, which are technically
unrelated and are both unrelated to SCHED_LOAD_RESOLUTION/etc - we
operate on units of almost-microseconds and we also do decays every
almost-millisecond.

There appears to be a bunch of confusion in the current code around
util_sum/util_avg which appears to using SCHED_LOAD_SCALE
for a fixed-point percentage or something, which is at least reasonable,
but is initializing it as scale_load_down(SCHED_LOAD_SCALE), which
results in either initializing as 100% or .1% depending on RESOLUTION.
This'll get clobbered on first update, but if it needs to be
initialized, it should either get initialized to something sane or at
least consistent.

load_sum/load_avg appear to be scale_load_down()ed properly, and appear
to be used as such at a quick glance.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1222115

On Wed, Sep 09, 2015 at 03:23:43PM -0700, bsegall@google.com wrote:
> Peter Zijlstra <peterz@infradead.org> writes:
> 
> > On Tue, Sep 08, 2015 at 03:31:58PM +0100, Morten Rasmussen wrote:
> >> On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote:
> >> > > Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
> >> 
> >> I don't get why LOAD_AVG_MAX relies on the util_avg shifting being
> >> 1<<10, it is just the sum of the geometric series and the upper bound of
> >> util_sum?
> >
> > It needs a 1024, it might just have been the 1024 ns we use a period
> > instead of the scale unit though.
> >
> > The LOAD_AVG_MAX is the number where adding a next element to the series
> > doesn't change the result anymore, so scaling it up will allow more
> > significant elements to the series before we bottom out, which is the _N
> > thing.
> >
> 
> Yes, as the comments say, the 1024ns unit is arbitrary (and is an
> average of not-quite-microseconds instead of just nanoseconds to allow
> more bits to load.weight when we multiply load.weight by this number).
> In fact there are two arbitrary 1024 units here, which are technically
> unrelated and are both unrelated to SCHED_LOAD_RESOLUTION/etc - we
> operate on units of almost-microseconds and we also do decays every
> almost-millisecond.
> 
> There appears to be a bunch of confusion in the current code around
> util_sum/util_avg which appears to using SCHED_LOAD_SCALE
> for a fixed-point percentage or something, which is at least reasonable,
> but is initializing it as scale_load_down(SCHED_LOAD_SCALE), which
> results in either initializing as 100% or .1% depending on RESOLUTION.
> This'll get clobbered on first update, but if it needs to be
> initialized, it should either get initialized to something sane or at
> least consistent.

This is what I thought too. The whole geometric series math is completely
independent of the scale used for priority in load_avg and the fixed
point shifting used for util_avg.

> load_sum/load_avg appear to be scale_load_down()ed properly, and appear
> to be used as such at a quick glance.

I don't think shifting by SCHED_LOAD_SHIFT in __update_load_avg() is
right:

	sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;

util_avg is initialized to low resolution (>> SCHED_LOAD_RESOLUTION):

        sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);

so it appear to be intended to be using low resolution like load_avg
(weight is scaled down before it is passed into __update_load_avg()),
but util_avg is shifted up to high resolution. It should be:

	sa->util_avg = (sa->util_sum << (SCHED_LOAD_SHIFT -
					SCHED_LOAD_SHIFT)) / LOAD_AVG_MAX;

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

[toc] | [prev] | [next] | [standalone]

#1222120 — Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

On 10 September 2015 at 13:06, Morten Rasmussen
<morten.rasmussen@arm.com> wrote:
> On Wed, Sep 09, 2015 at 03:23:43PM -0700, bsegall@google.com wrote:
>> Peter Zijlstra <peterz@infradead.org> writes:
>>
>> > On Tue, Sep 08, 2015 at 03:31:58PM +0100, Morten Rasmussen wrote:
>> >> On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote:
>> >> > > Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
>> >>
>> >> I don't get why LOAD_AVG_MAX relies on the util_avg shifting being
>> >> 1<<10, it is just the sum of the geometric series and the upper bound of
>> >> util_sum?
>> >
>> > It needs a 1024, it might just have been the 1024 ns we use a period
>> > instead of the scale unit though.
>> >
>> > The LOAD_AVG_MAX is the number where adding a next element to the series
>> > doesn't change the result anymore, so scaling it up will allow more
>> > significant elements to the series before we bottom out, which is the _N
>> > thing.
>> >
>>
>> Yes, as the comments say, the 1024ns unit is arbitrary (and is an
>> average of not-quite-microseconds instead of just nanoseconds to allow
>> more bits to load.weight when we multiply load.weight by this number).
>> In fact there are two arbitrary 1024 units here, which are technically
>> unrelated and are both unrelated to SCHED_LOAD_RESOLUTION/etc - we
>> operate on units of almost-microseconds and we also do decays every
>> almost-millisecond.
>>
>> There appears to be a bunch of confusion in the current code around
>> util_sum/util_avg which appears to using SCHED_LOAD_SCALE
>> for a fixed-point percentage or something, which is at least reasonable,
>> but is initializing it as scale_load_down(SCHED_LOAD_SCALE), which
>> results in either initializing as 100% or .1% depending on RESOLUTION.
>> This'll get clobbered on first update, but if it needs to be
>> initialized, it should either get initialized to something sane or at
>> least consistent.
>
> This is what I thought too. The whole geometric series math is completely
> independent of the scale used for priority in load_avg and the fixed
> point shifting used for util_avg.
>
>> load_sum/load_avg appear to be scale_load_down()ed properly, and appear
>> to be used as such at a quick glance.
>
> I don't think shifting by SCHED_LOAD_SHIFT in __update_load_avg() is
> right:
>
>         sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
>
> util_avg is initialized to low resolution (>> SCHED_LOAD_RESOLUTION):
>
>         sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
>
> so it appear to be intended to be using low resolution like load_avg
> (weight is scaled down before it is passed into __update_load_avg()),
> but util_avg is shifted up to high resolution. It should be:
>
>         sa->util_avg = (sa->util_sum << (SCHED_LOAD_SHIFT -
>                                         SCHED_LOAD_SHIFT)) / LOAD_AVG_MAX;

you probably mean (SCHED_LOAD_SHIFT -  SCHED_LOAD_RESOLUTION)

The goal of this patchset is to be able to scale util_avg in the range
of cpu capacity so why don't we directly initialize it with
sa->util_avg = SCHED_CAPACITY_SCALE;

and then use

 sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;

so we don't have to take care of high and low load resolution
Regards,

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

[toc] | [prev] | [next] | [standalone]

#1222148

On Thu, Sep 10, 2015 at 01:11:01PM +0200, Vincent Guittot wrote:
> On 10 September 2015 at 13:06, Morten Rasmussen
> <morten.rasmussen@arm.com> wrote:
> > On Wed, Sep 09, 2015 at 03:23:43PM -0700, bsegall@google.com wrote:
> >> Peter Zijlstra <peterz@infradead.org> writes:
> >>
> >> > On Tue, Sep 08, 2015 at 03:31:58PM +0100, Morten Rasmussen wrote:
> >> >> On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote:
> >> >> > > Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
> >> >>
> >> >> I don't get why LOAD_AVG_MAX relies on the util_avg shifting being
> >> >> 1<<10, it is just the sum of the geometric series and the upper bound of
> >> >> util_sum?
> >> >
> >> > It needs a 1024, it might just have been the 1024 ns we use a period
> >> > instead of the scale unit though.
> >> >
> >> > The LOAD_AVG_MAX is the number where adding a next element to the series
> >> > doesn't change the result anymore, so scaling it up will allow more
> >> > significant elements to the series before we bottom out, which is the _N
> >> > thing.
> >> >
> >>
> >> Yes, as the comments say, the 1024ns unit is arbitrary (and is an
> >> average of not-quite-microseconds instead of just nanoseconds to allow
> >> more bits to load.weight when we multiply load.weight by this number).
> >> In fact there are two arbitrary 1024 units here, which are technically
> >> unrelated and are both unrelated to SCHED_LOAD_RESOLUTION/etc - we
> >> operate on units of almost-microseconds and we also do decays every
> >> almost-millisecond.
> >>
> >> There appears to be a bunch of confusion in the current code around
> >> util_sum/util_avg which appears to using SCHED_LOAD_SCALE
> >> for a fixed-point percentage or something, which is at least reasonable,
> >> but is initializing it as scale_load_down(SCHED_LOAD_SCALE), which
> >> results in either initializing as 100% or .1% depending on RESOLUTION.
> >> This'll get clobbered on first update, but if it needs to be
> >> initialized, it should either get initialized to something sane or at
> >> least consistent.
> >
> > This is what I thought too. The whole geometric series math is completely
> > independent of the scale used for priority in load_avg and the fixed
> > point shifting used for util_avg.
> >
> >> load_sum/load_avg appear to be scale_load_down()ed properly, and appear
> >> to be used as such at a quick glance.
> >
> > I don't think shifting by SCHED_LOAD_SHIFT in __update_load_avg() is
> > right:
> >
> >         sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
> >
> > util_avg is initialized to low resolution (>> SCHED_LOAD_RESOLUTION):
> >
> >         sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
> >
> > so it appear to be intended to be using low resolution like load_avg
> > (weight is scaled down before it is passed into __update_load_avg()),
> > but util_avg is shifted up to high resolution. It should be:
> >
> >         sa->util_avg = (sa->util_sum << (SCHED_LOAD_SHIFT -
> >                                         SCHED_LOAD_SHIFT)) / LOAD_AVG_MAX;
> 
> you probably mean (SCHED_LOAD_SHIFT -  SCHED_LOAD_RESOLUTION)

Yes. Thanks for providing the right expression. There seems to be enough
confusion in this thread already :)

> The goal of this patchset is to be able to scale util_avg in the range
> of cpu capacity so why don't we directly initialize it with
> sa->util_avg = SCHED_CAPACITY_SCALE;
> 
> and then use
> 
>  sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
> 
> so we don't have to take care of high and low load resolution

That works for me, except that the left-shift has gone be PeterZ's
optimization patch posted earlier in this thread. It is changing
util_sum to scaled by capacity instead of being the pure geometric
series which requires the left shift at the end when we divide by
LOAD_AVG_MAX. So it should be equivalent to what you are proposing if we
change the initialization to your proposal too.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1222622

On Thu, Sep 10, 2015 at 01:10:19PM +0100, Morten Rasmussen wrote:
> > > so it appear to be intended to be using low resolution like load_avg
> > > (weight is scaled down before it is passed into __update_load_avg()),
> > > but util_avg is shifted up to high resolution. It should be:
> > >
> > >         sa->util_avg = (sa->util_sum << (SCHED_LOAD_SHIFT -
> > >                                         SCHED_LOAD_SHIFT)) / LOAD_AVG_MAX;
> > 
> > you probably mean (SCHED_LOAD_SHIFT -  SCHED_LOAD_RESOLUTION)
> 
> Yes. Thanks for providing the right expression. There seems to be enough
> confusion in this thread already :)
 
And yes, it is my bad in the first place, sorry, I did not think it though :)

> > The goal of this patchset is to be able to scale util_avg in the range
> > of cpu capacity so why don't we directly initialize it with
> > sa->util_avg = SCHED_CAPACITY_SCALE;

Yes, we should, and specifically, it is bacause we can combine the
resolution thing for util% * capacity%, so we only need to use the
resolution once.

> > and then use
> > 
> >  sa->util_avg = (sa->util_sum << SCHED_CAPACITY_SHIFT) / LOAD_AVG_MAX;
> > 
> > so we don't have to take care of high and low load resolution
> 
> That works for me, except that the left-shift has gone be PeterZ's
> optimization patch posted earlier in this thread. It is changing
> util_sum to scaled by capacity instead of being the pure geometric
> series which requires the left shift at the end when we divide by
> LOAD_AVG_MAX. So it should be equivalent to what you are proposing if we
> change the initialization to your proposal too.

I previously initialized the util_sum as:

sa->util_sum = LOAD_AVG_MAX;

it is because wihout capacity adjustment, this can save some multiplications
in __update_load_avg(), but actually if we do capacity adjustment, we must
multiply anyway, so it is better we initialize it as:

sa->util_sum = sa->util_avg * LOAD_AVG_MAX;

Anyway, with the patch I posted in the other email in this thread, we
can fix all this very clearly, I hope so. I did not post a fix patch,
it is because the solutions are already there, it is just how we make it 
look better, and you can provide it in your new version.

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

[toc] | [prev] | [next] | [standalone]

#1222329 — Re: [PATCH 5/6] sched/fair: Get rid of scaling utilization by capacity_orig

Morten Rasmussen <morten.rasmussen@arm.com> writes:

> On Wed, Sep 09, 2015 at 03:23:43PM -0700, bsegall@google.com wrote:
>> Peter Zijlstra <peterz@infradead.org> writes:
>> 
>> > On Tue, Sep 08, 2015 at 03:31:58PM +0100, Morten Rasmussen wrote:
>> >> On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote:
>> >> > > Tricky that, LOAD_AVG_MAX very much relies on the unit being 1<<10.
>> >> 
>> >> I don't get why LOAD_AVG_MAX relies on the util_avg shifting being
>> >> 1<<10, it is just the sum of the geometric series and the upper bound of
>> >> util_sum?
>> >
>> > It needs a 1024, it might just have been the 1024 ns we use a period
>> > instead of the scale unit though.
>> >
>> > The LOAD_AVG_MAX is the number where adding a next element to the series
>> > doesn't change the result anymore, so scaling it up will allow more
>> > significant elements to the series before we bottom out, which is the _N
>> > thing.
>> >
>> 
>> Yes, as the comments say, the 1024ns unit is arbitrary (and is an
>> average of not-quite-microseconds instead of just nanoseconds to allow
>> more bits to load.weight when we multiply load.weight by this number).
>> In fact there are two arbitrary 1024 units here, which are technically
>> unrelated and are both unrelated to SCHED_LOAD_RESOLUTION/etc - we
>> operate on units of almost-microseconds and we also do decays every
>> almost-millisecond.
>> 
>> There appears to be a bunch of confusion in the current code around
>> util_sum/util_avg which appears to using SCHED_LOAD_SCALE
>> for a fixed-point percentage or something, which is at least reasonable,
>> but is initializing it as scale_load_down(SCHED_LOAD_SCALE), which
>> results in either initializing as 100% or .1% depending on RESOLUTION.
>> This'll get clobbered on first update, but if it needs to be
>> initialized, it should either get initialized to something sane or at
>> least consistent.
>
> This is what I thought too. The whole geometric series math is completely
> independent of the scale used for priority in load_avg and the fixed
> point shifting used for util_avg.
>
>> load_sum/load_avg appear to be scale_load_down()ed properly, and appear
>> to be used as such at a quick glance.
>
> I don't think shifting by SCHED_LOAD_SHIFT in __update_load_avg() is
> right:
>
> 	sa->util_avg = (sa->util_sum << SCHED_LOAD_SHIFT) / LOAD_AVG_MAX;
>
> util_avg is initialized to low resolution (>> SCHED_LOAD_RESOLUTION):
>
>         sa->util_avg = scale_load_down(SCHED_LOAD_SCALE);
>
> so it appear to be intended to be using low resolution like load_avg
> (weight is scaled down before it is passed into __update_load_avg()),
> but util_avg is shifted up to high resolution. It should be:
>
> 	sa->util_avg = (sa->util_sum << (SCHED_LOAD_SHIFT -
> 					SCHED_LOAD_SHIFT)) / LOAD_AVG_MAX;
>
> to be consistent.

Yeah, util_avg was/is screwed up in terms of either the initialization
or which shift to use there. The load ones however appear to be fine.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1220985

On Tue, Sep 08, 2015 at 03:31:58PM +0100, Morten Rasmussen wrote:
> On Tue, Sep 08, 2015 at 02:52:05PM +0200, Peter Zijlstra wrote:
> > 
> > Something like teh below..
> > 
> > Another thing to ponder; the downside of scaled_delta_w is that its
> > fairly likely delta is small and you loose all bits, whereas the weight
> > is likely to be large can could loose a fwe bits without issue.
> 
> That issue applies both to load and util.
> 
> > 
> > That is, in fixed point scaling like this, you want to start with the
> > biggest numbers, not the smallest, otherwise you loose too much.
> > 
> > The flip side is of course that now you can share a multiplcation.
> 
> But if we apply the scaling to the weight instead of time, we would only
> have to apply it once and not three times like it is now? So maybe we
> can end up with almost the same number of multiplications.
> 
> We might be loosing bits for low priority task running on cpus at a low
> frequency though.

Something like the below. We should be saving one multiplication.

--- 8< ---

From: Morten Rasmussen <morten.rasmussen@arm.com>
Date: Tue, 8 Sep 2015 17:15:40 +0100
Subject: [PATCH] sched/fair: Scale load/util contribution rather than time

When updating load/util tracking the time delta might be very small (1)
in many cases, scaling it futher down with frequency and cpu invariance
scaling might cause us to loose precision. Instead of scaling time we
can scale the weight of the task for load and the capacity for
utilization. Both weight (>=15) and capacity should be significantly
bigger in most cases. Low priority tasks might still suffer a bit but
worst should be improved, as weight is at least 15 before invariance
scaling.

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
---
 kernel/sched/fair.c | 38 +++++++++++++++++++-------------------
 1 file changed, 19 insertions(+), 19 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 9301291..d5ee72a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2519,8 +2519,6 @@ static u32 __compute_runnable_contrib(u64 n)
 #error "load tracking assumes 2^10 as unit"
 #endif
 
-#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
-
 /*
  * We can represent the historical contribution to runnable average as the
  * coefficients of a geometric series.  To do this we sub-divide our runnable
@@ -2553,10 +2551,10 @@ static __always_inline int
 __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
 		  unsigned long weight, int running, struct cfs_rq *cfs_rq)
 {
-	u64 delta, scaled_delta, periods;
+	u64 delta, periods;
 	u32 contrib;
-	unsigned int delta_w, scaled_delta_w, decayed = 0;
-	unsigned long scale_freq, scale_cpu;
+	unsigned int delta_w, decayed = 0;
+	unsigned long scaled_weight = 0, scale_freq, scale_freq_cpu = 0;
 
 	delta = now - sa->last_update_time;
 	/*
@@ -2577,8 +2575,13 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
 		return 0;
 	sa->last_update_time = now;
 
-	scale_freq = arch_scale_freq_capacity(NULL, cpu);
-	scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
+	if (weight || running)
+		scale_freq = arch_scale_freq_capacity(NULL, cpu);
+	if (weight)
+		scaled_weight = weight * scale_freq >> SCHED_CAPACITY_SHIFT;
+	if (running)
+		scale_freq_cpu = scale_freq * arch_scale_cpu_capacity(NULL, cpu)
+							>> SCHED_CAPACITY_SHIFT;
 
 	/* delta_w is the amount already accumulated against our next period */
 	delta_w = sa->period_contrib;
@@ -2594,16 +2597,15 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
 		 * period and accrue it.
 		 */
 		delta_w = 1024 - delta_w;
-		scaled_delta_w = cap_scale(delta_w, scale_freq);
 		if (weight) {
-			sa->load_sum += weight * scaled_delta_w;
+			sa->load_sum += scaled_weight * delta_w;
 			if (cfs_rq) {
 				cfs_rq->runnable_load_sum +=
-						weight * scaled_delta_w;
+						scaled_weight * delta_w;
 			}
 		}
 		if (running)
-			sa->util_sum += scaled_delta_w * scale_cpu;
+			sa->util_sum += delta_w * scale_freq_cpu;
 
 		delta -= delta_w;
 
@@ -2620,25 +2622,23 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
 
 		/* Efficiently calculate \sum (1..n_period) 1024*y^i */
 		contrib = __compute_runnable_contrib(periods);
-		contrib = cap_scale(contrib, scale_freq);
 		if (weight) {
-			sa->load_sum += weight * contrib;
+			sa->load_sum += scaled_weight * contrib;
 			if (cfs_rq)
-				cfs_rq->runnable_load_sum += weight * contrib;
+				cfs_rq->runnable_load_sum += scaled_weight * contrib;
 		}
 		if (running)
-			sa->util_sum += contrib * scale_cpu;
+			sa->util_sum += contrib * scale_freq_cpu;
 	}
 
 	/* Remainder of delta accrued against u_0` */
-	scaled_delta = cap_scale(delta, scale_freq);
 	if (weight) {
-		sa->load_sum += weight * scaled_delta;
+		sa->load_sum += scaled_weight * delta;
 		if (cfs_rq)
-			cfs_rq->runnable_load_sum += weight * scaled_delta;
+			cfs_rq->runnable_load_sum += scaled_weight * delta;
 	}
 	if (running)
-		sa->util_sum += scaled_delta * scale_cpu;
+		sa->util_sum += delta * scale_freq_cpu;
 
 	sa->period_contrib += delta;
 
-- 
1.9.1

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | linux.kernel

csiph-web