Scheduler BOF @ LinuxCon.EU/ELCE

Hi,

several people have expressed interest of talking to me about the scheduler during the RTLWS/KS/LinuxCon.EU time-frame. Since I've just about lost track of who all wanted to talk about what and who can and can not make it out to Prague I need help ;-)

Also, since I'm too dis-organized (and mostly busy) to really arrange something, can someone volunteer to arrange a BOF or cafe with beer to discuss things?

The topics I'm most interested in are:

- power optimized load-balancing;
do packing based on cpu utilization
fix the current interface of sched_{mc,ht}_power_savings

- integration of the cpufreq/idle governors and the scheduler use the idle guestimate for NO_HZ
use $foo for $prev-topic to reduce double accounting etc.

- what can we do about the cgroup crap and how can we win some of the performance back;
start with fixing the cgroup enabled but unused case continue from there..

pjt was rewriting load tracking, do tell us about it
also tell us what the status of ncrao's hackery is, or does your hackery replace that?

Things I specifically do not want to talk about:

- systemd, its shit, go away.

I would recommend that LinuxCon is the best place for this. We could decide on a good bar to hold it perhaps, after we've been there for a week to figure out what bar would be good for this :)

It should be after KS so we can get a good idea of what Paul has to say about scheduler load tracking.

IIUC, LinuxCon has a way to add new BoF sessions at the conference. It may be best to wait till then, and just tell people that ask you, to look for it on the LinuxCon schedule postings.

-- Steve

I will attend the ELCE and I'm interested by scheduler discussion

I'm also interested

I'm also interested

We're also interested in this. Judging by the recent wreckage in SMT-balancing I don't have much faith in this code currently. Even in the non balance-for-performance case, stuffing one socket on a multi-socket system at low load levels is probably starting to become attractive with the new package level idle states.

Venki pointed out that there were a few talks at LPC regarding off-lining cores for power-saving. We should try to provide some saner policy.

I'll also note that if we're looking to make any fundmental changes here that testing is kind of a nightmare. But then, I guess that's one of the things I've got to talk about already :-(

I'd extend this to can we unify some of the accounting in general.

Also the knobs that attach to these such as wake_idx are questionable.

Emphatic YES. I will toss: 'can we kill cpuacct (over time) out there'? If not kill, at least migrate the useful fields to cpu and nack any new fields on it so that it can be deprecated. We already track the useful state (via sum_exec_runtime) at an entity level in cpu_cgroup anyway.

So the details are a little fiddly to get right but it's not too bad to explain... although now that I've written the 'longer' version it looks a little dense, short version now prepended!

I'll try to send out the initial draft of the patches but here's how it goes:
Short version:
runnable_i = usage_n_ticks_ago[i] * y^i where y^32 = 1/2
load_i = runnable_i * weight_i

cfs_rq->load_avg = \Sum runnable_load_i (1) + \Sum blocked_load_j (2) For each tick that load remains blocked in (2) we can multiply the whole thing by y to account an additional idle tick.

Longer version and background:
So we currently track the load average at a cfs_rq level, that is

Within each "window" w_j we track: \Sum load_i * t_i where \Sum t_i = w and each load_i represents a disjoint load level.

The load average is then \Sum w_j / 2^n.

Now this works reasonably well but there's a few problems (some of this next bit is a bit of a slog, feel free to skip if not interested):

1) Since decay occurs at boundary (w/2) there are a few 'skews' in the averaging:

- At a window boundary the 'foreground' time has a bias against the time immediately preceding it (as a result of the folding division by
2)
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 'w' you land on.

- 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.

(One of the first things we looked at improving the tracking here was actually not folding the foreground window into the considered average until it is again folded -- when there's more than one window -- this actually did improve the stability a fair amount modulo task migration).

2) 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.

We were actually able to improve the tracking in the pinned case on a stable load to produce a nice stable result, however things fell apart again once you let things move around the system again, even with no load external to the group.

*So*, what do we do?

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:

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^k = 1/2. We currently choose k to be 32 which roughly translates to about a sched period. This means that load tracked 1 P ago contributes about ~50% as the tracking of its immediate runnable state.

Now, the real problem of tracking per-entity is how do you handle the 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.

The fact that y^i above is continuous though has a particularly nice property for this:

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_j they just add the delta to the sum also).

The blocked load looks like: \Sum load_avg_k = \Sum weight_k \Sum(n->inf) u[k]_n * y^n

