Skip to contentSkip to conversation

sched: Improve scalability of select_idle_sibling using SMT balance

RFC PATCH Superseded subhra mazumdar 3 participants 4 messages Jan 8, 2018 – Jan 11, 2018 Scheduler

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

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
index 7d065ab..cd1f129 100644
@@ -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
index d17c5da..805451b 100644
@@ -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
index 0c00172..a3d5a7c 100644
@@ -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
index 14db76c..2c681cd 100644
@@ -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
index f1cf4f3..09c982f 100644
@@ -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
maintainer
#1 lore raw
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.

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.

#2 lore raw
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

#3 lore raw
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_idle and put_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