make cpu_sibling_map a cpumask_t

I'm not aware of any reason why the kernel should not become generally SMT aware. It is sufficiently different to SMP that it is worth specialising it, although I am only aware of P4 and POWER5 implementations.

I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

Before Ingo's is merged, I would like to discuss the pros and cons of both approaches with those interested. If Ingo's is accepted I should still be able to port my other SMP/NUMA improvements on top of it.

Quoted 6 lines

I'm not aware of any reason why the kernel should not become generally SMT aware. It is sufficiently different to SMP that it is worth specialising it, although I am only aware of P4 and POWER5 implementations.

I agree, SMT is likely to become more popular in the coming years.

Quoted 4 lines

I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

Quoted 4 lines

Before Ingo's is merged, I would like to discuss the pros and cons of both approaches with those interested. If Ingo's is accepted I should still be able to port my other SMP/NUMA improvements on top of it.

Sounds good, have you got anything to test? I can throw it on a POWER5.

I don't have an architecture independant way to build SMT scheduling descriptions, although with the cpu_sibling_map change, you can copy and paste the code for the P4 if you are able to build a cpu_sibling_map.

I'll just have to add a some bits so SMT and NUMA work together which I will be unable to test. I'll get back to you with some code.

http://www.kerneltrap.org/~npiggin/w26/
Against 2.6.0-test11

Quoted 2 lines · Nick Piggin

http://www.kerneltrap.org/~npiggin/w26/
Against 2.6.0-test11

Oh, this patchset also (mostly) cures my pet hate for the last few months: VolanoMark on the NUMA.

http://www.kerneltrap.org/~npiggin/w26/vmark.html

The "average" plot for w26 I think is a little misleading because it got an unlucky result on the second last point making it look like its has a downward curve. It is usually more linear with a sharp downward spike at 150 rooms like the "maximum" plot.

Don't ask me why it runs out of steam at 150 rooms. hackbench does something similar. I think it might be due to some resource running short, or a scalability problem somewhere else.

Quoted 18 lines · On Thu, 11 Dec 2003 18:24:20 +1100 Nick Piggin <[email protected]> wrote:

Quoted 3 lines · Nick Piggin

http://www.kerneltrap.org/~npiggin/w26/
Against 2.6.0-test11

Oh, this patchset also (mostly) cures my pet hate for the last few months: VolanoMark on the NUMA.

http://www.kerneltrap.org/~npiggin/w26/vmark.html

The "average" plot for w26 I think is a little misleading because it got an unlucky result on the second last point making it look like its has a downward curve. It is usually more linear with a sharp downward spike at 150 rooms like the "maximum" plot.

Quoted 4 lines

Don't ask me why it runs out of steam at 150 rooms. hackbench does something similar. I think it might be due to some resource running short, or a scalability problem somewhere else.

i didn't had the time to apply the patches (w26 and C1 from ingo ) on a vanilla t11, but i merged them with the wli-2,btw this one has really put my box on steroids ;) .

none of them finished a hackbench 320 run, the OOM killed all of my agetty's logging me out. the box is a 1way p4(HT) 1gb of ram and no swap heh.

	hackbench:

	sched-rollup-w26		sched-SMT-2.6.0-test11-C1
		
	 50	 4.839			 50	5.200
	100	 9.415			100	10.090
	150	14.469			150	14.764

	

	time tar -xvjpf linux-2.6.0-test11.tar.bz2:

	sched-rollup-w26		sched-SMT-2.6.0-test11-C1
	
	real		43.396		real		23.136

	user		27.608		user		20.700
	sys		 4.039		sys		 4.344

You won't be able to merge mine with Ingo's. Which one put the box on steroids? :)

Wonder whats going on here? Is this my patch vs Ingo's with nothing else applied?
How does plain 2.6.0-test11 go?

Thanks for testing.

Quoted 3 lines · On Thu, 11 Dec 2003 19:14:45 +1100 Nick Piggin <[email protected]> wrote:

You won't be able to merge mine with Ingo's. Which one put the box on steroids? :)

sorry if i wasn't clearly enough, but i merged each one of them separately on top of a wli-2. that comment was for the wli changes. :)

Quoted 5 lines

Wonder whats going on here? Is this my patch vs Ingo's with nothing else applied? How does plain 2.6.0-test11 go?

Thanks for testing.

ok, this time on a plain test11.

hackbench:

		w26						sched-SMT-C1

	 50	 5.026				 50	 5.182
	100	10.062				100	10.602
	150	15.906				150	16.214

time tar -xvjpf linux-2.6.0-test11.tar.bz2:

		w26						sched-SMT-C1
		
	real	0m21.835s			real	0m21.827s
	user	0m20.274s			user	0m20.412s
	sys	0m4.178s				sys	0m4.260s

