[PATCH v2 0/8] sched/fair: rework the CFS load balance

[Vincent Guittot <vincent.guittot@linaro.org>]

Several wrong task placement have been raised with the current load
balance algorithm but their fixes are not always straight forward and
end up with using biased values to force migrations. A cleanup and rework
of the load balance will help to handle such UCs and enable to fine grain
the behavior of the scheduler for other cases.

Patch 1 has already been sent separatly and only consolidate asym policy
in one place and help the review of the changes in load_balance.

Patch 2 renames the sum of h_nr_running in stats.

Patch 3 removes meaningless imbalance computation to make review of
patch 4 easier.

Patch 4 reworks load_balance algorithm and fixes some wrong task placement
but try to stay conservative.

Patch 5 add the sum of nr_running to monitor non cfs tasks and take that
into account when pulling tasks.

Patch 6 replaces runnable_load by load now that the metrics is only used
when overloaded.

Patch 7 improves the spread of tasks at the 1st scheduling level.

Patch 8 uses utilization instead of load in all steps of misfit task
path.

Some benchmarks results based on 8 iterations of each tests:
- small arm64 dual quad cores system

           tip/sched/core        w/ this patchset    improvement
schedpipe      54981 +/-0.36%        55459 +/-0.31%   (+0.97%)

hackbench
1 groups       0.906 +/-2.34%        0.906 +/-2.88%   (+0.06%)

- large arm64 2 nodes / 224 cores system

           tip/sched/core        w/ this patchset    improvement
schedpipe     125665 +/-0.61%       125455 +/-0.62%   (-0.17%)

hackbench -l (256000/#grp) -g #grp
1 groups      15.263 +/-3.53%       13.776 +/-3.30%   (+9.74%)
4 groups       5.852 +/-0.57%        5.340 +/-8.03%   (+8.75%)
16 groups      3.097 +/-1.08%        3.246 +/-0.97%   (-4.81%)
32 groups      2.882 +/-1.04%        2.845 +/-1.02%   (+1.29%)
64 groups      2.809 +/-1.30%        2.712 +/-1.17%   (+3.45%)
128 groups     3.129 +/-9.74%        2.813 +/-6.22%   (+9.11%)
256 groups     3.559 +/-11.07%       3.020 +/-1.75%  (+15.15%)

dbench
1 groups     330.897 +/-0.27%      330.612 +/-0.77%   (-0.09%)
4 groups     932.922 +/-0.54%      941.817 +/*1.10%   (+0.95%)
16 groups   1932.346 +/-1.37%     1962.944 +/-0.62%   (+1.58%)
32 groups   2251.079 +/-7.93%     2418.531 +/-0.69%   (+7.44%)
64 groups   2104.114 +/-9.67%     2348.698 +/-11.24% (+11.62%)
128 groups  2093.756 +/-7.26%     2278.156 +/-9.74%   (+8.81%)
256 groups  1216.736 +/-2.46%     1665.774 +/-4.68%  (+36.91%)

tip/sched/core sha1:
  a1dc0446d649 ('sched/core: Silence a warning in sched_init()')

Changes since v1:
- fixed some bugs
- Used switch case
- Renamed env->src_grp_type to env->balance_type
- split patches in smaller ones
- added comments

Vincent Guittot (8):
  sched/fair: clean up asym packing
  sched/fair: rename sum_nr_running to sum_h_nr_running
  sched/fair: remove meaningless imbalance calculation
  sched/fair: rework load_balance
  sched/fair: use rq->nr_running when balancing load
  sched/fair: use load instead of runnable load
  sched/fair: evenly spread tasks when not overloaded
  sched/fair: use utilization to select misfit task

 kernel/sched/fair.c  | 769 ++++++++++++++++++++++++++++-----------------------
 kernel/sched/sched.h |   2 +-
 2 files changed, 419 insertions(+), 352 deletions(-)

-- 
2.7.4