scheduler fix for 1cpu/node case

after talking to several people at OLS about the current NUMA scheduler the conclusion was:
(1) it sucks (for particular workloads),
(2) on x86_64 (embarassingly simple NUMA) it's useless, goto (1).

Fact is that the current separation of local and global balancing, where global balancing is done only in the timer interrupt at a fixed rate is way too unflexible. A CPU going idle inside a well balanced node will stay idle for a while even if there's a lot of work to do. Especially in the corner case of one CPU per node this is condemning that CPU to idleness for at least 5 ms.

So x86_64 platforms
(but not only those!) suffer and whish to switch off the NUMA scheduler while keeping NUMA memory management on.

The attached patch is a simple solution which
- solves the 1 CPU / node problem,
- lets other systems behave (almost) as before,
- opens the way to other optimisations like multi-level node hierarchies (by tuning the retry rate)
- simpifies the NUMA scheduler and deletes more lines of code than it adds.

The timer interrupt based global rebalancing might appear to be a simple and good idea but it takes the scheduler a lot of flexibility. In the patch the global rebalancing is done after a certain number of failed attempts to locally balance. The number of attempts is proportional to the number of CPUs in the current node.

Quoted 4 lines

after talking to several people at OLS about the current NUMA scheduler the conclusion was:
(1) it sucks (for particular workloads),
(2) on x86_64 (embarassingly simple NUMA) it's useless, goto (1).

I really feel there's no point in a NUMA scheduler for the Hammer style architectures. A config option to turn it off would seem like a simpler way to go, unless people can see some advantage of the full NUMA code?

Quoted 6 lines

Fact is that the current separation of local and global balancing, where global balancing is done only in the timer interrupt at a fixed rate is way too unflexible. A CPU going idle inside a well balanced node will stay idle for a while even if there's a lot of work to do. Especially in the corner case of one CPU per node this is condemning that CPU to idleness for at least 5 ms.

Surely it'll hit the idle local balancer and rebalance within the node? Or are you thinking of a case with 3 tasks on a 4 cpu/node system?

Quoted 3 lines

So x86_64 platforms
(but not only those!) suffer and whish to switch off the NUMA scheduler while keeping NUMA memory management on.

Right - I have a patch to make it a config option (CONFIG_NUMA_SCHED) ... I'll feed that upstream this week.

Quoted 7 lines

The attached patch is a simple solution which
- solves the 1 CPU / node problem,
- lets other systems behave (almost) as before,
- opens the way to other optimisations like multi-level node hierarchies (by tuning the retry rate)
- simpifies the NUMA scheduler and deletes more lines of code than it adds.

Looks simple, I'll test it out.

But the Hammer is a NUMA architecture and a working NUMA scheduler should be flexible enough to deal with it. And: the corner case of 1 CPU per node is possible also on any other NUMA platform, when in some of the nodes (or even just one) only one CPU is configured in. Solving that problem automatically gives the Hammer what it needs.

Quoted 7 lines

Quoted 6 lines

Fact is that the current separation of local and global balancing, where global balancing is done only in the timer interrupt at a fixed rate is way too unflexible. A CPU going idle inside a well balanced node will stay idle for a while even if there's a lot of work to do. Especially in the corner case of one CPU per node this is condemning that CPU to idleness for at least 5 ms.

Quoted 2 lines

Surely it'll hit the idle local balancer and rebalance within the node? Or are you thinking of a case with 3 tasks on a 4 cpu/node system?

No, no, the local load balancer just doesn't make sense now if you have one cpu per node. It is called although it will never find another cpu in the own cell to steal from. There just is nothing else... (or did I misunderstand your comment?)

That's one way, but the proposed patch just solves the problem (in a more general way, also for other NUMA cases). If you deconfigure NUMA for a NUMA platform, we'll have problems switching it back on when adding smarter things like node affine or homenode extensions.

Quoted 5 lines

But the Hammer is a NUMA architecture and a working NUMA scheduler should be flexible enough to deal with it. And: the corner case of 1 CPU per node is possible also on any other NUMA platform, when in some of the nodes (or even just one) only one CPU is configured in. Solving that problem automatically gives the Hammer what it needs.

OK, well what we have now is a "multi-cpu-per-node-numa-scheduler" if you really want to say all that ;-)

The question is "does Hammer benefit from the additional complexity"? I'm guessing not ... if so, then yes, it's worth fixing. If not, it would seem better to just leave it at SMP for the scheduler stuff. Simpler, more shared code with common systems.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