First consider an individual blocked entity's load: load_avg_k = \Sum u[k]_n * y^n
If we were to account an a new idle 0-th period then u[k]_i+1` = u[k]_i and u[k]_0 = 0, but this is equivalent to just multiplying by y. Since we then get \Sum u[k]_n * y^(n+1)

So then to account an idle tick for all blocked entities all we need to do is multiply the blocked-load sum by y and it's as if everything decayed.

Now to keep this running in constant time we have to be a little more sneaky since we don't get to do this every tick and we don't really want to evaluate load_avg_j * y^n for arbitrary n.

Luckily here we can combine a small look-up table with the fact that we chose y^k = 1/2 to make this always constant time. (specifically y^n = (1/2)^(n/32) * y^(n%32)).

So that gives us the blocked and running load averages.. well almost. See [*] above is not technically an average until you divide by the
elapsed time. We can actually employ further trickery here and
actually never do a division at all for this since: total_time being averaged = \Sum(n->inf) 1 * y^n.
But this is an infinite geometric series and so converges to a/(1-r) which allows us to treat the whole thing as a constant. I'm a little torn on whether to use that or not since having the actual time available does potentially let us do some other things and it also starts to push a little close to 64-bits in the large-blocked-load-sum case if you leave it multiplied in (~45k for y^32=1/2). We only have to do this division at most once a ms though even without the infinite series so it's a non-factor performance wise.

So that was a little dense, the other finicky bits are:
- doing the right thing on root_cgroup since it's not in the entity hierarchy
- accounting the removed load on an affine-wakeup (since we no longer hold the remote rq-lock; an atomic removed-load sum suffices fine here)
- making sure we synchronize with the 'decay' ticks in blocked load when pulling things between the runnable/blocked sums

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.

The property of a per-entity load-contribution could also allows us to make some better decisions in the load-balancer.
e.g. consider 1x80% task and 2x40% tasks on a 2-core machine. It's currently a bit of a crapshoot 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.

Nikhil was never able to reproduce the difference and also wasn't able to get much traction in getting the reporter to collect debugging data to investigate further. This actually does make a pretty big difference for the low-weight balance case so we might want to just consider enabling it again and perhaps then data will be more forthcoming =/.

This should probably be a quick discussion topic since we can probably agree on a sane next step within a few minutes of talking about it. I'll try to dig up where Nikhil's discussions tailed off in the meanwhile.

Things I would throw into the mix:

- wake_idle
We see a measurable benefit from this on a number of applications. Migration latency within a socket is quite reasonable and frequently dominates the run-delay caused by waking on an already running core. This is something it would be nice to talk about bringing back, even if only as a tunable.

- making soft_expires on hrtimers actually useful/usable in ganging wake-ups
- the more general topic of trying to gang background wake-ups

- group level sched-idle; a non-check_preempt_curr ttwu in general

- vruntime for cgroups. The per-entity timelines have a number of problems (e.g. A) for groups g1, g2 we might have g1 < g2 on cpu1, but g2 > g1 on cpu2 -- pre-emption decision is now dependent on where you choose to wake up B) we charge against the group entities current weight, but we're constantly fiddling with that same weight. This can actually work out quite badly when you consider that this fiddling normally has an upwards slope (the longer a task runs the more load_sum_avg on the cfs moves) which results in a lot of local over-charging for time). The stability of the load-tracking above lets us reformulate some things to get a more global notion of vruntime. While this stuff is still quite preliminary we've had some very positive performance results for mysql-oltp vs a cpu-antagonist; it would be interesting to discuss at least.

I would propose Weds/Thurs at LinuxCon/RTLWS. Perhaps Weds afternoon would be better as that would give us Thurs/Fri to continue hallway-tracking any discussion.

I'm happy to co-ordinate; if people want to send me (anywhere on this thread is fine), I can collate everything into a topic list and find out what we need to do to get some BoF space.

Thanks,

- Paul

Yes, people using cpu hotplug for power management like that are insane and should be taken out back and hugged,... by a grizzly bear.

definitely count me in for that.

I won't be in for KS, just linuxcon, and I am busy on Wed 26th.
I believe Steve Roasted's (*) suggestion is a sane one: Many of us
will be in other meetings during this time frame, so maybe is saner to find a free slot in the conference agenda.

(*) not a typo

hi,
i am new to this mailing list and i am a beginner in this kernel
development circle
if any body guide me that is useful for me also to give my effort to that building a kernel