sched: Improve scalability of select_idle_sibling using SMT balance
RFC PATCH v2 1/1 sched: Improve scalability of select_idle_sibling using SMT balance
Current select_idle_sibling first tries to find a fully idle core using select_idle_core which can potentially search all cores and if it fails it finds any idle cpu using select_idle_cpu. select_idle_cpu can potentially search all cpus in the llc domain. This doesn't scale for large llc domains and will only get worse with more cores in future.
This patch solves the scalability problem of potentially searching all cores or cpus by using a randomized approach called SMT balance. It maintains a utilization of the SMTs per scheduling group based on the number of busy CPUs in the group (henceforth referred to as SMT utilization). This is accounted at the time of context switch. The SMT utilization is maintained only for levels below the LLC domain, so only for cores. During context switch each cpu of a core atomically increments or decrements the SMT utilization variable of that core depending on whether the cpu is going busy or idle. Since the atomic variable is per core, it will be updated only by the hyperthreads in a core with minimal contention. The cost of context_switch() function below with this patch confirms that the overhead is minimal and mostly within noise margin.
In the fast path of wakeup the scheduler compares the target cpu group of select_idle_sibling with a random group in the LLC domain w.r.t SMT utilization to determine a better core to schedule. It chooses the core which has more SMT capacity (idle cpus) left. The SMT capacity is computed simply by subtracting SMT utilization from group weight. This comparison can be done in O(1). Finally it does an idle cpu search only in that core starting from a random cpu index. The random number generation needs to be fast and uses a per cpu pseudo random number generator.
Following are the numbers with various benchmarks on a x86 2 socket system with 22 cores per socket and 2 hyperthreads per core:
hackbench process:
groups baseline-rc6(avg) %stdev patch(avg) %stdev 1 0.4797 15.75 0.4324 (+9.86%) 2.23 2 0.4877 9.99 0.4535 (+7.01%) 3.36 4 0.8603 1.09 0.8376 (+2.64%) 0.95 8 1.496 0.60 1.4516 (+2.97%) 1.38 16 2.6642 0.37 2.5857 (+2.95%) 0.68 32 4.6715 0.40 4.5158 (+3.33%) 0.67
uperf pingpong throughput with loopback interface and message size = 8k:
threads baseline-rc6(avg) %stdev patch(avg) %stdev 8 49.47 0.35 51.16 (+3.42%) 0.53 16 95.28 0.77 101.02 (+6.03%) 0.43 32 156.77 1.17 181.52 (+15.79%) 0.96 48 193.24 0.22 212.90 (+10.17%) 0.45 64 216.21 9.33 264.14 (+22.17%) 0.69 128 379.62 10.29 416.36 (+9.68%) 1.04
Oracle DB TPC-C throughput normalized to baseline:
users baseline-rc6 norm(avg) %stdev patch norm(avg) %stdev 20 1 0.94 1.0071 (+0.71%) 1.03 40 1 0.82 1.0126 (+1.26%) 0.65 60 1 1.10 0.9928 (-0.72%) 0.67 80 1 0.63 1.003 (+0.30%) 0.64 100 1 0.82 0.9957 (-0.43%) 0.15 120 1 0.46 1.0034 (+0.34%) 1.74 140 1 1.44 1.0247 (+2.47%) 0.15 160 1 0.85 1.0445 (+4.45%) 0.81 180 1 0.19 1.0382 (+3.82%) 0.57 200 1 1.40 1.0295 (+2.95%) 0.94 220 1 1.02 1.0242 (+2.42%) 0.85
Following are the cost (in us) of context_switch() and select_idle_sibling() with hackbench 16 groups:
function baseline-rc6 %stdev patch %stdev context_switch() 663.8799 4.46 687.4068 (+3.54%) 2.85 select_idle_sibling() 0.556 1.72 0.263 (-52.70%) 0.78
--- include/linux/sched/topology.h | 2 + kernel/sched/core.c | 38 +++++++ kernel/sched/fair.c | 245 ++++++++++++++++++++--------------------- kernel/sched/idle_task.c | 1 - kernel/sched/sched.h | 26 ++--- kernel/sched/topology.c | 35 +++++- 6 files changed, 197 insertions(+), 150 deletions(-)
include/linux/sched/topology.h +2 -0
@@ -146,6 +146,8 @@ struct sched_domain {struct sched_domain_shared *shared;unsigned int span_weight; +struct sched_group **sg_array; +int sg_num;/* * Span of all CPUs in this domain. *
kernel/sched/core.c +38 -0
@@ -2743,6 +2743,18 @@ asmlinkage __visible void schedule_tail(struct task_struct *prev)put_user (task_pid_vnr (current), current->set_child_tid); } +static __always_inline void +sd_context_switch (struct sched_domain *sd,struct rq *rq,int util) +{ +struct sched_group *sg_cpu = sd->groups; + +/* atomically add/subtract the util */ +if (util >0 ) +atomic_inc ((atomic_t *)&sg_cpu->utilization); +else +atomic_dec ((atomic_t *)&sg_cpu->utilization); +} +/* * context_switch - switch to the new MM and the new thread's register state. */
@@ -2751,6 +2763,31 @@ context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next, struct rq_flags *rf) { struct mm_struct *mm, *oldmm; +int this_cpu = rq->cpu; +struct sched_domain *sd; +int prev_busy, next_busy; + +if (rq->curr_util ==UTIL_UNINITIALIZED ) + prev_busy =0 ; +else + prev_busy = (prev != rq->idle); + next_busy = (next != rq->idle); + +/* +* From sd_llc downward update the SMT utilization. +* Skip the lowest level 0. +*/ + sd =rcu_dereference_sched (per_cpu (sd_llc, this_cpu)); +if (next_busy != prev_busy) { +for_each_lower_domain (sd) { +if (sd->level ==0 ) +break ; +sd_context_switch (sd, rq, next_busy - prev_busy); + } + } + +if (sd) + rq->curr_util = next_busy;prepare_task_switch (rq, prev, next);
@@ -5917,6 +5954,7 @@ void __init sched_init(void) rq->idle_stamp =0 ; rq->avg_idle =2 *sysctl_sched_migration_cost; rq->max_idle_balance_cost = sysctl_sched_migration_cost; + rq->curr_util =UTIL_UNINITIALIZED ;INIT_LIST_HEAD (&rq->cfs_tasks);
kernel/sched/fair.c +117 -128
292 lines not on this page · raw message
kernel/sched/idle_task.c +0 -1
@@ -27,7 +27,6 @@ static struct task_struct * pick_next_task_idle(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) {put_prev_task (rq, prev); -update_idle_core (rq);schedstat_inc (rq->sched_goidle);return rq->idle; }
kernel/sched/sched.h +9 -17
@@ -47,6 +47,11 @@struct rq ;struct cpuidle_state ; +#define CPU_PSEUDO_RANDOM (cpu) (cpu_rq(cpu)->rotor++) + +/* uninitialized state of the rq */ +#define UTIL_UNINITIALIZED -1 +/* task_struct::on_rq states: */ #define TASK_ON_RQ_QUEUED 1#define TASK_ON_RQ_MIGRATING 2
@@ -737,6 +742,8 @@ struct rq {/* cpu of this runqueue: */ int cpu;int online; +unsigned int rotor; +int curr_util;struct list_head cfs_tasks;
@@ -808,23 +815,6 @@ static inline int cpu_of(struct rq *rq)#endif } - -#ifdef CONFIG_SCHED_SMT - -extern struct static_key_false sched_smt_present; - -extern void __update_idle_core (struct rq *rq); - -static inline void update_idle_core (struct rq *rq) -{ -if (static_branch_unlikely (&sched_smt_present)) -__update_idle_core (rq); -} - -#else -static inline void update_idle_core (struct rq *rq) { } -#endif - DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);#define cpu_rq (cpu) (&per_cpu(runqueues, (cpu)))
@@ -1080,6 +1070,8 @@ struct sched_group {unsigned int group_weight;struct sched_group_capacity *sgc;int asym_prefer_cpu;/* cpu of highest priority in group */ +int utilization; +int *cp_array;/* * The CPUs this group covers.
kernel/sched/topology.c +31 -4
@@ -333,8 +333,10 @@ static void free_sched_groups(struct sched_group *sg, int free_sgc)if (free_sgc &&atomic_dec_and_test (&sg->sgc->ref))kfree (sg->sgc); -if (atomic_dec_and_test (&sg->ref)) +if (atomic_dec_and_test (&sg->ref)) { +kfree (sg->cp_array);kfree (sg); + } sg = tmp; }while (sg != first); }
@@ -350,6 +352,9 @@ static void destroy_sched_domain(struct sched_domain *sd)if (sd->shared &&atomic_dec_and_test (&sd->shared->ref))kfree (sd->shared); + +kfree (sd->sg_array); +kfree (sd); }
@@ -910,17 +915,29 @@ build_sched_groups(struct sched_domain *sd, int cpu)* group having more cpu_capacity will pickup more load compared to the * group having less cpu_capacity. */ -static void init_sched_groups_capacity (int cpu,struct sched_domain *sd) +static void init_sched_groups_capacity (int cpu_orig,struct sched_domain *sd) {struct sched_group *sg = sd->groups; +int sg_num =0 , i, cp;WARN_ON (!sg); do { int cpu, max_cpu = -1; + sg_num++; sg->group_weight = cpumask_weight(sched_group_span(sg)); + /* Build the array of cpus for each group */ + if (!sg->cp_array) { + sg->cp_array = kzalloc_node(sg->group_weight * + sizeof(int), GFP_KERNEL, + cpu_to_node(cpu_orig)); + i = 0; + for_each_cpu(cp, sched_group_span(sg)) + sg->cp_array[i++] = cp; + } + if (!(sd->flags & SD_ASYM_PACKING)) goto next;
@@ -936,10 +953,20 @@ static void init_sched_groups_capacity(int cpu, struct sched_domain *sd) sg = sg->next; }while (sg != sd->groups); -if (cpu !=group_balance_cpu (sg)) +/* Build the array of groups for each domain */ + sd->sg_array =kzalloc_node (sg_num *sizeof (void *),GFP_KERNEL , +cpu_to_node (cpu_orig)); + sd->sg_num = sg_num; + i =0 ; +do { + sd->sg_array[i++] = sg; + sg = sg->next; + }while (sg != sd->groups); + +if (cpu_orig !=group_balance_cpu (sg))return ; -update_group_capacity (sd, cpu); +update_group_capacity (sd, cpu_orig); }/*
Signature · 1 line
2.9.3
Peter Zijlstra
maintainerQuoted 17 lines · subhra mazumdar
kernel/sched/core.c +13
-0@@ -2751,6 +2763,31 @@ context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next, struct rq_flags *rf) { struct mm_struct *mm, *oldmm; +int this_cpu = rq->cpu; +struct sched_domain *sd; +int prev_busy, next_busy; + +if (rq->curr_util ==UTIL_UNINITIALIZED ) + prev_busy =0 ; +else + prev_busy = (prev != rq->idle); + next_busy = (next != rq->idle); + +/* +* From sd_llc downward update the SMT utilization. +* Skip the lowest level 0.
kernel/sched/core.c context_switch(struct rq *rq, struct task_struct *prev, · line 2788
Quoted 10 lines
kernel/sched/core.c +10
-0+*/ + sd =rcu_dereference_sched (per_cpu (sd_llc, this_cpu)); +if (next_busy != prev_busy) { +for_each_lower_domain (sd) { +if (sd->level ==0 ) +break ; +sd_context_switch (sd, rq, next_busy - prev_busy); + } + } +
No, we're not going to be adding atomic ops here. We've been arguing over adding a single memory barrier to this path, atomic are just not going to happen.
Also this is entirely the wrong way to do this, we already have code paths that _know_ if they're going into or coming out of idle.
Quoted 33 lines · Peter Zijlstra
Quoted 17 lines · subhra mazumdar
kernel/sched/core.c +13
-0@@ -2751,6 +2763,31 @@ context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next, struct rq_flags *rf) { struct mm_struct *mm, *oldmm; +int this_cpu = rq->cpu; +struct sched_domain *sd; +int prev_busy, next_busy; + +if (rq->curr_util ==UTIL_UNINITIALIZED ) + prev_busy =0 ; +else + prev_busy = (prev != rq->idle); + next_busy = (next != rq->idle); + +/* +* From sd_llc downward update the SMT utilization. +* Skip the lowest level 0. kernel/sched/core.c context_switch(struct rq *rq, struct task_struct *prev, · line 2788
Quoted 10 lines
kernel/sched/core.c +10
-0+*/ + sd =rcu_dereference_sched (per_cpu (sd_llc, this_cpu)); +if (next_busy != prev_busy) { +for_each_lower_domain (sd) { +if (sd->level ==0 ) +break ; +sd_context_switch (sd, rq, next_busy - prev_busy); + } + } +No, we're not going to be adding atomic ops here. We've been arguing over adding a single memory barrier to this path, atomic are just not going to happen.
Quoted 2 lines
Also this is entirely the wrong way to do this, we already have code paths that _know_ if they're going into or coming out of idle.
Yes, it would be more efficient to adjust the busy-cpu count of each level of the hierarchy in pick_next_task_idle and put_prev_task_idle.
- Steve
Quoted 33 lines · Steven Sistare
Quoted 32 lines · Peter Zijlstra
Quoted 17 lines · subhra mazumdar
kernel/sched/core.c +13
-0@@ -2751,6 +2763,31 @@ context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next, struct rq_flags *rf) { struct mm_struct *mm, *oldmm; +int this_cpu = rq->cpu; +struct sched_domain *sd; +int prev_busy, next_busy; + +if (rq->curr_util ==UTIL_UNINITIALIZED ) + prev_busy =0 ; +else + prev_busy = (prev != rq->idle); + next_busy = (next != rq->idle); + +/* +* From sd_llc downward update the SMT utilization. +* Skip the lowest level 0. kernel/sched/core.c context_switch(struct rq *rq, struct task_struct *prev, · line 2788
Quoted 10 lines
kernel/sched/core.c +10
-0+*/ + sd =rcu_dereference_sched (per_cpu (sd_llc, this_cpu)); +if (next_busy != prev_busy) { +for_each_lower_domain (sd) { +if (sd->level ==0 ) +break ; +sd_context_switch (sd, rq, next_busy - prev_busy); + } + } +No, we're not going to be adding atomic ops here. We've been arguing over adding a single memory barrier to this path, atomic are just not going to happen.
Quoted 4 lines
Quoted 2 lines
Also this is entirely the wrong way to do this, we already have code paths that _know_ if they're going into or coming out of idle.
Yes, it would be more efficient to adjust the busy-cpu count of each level of the hierarchy in
pick_next_task_idleandput_prev_task_idle.
OK, I have moved it to pick_next_task_idle/put_prev_task_idle. Will send out the v3.
Thanks,
Subhra
Quoted 2 lines
- Steve