Fact is that the current separation of local and global balancing, where global balancing is done only in the timer interrupt at a fixed rate is way too unflexible. A CPU going idle inside a well balanced node will stay idle for a while even if there's a lot of work to do. Especially in the corner case of one CPU per node this is condemning that CPU to idleness for at least 5 ms.

Quoted 7 lines

Quoted 2 lines

Surely it'll hit the idle local balancer and rebalance within the node? Or are you thinking of a case with 3 tasks on a 4 cpu/node system?

No, no, the local load balancer just doesn't make sense now if you have one cpu per node. It is called although it will never find another cpu in the own cell to steal from. There just is nothing else... (or did I misunderstand your comment?)

Right, I realise that the 1 cpu per node case is broken. However, doesn't this also affect the multi-cpu per node case in the manner I suggested above? So even if we turn off NUMA scheduler for Hammer, this still needs fixing, right?

Quoted 4 lines

That's one way, but the proposed patch just solves the problem (in a more general way, also for other NUMA cases). If you deconfigure NUMA for a NUMA platform, we'll have problems switching it back on when adding smarter things like node affine or homenode extensions.

Yeah, maybe. I'd rather have the code in hand that needs it, but still ... if Andi's happy that fixes it, then we're OK.

Quoted 5 lines · Martin J. Bligh

Quoted 5 lines

But the Hammer is a NUMA architecture and a working NUMA scheduler should be flexible enough to deal with it. And: the corner case of 1 CPU per node is possible also on any other NUMA platform, when in some of the nodes (or even just one) only one CPU is configured in. Solving that problem automatically gives the Hammer what it needs.

I am going to ask a silly question, do we have any data showing this really is a problem on AMD? I would think, even if we have an idle cpu, sometimes
a little delay on task migration (on NUMA) may not be a bad thing. If it
is too long, can we just make the rebalance ticks arch specific?

I'd much rather have info related to the properties of the NUMA arch than something that makes decisions based on nr_cpus_node(). For example, we may want to inter-node balance as much or more often on ppc64 than even AMD, but it has 8 cpus per node. On this patch it would has the lowest inter-node balance frequency, even though it probably has one of the lowest latencies between nodes and highest throughput interconnects.

Quoted 4 lines

Right, I realise that the 1 cpu per node case is broken. However, doesn't this also affect the multi-cpu per node case in the manner I suggested above? So even if we turn off NUMA scheduler for Hammer, this still needs fixing, right?

Maybe so, but if we start making idle rebalance more aggressive, I think we would need to make CAN_MIGRATE more restrictive, taking memory placement of the tasks in to account. On AMD with interleaved memory allocation, tasks would move very easily, since their memory is spread out anyway. On "home node" or node-local policy, we may not move a task (or maybe not on the first attempt), even if there is an idle cpu in another node.

Personally, I'd like to see all systems use NUMA sched, non NUMA systems being a single node (no policy difference from non-numa sched), allowing us to remove all NUMA ifdefs. I think the code would be much more readable.

Quoted 7 lines · Andrew Theurer

Quoted 5 lines · Martin J. Bligh

Quoted 5 lines

But the Hammer is a NUMA architecture and a working NUMA scheduler should be flexible enough to deal with it. And: the corner case of 1 CPU per node is possible also on any other NUMA platform, when in some of the nodes (or even just one) only one CPU is configured in. Solving that problem automatically gives the Hammer what it needs.

Quoted 5 lines

I am going to ask a silly question, do we have any data showing this really is a problem on AMD? I would think, even if we have an idle cpu, sometimes a little delay on task migration (on NUMA) may not be a bad
thing. If it is too long, can we just make the rebalance ticks arch
specific?

The fact that global rebalances are done only in the timer interrupt is simply bad!

It complicates rebalance_tick() and wastes the opportunity to get feedback from the failed local balance attempts.

If you want data supporting my assumptions: Ted Ts'o's talk at OLS shows the necessity to rebalance ASAP (even in try_to_wake_up).

