Re: [PATCH v2] sched/fair: update scale invariance of PELT

From	Peter Zijlstra <peterz@infradead.org>
Newsgroups	linux.kernel
Subject	Re: [PATCH v2] sched/fair: update scale invariance of PELT
Date	2017-04-12 17:50 +0200
Message-ID	<tvsGS-6f3-21@gated-at.bofh.it> (permalink)
References	(5 earlier) <tv1x0-5Qj-17@gated-at.bofh.it> <tv1GF-5TL-3@gated-at.bofh.it> <tv3It-7q1-3@gated-at.bofh.it> <tvoDf-3Qd-9@gated-at.bofh.it> <tvrUu-5IE-23@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

On Wed, Apr 12, 2017 at 04:50:47PM +0200, Vincent Guittot wrote:
> Le Wednesday 12 Apr 2017 à 13:28:58 (+0200), Peter Zijlstra a écrit :

> > 
> >   |---------|---------|          (wall-time)
> >   ----****------------- F=100%
> >   ----******----------- F= 66%
> >   |--------------|----|          (fudge-time)
> 
> It has been a bit hard for me to catch the diagram above because you scale the
> idle time to get same ratio at 100% and 66% wherease I don't scale idle
> time but only running time.

Ah, so below I wrote that we then scale each window back to equal size,
so the absolute size in wall-time becomes immaterial.

> > (explicitly not used 50%, because then the second window would have
> > collapsed to 0, imagine the joy if you go lower still)
> 
> The second window can't collapse because we are working on delta time not
> absolute wall-time and the delta is for only 1 type at a time: running or idle

Right, but consider what happens when F drops too low, idle goes away
from where there would've been some at F=1. At that point things become
unrecoverable afaict.

> > So in fudge-time the first window has 6/15 == 4/10 for the max-freq /
> > wall-time combo.
> > 
> > > 
> > > Then l = p' - p''. The lost idle time is tracked to apply the same amount of decay
> > > window when the task is sleeping
> > > 
> > > so at the end we have a number of decay window of p''+l = p'' so we still have
> > > the same amount of decay window than previously.
> > 
> > Now, we have to stretch time back to equal window size, and while you do
> > that for the active windows, we have to do manual compensation for idle
> > windows (which is somewhat ugleh) and is where the lost-time comes from.
> 
> We can't stretch idle time because there is no relation between the idle time
> and the current capacity.

Brain melts..

> > Also, this all feels entirely yucky, because as per the above, if we'd
> > ran at 33%, we'd have ended up with a negative time window.
> 
> Not sure to catch how we can end up with negative window. We are working with
> delta time not absolute time.


   |---------|---------|---------|  F=100%
    --****------------------------

   |--------------|----|---------|  F= 66%
    --******----------------------

   |-------------------|---------|  F= 50%
    --********--------------------

   |-----------------------------|  F= 33%
    --************----------------


So what happens is that when the (wall) time for a window goes negative
it simply moves the next window along, until that too is compressed
etc..

So in the above figure, the right most edge of F=33% contains 2 whole
periods of idle time, both contracted to measure 0 (wall) time.

The only thing you have to recover them from is the lost idle time
measure.

> > Not to mention that this only seems to work for low utilization. Once
> > you hit higher utilization scenarios, where there isn't much idle time
> > to compensate for the stretching, things go wobbly. Although both
> > scenarios might end up being the same.
> 
> During the running phase, we calculate how much idle time has diseappeared
> because we are running at lower frequency and we compensate it once back to
> idle. 
> 
> > 
> > And instead of resurrecting 0 sized windows, you throw them out, which
> 
> I don't catch point above

It might've been slightly inaccurate. But the point remains that you
destroy time. Not all accrued lost idle time is recovered.

+               if (sa->util_sum < (LOAD_AVG_MAX * 1000)) {
+                       /*
+                        * Add the idle time stolen by running at lower compute
+                        * capacity
+                        */
+                       delta += sa->stolen_idle_time;
+               }
+               sa->stolen_idle_time = 0;

See here, stolen_idle_time is reset regardless. Time is non-continuous
at that point.


I still have to draw me more interesting cases, I'm not convinced I
fully understand things.

Thread

Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-10 19:40 +0200
  Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-11 10:00 +0200
    Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-11 11:00 +0200
      Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-11 11:50 +0200
        Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-11 12:50 +0200
          Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-11 13:00 +0200
            Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-11 15:10 +0200
              Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-12 13:30 +0200
                Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-12 17:00 +0200
                Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-12 17:50 +0200
                Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-13 11:50 +0200
                Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-13 15:40 +0200
                Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-13 17:00 +0200
                Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-13 20:10 +0200
                Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-14 10:50 +0200
          Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-11 14:10 +0200
    Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-11 11:20 +0200
      Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-11 11:50 +0200
    Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-13 15:40 +0200
      Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-13 17:20 +0200
        Re: [PATCH v2] sched/fair: update scale invariance of PELT Peter Zijlstra <peterz@infradead.org> - 2017-04-13 18:20 +0200
          Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-14 11:00 +0200
            Re: [PATCH v2] sched/fair: update scale invariance of PELT Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-19 18:40 +0200

csiph-web