Quoted 7 lines

The "average" plot for w26 I think is a little misleading because it got an unlucky result on the second last point making it look like its has a downward curve. It is usually more linear with a sharp downward spike at 150 rooms like the "maximum" plot. Don't ask me why it runs out of steam at 150 rooms. hackbench does something similar. I think it might be due to some resource running short, or a scalability problem somewhere else.

i didn't had the time to apply the patches (w26 and C1 from ingo ) on a vanilla t11, but i merged them with the wli-2,btw this one has really put my box on steroids ;) .
none of them finished a hackbench 320 run, the OOM killed all of my agetty's logging me out. the box is a 1way p4(HT) 1gb of ram and no swap heh.

It might help to check how many processes and/or threads are involved. I've got process scalability stuff in there (I'm not sure how to read your comments though they seem encouraging).

Quoted 3 lines

It might help to check how many processes and/or threads are involved. I've got process scalability stuff in there (I'm not sure how to read your comments though they seem encouraging).

heh, they were supposed to .it really looks good. if you provide me a test path to address your changes, i'll happily put it on.

Don't ask me why it runs out of steam at 150 rooms. hackbench does something similar. I think it might be due to some resource running short, or a scalability problem somewhere else.

OK, it is spinning on .text.lock.futex. The following results are top 10 profiles from a 120 rooms run and a 150 rooms run. The 150 room run managed only 24.8% the throughput of the 120 room run. Might this be a JVM problem?
I'm using Sun Java HotSpot(TM) Server VM (build 1.4.2_01-b06, mixed mode)
ROOMS 120 150
PROFILES
total 100.0% 100.0%
default_idle 81.0% 66.8%

.text.lock.rwsem          4.6%            1.3%
schedule                  1.9%            1.4%
.text.lock.futex          1.5%           19.1%
__wake_up                 1.1%            1.3%
futex_wait                0.7%            2.8%
futex_wake                0.7%            0.5%
.text.lock.dev            0.6%            0.2%
rwsem_down_read_failed    0.5%

unqueue_me 3.2%

Quoted 17 lines · Nick Piggin

OK, it is spinning on .text.lock.futex. The following results are top 10 profiles from a 120 rooms run and a 150 rooms run. The 150 room run managed only 24.8% the throughput of the 120 room run. Might this be a JVM problem?
I'm using Sun Java HotSpot(TM) Server VM (build 1.4.2_01-b06, mixed mode)
ROOMS 120 150
PROFILES
total 100.0% 100.0%
default_idle 81.0% 66.8%

.text.lock.rwsem          4.6%            1.3%
schedule                  1.9%            1.4%
.text.lock.futex          1.5%           19.1%
__wake_up                 1.1%            1.3%
futex_wait                0.7%            2.8%
futex_wake                0.7%            0.5%
.text.lock.dev            0.6%            0.2%
rwsem_down_read_failed    0.5%

Quoted 2 lines

unqueue_me 3.2%

If this thing is heavily threaded, it could be mm->page_table_lock.

Quoted 1 line

If this thing is heavily threaded, it could be mm->page_table_lock.

I'm not sure how threaded it is, probably very. Would inline spinlocks help show up mm->page_table_lock?
It really looks like .text.lock.futex though, doesn't it? Would that be the hashed futex locks? I wonder why it suddenly goes downhill past about 140 rooms though.

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines

If this thing is heavily threaded, it could be mm->page_table_lock.

Quoted 6 lines · Nick Piggin

I'm not sure how threaded it is, probably very. Would inline spinlocks help show up mm->page_table_lock?
It really looks like .text.lock.futex though, doesn't it? Would that be the hashed futex locks? I wonder why it suddenly goes downhill past about 140 rooms though.

It will get contention anyway if they're all pounding on the same futex. OTOH, if they're all threads in the same process, they can hit other problems. I'll try to find out more about hackbench.

Quoted 3 lines

It will get contention anyway if they're all pounding on the same futex. OTOH, if they're all threads in the same process, they can hit other problems. I'll try to find out more about hackbench.

Oh, sorry I was talking about volanomark. hackbench AFAIK doesn't use futexes at all, just pipes, and is not threaded at all, so it looks like a different problem to the volanomark one.
hackbench runs into trouble at large numbers of tasks too though.

Quoted 4 lines · William Lee Irwin III

Quoted 4 lines

It will get contention anyway if they're all pounding on the same futex. OTOH, if they're all threads in the same process, they can hit other problems. I'll try to find out more about hackbench.

Quoted 5 lines · Nick Piggin

Oh, sorry I was talking about volanomark. hackbench AFAIK doesn't use futexes at all, just pipes, and is not threaded at all, so it looks like a different problem to the volanomark one.
hackbench runs into trouble at large numbers of tasks too though.

