SMT Nice 2.6.4-rc1-mm1

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This patch provides full per-package priority support for SMT processors (aka pentium4 hyperthreading) when combined with CONFIG_SCHED_SMT.

It maintains cpu percentage distribution within each physical cpu package by limiting the time a lower priority task can run on a sibling cpu concurrently with a higher priority task.

It introduces a new flag into the scheduler domain
unsigned int per_cpu_gain; /* CPU % gained by adding domain cpus */

This is empirically set to 15% for pentium4 at the moment and can be modified to support different values dynamically as newer processors come out with improved SMT performance. It should not matter how many siblings there are.

How it works is it compares tasks running on sibling cpus and when a lower static priority task is running it will delay it till high_priority_timeslice * (100 - per_cpu_gain) / 100 <= low_prio_timeslice

eg. a nice 19 task timeslice is 10ms and nice 0 timeslice is 102ms On vanilla the nice 0 task runs on one logical cpu while the nice 19 task runs unabated on the other logical cpu. With smtnice the nice 0 runs on one logical cpu for 102ms and the nice 19 sleeps till the nice 0 task has 12ms remaining and then will schedule.

Real time tasks and kernel threads are not altered by this code, and kernel threads do not delay lower priority user tasks.

with lots of thanks to Zwane Mwaikambo and Nick Piggin for help with the coding of this version.

If this is merged, it is probably best to delay pushing this upstream in mainline till sched_domains gets tested for at least one major release.

Con Kolivas
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFAQt2+ZUg7+tp6mRURAvp0AJ0bBZRByQ3FRDwBaSGQALE28hYkywCghWNY rUjZKrA+G0UHHCYsQsmXuPk=
=E06v
-----END PGP SIGNATURE-----