There
are plenty of arguments towards this, starting with the steal delay parameter scans from the early days of multi-queue schedulers (Davide Libenzi), over my experiments with NUMA schedulers and the observation of Andi Kleen that on Opteron you better run from the wrong CPU than wait (if the tasks returns to the right cpu, all's fine anyway).

Quoted 6 lines

I'd much rather have info related to the properties of the NUMA arch than something that makes decisions based on nr_cpus_node(). For example, we may want to inter-node balance as much or more often on ppc64 than even AMD, but it has 8 cpus per node. On this patch it would has the lowest inter-node balance frequency, even though it probably has one of the lowest latencies between nodes and highest throughput interconnects.

We can still discuss on the formula. Currently there's a bug in the scheduler and the corner case of 1 cpu/node is just broken. The function local_balance_retries(attempts, cpus_in_this_node) must return 0 for cpus_in_this_node=1 and should return larger values for larger cpus_in_this_node. To have an upper limit is fine, but maybe not necessary.

Regarding the ppc64 interconnect, I'm glad that you said "probably" and "one of the ...". No need to point you to better ones ;-)

Quoted 5 lines

Quoted 4 lines

Right, I realise that the 1 cpu per node case is broken. However, doesn't this also affect the multi-cpu per node case in the manner I suggested above? So even if we turn off NUMA scheduler for Hammer, this still needs fixing, right?

Quoted 7 lines

Maybe so, but if we start making idle rebalance more aggressive, I think we would need to make CAN_MIGRATE more restrictive, taking memory placement of the tasks in to account. On AMD with interleaved memory allocation, tasks would move very easily, since their memory is spread out anyway. On "home node" or node-local policy, we may not move a task (or maybe not on the first attempt), even if there is an idle cpu in another node.

Aehm, that's another story and I'm sure we will fix that too. There are a few ideas around. But you shouldn't expect to solve all problems at once, after all optimal NUMA scheduling can still be considered a research area.

Quoted 5 lines

Personally, I'd like to see all systems use NUMA sched, non NUMA systems being a single node (no policy difference from non-numa sched), allowing us to remove all NUMA ifdefs. I think the code would be much more readable.

:-) Then you expect that everybody who reads the scheduler code knows

what NUMA stands for and what it means? Pretty optimistic, but yes, I'd like that, too.

Quoted 2 lines

The fact that global rebalances are done only in the timer interrupt is simply bad!

Even with this patch it still seems that most balances are still timer based, because we still call load_balance in rebalance_tick. Granted, we may inter-node balance more often, well, maybe less often since node_busy_rebalance_tick was busy_rebalance_tick*2. I do see the advantage of doing this at idle, but idle only, that's why I'd would be more inclined a only a much more aggressive idle rebalance.

Quoted 2 lines

It complicates rebalance_tick() and wastes the opportunity to get feedback from the failed local balance attempts.

What does "failed" really mean? To me, when *busiest=null, that means we passed, the node itself is probably balanced, and there's nothing to do. It gives no indication at all of the global load [im]balance. Shouldn't the thing we are looking for is the imbalance among node_nr_running[]? Would it make sense to go forward with a global balance based on that only?

Quoted 9 lines · Andrew Theurer

Quoted 2 lines

The fact that global rebalances are done only in the timer interrupt is simply bad!

Even with this patch it still seems that most balances are still timer based, because we still call load_balance in rebalance_tick. Granted, we may inter-node balance more often, well, maybe less often since node_busy_rebalance_tick was busy_rebalance_tick*2. I do see the advantage of doing this at idle, but idle only, that's why I'd would be more inclined a only a much more aggressive idle rebalance.

Without this patch the probability to globally balance when going idle is 0. Now it is 1/global_balance_rate(cpus_in_this_node) . This is tunable and we can make this probability depending on the node load imbalance. I'll try that in the next version, it sounds like a good idea. Also changing this probability by some factor could give us a way to handle the differences between the platforms.

Balancing globally only when idle isn't a good idea as long as we don't have multiple steals per balance attempt. Even then, tasks don't live all the same time, so you easilly end up with one node overloaded and others just busy and not able to steal from the busiest node.

Quoted 4 lines

I am going to ask a silly question, do we have any data showing this really is a problem on AMD? I would think, even if we have an idle cpu, sometimes
a little delay on task migration (on NUMA) may not be a bad thing. If it
is too long, can we just make the rebalance ticks arch specific?

The fact that global rebalances are done only in the timer interrupt is simply bad! It complicates rebalance_tick() and wastes the opportunity to get feedback from the failed local balance attempts.

