[RFC PATCH] sched/fair: Bias runqueue selection towards almost idle prev CPU
From: Mathieu Desnoyers
Date: Fri Sep 29 2023 - 14:34:30 EST
Introduce the WAKEUP_BIAS_PREV_IDLE scheduler feature. It biases
select_task_rq towards the previous CPU if it was almost idle
(avg_load <= 0.1%). It eliminates frequent task migrations from almost
idle CPU to completely idle CPUs. This is achieved by using the CPU
load of the previously used CPU as "almost idle" criterion in
wake_affine_idle() and select_idle_sibling().
The following benchmarks are performed on a v6.5.5 kernel with
mitigations=off.
This speeds up the following hackbench workload on a 192 cores AMD EPYC
9654 96-Core Processor (over 2 sockets):
hackbench -g 32 -f 20 --threads --pipe -l 480000 -s 100
from 49s to 32s. (34% speedup)
We can observe that the number of migrations is reduced significantly
(-94%) with this patch, which may explain the speedup:
Baseline: 118M cpu-migrations (9.286 K/sec)
With patch: 7M cpu-migrations (0.709 K/sec)
As a consequence, the stalled-cycles-backend are reduced:
Baseline: 8.16% backend cycles idle
With patch: 6.70% backend cycles idle
Interestingly, the rate of context switch increases with the patch, but
it does not appear to be an issue performance-wise:
Baseline: 454M context-switches (35.677 K/sec)
With patch: 654M context-switches (62.290 K/sec)
This was developed as part of the investigation into a weird regression
reported by AMD where adding a raw spinlock in the scheduler context
switch accelerated hackbench. It turned out that changing this raw
spinlock for a loop of 10000x cpu_relax within do_idle() had similar
benefits.
This patch achieves a similar effect without the busy-waiting by
allowing select_task_rq to favor almost idle previously used CPUs based
on the CPU load of that CPU. The threshold of 0.1% avg_load for almost
idle CPU load has been identified empirically using the hackbench
workload.
Feedback is welcome. I am especially interested to learn whether this
patch has positive or detrimental effects on performance of other
workloads.
Link: https://lore.kernel.org/r/09e0f469-a3f7-62ef-75a1-e64cec2dcfc5@xxxxxxx
Link: https://lore.kernel.org/lkml/20230725193048.124796-1-mathieu.desnoyers@xxxxxxxxxxxx/
Link: https://lore.kernel.org/lkml/20230810140635.75296-1-mathieu.desnoyers@xxxxxxxxxxxx/
Link: https://lore.kernel.org/lkml/20230810140635.75296-1-mathieu.desnoyers@xxxxxxxxxxxx/
Link: https://lore.kernel.org/lkml/f6dc1652-bc39-0b12-4b6b-29a2f9cd8484@xxxxxxx/
Link: https://lore.kernel.org/lkml/20230822113133.643238-1-mathieu.desnoyers@xxxxxxxxxxxx/
Link: https://lore.kernel.org/lkml/20230823060832.454842-1-aaron.lu@xxxxxxxxx/
Link: https://lore.kernel.org/lkml/20230905171105.1005672-1-mathieu.desnoyers@xxxxxxxxxxxx/
Link: https://lore.kernel.org/lkml/cover.1695704179.git.yu.c.chen@xxxxxxxxx/
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: Valentin Schneider <vschneid@xxxxxxxxxx>
Cc: Steven Rostedt <rostedt@xxxxxxxxxxx>
Cc: Ben Segall <bsegall@xxxxxxxxxx>
Cc: Mel Gorman <mgorman@xxxxxxx>
Cc: Daniel Bristot de Oliveira <bristot@xxxxxxxxxx>
Cc: Vincent Guittot <vincent.guittot@xxxxxxxxxx>
Cc: Juri Lelli <juri.lelli@xxxxxxxxxx>
Cc: Swapnil Sapkal <Swapnil.Sapkal@xxxxxxx>
Cc: Aaron Lu <aaron.lu@xxxxxxxxx>
Cc: Chen Yu <yu.c.chen@xxxxxxxxx>
Cc: Tim Chen <tim.c.chen@xxxxxxxxx>
Cc: K Prateek Nayak <kprateek.nayak@xxxxxxx>
Cc: Gautham R . Shenoy <gautham.shenoy@xxxxxxx>
Cc: x86@xxxxxxxxxx
---
kernel/sched/fair.c | 18 +++++++++++++-----
kernel/sched/features.h | 6 ++++++
2 files changed, 19 insertions(+), 5 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 1d9c2482c5a3..65a7d923ea61 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6599,6 +6599,14 @@ static int wake_wide(struct task_struct *p)
return 1;
}
+static bool
+almost_idle_cpu(int cpu, struct task_struct *p)
+{
+ if (!sched_feat(WAKEUP_BIAS_PREV_IDLE))
+ return false;
+ return cpu_load_without(cpu_rq(cpu), p) <= LOAD_AVG_MAX / 1000;
+}
+
/*
* The purpose of wake_affine() is to quickly determine on which CPU we can run
* soonest. For the purpose of speed we only consider the waking and previous
@@ -6612,7 +6620,7 @@ static int wake_wide(struct task_struct *p)
* for the overloaded case.
*/
static int
-wake_affine_idle(int this_cpu, int prev_cpu, int sync)
+wake_affine_idle(int this_cpu, int prev_cpu, int sync, struct task_struct *p)
{
/*
* If this_cpu is idle, it implies the wakeup is from interrupt
@@ -6632,7 +6640,7 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
if (sync && cpu_rq(this_cpu)->nr_running == 1)
return this_cpu;
- if (available_idle_cpu(prev_cpu))
+ if (available_idle_cpu(prev_cpu) || almost_idle_cpu(prev_cpu, p))
return prev_cpu;
return nr_cpumask_bits;
@@ -6687,7 +6695,7 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p,
int target = nr_cpumask_bits;
if (sched_feat(WA_IDLE))
- target = wake_affine_idle(this_cpu, prev_cpu, sync);
+ target = wake_affine_idle(this_cpu, prev_cpu, sync, p);
if (sched_feat(WA_WEIGHT) && target == nr_cpumask_bits)
target = wake_affine_weight(sd, p, this_cpu, prev_cpu, sync);
@@ -7139,7 +7147,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
*/
lockdep_assert_irqs_disabled();
- if ((available_idle_cpu(target) || sched_idle_cpu(target)) &&
+ if ((available_idle_cpu(target) || sched_idle_cpu(target) || (prev == target && almost_idle_cpu(target, p))) &&
asym_fits_cpu(task_util, util_min, util_max, target))
return target;
@@ -7147,7 +7155,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
* If the previous CPU is cache affine and idle, don't be stupid:
*/
if (prev != target && cpus_share_cache(prev, target) &&
- (available_idle_cpu(prev) || sched_idle_cpu(prev)) &&
+ (available_idle_cpu(prev) || sched_idle_cpu(prev) || almost_idle_cpu(prev, p)) &&
asym_fits_cpu(task_util, util_min, util_max, prev))
return prev;
diff --git a/kernel/sched/features.h b/kernel/sched/features.h
index ee7f23c76bd3..b06d06c2b728 100644
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -37,6 +37,12 @@ SCHED_FEAT(CACHE_HOT_BUDDY, true)
*/
SCHED_FEAT(WAKEUP_PREEMPTION, true)
+/*
+ * Bias runqueue selection towards previous runqueue if it is almost
+ * idle.
+ */
+SCHED_FEAT(WAKEUP_BIAS_PREV_IDLE, true)
+
SCHED_FEAT(HRTICK, false)
SCHED_FEAT(HRTICK_DL, false)
SCHED_FEAT(DOUBLE_TICK, false)
--
2.39.2