Volano is all one process address space so it could be ->page_table_lock; any chance you could find which spin_lock() call the pounded chunk of the lock section jumps back to?

Quoted 3 lines

Volano is all one process address space so it could be ->page_table_lock; any chance you could find which spin_lock() call the pounded chunk of the lock section jumps back to?

OK its in futex_wait, up_read(&current->mm->mmap_sem) right after out_release_sem (line 517).
So you get half points. Looks like its waiting on the bus rather than spinning on a lock. Or am I'm wrong?

Quoted 4 lines · William Lee Irwin III

Quoted 4 lines

Volano is all one process address space so it could be ->page_table_lock; any chance you could find which spin_lock() call the pounded chunk of the lock section jumps back to?

On Fri, Dec 12, 2003 at 02:30:27AM +1100, Nick Piggin wrote:

Quoted 5 lines

OK its in futex_wait, up_read(&current->mm->mmap_sem) right after out_release_sem (line 517).
So you get half points. Looks like its waiting on the bus rather than spinning on a lock. Or am I'm wrong?

There is a spinloop in __up_read(), which is probably it.

Quoted 1 line

There is a spinloop in __up_read(), which is probably it.

Oh I see - in rwsem_wake?

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines

There is a spinloop in __up_read(), which is probably it.

Quoted 2 lines · Nick Piggin

Oh I see - in rwsem_wake?

Even before that:

static inline void __up_read(struct rw_semaphore *sem)