If you want data supporting my assumptions: Ted Ts'o's talk at OLS shows the necessity to rebalance ASAP (even in try_to_wake_up). There are plenty of arguments towards this, starting with the steal delay parameter scans from the early days of multi-queue schedulers (Davide Libenzi), over my experiments with NUMA schedulers and the observation of Andi Kleen that on Opteron you better run from the wrong CPU than wait (if the tasks returns to the right cpu, all's fine anyway).

Personally, I'd like to see all systems use NUMA sched, non NUMA systems being a single node (no policy difference from non-numa sched), allowing us to remove all NUMA ifdefs. I think the code would be much more readable.

Quoted 4 lines · Andrew Theurer

Personally, I'd like to see all systems use NUMA sched, non NUMA systems being a single node (no policy difference from non-numa sched), allowing us to remove all NUMA ifdefs. I think the code would be much more readable.

That sounds like a great idea, but I'm not sure it could be realized short of a major rewrite. Look how hard Ingo and Con are working just to get a single node doing a good job with interactive and throughput tradeoffs.

Once they get a good handle on identifying process behaviour, and I believe they will, that information could be used in improving NUMA performance, by sending not just 'a job" but "the right job" if it exists. I'm sure there are still a few graduate theses possible on the topic!

Quoted 7 lines · Bill Davidsen

Quoted 5 lines · Andrew Theurer

Personally, I'd like to see all systems use NUMA sched, non NUMA systems being a single node (no policy difference from non-numa sched), allowing us to remove all NUMA ifdefs. I think the code would be much more readable.

Quoted 4 lines

That sounds like a great idea, but I'm not sure it could be realized short of a major rewrite. Look how hard Ingo and Con are working just to get a single node doing a good job with interactive and throughput tradeoffs.

Actually it's not too bad. Attached is a patch to do it. It also does multi-level node support and makes all the load balance routines runqueue-centric instead of cpu-centric, so adding something like shared runqueues (for HT) should be really easy. Hmm, other things: inter-node balance intervals are now arch specific (AMD is "1"). The default busy/idle balance timers of 200/1 are not arch specific, but I'm thinking they should be. And for non-numa, the scheduling policy is the same as it was with vanilla O(1).

Quoted 12 lines · Andrew Theurer

Quoted 10 lines · Bill Davidsen

Quoted 4 lines · Andrew Theurer

Personally, I'd like to see all systems use NUMA sched, non NUMA systems being a single node (no policy difference from non-numa sched), allowing us to remove all NUMA ifdefs. I think the code would be much more readable.

That sounds like a great idea, but I'm not sure it could be realized short of a major rewrite. Look how hard Ingo and Con are working just to get a single node doing a good job with interactive and throughput tradeoffs.

Quoted 8 lines

Actually it's not too bad. Attached is a patch to do it. It also does multi-level node support and makes all the load balance routines runqueue-centric instead of cpu-centric, so adding something like shared runqueues (for HT) should be really easy. Hmm, other things: inter-node balance intervals are now arch specific (AMD is "1"). The default busy/idle balance timers of 200/1 are not arch specific, but I'm thinking they should be. And for non-numa, the scheduling policy is the same as it was with vanilla O(1).

I'm not saying you're wrong, but do you have some numbers where this helps? ie. two architectures that need very different balance numbers. And what is the reason for making AMD's balance interval 1?

Also, things like nr_running_inc are supposed to be very fast. I am a bit worried to see a loop and CPU shared atomics in there.

node_2_node is an odd sounding conversion too ;)

BTW. you should be CC'ing Ingo if you have any intention of scheduler stuff getting into 2.6.

Quoted 25 lines · Nick Piggin

Quoted 23 lines · Andrew Theurer

Quoted 7 lines · Bill Davidsen

Quoted 5 lines · Andrew Theurer

Personally, I'd like to see all systems use NUMA sched, non NUMA systems being a single node (no policy difference from non-numa sched), allowing us to remove all NUMA ifdefs. I think the code would be much more readable.

Quoted 5 lines

That sounds like a great idea, but I'm not sure it could be realized short of a major rewrite. Look how hard Ingo and Con are working just to get a single node doing a good job with interactive and throughput tradeoffs.

Actually it's not too bad. Attached is a patch to do it. It also does multi-level node support and makes all the load balance routines runqueue-centric instead of cpu-centric, so adding something like shared runqueues (for HT) should be really easy. Hmm, other things: inter-node balance intervals are now arch specific (AMD is "1"). The default busy/idle balance timers of 200/1 are not arch specific, but I'm thinking they should be. And for non-numa, the scheduling policy is the same as it was with vanilla O(1).

Quoted 4 lines

I'm not saying you're wrong, but do you have some numbers where this helps? ie. two architectures that need very different balance numbers. And what is the reason for making AMD's balance interval 1?

