[PATCH] hyperthreading scheduler improvement

[PATCH] hyperthreading scheduler improvement

[Robert Love]

Linus,

This patch implements a per-arch load balancing scheme for P4s to better
balance across the virtual CPUs (e.g. prefer fully unused CPUs to a
single available HT unit).  This is the same logic in 2.4-ac, 2.4-aa,
etc.

This patch uses the previously posted per-arch load balancing
infrastructure.

The new logic is keyed off of a new CONFIG_X86_HYPERTHREADING value
which is currently set off of CONFIG_MPENTIUM4.  Thus, only kernels
compiled for P4s will receive the new logic.  It is safe to make the
code available to all x86s, however.

As I am not fortunate enough to have dual Xeons at my disposal, this
patch is largely untested for performance, although it is present in -aa
and -ac.  I suspect this could show very acceptable performance gains.

	Robert Love

diff -urN linux-2.5.31/arch/i386/config.in linux/arch/i386/config.in
--- linux-2.5.31/arch/i386/config.in	Sat Aug 10 21:41:25 2002
+++ linux/arch/i386/config.in	Sat Aug 24 22:07:10 2002
@@ -103,6 +103,7 @@
    define_bool CONFIG_X86_TSC y
    define_bool CONFIG_X86_GOOD_APIC y
    define_bool CONFIG_X86_USE_PPRO_CHECKSUM y
+   define_bool CONFIG_X86_HYPERTHREADING y
 fi
 if [ "$CONFIG_MK6" = "y" ]; then
    define_int  CONFIG_X86_L1_CACHE_SHIFT 5
diff -urN linux-2.5.31/include/asm-i386/processor.h linux/include/asm-i386/processor.h
--- linux-2.5.31/include/asm-i386/processor.h	Sat Aug 10 21:41:18 2002
+++ linux/include/asm-i386/processor.h	Sat Aug 24 22:07:10 2002
@@ -488,4 +488,6 @@
 
 #endif
 
+#define ARCH_HAS_SMP_BALANCE
+
 #endif /* __ASM_I386_PROCESSOR_H */
diff -urN linux-2.5.31/include/asm-i386/smp_balance.h linux/include/asm-i386/smp_balance.h
--- linux-2.5.31/include/asm-i386/smp_balance.h	Wed Dec 31 19:00:00 1969
+++ linux/include/asm-i386/smp_balance.h	Sat Aug 24 22:26:15 2002
@@ -0,0 +1,55 @@
+#ifndef _ASM_SMP_BALANCE_H
+#define _ASM_SMP_BALANCE_H
+
+/*
+ * We have an architecture-specific SMP load balancer to improve
+ * scheduling behavior on hyperthreaded CPUs.  Since only P4s have
+ * HT, we only use the code if CONFIG_MPENTIUM4 is set.
+ *
+ * Distributions may want to make this unconditional to support all
+ * x86 machines on one kernel.  The overhead in the non-P4 case is
+ * minimal while the benefit to SMP P4s is probably decent.
+ */
+#if defined(CONFIG_X86_HYPERTHREADING)
+
+/*
+ * Find any idle processor package (i.e. both virtual processors are idle)
+ */
+static inline int find_idle_package(int this_cpu)
+{
+	int i;
+
+	i = this_cpu;
+
+	for (i = (this_cpu + 1) % NR_CPUS;
+	     i != this_cpu;
+	     i = (i + 1) % NR_CPUS) {
+		int sibling = cpu_sibling_map[i];
+
+		if (idle_cpu(i) && idle_cpu(sibling))
+			return i;
+	}
+	return -1;	/* not found */
+}
+
+static inline int arch_load_balance(int this_cpu, int idle)
+{
+	/* Special hack for hyperthreading */
+       if (unlikely(smp_num_siblings > 1 && idle && !idle_cpu(cpu_sibling_map[this_cpu]))) {
+               int found;
+               struct runqueue *rq_target;
+
+               if ((found = find_idle_package(this_cpu)) >= 0 ) {
+                       rq_target = cpu_rq(found);
+                       resched_task(rq_target->idle);
+                       return 1;
+               }
+       }
+       return 0;
+}
+
+#else
+#define arch_load_balance(x, y)		(0)
+#endif
+
+#endif /* _ASM_SMP_BALANCE_H */

Re: [PATCH] hyperthreading scheduler improvement

[Alan Cox]

On Mon, 2002-08-26 at 21:05, Robert Love wrote:
> Linus,
> 
> This patch implements a per-arch load balancing scheme for P4s to better
> balance across the virtual CPUs (e.g. prefer fully unused CPUs to a
> single available HT unit).  This is the same logic in 2.4-ac, 2.4-aa,
> etc.