{
       __s32 tmp = -RWSEM_ACTIVE_READ_BIAS;
       __asm__ __volatile__(
               "# beginning __up_read\n\t"
LOCK_PREFIX     "  xadd      %%edx,(%%eax)\n\t" /* subtracts 1, returns the old value */
               "  js        2f\n\t" /* jump if the lock is being waited upon */
               "1:\n\t"
               LOCK_SECTION_START("")
               "2:\n\t"
               "  decw      %%dx\n\t" /* do nothing if still outstanding active readers
*/
               "  jnz       1b\n\t"
               "  pushl     %%ecx\n\t"
               "  call      rwsem_wake\n\t"
               "  popl      %%ecx\n\t"
               "  jmp       1b\n"

LOCK_SECTION_END

I think there shouldn't be a loop - remember the lock section.

Quoted 16 lines · William Lee Irwin III

Quoted 4 lines · William Lee Irwin III

Quoted 4 lines

It will get contention anyway if they're all pounding on the same futex. OTOH, if they're all threads in the same process, they can hit other problems. I'll try to find out more about hackbench.

Quoted 5 lines · Nick Piggin

Oh, sorry I was talking about volanomark. hackbench AFAIK doesn't use futexes at all, just pipes, and is not threaded at all, so it looks like a different problem to the volanomark one.
hackbench runs into trouble at large numbers of tasks too though.

Quoted 6 lines

Volano is all one process address space so it could be ->page_table_lock;
any chance you could find which spin_lock() call the pounded chunk of the lock section jumps back to?

OK its in futex_wait, up_read(&current->mm->mmap_sem) right after out_release_sem (line 517).

So you get half points. Looks like its waiting on the bus rather than spinning on a lock. Or am I'm wrong?

The following patch moves the rwsem's up_read wake ups out of the wait_lock. Wakeups need to aquire a runqueue lock which is probably getting contended. The following graph is a best of 3 runs average.
http://www.kerneltrap.org/~npiggin/rwsem.png

The part to look at is the tail. I need to do some more testing to see if its significant.

getting contended. The following graph is a best of 3 runs average.
http://www.kerneltrap.org/~npiggin/rwsem.png

The part to look at is the tail. I need to do some more testing to see if its significant.

Quoted 3 lines · Nick Piggin

getting contended. The following graph is a best of 3 runs average.
http://www.kerneltrap.org/~npiggin/rwsem.png

the graphs are too noise to be conclusive.

Quoted 3 lines

The part to look at is the tail. I need to do some more testing to see if its significant.

yes, could you go from 150 to 300?

Quoted 14 lines · Ingo Molnar

Quoted 3 lines · Nick Piggin

getting contended. The following graph is a best of 3 runs average.
http://www.kerneltrap.org/~npiggin/rwsem.png

the graphs are too noise to be conclusive.

Quoted 3 lines

The part to look at is the tail. I need to do some more testing to see if its significant.

Quoted 2 lines

yes, could you go from 150 to 300?

The benchmark dies at 160 rooms unfortunately. Probably something in the JVM.

I'll do a larger number of runs around the 130-150 mark.

Quoted 5 lines · Nick Piggin

The benchmark dies at 160 rooms unfortunately. Probably something in the JVM.

Quoted 2 lines

I'll do a larger number of runs around the 130-150 mark.

OK, this is an average of 5 runs at 145, 150, 155 rooms with my scheduler patches, with and without my rwsem patch. Its all over the place, but I think rwsem does give a small but significant improvement.

http://www.kerneltrap.org/~npiggin/rwsem2.png

Quoted 6 lines · Nick Piggin

OK, this is an average of 5 runs at 145, 150, 155 rooms with my scheduler patches, with and without my rwsem patch. Its all over the place, but I think rwsem does give a small but significant improvement.

http://www.kerneltrap.org/~npiggin/rwsem2.png

What do you think? Is there any other sorts of benchmarks I should try? The improvement I think is significant, although volanomark is quite erratic and doesn't show it well.

I don't see any problem with moving the wakeups out of the rwsem's spinlock.

Quoted 7 lines

What do you think? Is there any other sorts of benchmarks I should try? The improvement I think is significant, although volanomark is quite erratic and doesn't show it well.

I don't see any problem with moving the wakeups out of the rwsem's spinlock.

Actually my implementation does have a race because list_del_init isn't atomic. Shouldn't be difficult to fix if anyone cares about it... otherwise I won't bother.

Quoted 7 lines

Quoted 7 lines

What do you think? Is there any other sorts of benchmarks I should try? The improvement I think is significant, although volanomark is quite erratic and doesn't show it well.

I don't see any problem with moving the wakeups out of the rwsem's spinlock.

Quoted 4 lines

Actually my implementation does have a race because list_del_init isn't atomic. Shouldn't be difficult to fix if anyone cares about it... otherwise I won't bother.

If you can fix it up, I'll get people here to do some more testing on the patch on other benchmarks, etc.

Quoted 4 lines · Nick Piggin

Don't ask me why it runs out of steam at 150 rooms. hackbench does something similar. I think it might be due to some resource running short, or a scalability problem somewhere else.

OK, it is spinning on .text.lock.futex. The following results are top 10 profiles from a 120 rooms run and a 150 rooms run. The 150 room run managed only 24.8% the throughput of the 120 room run.

Might this be a JVM problem?

I'm using Sun Java HotSpot(TM) Server VM (build 1.4.2_01-b06, mixed mode)

ROOMS 120 150
PROFILES
total 100.0% 100.0%
default_idle 81.0% 66.8%

.text.lock.rwsem          4.6%            1.3%
schedule                  1.9%            1.4%
.text.lock.futex          1.5%           19.1%

http://www.kerneltrap.org/~npiggin/w26/
Against 2.6.0-test11

This includes the SMT description for P4. Initial results shows comparable performance to Ingo's shared runqueue's patch on a dual P4 Xeon.

Quoted 6 lines · Nick Piggin

http://www.kerneltrap.org/~npiggin/w26/
Against 2.6.0-test11

This includes the SMT description for P4. Initial results shows comparable performance to Ingo's shared runqueue's patch on a dual P4 Xeon.

Is there any value in testing/using this on a single CPU P4-HT system, or is it only targeted at multi-CPU systems?

http://www.kerneltrap.org/~npiggin/w26/
Against 2.6.0-test11

This includes the SMT description for P4. Initial results shows comparable performance to Ingo's shared runqueue's patch on a dual P4 Xeon.

In message <[email protected]> you write:

Quoted 6 lines

http://www.kerneltrap.org/~npiggin/w26/
Against 2.6.0-test11

This includes the SMT description for P4. Initial results shows comparable performance to Ingo's shared runqueue's patch on a dual P4 Xeon.

I'm still not convinced. Sharing runqueues is simple, and in fact exactly what you want for HT: you want to balance *runqueues*, not CPUs. In fact, it can be done without a CONFIG_SCHED_SMT addition.

Your patch is more general, more complex, but doesn't actually seem to buy anything. It puts a general domain structure inside the scheduler, without putting it anywhere else which wants it (eg. slab cache balancing). My opinion is either (1) produce a general NUMA topology which can then be used by the scheduler, or (2) do the minimal change in the scheduler which makes HT work well.

Note: some of your changes I really like, it's just that I think this is overkill.

I'll produce a patch so we can have something solid to talk about.

w26 does ALL this, while sched.o is 3K smaller than Ingo's shared runqueue patch on NUMA and SMP, and 1K smaller on UP (although sched.c is 90 lines longer). kernbench system time is down nearly 10% on the NUMAQ, so it isn't hurting performance either.

Quoted 6 lines

w26 does ALL this, while sched.o is 3K smaller than Ingo's shared runqueue
patch on NUMA and SMP, and 1K smaller on UP (although sched.c is 90 lines longer). kernbench system time is down nearly 10% on the NUMAQ, so it isn't
hurting performance either.

Hackbench performance on the NUMAQ is improved by nearly 50% at large numbers of tasks due to a better scaling factor (which I think is slightly "more" linear too). It is also improved by nearly 25% (4.08 vs 3.15) on OSDLs 8 ways at small number of tasks, due to a better constant factor.

http://www.kerneltrap.org/~npiggin/w26/hbench.png

And yeah hackbench kills the NUMAQ after about 350 rooms. This is due to memory shortages. All the processes are getting stuck in shrink_caches, get_free_pages, etc.

Thanks for having a look Rusty. I'll try to convince you :)

As you know, the domain classes is not just for HT, but can do multi levels of NUMA, and it can be built by architecture specific code which is good for Opteron, for example. It doesn't need CONFIG_SCHED_SMT either, of course,
or CONFIG_NUMA even: degenerate domains can just be collapsed (code isn't there to do that now).

Shared runqueues I find isn't so flexible. I think it perfectly describes the P4 HT architecture, but what happens if (when) siblings get seperate L1 caches? What about SMT, CMP, SMP and NUMA levels in the POWER5?

The large SGI (and I imagine IBM's POWER5s) systems need things like progressive balancing backoff and would probably benefit with a more heirachical balancing scheme so all the balancing operations don't kill the system.

w26 does ALL this, while sched.o is 3K smaller than Ingo's shared runqueue patch on NUMA and SMP, and 1K smaller on UP (although sched.c is 90 lines longer). kernbench system time is down nearly 10% on the NUMAQ, so it isn't hurting performance either.

And finally, Linus also wanted the balancing code to be generalised to handle SMT, and Ingo said he liked my patch from a first look.

In message <[email protected]> you write:

Quoted 8 lines

Thanks for having a look Rusty. I'll try to convince you :)

As you know, the domain classes is not just for HT, but can do multi levels of NUMA, and it can be built by architecture specific code which is good for Opteron, for example. It doesn't need CONFIG_SCHED_SMT either, of course, or CONFIG_NUMA even: degenerate domains can just be collapsed (code isn't there to do that now).

Yes, but this isn't what we really want. I'm actually accusing you of lacking ambition 8)

Quoted 4 lines

Shared runqueues I find isn't so flexible. I think it perfectly describes the P4 HT architecture, but what happens if (when) siblings get seperate L1 caches? What about SMT, CMP, SMP and NUMA levels in the POWER5?

It describes every HyperThread implementation I am aware of today, so it suits us fine for the moment. Runqueues may still be worth sharing even if L1 isn't, for example.

Quoted 6 lines

The large SGI (and I imagine IBM's POWER5s) systems need things like progressive balancing backoff and would probably benefit with a more heirachical balancing scheme so all the balancing operations don't kill the system.

But this is my point. Scheduling is one part of the problem. I want to be able to have the arch-specific code feed in a description of memory and cpu distances, bandwidths and whatever, and have the scheduler, slab allocator, per-cpu data allocation, page cache, page migrator and anything else which cares adjust itself based on that.

Power 4 today has pairs of CPUs on a die, four dies on a board, and four boards in a machine. I want one infrastructure to descibe it, not have to do program every infrastructure from arch-specific code.

Quoted 6 lines

w26 does ALL this, while sched.o is 3K smaller than Ingo's shared runqueue patch on NUMA and SMP, and 1K smaller on UP (although sched.c is 90 lines longer). kernbench system time is down nearly 10% on the NUMAQ, so it isn't hurting performance either.

Agreed, but Ingo's shared runqueue patch is poor implementation of a good idea: I've always disliked it. I'm halfway through updating my patch, and I really think you'll like it better. It's not incompatible with NUMA changes, in fact it's fairly non-invasive.

In article <[email protected]>,
Nick Piggin <[email protected]> wrote:

| Possibly. But it restricts your load balancing to a specific case, it
| eliminates any possibility of CPU affinity: 4 running threads on 1 HT
| CPU for example, they'll ping pong from one cpu to the other happily.

Huh? I hope you meant sibling and not CPU, here.

| I could get domains to do the same thing, but at the moment a CPU only looks
| at its sibling's runqueue if they are unbalanced or is about to become idle.
| I'm pretty sure domains can do anything shared runqueues can. I don't know
| if you're disputing this or not?

Shared runqueues sound like a simplification to describe execution units which have shared resourses and null cost of changing units. You can do that by having a domain which behaved like that, but a shared runqueue sounds better because it would eliminate the cost of even considering moving a process from one sibling to another.

Sorry if I'm mixing features of Con/Nick/Ingo approaches here, I just spent some time looking at the code for several approaches, thinking about moving jobs from the end of the runqueue vs. the head, in terms of fair vs. overall cache impact.

| >But this is my point.  Scheduling is one part of the problem.  I want
| >to be able to have the arch-specific code feed in a description of
| >memory and cpu distances, bandwidths and whatever, and have the
| >scheduler, slab allocator, per-cpu data allocation, page cache, page
| >migrator and anything else which cares adjust itself based on that.

And would shared runqueues not fit into that model?

| (Plus two threads / siblings per CPU, right?)
| | I agree with you here. You know, we could rename struct sched_domain, add
| a few fields to it and it becomes what you want. Its a _heirachical set_
| of _sets of cpus sharing a certian property_ (underlining to aid grouping.
| | Uniform access to certian memory ranges could easily be one of these
| properties. There is already some info about the amount of cache shared,
| that also could be expanded on.
| | (Perhaps some exotic architecture  would like scheduling and memory a bit
| more decoupled, but designing for *that* before hitting it would be over
| engineering).
| | I'm not going to that because 2.6 doesn't need a generalised topology
| because nothing makes use of it. Perhaps if something really good came up
| in 2.7, there would be a case for backporting it. 2.6 does need improvements
| to the scheduler though.

| But if sched domains are accepted, there is no need for shared runqueues,
| because as I said they can do anything sched domains can, so the code would
| just be a redundant specialisation - unless you specifically wanted to share
| locks & data with siblings.

I doubt the gain would be worth the complexity, but what do I know?

Quoted 5 lines

Shared runqueues sound like a simplification to describe execution units which have shared resourses and null cost of changing units. You can do that by having a domain which behaved like that, but a shared runqueue sounds better because it would eliminate the cost of even considering moving a process from one sibling to another.

You are correct, however it would be a miniscule cost advantage, possibly outweighed by the shared lock, and overhead of more changing of CPUs (I'm sure there would be some cost).

Quoted 10 lines · Nick Piggin

Quoted 6 lines

Shared runqueues sound like a simplification to describe execution units which have shared resourses and null cost of changing units. You can do that by having a domain which behaved like that, but a shared runqueue sounds better because it would eliminate the cost of even considering moving a process from one sibling to another.

You are correct, however it would be a miniscule cost advantage, possibly outweighed by the shared lock, and overhead of more changing of CPUs (I'm sure there would be some cost).

Regarding the overhead of the shared runqueue lock:

Is the "lock" prefix actually required for locking between x86 siblings which share the same L1 cache?

Quoted 6 lines

Regarding the overhead of the shared runqueue lock:

Is the "lock" prefix actually required for locking between x86 siblings which share the same L1 cache?

That lock is still taken by other CPUs as well for eg. wakeups, balancing, and so forth. I guess it could be a very specific optimisation for spinlocks in general if there was only one HT core. Don't know if it would be worthwhile though.

Quoted 15 lines · Jamie Lokier

Quoted 10 lines · Nick Piggin

Quoted 6 lines

Shared runqueues sound like a simplification to describe execution units which have shared resourses and null cost of changing units. You can do that by having a domain which behaved like that, but a shared runqueue sounds better because it would eliminate the cost of even considering moving a process from one sibling to another.

You are correct, however it would be a miniscule cost advantage, possibly outweighed by the shared lock, and overhead of more changing of CPUs (I'm sure there would be some cost).

Regarding the overhead of the shared runqueue lock:

Quoted 3 lines

Is the "lock" prefix actually required for locking between x86 siblings which share the same L1 cache?

That lock is still taken by other CPUs as well for eg. wakeups, balancing, and so forth. I guess it could be a very specific optimisation for spinlocks in general if there was only one HT core. Don't know if it would be worthwhile though.

Quoted 6 lines · Nick Piggin

Quoted 5 lines

Shared runqueues sound like a simplification to describe execution units which have shared resourses and null cost of changing units. You can do that by having a domain which behaved like that, but a shared runqueue sounds better because it would eliminate the cost of even considering moving a process from one sibling to another.

Quoted 3 lines

You are correct, however it would be a miniscule cost advantage, possibly outweighed by the shared lock, and overhead of more changing of CPUs (I'm sure there would be some cost).

Regarding the overhead of the shared runqueue lock:

Is the "lock" prefix actually required for locking between x86 siblings which share the same L1 cache?

I bet it is. In a big way.

The lock does two independent things:
- it tells the core that it can't just crack up the load and store.
- it also tells other memory ops that they can't re-order around it.

Quoted 5 lines

I bet it is. In a big way.

The lock does two independent things:
- it tells the core that it can't just crack up the load and store.
- it also tells other memory ops that they can't re-order around it.

You forgot the one where no HT knowledge can be used for optimizations.

- Asserting the CPU's #LOCK pin to take control of the system bus. That in MP system translate into the signaling CPU taking full control of the system bus until the pin is deasserted.

Quoted 11 lines · Davide Libenzi

Quoted 5 lines

I bet it is. In a big way.

The lock does two independent things:
- it tells the core that it can't just crack up the load and store.
- it also tells other memory ops that they can't re-order around it.

You forgot the one where no HT knowledge can be used for optimizations.

- Asserting the CPU's #LOCK pin to take control of the system bus. That in MP system translate into the signaling CPU taking full control of the system bus until the pin is deasserted.

I think this is historical and no longer true.

All modern CPU's do atomic accesses on a cache coherency (and write buffer ordering) level, and it has nothing to do with the external bus any more.

I suspect locked accesses to memory-mapped IO _may_ still set an external flag, but I seriously doubt anybody cares. I wouldn't be surprised if the pin doesn't even exist any more.

Quoted 9 lines · bill davidsen

In article <[email protected]>,
Nick Piggin <[email protected]> wrote:

Shared runqueues sound like a simplification to describe execution units which have shared resourses and null cost of changing units. You can do that by having a domain which behaved like that, but a shared runqueue sounds better because it would eliminate the cost of even considering moving a process from one sibling to another.

You are correct, however it would be a miniscule cost advantage, possibly outweighed by the shared lock, and overhead of more changing of CPUs (I'm sure there would be some cost).

Quoted 5 lines

| But if sched domains are accepted, there is no need for shared runqueues,
| because as I said they can do anything sched domains can, so the code would
| just be a redundant specialisation - unless you specifically wanted to share
| locks & data with siblings.

Quoted 2 lines

I doubt the gain would be worth the complexity, but what do I know?

Sorry I didn't follow, gain and complexity of what?

Earlier in the thread Ingo thought my approach is simpler. code size is the same size, object size for my patch is significantly smaller, and it does more. Benchmarks have so far shown that my patch is as performant as shared runqueues.

Quoted 3 lines · Rusty Russell

In message <[email protected]> you write:

Quoted 1 line

Thanks for having a look Rusty. I'll try to convince you :)

In message <[email protected]> you write:

Quoted 8 lines

Quoted 5 lines · Rusty Russell

In message <[email protected]> you write:

Quoted 2 lines

Thanks for having a look Rusty. I'll try to convince you :)

Actually, having produced the patch, I've changed my mind.

While it was spiritually rewarding to separate "struct runqueue" into the stuff which was to do with the runqueue, and the stuff which was per-cpu but there because it was convenient, I'm not sure the churn is worthwhile since we will want the rest of your stuff anyway.

It (and lots of other things) might become worthwhile if single processors with HT become the de-facto standard. For these, lots of our assumptions about CONFIG_SMP, such as the desirability of per-cpu data, become bogus.

A few things need work:

1) There's a race between sys_sched_setaffinity() and sched_migrate_task() (this is nothing to do with your patch).

2) Please change those #defines into an enum for idle (patch follows, untested but trivial)

3) conditional locking in load_balance is v. bad idea.

4) load_balance returns "(!failed && !balanced)", but callers stop calling it when it returns true. Why not simply return "balanced", or at least "balanced && !failed"?

Quoted 1 line · Rusty Russell

Quoted 5 lines

A few things need work:

1) There's a race between sys_sched_setaffinity() and sched_migrate_task() (this is nothing to do with your patch).

Yep. They should both take the task's runqueue lock.

Quoted 6 lines

2) Please change those #defines into an enum for idle (patch follows, untested but trivial)

Thanks, I'll take the patch.

Quoted 4 lines

3) conditional locking in load_balance is v. bad idea.

Yeah... I'm thinking about this. I don't think it should be too hard to break out the shared portion.

Quoted 8 lines

4) load_balance returns "(!failed && !balanced)", but callers stop calling it when it returns true. Why not simply return "balanced", or at least "balanced && !failed"?

No, the idle balancer stops calling it when it returns true, the periodic balancer sets idle to 0 when it returns true.

!balanced && !failed means it has moved a task.

I'll either comment that, or return it in a more direct way.

Easier said than done... anyway, how does this patch look? It should also cure a possible and not entirely unlikely use after free of the task_struct in sched_migrate_task on NUMA AFAIKS.

+ * See comment for set_cpus_allowed. calling rules are different:
+ * the task's runqueue lock must be held, and __set_cpus_allowed
+ * will return with the runqueue unlocked.

In message <[email protected]> you write:

Quoted 4 lines

+ * See comment for set_cpus_allowed. calling rules are different:
+ * the task's runqueue lock must be held, and __set_cpus_allowed
+ * will return with the runqueue unlocked.

Please, never *ever* do this.

Locking is probably the hardest thing to get right, and code like this makes it harder.

Fortunately, there is a simple solution coming with the hotplug CPU
code: we need to hold the cpucontrol semaphore here anyway, against cpus vanishing.

Perhaps we should just use that in both places.

Actually, having produced the patch, I've changed my mind.

While it was spiritually rewarding to separate "struct runqueue" into the stuff which was to do with the runqueue, and the stuff which was per-cpu but there because it was convenient, I'm not sure the churn is worthwhile since we will want the rest of your stuff anyway.

It (and lots of other things) might become worthwhile if single processors with HT become the de-facto standard. For these, lots of our assumptions about CONFIG_SMP, such as the desirability of per-cpu data, become bogus.

Hello Nick,
This is somewhat unrelated to the current thread topic direction,
but i noticed that your HT scheduler really behaves oddly when the box is used interactively. The one application which really seemed to be misbehaving was 'gaim', whenever someone typed a message X11 would pause for a second or so until the text displayed causing the mouse to jump around erratically. I can try help with this but unfortunately i can't do too much rebooting this week due to work (main workstation), but perhaps we can discuss it over a weekend. The system is 4x logical 2.0GHz.

Thats weird. I assume you don't have problems with the regular SMP kernel. Unfortunately I don't have an HT box I can do these sorts of tests with. The first thing you could try is with CONFIG_SCHED_SMT 'N'.

Hi guys,
This is rather a trivial change but is not for 2.6.0. The patch is actually on top of some of my HT stuff so one part is slightly different, but its purpose is to gather feedback.

It turns the cpu_sibling_map array from an array of cpus to an array of cpumasks. This allows handling of more than 2 siblings, not that I know of any immediate need.

I think it generalises cpu_sibling_map sufficiently that it can become generic code. This would allow architecture specific code to build the sibling map, and then Ingo's or my HT implementations to build their scheduling descriptions in generic code.

I'm not aware of any reason why the kernel should not become generally SMT aware. It is sufficiently different to SMP that it is worth specialising it, although I am only aware of P4 and POWER5 implementations.

Best regards
Nick

P.S.
I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

Before Ingo's is merged, I would like to discuss the pros and cons of both approaches with those interested. If Ingo's is accepted I should still be able to port my other SMP/NUMA improvements on top of it.

P.S.
I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

It turns the cpu_sibling_map array from an array of cpus to an array of cpumasks. This allows handling of more than 2 siblings, not that I know of any immediate need.

I think it generalises cpu_sibling_map sufficiently that it can become generic code. This would allow architecture specific code to build the sibling map, and then Ingo's or my HT implementations to build their scheduling descriptions in generic code.

I'm not aware of any reason why the kernel should not become generally SMT aware. It is sufficiently different to SMP that it is worth specialising it, although I am only aware of P4 and POWER5 implementations.

P.S.
I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

Quoted 4 lines

P.S.
I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

-j3 is an odd number, what does -j4, -j8, -j16 look like?

Quoted 5 lines · Zwane Mwaikambo

Quoted 5 lines

P.S.
I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

Quoted 2 lines

-j3 is an odd number, what does -j4, -j8, -j16 look like?

let me guess: -j3 is the one that gives the highest performance boost on a 2-way/4-logical P4 box?

for the SMT/HT scheduler to give any benefits there has to be idle time - so that SMT decisions actually make a difference.

the higher -j values are only useful to make sure that SMT scheduling does not introduce regressions - performance should be the same as the pure SMP/NUMA scheduler's performance.

the thing that makes balancing-only driven SMT possible with current 2.6.0 is the overbalancing we do (to have cross-CPU fairness). Previous iterations of the O(1) scheduler (all the 2.4 backports) didnt do this so all the add-on SMT schedulers tended to have a problem achieving good SMT distribution. Now that we more agressively balance, this isnt such a big issue anymore.

so i tend to lean towards your SMT patch, it's much easier to maintain than my runqueue-sharing approach. The performance is equivalent as far as i can see (around 20%, and a stabilization of the distribution of runtimes) - but please also boot my patch and repeat the exact same measurements you did.

I'm not aware of any reason why the kernel should not become generally SMT aware. It is sufficiently different to SMP that it is worth specialising it, although I am only aware of P4 and POWER5 implementations.

I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

In message <[email protected]> you write:

Quoted 4 lines

I'm not aware of any reason why the kernel should not become generally SMT aware. It is sufficiently different to SMP that it is worth specialising it, although I am only aware of P4 and POWER5 implementations.

To do it properly, it should be done within the NUMA framework. That would allow generic slab cache optimizations, etc. We'd really need a multi-level NUMA framework for this though.

But patch looks fine.

Quoted 5 lines

I have an alternative to Ingo's HT scheduler which basically does the same thing. It is showing a 20% elapsed time improvement with a make -j3 on a 2xP4 Xeon (4 logical CPUs).

Me too.

My main argument with Ingo's patch (last I looked) was technical: the code becomes clearer if the structures are explicitly split into the "per-runqueue stuff" and the "per-cpu stuff" (containing a my_runqueue pointer).

I'd be very interested in your patch though, Nick.