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

Groups > linux.kernel > #1375507 > unrolled thread

[PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

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

  [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue Yuyang Du <yuyang.du@intel.com> - 2016-04-11 08:20 +0200
    Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Vincent Guittot <vincent.guittot@linaro.org> - 2016-04-11 11:10 +0200
      Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Yuyang Du <yuyang.du@intel.com> - 2016-04-12 05:30 +0200
        Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Vincent Guittot <vincent.guittot@linaro.org> - 2016-04-12 14:00 +0200
          Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Yuyang Du <yuyang.du@intel.com> - 2016-04-13 07:00 +0200
            Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Vincent Guittot <vincent.guittot@linaro.org> - 2016-04-13 13:20 +0200
    Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Dietmar Eggemann <dietmar.eggemann@arm.com> - 2016-04-12 14:10 +0200
      Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Yuyang Du <yuyang.du@intel.com> - 2016-04-13 06:00 +0200
        Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Joe Perches <joe@perches.com> - 2016-04-13 06:10 +0200
        Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Morten Rasmussen <morten.rasmussen@arm.com> - 2016-04-13 10:40 +0200
    Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Dietmar Eggemann <dietmar.eggemann@arm.com> - 2016-04-13 17:20 +0200
      Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Vincent Guittot <vincent.guittot@linaro.org> - 2016-04-13 17:30 +0200
        Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Vincent Guittot <vincent.guittot@linaro.org> - 2016-04-13 18:30 +0200
        Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Yuyang Du <yuyang.du@intel.com> - 2016-04-14 04:30 +0200
          Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Dietmar Eggemann <dietmar.eggemann@arm.com> - 2016-04-14 15:00 +0200
            Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when  sched averages accrue Yuyang Du <yuyang.du@intel.com> - 2016-04-15 05:50 +0200

#1375507 — [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

In __update_load_avg(), the current period is never complete. This
basically leads to a slightly over-decayed average, say on average we
have 50% current period, then we will lose 1.08%(=(1-0.5^(1/64)) of
past avg. More importantly, the incomplete current period significantly
complicates the avg computation, even a full period is only about 1ms.

So we attempt to drop it. The outcome is that for any x.y periods to
update, we will either lose the .y period or unduely gain (1-.y) period.
How big is the impact? For a large x (say 20ms), you barely notice the
difference, which is plus/minus 1% (=(before-after)/before). Moreover,
the aggregated losses and gains in the long run should statistically
even out.

Signed-off-by: Yuyang Du <yuyang.du@intel.com>
---
 include/linux/sched.h |   2 +-
 kernel/sched/fair.c   | 170 +++++++++++++++++++-------------------------------
 2 files changed, 66 insertions(+), 106 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 45e848c..c5948e1 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1214,7 +1214,7 @@ struct load_weight {
  */
 struct sched_avg {
 	u64 last_update_time, load_sum;
-	u32 util_sum, period_contrib;
+	u32 util_sum;
 	unsigned long load_avg, util_avg;
 };
 
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 6e0eec0..68273e8 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -661,7 +661,7 @@ static unsigned long task_h_load(struct task_struct *p);
 
 /*
  * We choose a half-life close to 1 scheduling period.
- * Note: The tables runnable_avg_yN_inv and runnable_avg_yN_sum are
+ * Note: The tables __decay_inv_multiply_N and __accumulated_sum_N are
  * dependent on this value.
  */
 #define LOAD_AVG_PERIOD 32
@@ -674,12 +674,6 @@ void init_entity_runnable_average(struct sched_entity *se)
 	struct sched_avg *sa = &se->avg;
 
 	sa->last_update_time = 0;
-	/*
-	 * sched_avg's period_contrib should be strictly less then 1024, so
-	 * we give it 1023 to make sure it is almost a period (1024us), and
-	 * will definitely be update (after enqueue).
-	 */
-	sa->period_contrib = 1023;
 	sa->load_avg = scale_load_down(se->load.weight);
 	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
 	/*
@@ -2582,8 +2576,8 @@ static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 #ifdef CONFIG_SMP
-/* Precomputed fixed inverse multiplies for multiplication by y^n */
-static const u32 runnable_avg_yN_inv[] = {
+/* Precomputed fixed inverse multipliers for multiplication by y^n */
+static const u32 __decay_inv_multiply_N[] = {
 	0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
 	0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
 	0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
@@ -2593,10 +2587,10 @@ static const u32 runnable_avg_yN_inv[] = {
 };
 
 /*
- * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
+ * Precomputed \Sum y^k { 1<=k<=n }. These are floor(true_value) to prevent
  * over-estimates when re-combining.
  */
-static const u32 runnable_avg_yN_sum[] = {
+static const u32 __accumulated_sum_N[] = {
 	    0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
 	 9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
 	17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
@@ -2612,58 +2606,54 @@ static const u32 __accumulated_sum_N32[] = {
 };
 
 /*
- * Approximate:
- *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
+ * val * y^n, where y^32 ~= 0.5 and n's unit is ms (slightly bigger than ms),
+ * so 32-bit n is approximately a maximum of 49 (2^32/1000/3600/24) days
  */
-static __always_inline u64 decay_load(u64 val, u64 n)
+static __always_inline u64 __decay_sum(u64 val, u32 n)
 {
-	unsigned int local_n;
-
 	if (!n)
 		return val;
 	else if (unlikely(n > LOAD_AVG_PERIOD * 63))
 		return 0;
 
-	/* after bounds checking we can collapse to 32-bit */
-	local_n = n;
-
 	/*
-	 * As y^PERIOD = 1/2, we can combine
-	 *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
-	 * With a look-up table which covers y^n (n<PERIOD)
-	 *
-	 * To achieve constant time decay_load.
+	 * As y^32 = 1/2, we can accelerate the computation as:
+	 * y^n = 1/2^(n/32) * y^(n%32) with a look-up table which
+	 * covers y^x (x<32). This achieves a constant time __decay_sum.
 	 */
-	if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
-		val >>= local_n / LOAD_AVG_PERIOD;
-		local_n %= LOAD_AVG_PERIOD;
+	if (unlikely(n >= LOAD_AVG_PERIOD)) {
+		val >>= n / LOAD_AVG_PERIOD;
+		n %= LOAD_AVG_PERIOD;
 	}
 
-	val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
+	val = mul_u64_u32_shr(val, __decay_inv_multiply_N[n], 32);
 	return val;
 }
 
 /*
- * For updates fully spanning n periods, the contribution to runnable
- * average will be: \Sum 1024*y^n
+ * For updates fully spanning n periods, the accumulated contribution
+ * will be: \Sum 1024*y^n, in the meantime the contribution should
+ * be decayed.
+ *
+ * We can compute this efficiently by combining:
+ * y^32 = 1/2 with precomputed \Sum 1024*y^n {for n < 32}
  *
- * We can compute this reasonably efficiently by combining:
- *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
+ * Here, n is also large enough to hold the number of past periods
  */
-static u32 __compute_runnable_contrib(u64 n)
+static u32 __accumulate_sum(u32 n)
 {
 	u32 contrib = 0;
 
 	if (likely(n <= LOAD_AVG_PERIOD))
-		return runnable_avg_yN_sum[n];
+		return __accumulated_sum_N[n];
 	else if (unlikely(n >= LOAD_AVG_MAX_N))
 		return LOAD_AVG_MAX;
 
 	/* Since n < LOAD_AVG_MAX_N, n/LOAD_AVG_PERIOD < 11 */
 	contrib = __accumulated_sum_N32[n>>5]; /* =n/LOAD_AVG_PERIOD */
 	n %= LOAD_AVG_PERIOD;
-	contrib = decay_load(contrib, n);
-	return contrib + runnable_avg_yN_sum[n];
+	contrib = __decay_sum(contrib, n);
+	return contrib + __accumulated_sum_N[n];
 }
 
 #if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != 10 || SCHED_CAPACITY_SHIFT != 10
@@ -2704,11 +2694,14 @@ 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;
-	u32 contrib;
-	unsigned int delta_w, scaled_delta_w, decayed = 0;
+	u64 delta;
+	u32 contrib, periods;
 	unsigned long scale_freq, scale_cpu;
 
+	/*
+	 * now rolls down to a period boundary
+	 */
+	now = now && (u64)(~0xFFFFF);
 	delta = now - sa->last_update_time;
 	/*
 	 * This should only happen when time goes backwards, which it
@@ -2720,89 +2713,56 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
 	}
 
 	/*
-	 * Use 1024ns as the unit of measurement since it's a reasonable
-	 * approximation of 1us and fast to compute.
+	 * Use 1024*1024ns as an approximation of 1ms period, pretty close.
 	 */
-	delta >>= 10;
-	if (!delta)
+	periods = delta >> 20;
+	if (!periods)
 		return 0;
 	sa->last_update_time = now;
 
 	scale_freq = arch_scale_freq_capacity(NULL, cpu);
 	scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
 
-	/* delta_w is the amount already accumulated against our next period */
-	delta_w = sa->period_contrib;
-	if (delta + delta_w >= 1024) {
-		decayed = 1;
-
-		/* how much left for next period will start over, we don't know yet */
-		sa->period_contrib = 0;
-
-		/*
-		 * Now that we know we're crossing a period boundary, figure
-		 * out how much from delta we need to complete the current
-		 * 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;
-			if (cfs_rq) {
-				cfs_rq->runnable_load_sum +=
-						weight * scaled_delta_w;
-			}
-		}
-		if (running)
-			sa->util_sum += scaled_delta_w * scale_cpu;
-
-		delta -= delta_w;
-
-		/* Figure out how many additional periods this update spans */
-		periods = delta / 1024;
-		delta %= 1024;
+	/*
+	 * Now we know we're crossing period boundaries, and the *_sum accrues by
+	 * two steps.
+	 */
 
-		sa->load_sum = decay_load(sa->load_sum, periods + 1);
-		if (cfs_rq) {
-			cfs_rq->runnable_load_sum =
-				decay_load(cfs_rq->runnable_load_sum, periods + 1);
-		}
-		sa->util_sum = decay_load((u64)(sa->util_sum), periods + 1);
-
-		/* 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;
-			if (cfs_rq)
-				cfs_rq->runnable_load_sum += weight * contrib;
-		}
-		if (running)
-			sa->util_sum += contrib * scale_cpu;
+	/*
+	 * Step 1: decay old *_sum
+	 */
+	sa->load_sum = __decay_sum(sa->load_sum, periods);
+	if (cfs_rq) {
+		cfs_rq->runnable_load_sum =
+			__decay_sum(cfs_rq->runnable_load_sum, periods);
 	}
+	sa->util_sum = __decay_sum((u64)(sa->util_sum), periods);
 
-	/* Remainder of delta accrued against u_0` */
-	scaled_delta = cap_scale(delta, scale_freq);
+	/*
+	 * Step 2: accumulate and meanwhile decay new *_sum by periods since
+	 * last_update_time
+	 */
+	contrib = __accumulate_sum(periods);
+	contrib = cap_scale(contrib, scale_freq);
 	if (weight) {
-		sa->load_sum += weight * scaled_delta;
+		sa->load_sum += weight * contrib;
 		if (cfs_rq)
-			cfs_rq->runnable_load_sum += weight * scaled_delta;
+			cfs_rq->runnable_load_sum += weight * contrib;
 	}
 	if (running)
-		sa->util_sum += scaled_delta * scale_cpu;
+		sa->util_sum += contrib * scale_cpu;
 
-	sa->period_contrib += delta;
-
-	if (decayed) {
-		sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX);
-		if (cfs_rq) {
-			cfs_rq->runnable_load_avg =
-				div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
-		}
-		sa->util_avg = sa->util_sum / LOAD_AVG_MAX;
+	/*
+	 * *_sum must have been evolved, we update *_avg
+	 */
+	sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX);
+	if (cfs_rq) {
+		cfs_rq->runnable_load_avg =
+			div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
 	}
+	sa->util_avg = sa->util_sum / LOAD_AVG_MAX;
 
-	return decayed;
+	return 1;
 }
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
-- 
2.1.4

[toc] | [next] | [standalone]

#1375647 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

Hi Yuyang

On 11 April 2016 at 00:36, Yuyang Du <yuyang.du@intel.com> wrote:
> In __update_load_avg(), the current period is never complete. This
> basically leads to a slightly over-decayed average, say on average we

yes, that also explains why we almost never reach the max value

> have 50% current period, then we will lose 1.08%(=(1-0.5^(1/64)) of
> past avg. More importantly, the incomplete current period significantly
> complicates the avg computation, even a full period is only about 1ms.
>
> So we attempt to drop it. The outcome is that for any x.y periods to
> update, we will either lose the .y period or unduely gain (1-.y) period.
> How big is the impact? For a large x (say 20ms), you barely notice the
> difference, which is plus/minus 1% (=(before-after)/before). Moreover,
> the aggregated losses and gains in the long run should statistically
> even out.
>
> Signed-off-by: Yuyang Du <yuyang.du@intel.com>
> ---
>  include/linux/sched.h |   2 +-
>  kernel/sched/fair.c   | 170 +++++++++++++++++++-------------------------------
>  2 files changed, 66 insertions(+), 106 deletions(-)
>

 [snip]

>
>  #if (SCHED_LOAD_SHIFT - SCHED_LOAD_RESOLUTION) != 10 || SCHED_CAPACITY_SHIFT != 10
> @@ -2704,11 +2694,14 @@ 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;
> -       u32 contrib;
> -       unsigned int delta_w, scaled_delta_w, decayed = 0;
> +       u64 delta;
> +       u32 contrib, periods;
>         unsigned long scale_freq, scale_cpu;
>
> +       /*
> +        * now rolls down to a period boundary
> +        */
> +       now = now && (u64)(~0xFFFFF);
>         delta = now - sa->last_update_time;
>         /*
>          * This should only happen when time goes backwards, which it
> @@ -2720,89 +2713,56 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
>         }
>
>         /*
> -        * Use 1024ns as the unit of measurement since it's a reasonable
> -        * approximation of 1us and fast to compute.
> +        * Use 1024*1024ns as an approximation of 1ms period, pretty close.
>          */
> -       delta >>= 10;
> -       if (!delta)
> +       periods = delta >> 20;
> +       if (!periods)
>                 return 0;
>         sa->last_update_time = now;

The optimization looks quite interesting but I see one potential issue
with migration as we will lose the part of the ongoing period that is
now not saved anymore. This lost part can be quite significant for a
short task that ping pongs between CPUs.

>
>         scale_freq = arch_scale_freq_capacity(NULL, cpu);
>         scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
>
> -       /* delta_w is the amount already accumulated against our next period */
> -       delta_w = sa->period_contrib;
> -       if (delta + delta_w >= 1024) {
> -               decayed = 1;
> -
> -               /* how much left for next period will start over, we don't know yet */
> -               sa->period_contrib = 0;
> -
> -               /*
> -                * Now that we know we're crossing a period boundary, figure
> -                * out how much from delta we need to complete the current
> -                * 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;
> -                       if (cfs_rq) {
> -                               cfs_rq->runnable_load_sum +=
> -                                               weight * scaled_delta_w;
> -                       }
> -               }
> -               if (running)
> -                       sa->util_sum += scaled_delta_w * scale_cpu;
> -
> -               delta -= delta_w;
> -
> -               /* Figure out how many additional periods this update spans */
> -               periods = delta / 1024;
> -               delta %= 1024;
> +       /*
> +        * Now we know we're crossing period boundaries, and the *_sum accrues by
> +        * two steps.
> +        */
>
> -               sa->load_sum = decay_load(sa->load_sum, periods + 1);
> -               if (cfs_rq) {
> -                       cfs_rq->runnable_load_sum =
> -                               decay_load(cfs_rq->runnable_load_sum, periods + 1);
> -               }
> -               sa->util_sum = decay_load((u64)(sa->util_sum), periods + 1);
> -
> -               /* 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;
> -                       if (cfs_rq)
> -                               cfs_rq->runnable_load_sum += weight * contrib;
> -               }
> -               if (running)
> -                       sa->util_sum += contrib * scale_cpu;
> +       /*
> +        * Step 1: decay old *_sum
> +        */
> +       sa->load_sum = __decay_sum(sa->load_sum, periods);
> +       if (cfs_rq) {
> +               cfs_rq->runnable_load_sum =
> +                       __decay_sum(cfs_rq->runnable_load_sum, periods);
>         }
> +       sa->util_sum = __decay_sum((u64)(sa->util_sum), periods);
>
> -       /* Remainder of delta accrued against u_0` */
> -       scaled_delta = cap_scale(delta, scale_freq);
> +       /*
> +        * Step 2: accumulate and meanwhile decay new *_sum by periods since
> +        * last_update_time
> +        */
> +       contrib = __accumulate_sum(periods);
> +       contrib = cap_scale(contrib, scale_freq);
>         if (weight) {
> -               sa->load_sum += weight * scaled_delta;
> +               sa->load_sum += weight * contrib;
>                 if (cfs_rq)
> -                       cfs_rq->runnable_load_sum += weight * scaled_delta;
> +                       cfs_rq->runnable_load_sum += weight * contrib;
>         }
>         if (running)
> -               sa->util_sum += scaled_delta * scale_cpu;
> +               sa->util_sum += contrib * scale_cpu;
>
> -       sa->period_contrib += delta;
> -
> -       if (decayed) {
> -               sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX);
> -               if (cfs_rq) {
> -                       cfs_rq->runnable_load_avg =
> -                               div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
> -               }
> -               sa->util_avg = sa->util_sum / LOAD_AVG_MAX;
> +       /*
> +        * *_sum must have been evolved, we update *_avg
> +        */
> +       sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX);
> +       if (cfs_rq) {
> +               cfs_rq->runnable_load_avg =
> +                       div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
>         }
> +       sa->util_avg = sa->util_sum / LOAD_AVG_MAX;
>
> -       return decayed;
> +       return 1;
>  }
>
>  #ifdef CONFIG_FAIR_GROUP_SCHED
> --
> 2.1.4
>

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

#1376426 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

Hi Vincent,

On Mon, Apr 11, 2016 at 11:08:04AM +0200, Vincent Guittot wrote:
> > @@ -2704,11 +2694,14 @@ 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;
> > -       u32 contrib;
> > -       unsigned int delta_w, scaled_delta_w, decayed = 0;
> > +       u64 delta;
> > +       u32 contrib, periods;
> >         unsigned long scale_freq, scale_cpu;
> >
> > +       /*
> > +        * now rolls down to a period boundary
> > +        */
> > +       now = now && (u64)(~0xFFFFF);
> >         delta = now - sa->last_update_time;
> >         /*
> >          * This should only happen when time goes backwards, which it
> > @@ -2720,89 +2713,56 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> >         }
> >
> >         /*
> > -        * Use 1024ns as the unit of measurement since it's a reasonable
> > -        * approximation of 1us and fast to compute.
> > +        * Use 1024*1024ns as an approximation of 1ms period, pretty close.
> >          */
> > -       delta >>= 10;
> > -       if (!delta)
> > +       periods = delta >> 20;
> > +       if (!periods)
> >                 return 0;
> >         sa->last_update_time = now;
> 
> The optimization looks quite interesting but I see one potential issue
> with migration as we will lose the part of the ongoing period that is
> now not saved anymore. This lost part can be quite significant for a
> short task that ping pongs between CPUs.

Yes, basically, it is we lose precision (~1ms scale in contrast with ~1us scale).
But as I wrote, we may either lose a sub-1ms, or gain a sub-1ms, statistically,
they should even out, given the load/util updates are quite a large number of
samples, and we do want a lot of samples for the metrics, this is the point of
the entire average thing. Plus, as you also said, the incomplete current period
also plays a (somewhat) negative role here.

In addition, excluding the flat hierarchical util patch, we gain quite some
efficiency.

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

#1376732 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

Le Tuesday 12 Apr 2016 à 03:41:41 (+0800), Yuyang Du a écrit :
> Hi Vincent,
> 
> On Mon, Apr 11, 2016 at 11:08:04AM +0200, Vincent Guittot wrote:
> > > @@ -2704,11 +2694,14 @@ 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;
> > > -       u32 contrib;
> > > -       unsigned int delta_w, scaled_delta_w, decayed = 0;
> > > +       u64 delta;
> > > +       u32 contrib, periods;
> > >         unsigned long scale_freq, scale_cpu;
> > >
> > > +       /*
> > > +        * now rolls down to a period boundary
> > > +        */
> > > +       now = now && (u64)(~0xFFFFF);
> > >         delta = now - sa->last_update_time;
> > >         /*
> > >          * This should only happen when time goes backwards, which it
> > > @@ -2720,89 +2713,56 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> > >         }
> > >
> > >         /*
> > > -        * Use 1024ns as the unit of measurement since it's a reasonable
> > > -        * approximation of 1us and fast to compute.
> > > +        * Use 1024*1024ns as an approximation of 1ms period, pretty close.
> > >          */
> > > -       delta >>= 10;
> > > -       if (!delta)
> > > +       periods = delta >> 20;
> > > +       if (!periods)
> > >                 return 0;
> > >         sa->last_update_time = now;
> > 
> > The optimization looks quite interesting but I see one potential issue
> > with migration as we will lose the part of the ongoing period that is
> > now not saved anymore. This lost part can be quite significant for a
> > short task that ping pongs between CPUs.
> 
> Yes, basically, it is we lose precision (~1ms scale in contrast with ~1us scale).

But with a HZ set to 1000 and a sched-slice in the same range, having a precision
of 1ms instead of 1us makes the precision of load tracking of short task quite
random IMHO.

you can keep recording this partial period without using it in the load tracking.
Something like below keep precision without sacrifying the optimization.

---
 kernel/sched/fair.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 68273e8..b234169 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -674,6 +674,12 @@ void init_entity_runnable_average(struct sched_entity *se)
 	struct sched_avg *sa = &se->avg;
 
 	sa->last_update_time = 0;
+	/*
+	 * sched_avg's period_contrib should be strictly less then 1024 * 1024, so
+	 * we give it 1023 * 1024 to make sure it is almost a period (1024us), and
+	 * will definitely be updated (after enqueue).
+	 */
+	sa->period_contrib = 1023*1024;
 	sa->load_avg = scale_load_down(se->load.weight);
 	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
 	/*
@@ -2698,10 +2704,6 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
 	u32 contrib, periods;
 	unsigned long scale_freq, scale_cpu;
 
-	/*
-	 * now rolls down to a period boundary
-	 */
-	now = now && (u64)(~0xFFFFF);
 	delta = now - sa->last_update_time;
 	/*
 	 * This should only happen when time goes backwards, which it
@@ -2712,6 +2714,9 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
 		return 0;
 	}
 
+	/* Add how much left for the current period */
+	delta += sa->period_contrib;
+
 	/*
 	 * Use 1024*1024ns as an approximation of 1ms period, pretty close.
 	 */
@@ -2720,6 +2725,9 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
 		return 0;
 	sa->last_update_time = now;
 
+	/* Get how much left for the next period */
+	sa->period_contrib = delta & (u64)(0xFFFFF);
+
 	scale_freq = arch_scale_freq_capacity(NULL, cpu);
 	scale_cpu = arch_scale_cpu_capacity(NULL, cpu);

> But as I wrote, we may either lose a sub-1ms, or gain a sub-1ms, statistically,
> they should even out, given the load/util updates are quite a large number of
> samples, and we do want a lot of samples for the metrics, this is the point of
> the entire average thing. Plus, as you also said, the incomplete current period
> also plays a (somewhat) negative role here.
> 
> In addition, excluding the flat hierarchical util patch, we gain quite some
> efficiency.

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

#1377508 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

Hi Vincent,

On Tue, Apr 12, 2016 at 01:56:45PM +0200, Vincent Guittot wrote:
> Le Tuesday 12 Apr 2016 à 03:41:41 (+0800), Yuyang Du a écrit :
> > Hi Vincent,
> > 
> > On Mon, Apr 11, 2016 at 11:08:04AM +0200, Vincent Guittot wrote:
> > > > @@ -2704,11 +2694,14 @@ 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;
> > > > -       u32 contrib;
> > > > -       unsigned int delta_w, scaled_delta_w, decayed = 0;
> > > > +       u64 delta;
> > > > +       u32 contrib, periods;
> > > >         unsigned long scale_freq, scale_cpu;
> > > >
> > > > +       /*
> > > > +        * now rolls down to a period boundary
> > > > +        */
> > > > +       now = now && (u64)(~0xFFFFF);
> > > >         delta = now - sa->last_update_time;
> > > >         /*
> > > >          * This should only happen when time goes backwards, which it
> > > > @@ -2720,89 +2713,56 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> > > >         }
> > > >
> > > >         /*
> > > > -        * Use 1024ns as the unit of measurement since it's a reasonable
> > > > -        * approximation of 1us and fast to compute.
> > > > +        * Use 1024*1024ns as an approximation of 1ms period, pretty close.
> > > >          */
> > > > -       delta >>= 10;
> > > > -       if (!delta)
> > > > +       periods = delta >> 20;
> > > > +       if (!periods)
> > > >                 return 0;
> > > >         sa->last_update_time = now;
> > > 
> > > The optimization looks quite interesting but I see one potential issue
> > > with migration as we will lose the part of the ongoing period that is
> > > now not saved anymore. This lost part can be quite significant for a
> > > short task that ping pongs between CPUs.
> > 
> > Yes, basically, it is we lose precision (~1ms scale in contrast with ~1us scale).
> 
> But with a HZ set to 1000 and a sched-slice in the same range, having a precision
> of 1ms instead of 1us makes the precision of load tracking of short task quite
> random IMHO.
> 
> you can keep recording this partial period without using it in the load tracking.
> Something like below keep precision without sacrifying the optimization.
 
The residue is accumulated and rolled over to next update every time. But its
state is runnable/not-runnable, or running/not-running?

> ---
>  kernel/sched/fair.c | 16 ++++++++++++----
>  1 file changed, 12 insertions(+), 4 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 68273e8..b234169 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -674,6 +674,12 @@ void init_entity_runnable_average(struct sched_entity *se)
>  	struct sched_avg *sa = &se->avg;
>  
>  	sa->last_update_time = 0;
> +	/*
> +	 * sched_avg's period_contrib should be strictly less then 1024 * 1024, so
> +	 * we give it 1023 * 1024 to make sure it is almost a period (1024us), and
> +	 * will definitely be updated (after enqueue).
> +	 */
> +	sa->period_contrib = 1023*1024;
>  	sa->load_avg = scale_load_down(se->load.weight);
>  	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
>  	/*
> @@ -2698,10 +2704,6 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
>  	u32 contrib, periods;
>  	unsigned long scale_freq, scale_cpu;
>  
> -	/*
> -	 * now rolls down to a period boundary
> -	 */
> -	now = now && (u64)(~0xFFFFF);
>  	delta = now - sa->last_update_time;
>  	/*
>  	 * This should only happen when time goes backwards, which it
> @@ -2712,6 +2714,9 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
>  		return 0;
>  	}
>  
> +	/* Add how much left for the current period */
> +	delta += sa->period_contrib;
> +
>  	/*
>  	 * Use 1024*1024ns as an approximation of 1ms period, pretty close.
>  	 */
> @@ -2720,6 +2725,9 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
>  		return 0;
>  	sa->last_update_time = now;
>  
> +	/* Get how much left for the next period */
> +	sa->period_contrib = delta & (u64)(0xFFFFF);
> +
>  	scale_freq = arch_scale_freq_capacity(NULL, cpu);
>  	scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
> 
> > But as I wrote, we may either lose a sub-1ms, or gain a sub-1ms, statistically,
> > they should even out, given the load/util updates are quite a large number of
> > samples, and we do want a lot of samples for the metrics, this is the point of
> > the entire average thing. Plus, as you also said, the incomplete current period
> > also plays a (somewhat) negative role here.
> > 
> > In addition, excluding the flat hierarchical util patch, we gain quite some
> > efficiency.

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

#1377766 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On 12 April 2016 at 23:09, Yuyang Du <yuyang.du@intel.com> wrote:
>
> Hi Vincent,
>
> On Tue, Apr 12, 2016 at 01:56:45PM +0200, Vincent Guittot wrote:
> > Le Tuesday 12 Apr 2016 à 03:41:41 (+0800), Yuyang Du a écrit :
> > > Hi Vincent,
> > >
> > > On Mon, Apr 11, 2016 at 11:08:04AM +0200, Vincent Guittot wrote:
> > > > > @@ -2704,11 +2694,14 @@ 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;
> > > > > -       u32 contrib;
> > > > > -       unsigned int delta_w, scaled_delta_w, decayed = 0;
> > > > > +       u64 delta;
> > > > > +       u32 contrib, periods;
> > > > >         unsigned long scale_freq, scale_cpu;
> > > > >
> > > > > +       /*
> > > > > +        * now rolls down to a period boundary
> > > > > +        */
> > > > > +       now = now && (u64)(~0xFFFFF);
> > > > >         delta = now - sa->last_update_time;
> > > > >         /*
> > > > >          * This should only happen when time goes backwards, which it
> > > > > @@ -2720,89 +2713,56 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> > > > >         }
> > > > >
> > > > >         /*
> > > > > -        * Use 1024ns as the unit of measurement since it's a reasonable
> > > > > -        * approximation of 1us and fast to compute.
> > > > > +        * Use 1024*1024ns as an approximation of 1ms period, pretty close.
> > > > >          */
> > > > > -       delta >>= 10;
> > > > > -       if (!delta)
> > > > > +       periods = delta >> 20;
> > > > > +       if (!periods)
> > > > >                 return 0;
> > > > >         sa->last_update_time = now;
> > > >
> > > > The optimization looks quite interesting but I see one potential issue
> > > > with migration as we will lose the part of the ongoing period that is
> > > > now not saved anymore. This lost part can be quite significant for a
> > > > short task that ping pongs between CPUs.
> > >
> > > Yes, basically, it is we lose precision (~1ms scale in contrast with ~1us scale).
> >
> > But with a HZ set to 1000 and a sched-slice in the same range, having a precision
> > of 1ms instead of 1us makes the precision of load tracking of short task quite
> > random IMHO.
> >
> > you can keep recording this partial period without using it in the load tracking.
> > Something like below keep precision without sacrifying the optimization.
>
> The residue is accumulated and rolled over to next update every time. But its
> state is runnable/not-runnable, or running/not-running?

yes, this need to be sorted

>
>
> > ---
> >  kernel/sched/fair.c | 16 ++++++++++++----
> >  1 file changed, 12 insertions(+), 4 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 68273e8..b234169 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -674,6 +674,12 @@ void init_entity_runnable_average(struct sched_entity *se)
> >       struct sched_avg *sa = &se->avg;
> >
> >       sa->last_update_time = 0;
> > +     /*
> > +      * sched_avg's period_contrib should be strictly less then 1024 * 1024, so
> > +      * we give it 1023 * 1024 to make sure it is almost a period (1024us), and
> > +      * will definitely be updated (after enqueue).
> > +      */
> > +     sa->period_contrib = 1023*1024;
> >       sa->load_avg = scale_load_down(se->load.weight);
> >       sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
> >       /*
> > @@ -2698,10 +2704,6 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> >       u32 contrib, periods;
> >       unsigned long scale_freq, scale_cpu;
> >
> > -     /*
> > -      * now rolls down to a period boundary
> > -      */
> > -     now = now && (u64)(~0xFFFFF);
> >       delta = now - sa->last_update_time;
> >       /*
> >        * This should only happen when time goes backwards, which it
> > @@ -2712,6 +2714,9 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> >               return 0;
> >       }
> >
> > +     /* Add how much left for the current period */
> > +     delta += sa->period_contrib;
> > +
> >       /*
> >        * Use 1024*1024ns as an approximation of 1ms period, pretty close.
> >        */
> > @@ -2720,6 +2725,9 @@ __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
> >               return 0;
> >       sa->last_update_time = now;
> >
> > +     /* Get how much left for the next period */
> > +     sa->period_contrib = delta & (u64)(0xFFFFF);
> > +
> >       scale_freq = arch_scale_freq_capacity(NULL, cpu);
> >       scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
> >
> > > But as I wrote, we may either lose a sub-1ms, or gain a sub-1ms, statistically,
> > > they should even out, given the load/util updates are quite a large number of
> > > samples, and we do want a lot of samples for the metrics, this is the point of
> > > the entire average thing. Plus, as you also said, the incomplete current period
> > > also plays a (somewhat) negative role here.
> > >
> > > In addition, excluding the flat hierarchical util patch, we gain quite some
> > > efficiency.

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

#1376737 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On 10/04/16 23:36, Yuyang Du wrote:

[...]

> @@ -2704,11 +2694,14 @@ 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;
> -	u32 contrib;
> -	unsigned int delta_w, scaled_delta_w, decayed = 0;
> +	u64 delta;
> +	u32 contrib, periods;
>  	unsigned long scale_freq, scale_cpu;
>  
> +	/*
> +	 * now rolls down to a period boundary
> +	 */
> +	now = now && (u64)(~0xFFFFF);

This forces now to be 1.

s/&&/&

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

#1377492 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On Tue, Apr 12, 2016 at 01:02:58PM +0100, Dietmar Eggemann wrote:
> On 10/04/16 23:36, Yuyang Du wrote:
> 
> [...]
> 
> > @@ -2704,11 +2694,14 @@ 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;
> > -	u32 contrib;
> > -	unsigned int delta_w, scaled_delta_w, decayed = 0;
> > +	u64 delta;
> > +	u32 contrib, periods;
> >  	unsigned long scale_freq, scale_cpu;
> >  
> > +	/*
> > +	 * now rolls down to a period boundary
> > +	 */
> > +	now = now && (u64)(~0xFFFFF);
> 
> This forces now to be 1.
> 
> s/&&/&

Duh, :)

Thanks.

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

#1377498 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On Wed, 2016-04-13 at 04:14 +0800, Yuyang Du wrote:
> On Tue, Apr 12, 2016 at 01:02:58PM +0100, Dietmar Eggemann wrote:
> > On 10/04/16 23:36, Yuyang Du wrote:
> > [...]
> > > @@ -2704,11 +2694,14 @@ 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;
> > > -	u32 contrib;
> > > -	unsigned int delta_w, scaled_delta_w, decayed = 0;
> > > +	u64 delta;
> > > +	u32 contrib, periods;
> > >  	unsigned long scale_freq, scale_cpu;
> > >  
> > > +	/*
> > > +	 * now rolls down to a period boundary
> > > +	 */
> > > +	now = now && (u64)(~0xFFFFF);
> > This forces now to be 1.
> > 
> > s/&&/&
> Duh, :)

You could also avoid the cast:

	now &= 0xFFFFull;

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

#1377652 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On Wed, Apr 13, 2016 at 04:14:48AM +0800, Yuyang Du wrote:
> On Tue, Apr 12, 2016 at 01:02:58PM +0100, Dietmar Eggemann wrote:
> > On 10/04/16 23:36, Yuyang Du wrote:
> > 
> > [...]
> > 
> > > @@ -2704,11 +2694,14 @@ 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;
> > > -	u32 contrib;
> > > -	unsigned int delta_w, scaled_delta_w, decayed = 0;
> > > +	u64 delta;
> > > +	u32 contrib, periods;
> > >  	unsigned long scale_freq, scale_cpu;
> > >  
> > > +	/*
> > > +	 * now rolls down to a period boundary
> > > +	 */
> > > +	now = now && (u64)(~0xFFFFF);
> > 
> > This forces now to be 1.
> > 
> > s/&&/&
> 
> Duh, :)

Have you, or anybody else, actually tested the impact of this patch?

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

#1378030 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On 10/04/16 23:36, Yuyang Du wrote:
> In __update_load_avg(), the current period is never complete. This
> basically leads to a slightly over-decayed average, say on average we
> have 50% current period, then we will lose 1.08%(=(1-0.5^(1/64)) of
> past avg. More importantly, the incomplete current period significantly
> complicates the avg computation, even a full period is only about 1ms.
> 
> So we attempt to drop it. The outcome is that for any x.y periods to
> update, we will either lose the .y period or unduely gain (1-.y) period.
> How big is the impact? For a large x (say 20ms), you barely notice the
> difference, which is plus/minus 1% (=(before-after)/before). Moreover,
> the aggregated losses and gains in the long run should statistically
> even out.
> 

For a periodic task, the signals really get much more unstable. Even for
a steady state (load/util related) periodic task there is a meander
pattern which depends on if we for instance hit a dequeue (decay +
accrue) or an enqueue (decay only) after the 1ms has elapsed.

IMHO, 1ms is too big to create signals describing task and cpu load/util
signals given the current scheduler dynamics. We simply see too many
signal driving points (e.g. enqueue/dequeue) bailing out of
__update_load_avg().

Examples of 1 periodic task pinned to a cpu on an ARM64 system, HZ=250
in steady state:

(1) task runtime = 100us period = 200us

  pelt		load/util signal

  1us: 		488-491

  1ms: 		483-534

We get ~2 dequeues (load/util example: 493->504) and ~2 enqueues
(load/util example: 496->483) in the meander pattern in the 1ms case.

(2) task runtime = 100us period = 1000us

  pelt	 	load/util signal

  1us: 		103-105

  1ms: 		 84-145

We get ~3-4 dequeues (load/util example: 104->124->134->140) and ~16-20
enqueues (load/util example: 137->134->...->99->97) in the meander
pattern in the 1ms case.

[...]

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

#1378049 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On 13 April 2016 at 17:13, Dietmar Eggemann <dietmar.eggemann@arm.com> wrote:
> On 10/04/16 23:36, Yuyang Du wrote:
>> In __update_load_avg(), the current period is never complete. This
>> basically leads to a slightly over-decayed average, say on average we
>> have 50% current period, then we will lose 1.08%(=(1-0.5^(1/64)) of
>> past avg. More importantly, the incomplete current period significantly
>> complicates the avg computation, even a full period is only about 1ms.
>>
>> So we attempt to drop it. The outcome is that for any x.y periods to
>> update, we will either lose the .y period or unduely gain (1-.y) period.
>> How big is the impact? For a large x (say 20ms), you barely notice the
>> difference, which is plus/minus 1% (=(before-after)/before). Moreover,
>> the aggregated losses and gains in the long run should statistically
>> even out.
>>
>
> For a periodic task, the signals really get much more unstable. Even for
> a steady state (load/util related) periodic task there is a meander
> pattern which depends on if we for instance hit a dequeue (decay +
> accrue) or an enqueue (decay only) after the 1ms has elapsed.
>
> IMHO, 1ms is too big to create signals describing task and cpu load/util
> signals given the current scheduler dynamics. We simply see too many
> signal driving points (e.g. enqueue/dequeue) bailing out of
> __update_load_avg().
>
> Examples of 1 periodic task pinned to a cpu on an ARM64 system, HZ=250
> in steady state:
>
> (1) task runtime = 100us period = 200us
>
>   pelt          load/util signal
>
>   1us:          488-491
>
>   1ms:          483-534
>
> We get ~2 dequeues (load/util example: 493->504) and ~2 enqueues
> (load/util example: 496->483) in the meander pattern in the 1ms case.
>
> (2) task runtime = 100us period = 1000us
>
>   pelt          load/util signal
>
>   1us:          103-105
>
>   1ms:           84-145
>
> We get ~3-4 dequeues (load/util example: 104->124->134->140) and ~16-20
> enqueues (load/util example: 137->134->...->99->97) in the meander
> pattern in the 1ms case.

yes, similarly i have some use cases with 2ms running task in a period
of 5.12ms. it will be seen either as a 1ms running task or a 2ms
running tasks depending on how the running is synced with the 1ms
boundary

so the load will vary between 197-215 up to 396-423 depending of when
the 1ms boundary occurs in the 2ms running

Vincent

>
> [...]

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

#1378097 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On 13 April 2016 at 17:28, Vincent Guittot <vincent.guittot@linaro.org> wrote:
> On 13 April 2016 at 17:13, Dietmar Eggemann <dietmar.eggemann@arm.com> wrote:
>> On 10/04/16 23:36, Yuyang Du wrote:
>>> In __update_load_avg(), the current period is never complete. This
>>> basically leads to a slightly over-decayed average, say on average we
>>> have 50% current period, then we will lose 1.08%(=(1-0.5^(1/64)) of
>>> past avg. More importantly, the incomplete current period significantly
>>> complicates the avg computation, even a full period is only about 1ms.
>>>
>>> So we attempt to drop it. The outcome is that for any x.y periods to
>>> update, we will either lose the .y period or unduely gain (1-.y) period.
>>> How big is the impact? For a large x (say 20ms), you barely notice the
>>> difference, which is plus/minus 1% (=(before-after)/before). Moreover,
>>> the aggregated losses and gains in the long run should statistically
>>> even out.
>>>
>>
>> For a periodic task, the signals really get much more unstable. Even for
>> a steady state (load/util related) periodic task there is a meander
>> pattern which depends on if we for instance hit a dequeue (decay +
>> accrue) or an enqueue (decay only) after the 1ms has elapsed.
>>
>> IMHO, 1ms is too big to create signals describing task and cpu load/util
>> signals given the current scheduler dynamics. We simply see too many
>> signal driving points (e.g. enqueue/dequeue) bailing out of
>> __update_load_avg().
>>
>> Examples of 1 periodic task pinned to a cpu on an ARM64 system, HZ=250
>> in steady state:
>>
>> (1) task runtime = 100us period = 200us
>>
>>   pelt          load/util signal
>>
>>   1us:          488-491
>>
>>   1ms:          483-534
>>
>> We get ~2 dequeues (load/util example: 493->504) and ~2 enqueues
>> (load/util example: 496->483) in the meander pattern in the 1ms case.
>>
>> (2) task runtime = 100us period = 1000us
>>
>>   pelt          load/util signal
>>
>>   1us:          103-105
>>
>>   1ms:           84-145
>>
>> We get ~3-4 dequeues (load/util example: 104->124->134->140) and ~16-20
>> enqueues (load/util example: 137->134->...->99->97) in the meander
>> pattern in the 1ms case.
>
> yes, similarly i have some use cases with 2ms running task in a period
> of 5.12ms. it will be seen either as a 1ms running task or a 2ms

sorry, it's 5.242ms no 5.12ms

> running tasks depending on how the running is synced with the 1ms
> boundary
>
> so the load will vary between 197-215 up to 396-423 depending of when
> the 1ms boundary occurs in the 2ms running
>
> Vincent
>
>>
>> [...]

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

#1378405 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On Wed, Apr 13, 2016 at 05:28:18PM +0200, Vincent Guittot wrote:
> > For a periodic task, the signals really get much more unstable. Even for
> > a steady state (load/util related) periodic task there is a meander
> > pattern which depends on if we for instance hit a dequeue (decay +
> > accrue) or an enqueue (decay only) after the 1ms has elapsed.
> >
> > IMHO, 1ms is too big to create signals describing task and cpu load/util
> > signals given the current scheduler dynamics. We simply see too many
> > signal driving points (e.g. enqueue/dequeue) bailing out of
> > __update_load_avg().

By "bailing out", you mean return without update because the delta is less
than 1ms?

> > Examples of 1 periodic task pinned to a cpu on an ARM64 system, HZ=250
> > in steady state:
> >
> > (1) task runtime = 100us period = 200us
> >
> >   pelt          load/util signal
> >
> >   1us:          488-491
> >
> >   1ms:          483-534

100us/200us = 50%, so the util should center around 512, it seems in this
regard, it is better, but the variance is undesirable.

> > We get ~2 dequeues (load/util example: 493->504) and ~2 enqueues
> > (load/util example: 496->483) in the meander pattern in the 1ms case.
> >
> > (2) task runtime = 100us period = 1000us
> >
> >   pelt          load/util signal
> >
> >   1us:          103-105
> >
> >   1ms:           84-145
> >
> > We get ~3-4 dequeues (load/util example: 104->124->134->140) and ~16-20
> > enqueues (load/util example: 137->134->...->99->97) in the meander
> > pattern in the 1ms case.

The same as above.

> 
> yes, similarly i have some use cases with 2ms running task in a period
> of 5.12ms. it will be seen either as a 1ms running task or a 2ms
> running tasks depending on how the running is synced with the 1ms
> boundary
> 
> so the load will vary between 197-215 up to 396-423 depending of when
> the 1ms boundary occurs in the 2ms running
> 

Same as above, and this time, the util is "expected" to be 2/5.242*1024=391
of all the samples. We solve the problem of overly-decay, but the precision
loss is a new problem.

Let me see if we can get to a 2-level period scheme, :)

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

#1378812 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

On 13/04/16 19:44, Yuyang Du wrote:
> On Wed, Apr 13, 2016 at 05:28:18PM +0200, Vincent Guittot wrote:

[...]

> By "bailing out", you mean return without update because the delta is less
> than 1ms?

yes.

> 
>>> Examples of 1 periodic task pinned to a cpu on an ARM64 system, HZ=250
>>> in steady state:
>>>
>>> (1) task runtime = 100us period = 200us
>>>
>>>   pelt          load/util signal
>>>
>>>   1us:          488-491
>>>
>>>   1ms:          483-534
> 
> 100us/200us = 50%, so the util should center around 512, it seems in this
> regard, it is better, but the variance is undesirable.

I see. You mentioned the over-decay thing in the patch header. Is this
also why you change the contribution of the most recent period from 1002
(1024*y) to 1024?

This variance gets worse if the ratio runtime/period is further reduced
(e.g. 25us/1000us).

You can even create tasks which go stealth mode (e.g. 25us/1048us). It
shows periods of 0 load/util (~1.55s) and than massive spikes (~700 for
~300ms). The short runtime and the task period synced to 1024*1024ns
allow that we hit consecutive enqueues or dequeues for a long time even
the task might drift relative to the pelt window.

[...]

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

#1379449 — Re: [PATCH 2/4] sched/fair: Drop out incomplete current period when sched averages accrue

Hi Dietmar,

On Thu, Apr 14, 2016 at 01:52:43PM +0100, Dietmar Eggemann wrote:
> On 13/04/16 19:44, Yuyang Du wrote:
> > On Wed, Apr 13, 2016 at 05:28:18PM +0200, Vincent Guittot wrote:
> 
> [...]
> 
> > By "bailing out", you mean return without update because the delta is less
> > than 1ms?
> 
> yes.
> 
> > 
> >>> Examples of 1 periodic task pinned to a cpu on an ARM64 system, HZ=250
> >>> in steady state:
> >>>
> >>> (1) task runtime = 100us period = 200us
> >>>
> >>>   pelt          load/util signal
> >>>
> >>>   1us:          488-491
> >>>
> >>>   1ms:          483-534
> > 
> > 100us/200us = 50%, so the util should center around 512, it seems in this
> > regard, it is better, but the variance is undesirable.
> 
> I see. You mentioned the over-decay thing in the patch header. Is this
> also why you change the contribution of the most recent period from 1002
> (1024*y) to 1024?

Yes, it is because that (most recent) period is the "current" period.
 
> This variance gets worse if the ratio runtime/period is further reduced
> (e.g. 25us/1000us).
> 
> You can even create tasks which go stealth mode (e.g. 25us/1048us).

En... this is a good case to beat it.

> It shows periods of 0 load/util (~1.55s) and than massive spikes (~700 for
> ~300ms). The short runtime and the task period synced to 1024*1024ns
> allow that we hit consecutive enqueues or dequeues for a long time even
> the task might drift relative to the pelt window.

But whenever we pass 1ms, we will update. And I am curious, how does the
current 1us works in this case? Anyway, I will reproduce it myself.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web