Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1429002 > unrolled thread

[PATCH v2 00/13] sched: Clean-ups and asymmetric cpu capacity support

Back to article view | Back to linux.kernel

Contents

  [PATCH v2 00/13] sched: Clean-ups and asymmetric cpu capacity support Morten Rasmussen <morten.rasmussen@arm.com> - 2016-06-22 19:10 +0200
    [PATCH v2 11/13] sched/fair: Avoid pulling tasks from non-overloaded higher capacity groups Morten Rasmussen <morten.rasmussen@arm.com> - 2016-06-22 19:10 +0200
    [PATCH v2 09/13] sched/fair: Consider spare capacity in find_idlest_group() Morten Rasmussen <morten.rasmussen@arm.com> - 2016-06-22 19:10 +0200
    [PATCH v2 12/13] arm: Set SD_ASYM_CPUCAPACITY for big.LITTLE platforms Morten Rasmussen <morten.rasmussen@arm.com> - 2016-06-22 19:10 +0200
    [PATCH v2 05/13] sched: Enable SD_BALANCE_WAKE for asymmetric capacity systems Morten Rasmussen <morten.rasmussen@arm.com> - 2016-06-22 19:10 +0200

#1429002 — [PATCH v2 00/13] sched: Clean-ups and asymmetric cpu capacity support

Hi,

The scheduler is currently not doing much to help performance on systems with
asymmetric compute capacities (read ARM big.LITTLE). This series improves the
situation with a few tweaks mainly to the task wake-up path that considers
compute capacity at wake-up and not just whether a cpu is idle for these
systems. This gives us consistent, and potentially higher, throughput in
partially utilized scenarios. SMP behaviour and performance should be
unaffected.

Test 0:
	for i in `seq 1 10`; \
	       do sysbench --test=cpu --max-time=3 --num-threads=1 run; \
	       done \
	| awk '{if ($4=="events:") {print $5; sum +=$5; runs +=1}} \
	       END {print "Average events: " sum/runs}'

Target: ARM TC2 (2xA15+3xA7)

	(Higher is better)
tip:	Average events: 146.9
patch:	Average events: 217.9

Test 1:
	perf stat --null --repeat 10 -- \
	perf bench sched messaging -g 50 -l 5000

Target: Intel IVB-EP (2*10*2)

tip:    4.861970420 seconds time elapsed ( +-  1.39% )
patch:  4.886204224 seconds time elapsed ( +-  0.75% )

Target: ARM TC2 A7-only (3xA7) (-l 1000)

tip:    61.485682596 seconds time elapsed ( +-  0.07% )
patch:  62.667950130 seconds time elapsed ( +-  0.36% )

More analysis:

Statistics from mixed periodic task workload (rt-app) containing both
big and little task, single run on ARM TC2:

tu   = Task utilization big/little
pcpu = Previous cpu big/little
tcpu = This (waker) cpu big/little
dl   = New cpu is little
db   = New cpu is big
sis  = New cpu chosen by select_idle_sibling()
figc = New cpu chosen by find_idlest_*()
ww   = wake_wide(task) count for figc wakeups
bw   = sd_flag & SD_BALANCE_WAKE (non-fork/exec wake)
       for figc wakeups

case tu   pcpu tcpu   dl   db  sis figc   ww   bw
1    l    l    l     122   68   28  162  161  161
2    l    l    b      11    4    0   15   15   15
3    l    b    l       0  252    8  244  244  244
4    l    b    b      36 1928  711 1253 1016 1016
5    b    l    l       5   19    0   24   22   24
6    b    l    b       5    1    0    6    0    6
7    b    b    l       0   31    0   31   31   31
8    b    b    b       1  194  109   86   59   59
--------------------------------------------------
                     180 2497  856 1821

Cases 1-4 + 8 are fine to be served by select_idle_sibling() as both
this_cpu and prev_cpu are suitable cpus for the task. However, as the
figc column reveals, those cases are often served by find_idlest_*()
anyway due to wake_wide() sending the wakeup that way when
SD_BALANCE_WAKE is set on the sched_domains.

Pulling in the wakee_flip patch (dropped in v2) from v1 shifts a
significant share of the wakeups to sis from figc:

case tu   pcpu tcpu   dl   db  sis figc   ww   bw
1    l    l    l     537    8  537    8    6    6
2    l    l    b      49   11   32   28   28   28
3    l    b    l       4  323  322    5    5    5
4    l    b    b       1 1910 1209  702  458  456
5    b    l    l       0    5    0    5    1    5
6    b    l    b       0    0    0    0    0    0
7    b    b    l       0   32    0   32    2   32
8    b    b    b       0  198  168   30   13   13
--------------------------------------------------
                     591 2487 2268  810

Notes:

Active migration of tasks away from small capacity cpus isn't addressed
in this set although it is necessary for consistent throughput in other
scenarios on asymmetric cpu capacity systems.

The infrastructure to enable capacity awareness for arm64 is not provided here
but will be based on Juri's DT bindings patch set [1]. A combined preview
branch is available [2].

[1] https://lkml.org/lkml/2016/6/15/291
[2] git://linux-arm.org/linux-power.git capacity_awareness_v2_arm64_v1

Patch   1-3: Generic fixes and clean-ups.
Patch  4-11: Improve capacity awareness.
Patch 11-12: Arch features for arm to enable asymmetric capacity support.

v2:

- Dropped patch ignoring wakee_flips for pid=0 for now as we can not
  distinguish cpu time processing irqs from idle time.

- Dropped disabling WAKE_AFFINE as suggested by Vincent to allow more
  scenarios to use fast-path (select_idle_sibling()). Asymmetric wake
  conditions adjusted accordingly.

- Changed use of new SD_ASYM_CPUCAPACITY slightly. Now enables
  SD_BALANCE_WAKE.

- Minor clean-ups and rebased to more recent tip/sched/core.

v1: https://lkml.org/lkml/2014/5/23/621

Dietmar Eggemann (1):
  sched: Store maximum per-cpu capacity in root domain

Morten Rasmussen (12):
  sched: Fix power to capacity renaming in comment
  sched/fair: Consistent use of prev_cpu in wakeup path
  sched/fair: Optimize find_idlest_cpu() when there is no choice
  sched: Introduce SD_ASYM_CPUCAPACITY sched_domain topology flag
  sched: Enable SD_BALANCE_WAKE for asymmetric capacity systems
  sched/fair: Let asymmetric cpu configurations balance at wake-up
  sched/fair: Compute task/cpu utilization at wake-up more correctly
  sched/fair: Consider spare capacity in find_idlest_group()
  sched: Add per-cpu max capacity to sched_group_capacity
  sched/fair: Avoid pulling tasks from non-overloaded higher capacity
    groups
  arm: Set SD_ASYM_CPUCAPACITY for big.LITTLE platforms
  arm: Update arch_scale_cpu_capacity() to reflect change to define

 arch/arm/include/asm/topology.h |   5 +
 arch/arm/kernel/topology.c      |  25 ++++-
 include/linux/sched.h           |   3 +-
 kernel/sched/core.c             |  21 +++-
 kernel/sched/fair.c             | 212 +++++++++++++++++++++++++++++++++++-----
 kernel/sched/sched.h            |   5 +-
 6 files changed, 241 insertions(+), 30 deletions(-)

-- 
1.9.1

[toc] | [next] | [standalone]

#1429003 — [PATCH v2 11/13] sched/fair: Avoid pulling tasks from non-overloaded higher capacity groups

For asymmetric cpu capacity systems it is counter-productive for
throughput if low capacity cpus are pulling tasks from non-overloaded
cpus with higher capacity. The assumption is that higher cpu capacity is
preferred over running alone in a group with lower cpu capacity.

This patch rejects higher cpu capacity groups with one or less task per
cpu as potential busiest group which could otherwise lead to a series of
failing load-balancing attempts leading to a force-migration.

cc: Ingo Molnar <mingo@redhat.com>
cc: Peter Zijlstra <peterz@infradead.org>

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
---
 kernel/sched/fair.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 4d10d022006d..ca0048d95b3f 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6789,6 +6789,17 @@ group_is_overloaded(struct lb_env *env, struct sg_lb_stats *sgs)
 	return false;
 }
 
+/*
+ * group_smaller_cpu_capacity: Returns true if sched_group sg has smaller
+ * per-cpu capacity than sched_group ref.
+ */
+static inline bool
+group_smaller_cpu_capacity(struct sched_group *sg, struct sched_group *ref)
+{
+	return sg->sgc->max_capacity * capacity_margin <
+						ref->sgc->max_capacity * 1024;
+}
+
 static inline enum
 group_type group_classify(struct sched_group *group,
 			  struct sg_lb_stats *sgs)