AMD is 1 because there's no need to balance within a node, so I want the inter-node balance frequency to be as often as it was with just O(1). This interval would not work well with other NUMA boxes, so that's the main reason to have arch specific intervals.

And, as a general guideline, boxes with
different local-remote latency ratios will probably benefit from different inter-node balance intervals. I don't know what these ratios are, but I'd like the kernel to have the ability to change for one arch and not affect another.

Quoted 4 lines

Also, things like nr_running_inc are supposed to be very fast. I am a bit worried to see a loop and CPU shared atomics in there.

That has concerned me, too. So far I haven't been able to see a measurable difference either way (within noise level), but it's possible. The other alternative is to sum up node load at sched_best_cpu and find_busiest_node.

Quoted 3 lines

node_2_node is an odd sounding conversion too ;)

I just went off the toplogy already there, so I left it.

Quoted 3 lines

BTW. you should be CC'ing Ingo if you have any intention of scheduler stuff getting into 2.6.

OK, thanks!

Hmm... get someone to try the scheduler benchmarks on a 32 way box ;)

Quoted 2 lines · Nick Piggin

Hmm... get someone to try the scheduler benchmarks on a 32 way box ;)

What scheduler benchmark?

Quoted 4 lines

AMD is 1 because there's no need to balance within a node, so I want the inter-node balance frequency to be as often as it was with just O(1). This interval would not work well with other NUMA boxes, so that's the main reason to have arch specific intervals.

OK, I misread the patch. IIRC AMD has 1 CPU per node? If so, why doesn't this simply prevent balancing within a node?

Quoted 5 lines

And, as a general guideline, boxes with
different local-remote latency ratios will probably benefit from different inter-node balance intervals. I don't know what these ratios are, but I'd like the kernel to have the ability to change for one arch and not affect another.

I fully appreciate there are huge differences... I am curious if you can see much improvements in practice.

Quoted 1 line

node_2_node is an odd sounding conversion too ;)

I just went off the toplogy already there, so I left it.

Quoted 5 lines

But the Hammer is a NUMA architecture and a working NUMA scheduler should be flexible enough to deal with it. And: the corner case of 1 CPU per node is possible also on any other NUMA platform, when in some of the nodes (or even just one) only one CPU is configured in. Solving that problem automatically gives the Hammer what it needs.

OK, well what we have now is a "multi-cpu-per-node-numa-scheduler" if you really want to say all that ;-)

The question is "does Hammer benefit from the additional complexity"? I'm guessing not ... if so, then yes, it's worth fixing. If not, it would seem better to just leave it at SMP for the scheduler stuff. Simpler, more shared code with common systems.

Quoted 4 lines

No, no, the local load balancer just doesn't make sense now if you have one cpu per node. It is called although it will never find another cpu in the own cell to steal from. There just is nothing else... (or did I misunderstand your comment?)

Right, I realise that the 1 cpu per node case is broken. However, doesn't this also affect the multi-cpu per node case in the manner I suggested above? So even if we turn off NUMA scheduler for Hammer, this still needs fixing, right?

Quoted 4 lines

That's one way, but the proposed patch just solves the problem (in a more general way, also for other NUMA cases). If you deconfigure NUMA for a NUMA platform, we'll have problems switching it back on when adding smarter things like node affine or homenode extensions.

Yeah, maybe. I'd rather have the code in hand that needs it, but still ... if Andi's happy that fixes it, then we're OK.

Quoted 6 lines

Quoted 3 lines

So x86_64 platforms
(but not only those!) suffer and whish to switch off the NUMA scheduler while keeping NUMA memory management on.

Right - I have a patch to make it a config option (CONFIG_NUMA_SCHED) ... I'll feed that upstream this week.

That's one way, but the proposed patch just solves the problem (in a more general way, also for other NUMA cases). If you deconfigure NUMA for a NUMA platform, we'll have problems switching it back on when adding smarter things like node affine or homenode extensions.

you're using node_to_cpu_mask for ia64 ... others were using node_to_cpumask (1 less "_"), so this doesn't build ...

Quoted 2 lines

you're using node_to_cpu_mask for ia64 ... others were using node_to_cpumask (1 less "_"), so this doesn't build ...

Ooops, you're right, of course. Sorry about this mistake :-(

np - was easy to fix up ;-) I did run some benchmarks on it ... low end SDET seemed highly variable, but otherwise looked OK. If I have only 4 tasks running on a 16x (4x4), what's the rate limit on the idle cpus trying to steal now?