Re: [RFC PATCH 00/14] sched: entity load-tracking re-work

[Vincent Guittot]

On 14 March 2012 16:59, Paul Turner <pjt@xxxxxxxxxx> wrote:
>
> On Mon, Mar 12, 2012 at 3:57 AM, Vincent Guittot
> <vincent.guittot@xxxxxxxxxx> wrote:
> > Hi Paul,
> >
> > On 2 February 2012 02:38, Paul Turner <pjt@xxxxxxxxxx> wrote:
> >> Hi all,
> >>
> >> The attached series is an RFC on implementing load tracking at the entity
> >> instead of cfs_rq level. This results in a bottom-up load-computation in which
> >> entities contribute to their parents load, as opposed to the current top-down
> >> where the parent averages its children.  In particular this allows us to
> >> correctly migrate load with their accompanying entities and provides the
> >> necessary inputs for intelligent load-balancing and power-management.
> >>
> >> It was previously well tested and stable, but that was on v3.1-; there's been
> >> some fairly extensive changes in the wake-up path since so apologies if anything
> >> was broken in the rebase.Note also, since this is also an RFC on the approach I
> >> have not yet de-linted the various CONFIG combinations for introduced compiler
> >> errors.
> >>
> >> Background:
> >> ----------
> >> We currently track the load average at the parenting cfs_rq level. We divide
> >> execution into a series of consecutive "windows, w_i".  Within each we track:
> >>  \Sum load_i * t_i where \Sum t_i = w and each load_i a disjoint load level.
> >>
> >> The load average is then \Sum w_j / 2^n.
> >>
> >> This this works reasonably well but there's a few problems
> >> 1) Since decay occurs at boundary window boundary there are 'skews':
> >> At a window boundary the 'foreground' time has a bias against the
> >> time immediately preceding it (as a result of the folding division)
> >> e.g.  __xx_|_yyyy___ vs __xx_yyyy_|___  (where '|' is a window boundary).
> >>
> >> The accounting here is 2x + 4y/2 or 2x + 4y, depending on which side of the
> >> window your load lands on.
> >>
> >> 2) Everything within a window 'w' is accounted equally, we only fold at
> >> the boundaries.  This actually means you can't set 'w' large enough to
> >> really have meaningful coverage of the sched period without throwing
> >> decay out the window.  But then with w/2 << sched_period (currently
> >> w/2=5ms) the average ends up having fairly drastic swings even with
> >> stable loads.
> >>
> >> (Note:  Before we even looked at migrating to per-entity tracking we evaluating
> >> foreground window into the considered average until it was "complete", this
> >> represented a measurable improvement in stability under predictable load.)
> >>
> >> 3) Since the load sum average is per-cfs_rq and not per-entity when a task
> >> entity migrates we lose its contribution to load-sum and effectively double
> >> count it while it former sum decays.
> >>
> >> New approach:
> >> -------------
> >> Instead of tracking load on a per-cfs_rq basis we do it on a per-sched_entity
> >> basis.  The load sum for a cfs_rq is then just the sum of its childrens' load
> >> averages.  The obvious immediately nice property is that when we migrate thread
> >> A from cpu1-->cpu2, we carry its load with it; leaving the global load sum
> >> unmodified.
> >>
> >> The 'windows' above are replaced with more fine-grained tracking, that is (for
> >> an entity j):
> >>
> >> runnable_j = u_i * y^i , load_avg_j = runnable_j * weight_j [*]
> >>
> >> Where: u_i is the usage in the last i`th ~ms and y is chosen such that
> >> y^~sched_period = 1/2 (we currently choose k=32).This means that load tracked 1
> >> sched_period ago contributes about ~50% as current execution.
> >
> > We have a sched_period of 30ms for a 16 cores system but it's only 12
> > ms on a dual core. Do you think that it's important to keep this rule
> > (y^~sched_period = 1/2) whatever the number of core is ? The
> > sched_period also increases with a large number of running thread
> >
>
> Yes both of these points are valid.
>
> We could consider tuning it on demand, however, I'm not sure it's
> required.  The only real requirement for stability here is that we
> have a period that's typically larger than the scheduling quantum
> (although, without being so large that decay is not meaningful!).
>
> This does not hold in the opposite direction, that is, it's not a
> requirement that we not span several quantums, only that we span at
> least *one*.
>
> We ran it across a variety of topologies (both large and small) in
> LinSched and did not see any immediate ill effects.  I would suggest
> we play this one by ear and see if a negative case arises.
>
> >>
> >> Now, the real challenge in tracking at an entity basis is handling blocked
> >> entities.  Obviously runnable entities will be updated naturally as we iterate
> >> through them but there could be O(many) blocked entities so we can't afford to
> >> iterate through them and update their tracking.
> >>
> >
> > I have run sysbench of my 32bits ARM platform. The results are available below:
> >
> > config 1 : v3.3-rc3 and CONFIG_FAIR_GROUP_SCHED not set
> > config 2 : v3.3-rc3 and CONFIG_FAIR_GROUP_SCHED set
> > config 3 : v3.3-rc3 with your patches and  CONFIG_FAIR_GROUP_SCHED not set
> > config 4 : v3.3-rc3 with your patches and  CONFIG_FAIR_GROUP_SCHED set
> >
> > sysbench --test=cpu --num-threads=12 --max-time=10 run
> >             total number of events
> >             test1 test2 test3
> > config1    336   336   338
> > config2    336   337   338
> > config3    336   338   336
> > config4    336   338   337
> >
> > sysbench --test=threads --thread-locks=9 --num-threads=12 --max-time=10 run
> >             total number of events
> >             test1 test2 test3
> > config1   5218 5228 5203
> > config2   5204 5217 5251
> > config3   5221 5219 5217
> > config4   4859 4796 4836
> >
> >
> > Whereas we have no difference for the cpu test (all the threads on in
> > the run queue waiting for a core), we can see a decrease for the
> > threads test. I'm wondering if it's linked to the fact that I have a
> > 32bits machine doing 64bits division. Have you seen such kind of
> > difference on a 64bits system ?
> >
>
> So I unfortunately do not have a (non-x86) 32-bit system to
> meaningfully benchmark this on.  And yes, 32-bit was my only *real*
> worry so I'm not completely shocked to see an initial regression here
> :-(
>
> With 32-bit performance in mind there are a few obvious things to
> change in our runnable_sum accumulations (these can fit in 32-bit).
> Once we grab those low hanging fruit I'm happy to work with you to see
> what remains.  Do you have any that are externally accessible
> per-chance or would you prefer several differently tuned patch-bombs?
> :)

I will be pleased to help you on (non-x86) 32bits system.
Let me check how we can do for such tests.

>
>
>
> > Regards,
> > Vincent
> >
> >> That our decay for a unit period is exponential introduces a particularly nice
> >> property here:
> >> We can separate the contributed load on a cfs_rq into blocked and runnable.
> >> Runnable load is just the sum of all load_avg_j above, maintained by the
> >> entities themselves as they run and self update (when they update their
> >> load_avg they update the cumulative sum also).
> >>
> >> Blocked load then looks like:
> >>  load_avg_j = weight_k * \Sum u[k]_n * y^n
> >>
> >> To account an entirely idle period we then only need to multiply by y.
> >>
> >> This ends up being orders of magnitude more accurate than the current
> >> tracking schema, even with the old shares_window massively dilated to
> >> better capture a stable load-state.  It's also obviously stable under
> >> migration.
> >>
> >> As referenced above this also allows us to potentially improve decisions within
> >> the load-balancer, for both distribution and power-management.
> >>
> >> Exmaple: consider 1x80% task  and 2x40% tasks on a 2-core machine.  It's
> >> currently a bit of a gamble as to whether you get an {AB, B} or {A,
> >> BB} split since they have equal weight (assume 1024).  With per-task
> >> tracking we can actually consider them at their contributed weight and
> >> see a stable ~{800,{400, 400}} load-split.  Likewise within balance_tasks we can
> >> consider the load migrated to be that actually contributed.
> >>
> >> Thanks,
> >>
> >> - Paul
> >>
> >>
> >> ---
> >>
> >> Ben Segall (1):
> >>      sched: maintain per-rq runnable averages
> >>
> >> Paul Turner (13):
> >>      sched: track the runnable average on a per-task entitiy basis
> >>      sched: aggregate load contributed by task entities on parenting cfs_rq
> >>      sched: maintain the load contribution of blocked entities
> >>      sched: account for blocked load waking back up
> >>      sched: aggregate total task_group load
> >>      sched: compute load contribution by a group entity
> >>      sched: normalize tg load contributions against runnable time
> >>      sched: maintain runnable averages across throttled periods
> >>      sched: replace update_shares weight distribution with per-entity computation
> >>      sched: refactor update_shares_cpu() -> update_blocked_avgs()
> >>      sched: update_cfs_shares at period edge
> >>      sched: make __update_entity_runnable_avg() fast
> >>      sched: implement usage tracking
> >>
> >>
> >>  include/linux/sched.h |   11 +
> >>  kernel/sched/core.c   |    3
> >>  kernel/sched/debug.c  |   37 ++-
> >>  kernel/sched/fair.c   |  714 ++++++++++++++++++++++++++++++++++++++-----------
> >>  kernel/sched/sched.h  |   29 +-
> >>  5 files changed, 611 insertions(+), 183 deletions(-)
> >>
> >>
> >> --
> >> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> >> the body of a message to majordomo@xxxxxxxxxxxxxxx
> >> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >> Please read the FAQ at  http://www.tux.org/lkml/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/