@@ -6892,6 +6903,19 @@ static bool update_sd_pick_busiest(struct lb_env *env,
 	if (sgs->avg_load <= busiest->avg_load)
 		return false;
 
+	if (!(env->sd->flags & SD_ASYM_CPUCAPACITY))
+		goto asym_packing;
+
+	/* Candidate sg has no more than one task per cpu and has
+	 * higher per-cpu capacity. Migrating tasks to less capable
+	 * cpus may harm throughput. Maximize throughput,
+	 * power/energy consequences are not considered.
+	 */
+	if (sgs->sum_nr_running <= sgs->group_weight &&
+	    group_smaller_cpu_capacity(sds->local, sg))
+		return false;
+
+asym_packing:
 	/* This is the busiest node in its class. */
 	if (!(env->sd->flags & SD_ASYM_PACKING))
 		return true;
-- 
1.9.1

[toc] | [prev] | [next] | [standalone]

#1429006 — [PATCH v2 09/13] sched/fair: Consider spare capacity in find_idlest_group()

In low-utilization scenarios comparing relative loads in
find_idlest_group() doesn't always lead to the most optimum choice.
Systems with groups containing different numbers of cpus and/or cpus of
different compute capacity are significantly better off when considering
spare capacity rather than relative load in those scenarios.

In addition to existing load based search an alternative spare capacity
based candidate sched_group is found and selected instead if sufficient
spare capacity exists. If not, existing behaviour is preserved.

cc: Ingo Molnar <mingo@redhat.com>
cc: Peter Zijlstra <peterz@infradead.org>

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
---
 kernel/sched/fair.c | 46 +++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 41 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 2874aeb08fb4..9c9b837742f6 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5058,6 +5058,14 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p,
 	return 1;
 }
 
+static inline int task_util(struct task_struct *p);
+static int cpu_util_wake(int cpu, struct task_struct *p);
+
+static unsigned long capacity_spare_wake(int cpu, struct task_struct *p)
+{
+	return capacity_orig_of(cpu) - cpu_util_wake(cpu, p);
+}
+
 /*
  * find_idlest_group finds and returns the least busy CPU group within the
  * domain.
@@ -5067,7 +5075,9 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 		  int this_cpu, int sd_flag)
 {
 	struct sched_group *idlest = NULL, *group = sd->groups;
+	struct sched_group *most_spare_sg = NULL;
 	unsigned long min_load = ULONG_MAX, this_load = 0;
+	unsigned long most_spare = 0, this_spare = 0;
 	int load_idx = sd->forkexec_idx;
 	int imbalance = 100 + (sd->imbalance_pct-100)/2;
 
@@ -5075,7 +5085,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 		load_idx = sd->wake_idx;
 
 	do {
-		unsigned long load, avg_load;
+		unsigned long load, avg_load, spare_cap, max_spare_cap;
 		int local_group;
 		int i;
 
@@ -5087,8 +5097,12 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 		local_group = cpumask_test_cpu(this_cpu,
 					       sched_group_cpus(group));
 
-		/* Tally up the load of all CPUs in the group */
+		/*
+		 * Tally up the load of all CPUs in the group and find
+		 * the group containing the cpu with most spare capacity.
+		 */
 		avg_load = 0;
+		max_spare_cap = 0;
 
 		for_each_cpu(i, sched_group_cpus(group)) {
 			/* Bias balancing toward cpus of our domain */
@@ -5098,6 +5112,13 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 				load = target_load(i, load_idx);
 
 			avg_load += load;
+
+			spare_cap = capacity_spare_wake(i, p);
+
+			if (spare_cap > max_spare_cap &&
+			    spare_cap > capacity_of(i) >> 3) {
+				max_spare_cap = spare_cap;
+			}
 		}
 
 		/* Adjust by relative CPU capacity of the group */
@@ -5105,12 +5126,27 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 
 		if (local_group) {
 			this_load = avg_load;
-		} else if (avg_load < min_load) {
-			min_load = avg_load;
-			idlest = group;
+			this_spare = max_spare_cap;
+		} else {
+			if (avg_load < min_load) {
+				min_load = avg_load;
+				idlest = group;
+			}
+
+			if (most_spare < max_spare_cap) {
+				most_spare = max_spare_cap;
+				most_spare_sg = group;
+			}
 		}
 	} while (group = group->next, group != sd->groups);
 