@@ -1159,8 +1159,12 @@ __init void arch_init_sched_domains(void
 		int j;
 		first_cpu = last_cpu = NULL;
 
-		if (i != first_cpu(cpu_domain->span))
+		if (i != first_cpu(cpu_domain->span)) {
+			cpu_sched_domain(i)->flags |= SD_FLAG_SHARE_CPUPOWER;
+			cpu_sched_domain(first_cpu(cpu_domain->span))->flags |=
+				SD_FLAG_SHARE_CPUPOWER;				
 			continue;
+		}
 
 		for_each_cpu_mask(j, cpu_domain->span) {
 			struct sched_group *cpu = &sched_group_cpus[j];

@@ -1279,8 +1283,12 @@ __init void arch_init_sched_domains(void
 		int j;
 		first_cpu = last_cpu = NULL;
 
-		if (i != first_cpu(cpu_domain->span))
+		if (i != first_cpu(cpu_domain->span)) {
+			cpu_sched_domain(i)->flags |= SD_FLAG_SHARE_CPUPOWER;
+			cpu_sched_domain(first_cpu(cpu_domain->span))->flags |=
+				SD_FLAG_SHARE_CPUPOWER;				
 			continue;
+		}
 
 		for_each_cpu_mask(j, cpu_domain->span) {
 			struct sched_group *cpu = &sched_group_cpus[j];

@@ -542,6 +542,7 @@ do { if (atomic_dec_and_test(&(tsk)->usa
 #define SD_FLAG_EXEC		2	/* Balance on exec */
 #define SD_FLAG_WAKE		4	/* Balance on task wakeup */
 #define SD_FLAG_FASTMIGRATE	8	/* Sync wakes put task on waking CPU */
+#define SD_FLAG_SHARE_CPUPOWER	16	/* Domain members share cpu power */
 
 struct sched_group {
 	struct sched_group *next;	/* Must be a circular list */

@@ -567,6 +568,7 @@ struct sched_domain {
 	unsigned int imbalance_pct;	/* No balance until over watermark */
 	unsigned long long cache_hot_time; /* Task considered cache hot (ns) */
 	unsigned int cache_nice_tries;	/* Leave cache hot tasks for # tries */
+	unsigned int per_cpu_gain;	/* CPU % gained by adding domain cpus */
 	int flags;			/* See SD_FLAG_* */
 
 	/* Runtime fields. */

@@ -586,6 +588,7 @@ struct sched_domain {
 	.imbalance_pct		= 110,			\
 	.cache_hot_time		= 0,			\
 	.cache_nice_tries	= 0,			\
+	.per_cpu_gain		= 15,			\
 	.flags			= SD_FLAG_FASTMIGRATE | SD_FLAG_NEWIDLE | SD_FLAG_WAKE,\
 	.last_balance		= jiffies,		\
 	.balance_interval	= 1,			\

@@ -603,6 +606,7 @@ struct sched_domain {
 	.imbalance_pct		= 125,			\
 	.cache_hot_time		= (5*1000000/2),	\
 	.cache_nice_tries	= 1,			\
+	.per_cpu_gain		= 100,			\
 	.flags			= SD_FLAG_FASTMIGRATE | SD_FLAG_NEWIDLE,\
 	.last_balance		= jiffies,		\
 	.balance_interval	= 1,			\

@@ -621,6 +625,7 @@ struct sched_domain {
 	.imbalance_pct		= 125,			\
 	.cache_hot_time		= (10*1000000),		\
 	.cache_nice_tries	= 1,			\
+	.per_cpu_gain		= 100,			\
 	.flags			= SD_FLAG_EXEC,		\
 	.last_balance		= jiffies,		\
 	.balance_interval	= 1,			\

And here are some benchmarks to demonstrate what happens.
P4 3.06Ghz booted with bios HT off as UP (up), SMP with mm1(mm1), SMP with mm1-smtnice(sn)

What would a benchmark from me be if not based on a kernel compile? These numbers are coarse so the range is about +/- 2 seconds however the results should be clear. Time is in seconds, rounded.

Straight kernel compile: make
Time
up 87
mm1 88
sn 88

Concurrent kernel compiles, one make, the other nice +19 make

		Nice0	Nice19

up 183 235
mm1 208 211
sn 180 237

Kernel compile with an artifical cpu load running nice +19 (while true ; do a=1 ; done)
Time
up 92
mm1 129
sn 104

Kernel compile with a true distributed computing cache burner running nice +19 (mprime www.mersenne.org)
Time
up 96
mm1 168
sn 94

Clearly the type of load running will influence the balance here depending on how long the task actually runs and how cache intensive it is. Basically for real world loads priority is very poorly preserved by default because of the shared cpu resources, and the worst case is a very common one; running a distributed computing client.

Note this patch has no demonstrable effect if tasks are run at the same nice value.

Con

Pretty impressive numbers.

How does it go on the desktop when running mprime at nice +19? How much worse can latencies of the niced tasks become? Any idea?

Worst case scenario is easy to model; if a nice -19 task starts at exactly the same time as a nice +19 task, the timeslices are 200 and 10ms. On uniprocessor the nice+19 task will wait _at least_ 200 ms. On SMT nice SMP it will be 200 - (200 * 15 / 100) so 170ms. That is of course worst case scenario and still better than UP since the latency will be less, the task will definitely start (interactive reinsertion wont affect it) and it will be on a second runqueue.

Con

Ok if you're having trouble with working that out it's because it's wrong goddamn it. It's when the timeslice of the high priority task drops to 10 * 100 / 85 so when it drops to 12ms. ie 188 ms latency.

Con

OK thats good. I'm still not exactly how to generalise the cpu power / impact stuff, but that isn't critical. It should be done some time though.

I'd be happy to see this patch in -mm. As Con mentioned, it would be probably good to merge it one major release after base sched domains is merged (if ever).

Thanks Con.

Woops forgot to answer this one. Since this was the problem that started it all you can imagine it works well and indeed I find it works very nicely. Actually I tend to run two mprime clients with affinity set for each logical cpu and it's not noticable. Previously one mprime client would make the machine run at half speed and it was painfully obvious.

Con