This patch is disabled in -ac because it caused crashes for some users

Re: [PATCH] hyperthreading scheduler improvement

[Robert Love]

On Mon, 2002-08-26 at 16:15, Alan Cox wrote:

> This patch is disabled in -ac because it caused crashes for some users

I noticed - I actually got around to doing these patches because I was
trying to find a solution to that problem. :)

Do you think it could be some odd behavior on non-P4 x86 SMP systems? 
Maybe sparse CPU ids?

At least for now, this 2.5 patch is P4-only.

	Robert Love

Re: [PATCH] hyperthreading scheduler improvement

[Alan Cox]

On Mon, 2002-08-26 at 21:25, Robert Love wrote:
> Do you think it could be some odd behavior on non-P4 x86 SMP systems? 
> Maybe sparse CPU ids?
> 
> At least for now, this 2.5 patch is P4-only.


It crashes on P4 systems

Re: [PATCH] hyperthreading scheduler improvement

[Robert Love]

On Mon, 2002-08-26 at 16:35, Alan Cox wrote:

> It crashes on P4 systems

Hm, we must be doing some silly, then...

Similar logic is even in the stock 2.4 scheduler, in
reschedule_idle()...


	Robert Love

Re: [PATCH] hyperthreading scheduler improvement

[Robert Love]

On Mon, 2002-08-26 at 16:05, Robert Love wrote:

Linus,

> This patch implements a per-arch load balancing scheme for P4s to better
> balance across the virtual CPUs (e.g. prefer fully unused CPUs to a
> single available HT unit).  This is the same logic in 2.4-ac, 2.4-aa,
> etc.
> 
> This patch uses the previously posted per-arch load balancing
> infrastructure.

This is an updated version, to use the new asm/sched.h infrastructure
hch suggested (see previous patch).

	Robert Love

diff -urN linux-dogmeat/arch/i386/config.in linux/arch/i386/config.in
--- linux-dogmeat/arch/i386/config.in	Mon Aug 26 16:30:53 2002
+++ linux/arch/i386/config.in	Mon Aug 26 16:45:57 2002
@@ -103,6 +103,7 @@
    define_bool CONFIG_X86_TSC y
    define_bool CONFIG_X86_GOOD_APIC y
    define_bool CONFIG_X86_USE_PPRO_CHECKSUM y
+   define_bool CONFIG_X86_HYPERTHREADING y
 fi
 if [ "$CONFIG_MK6" = "y" ]; then
    define_int  CONFIG_X86_L1_CACHE_SHIFT 5
diff -urN linux-dogmeat/include/asm-i386/sched.h linux/include/asm-i386/sched.h
--- linux-dogmeat/include/asm-i386/sched.h	Mon Aug 26 16:31:12 2002
+++ linux/include/asm-i386/sched.h	Mon Aug 26 16:46:37 2002
@@ -1,7 +1,55 @@
 #ifndef _I386_SCHED_H
 #define _I386_SCHED_H
 
-/* nothing to see here, move along */
-#include <asm-generic/sched.h>
+/*
+ * We have an architecture-specific SMP load balancer to improve
+ * scheduling behavior on hyperthreaded CPUs.  Since only P4s have
+ * HT, we only use the code if CONFIG_MPENTIUM4 is set.
+ *
+ * Distributions may want to make this unconditional to support all
+ * x86 machines on one kernel.  The overhead in the non-P4 case is
+ * minimal while the benefit to SMP P4s is probably decent.
+ */
+#if defined(CONFIG_X86_HYPERTHREADING)
+
+/*
+ * Find any idle processor package (i.e. both virtual processors are idle)
+ */
+static inline int find_idle_package(int this_cpu)
+{
+	int i;
+
+	i = this_cpu;
+
+	for (i = (this_cpu + 1) % NR_CPUS;
+	     i != this_cpu;
+	     i = (i + 1) % NR_CPUS) {
+		int sibling = cpu_sibling_map[i];
+
+		if (idle_cpu(i) && idle_cpu(sibling))
+			return i;
+	}
+	return -1;	/* not found */
+}
+
+static inline int arch_load_balance(int this_cpu, int idle)
+{
+	/* Special hack for hyperthreading */
+       if (unlikely(smp_num_siblings > 1 && idle && !idle_cpu(cpu_sibling_map[this_cpu]))) {
+               int found;
+               struct runqueue *rq_target;
+
+               if ((found = find_idle_package(this_cpu)) >= 0 ) {
+                       rq_target = cpu_rq(found);
+                       resched_task(rq_target->idle);
+                       return 1;
+               }
+       }
+       return 0;
+}
+
+#else
+#define arch_load_balance(x, y)		(0)
+#endif
 
 #endif /* _I386_SCHED_H */