+	/* Found a significant amount of spare capacity. */
+	if (this_spare > task_util(p) / 2 &&
+	    imbalance*this_spare > 100*most_spare)
+		return NULL;
+	else if (most_spare > task_util(p) / 2)
+		return most_spare_sg;
+
 	if (!idlest || 100*this_load < imbalance*min_load)
 		return NULL;
 	return idlest;
-- 
1.9.1

[toc] | [prev] | [next] | [standalone]

#1429007 — [PATCH v2 12/13] arm: Set SD_ASYM_CPUCAPACITY for big.LITTLE platforms

Set the SD_ASYM_CPUCAPACITY flag for DIE and MC level sched_domains
on big.LITTLE systems.

cc: Russell King <linux@arm.linux.org.uk>

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
---
 arch/arm/kernel/topology.c | 23 ++++++++++++++++++++---
 1 file changed, 20 insertions(+), 3 deletions(-)

diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c
index ec279d161b32..ab6d9c1835a4 100644
--- a/arch/arm/kernel/topology.c
+++ b/arch/arm/kernel/topology.c
@@ -78,6 +78,7 @@ static unsigned long *__cpu_capacity;
 #define cpu_capacity(cpu)	__cpu_capacity[cpu]
 
 static unsigned long middle_capacity = 1;
+static unsigned int big_little;
 
 /*
  * Iterate all CPUs' descriptor in DT and compute the efficiency
@@ -151,6 +152,8 @@ static void __init parse_dt_topology(void)
 		middle_capacity = ((max_capacity / 3)
 				>> (SCHED_CAPACITY_SHIFT-1)) + 1;
 
+	if (max_capacity && max_capacity != min_capacity)
+		big_little = 1;
 }
 
 /*
@@ -277,15 +280,29 @@ void store_cpu_topology(unsigned int cpuid)
 
 static inline int cpu_corepower_flags(void)
 {
-	return SD_SHARE_PKG_RESOURCES  | SD_SHARE_POWERDOMAIN;
+	int flags = SD_SHARE_PKG_RESOURCES | SD_SHARE_POWERDOMAIN;
+
+	return big_little ? SD_ASYM_CPUCAPACITY | flags : flags;
+}
+
+static inline int arm_cpu_core_flags(void)
+{
+	int flags = SD_SHARE_PKG_RESOURCES;
+
+	return big_little ? SD_ASYM_CPUCAPACITY | flags : flags;
+}
+
+static inline int arm_cpu_cpu_flags(void)
+{
+	return big_little ? SD_ASYM_CPUCAPACITY : 0;
 }
 
 static struct sched_domain_topology_level arm_topology[] = {
 #ifdef CONFIG_SCHED_MC
 	{ cpu_corepower_mask, cpu_corepower_flags, SD_INIT_NAME(GMC) },
-	{ cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
+	{ cpu_coregroup_mask, arm_cpu_core_flags, SD_INIT_NAME(MC) },
 #endif
-	{ cpu_cpu_mask, SD_INIT_NAME(DIE) },
+	{ cpu_cpu_mask, arm_cpu_cpu_flags, SD_INIT_NAME(DIE) },
 	{ NULL, },
 };
 
-- 
1.9.1

[toc] | [prev] | [next] | [standalone]

#1429008 — [PATCH v2 05/13] sched: Enable SD_BALANCE_WAKE for asymmetric capacity systems

Systems with the SD_ASYM_CPUCAPACITY flag set indicate that sched_groups
at this level or below do not include cpus of all capacities available
(e.g. group containing little-only or big-only cpus in big.LITTLE
systems). It is therefore necessary to put in more effort in finding an
appropriate cpu at task wake-up by enabling balancing at wake-up
(SD_BALANCE_WAKE).

cc: Ingo Molnar <mingo@redhat.com>
cc: Peter Zijlstra <peterz@infradead.org>

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
---
 kernel/sched/core.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 351609279341..fe39118ffdfb 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6397,6 +6397,9 @@ sd_init(struct sched_domain_topology_level *tl, int cpu)
 	 * Convert topological properties into behaviour.
 	 */
 
+	if (sd->flags & SD_ASYM_CPUCAPACITY)
+		sd->flags |= SD_BALANCE_WAKE;
+
 	if (sd->flags & SD_SHARE_CPUCAPACITY) {
 		sd->flags |= SD_PREFER_SIBLING;
 		sd->imbalance_pct = 110;
-- 
1.9.1

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web