Node affine NUMA scheduler extension
This patch is an adaptation of the earlier work on the node affine NUMA scheduler to the NUMA features meanwhile integrated into 2.5. Compared to the patch posted for 2.5.39 this one is much simpler and easier to understand.
The main idea is (still) that tasks are assigned a homenode to which they are preferentially scheduled. They are not only sticking as much as possible to a node (as in the current 2.5 NUMA scheduler) but will also be attracted back to their homenode if they had to be scheduled away. Therefore the tasks can be called "affine" to the homenode.
The implementation is straight forward:
- Tasks have an additional element in their task structure (node).
- The scheduler keeps track of the homenodes of the tasks running in each node and on each runqueue.
- At cross-node load balance time nodes/runqueues which run tasks originating from the stealer node are preferred. They get a weight bonus for each task with the homenode of the stealer.
- When stealing from a remote node one tries to get the own tasks (if any) or tasks from other nodes (if any). This way tasks are kept on their homenode as long as possible.
The selection of the homenode is currently done at initial load balancing, i.e. at exec(). A smarter selection method might be needed for improving the situation for multithreaded processes. An option is the dynamic_homenode patch I posted for 2.5.39 or some other scheme based on an RSS/node measure. But that's another story...
A node affine NUMA scheduler based on these principles is running very successfully in production on NEC TX7 machines since 1 year. The current patch was tested on a 32 CPU Itanium2 TX7 machine.
Curious about comments...
Erich
-----------------8<----- node_affine_sched-2.5.70-23.diff ---------
include/linux/sched.h +5 -0
@@ -340,6 +340,9 @@unsigned long policy;unsigned long cpus_allowed;unsigned int time_slice, first_time_slice; +#ifdef CONFIG_NUMA +int node;/* homenode: task will be preferrentially scheduled on it */ +#endif struct list_head tasks;struct list_head ptrace_children;
@@ -489,9 +492,11 @@#ifdef CONFIG_NUMA extern void sched_balance_exec (void );extern void node_nr_running_init (void ); +extern void set_task_node (task_t *p,int node);#else #define sched_balance_exec () {}#define node_nr_running_init () {} +#define set_task_node (p,n) {}#endif extern void set_user_nice (task_t *p,long nice);
kernel/sched.c +92 -14
223 lines not on this page · raw message
Quoted 4 lines · Erich Focht
This patch is an adaptation of the earlier work on the node affine NUMA scheduler to the NUMA features meanwhile integrated into 2.5. Compared to the patch posted for 2.5.39 this one is much simpler and easier to understand.
Yes, it is also much simpler than my implementation (I did a similar homenode scheduler for an 2.4 kernel). The basic principles are the same.
But the main problems I have is that the tuning for threads is very difficult. On AMD64 where Node equals CPU it is important
to home node balance threads too. After some experiments I settled on homenode assignment on the first load balance (called "lazy homenode") When a thread clones it initially executes on the CPU of the parent, but there is a window until the first load balance tick where it can allocate memory on the wrong node. I found a lot of code runs very badly until the cache decay parameter is set to 0 (no special cache affinity) to allow quick initial migration. Migration directly on fork/clone requires a lot of changes and also breaks down on some benchmarks.
-Andi
Quoted 8 lines · Andi Kleen
Quoted 4 lines · Erich Focht
This patch is an adaptation of the earlier work on the node affine NUMA scheduler to the NUMA features meanwhile integrated into 2.5. Compared to the patch posted for 2.5.39 this one is much simpler and easier to understand.
Yes, it is also much simpler than my implementation (I did a similar homenode scheduler for an 2.4 kernel). The basic principles are the same.
:-)
Quoted 9 lines
But the main problems I have is that the tuning for threads is very difficult. On AMD64 where Node equals CPU it is important
to home node balance threads too. After some experiments I settled on homenode assignment on the first load balance (called "lazy homenode") When a thread clones it initially executes on the CPU of the parent, but there is a window until the first load balance tick where it can allocate memory on the wrong node. I found a lot of code runs very badly until the cache decay parameter is set to 0 (no special cache affinity) to allow quick initial migration.
Interesting observation, I didn't make it when I tried the lazy homenode (quite a while ago). But I was focusing on MPI jobs. So what if we add a condition to CAN_MIGRATE which disables the cache affinity before the first load balance?
Quoted 2 lines
Migration directly on fork/clone requires a lot of changes and also breaks down on some benchmarks.
Hmmm, I wouldn't allow this to any task/child, only to special ones. Under 2.4 I currently use a sched_balance_fork() function similar to sched_balance_exec(). Tasks have a default initial load balancing policy of being migrated (and selecting the homenode) at exec(). This can be changed (with prctl) to fork(). The ilb policy is inheritable. Works fine for OpenMP jobs.
Regards,
Erich
Quoted 10 lines · Erich Focht
Quoted 9 lines
But the main problems I have is that the tuning for threads is very difficult. On AMD64 where Node equals CPU it is important
to home node balance threads too. After some experiments I settled on homenode assignment on the first load balance (called "lazy homenode") When a thread clones it initially executes on the CPU of the parent, but there is a window until the first load balance tick where it can allocate memory on the wrong node. I found a lot of code runs very badly until the cache decay parameter is set to 0 (no special cache affinity) to allow quick initial migration.
Quoted 4 lines
Interesting observation, I didn't make it when I tried the lazy homenode (quite a while ago). But I was focusing on MPI jobs. So what if we add a condition to
CAN_MIGRATEwhich disables the cache affinity before the first load balance?
What I currently have is two cache decay variables: one is used if the homenode is not assigned, the other otherwise. Both are sysctls too. But it obviously only works with lazy homenode, but the state is the same. I'm still not completely happy with it though.
Why exactly did you gave up to use the lazy homenode?
Quoted 6 lines
Quoted 3 lines
Migration directly on fork/clone requires a lot of changes and also breaks down on some benchmarks.
Hmmm, I wouldn't allow this to any task/child, only to special ones. Under 2.4 I currently use a
sched_balance_fork()function
Yes, I agree.
Quoted 4 lines
similar to
sched_balance_exec(). Tasks have a default initial load balancing policy of being migrated (and selecting the homenode) atexec(). This can be changed (with prctl) tofork(). The ilb policy is inheritable. Works fine for OpenMP jobs.
Hmm, I should try that I guess. Where do you call it? At the end of do_fork? I tried to hack up wake_up_forked_process() to do it, but it required large scale changes all over the scheduler so I eventually gave up.
-Andi
Quoted 9 lines · Andi Kleen
Quoted 8 lines
Quoted 3 lines
allocate memory on the wrong node. I found a lot of code runs very badly until the cache decay parameter is set to 0 (no special cache affinity) to allow quick initial migration.
Interesting observation, I didn't make it when I tried the lazy homenode (quite a while ago). But I was focusing on MPI jobs. So what if we add a condition to
CAN_MIGRATEwhich disables the cache affinity before the first load balance?
Quoted 6 lines
What I currently have is two cache decay variables: one is used if the homenode is not assigned, the other otherwise. Both are sysctls too. But it obviously only works with lazy homenode, but the state is the same. I'm still not completely happy with it though.
Why exactly did you gave up to use the lazy homenode?
I left the loadbalancer to decide on where the homenode should be. And the decision wasn't good enough (it lead to unbalanced nodes, that's certainly not the case on Opteron :-). So it made sense to have a specialized homenode chooser which considered the node loads instead of changing the normal load balancer.
BTW: do you assign the homenode at first load balancing or at first cross-node balancing?
Quoted 9 lines
Quoted 4 lines
similar to
sched_balance_exec(). Tasks have a default initial load balancing policy of being migrated (and selecting the homenode) atexec(). This can be changed (with prctl) tofork(). The ilb policy is inheritable. Works fine for OpenMP jobs.Hmm, I should try that I guess. Where do you call it? At the end of
do_fork? I tried to hack upwake_up_forked_process()to do it, but it required large scale changes all over the scheduler so I eventually gave up.
For the processes with ilb_policy=FORK I chose the homenode and set the cpu before the task is woken up. It is done in do_fork right after the task structure has been cloned. wake_up_forked_process was changed to lock the rq of the child (and not the one of current) and not set the cpu any more. I don't think there was more...
Regards,
Erich
Quoted 5 lines
I left the loadbalancer to decide on where the homenode should be. And the decision wasn't good enough (it lead to unbalanced nodes, that's certainly not the case on Opteron :-). So it made sense to have a specialized homenode chooser which considered the node loads instead of changing the normal load balancer.
I have that, but only on exec (similar to what 2.5 mainline does with the NUMA scheduler)
Quoted 2 lines
BTW: do you assign the homenode at first load balancing or at first cross-node balancing?
It's the same on Opteron: each CPU is an own node. The lazy homenode for fork/clone is chosen on the first load balance of the new thread.
-Andi
Quoted 8 lines · Andi Kleen
Quoted 5 lines
I left the loadbalancer to decide on where the homenode should be. And the decision wasn't good enough (it lead to unbalanced nodes, that's certainly not the case on Opteron :-). So it made sense to have a specialized homenode chooser which considered the node loads instead of changing the normal load balancer.
I have that, but only on exec (similar to what 2.5 mainline does with the NUMA scheduler)
Oh, that's fine, then. It's better than just on exec().
Quoted 5 lines
Quoted 2 lines
BTW: do you assign the homenode at first load balancing or at first cross-node balancing?
It's the same on Opteron: each CPU is an own node. The lazy homenode for fork/clone is chosen on the first load balance of the new thread.
Ah, you're right :-)
Erich
Quoted 8 lines
Interesting observation, I didn't make it when I tried the lazy homenode (quite a while ago). But I was focusing on MPI jobs. So what if we add a condition to
CAN_MIGRATEwhich disables the cache affinity before the first load balance?Quoted 2 lines
Migration directly on fork/clone requires a lot of changes and also breaks down on some benchmarks.
Quoted 6 lines
Hmmm, I wouldn't allow this to any task/child, only to special ones. Under 2.4 I currently use a
sched_balance_fork()function similar tosched_balance_exec(). Tasks have a default initial load balancing policy of being migrated (and selecting the homenode) atexec(). This can be changed (with prctl) tofork(). The ilb policy is inheritable. Works fine for OpenMP jobs.
It'd be nice not to require user intervention here ... is it OK to set CAN_MIGRATE for all clone operations?
M.
Quoted 4 lines · Martin J. Bligh
Quoted 4 lines
Interesting observation, I didn't make it when I tried the lazy homenode (quite a while ago). But I was focusing on MPI jobs. So what if we add a condition to
CAN_MIGRATEwhich disables the cache affinity before the first load balance?
...
Quoted 3 lines
It'd be nice not to require user intervention here ... is it OK to set
CAN_MIGRATEfor all clone operations?
Do you think of something like:
#define CAN_MIGRATE_TASK(p,rq,this_cpu) \
(HOMENODE_UNSET(p) && \ //<--
(jiffies - (p)->last_run > cache_decay_ticks) && \
!task_running(rq, p) && \
((p)->cpus_allowed & (1UL << (this_cpu))))
curr = curr->prev;
if (!CAN_MIGRATE_TASK(tmp, busiest, this_cpu)
|| !numa_should_migrate(tmp, busiest, this_cpu)) {
if (curr != head)
goto skip_queue;
idx++;
goto skip_bitmap;
}
if (HOMENODE_UNSET(tmp)) //<--
set_task_node(tmp,cpu_to_node(this_cpu)); //<--
pull_task(busiest, array, tmp, this_rq, this_cpu);
if (!idle && --imbalance) {
...?
Guess this would help a bit for multithreaded jobs. Chosing the homenode more carefully here would be pretty expensive.
Regards,
Erich
--Erich Focht <[email protected]> wrote (on Tuesday, May 27, 2003 23:28:27 +0200):
Quoted 33 lines · Martin J. Bligh
Quoted 4 lines
Quoted 4 lines
Interesting observation, I didn't make it when I tried the lazy homenode (quite a while ago). But I was focusing on MPI jobs. So what if we add a condition to
CAN_MIGRATEwhich disables the cache affinity before the first load balance?...
Quoted 3 lines
It'd be nice not to require user intervention here ... is it OK to set
CAN_MIGRATEfor all clone operations?Do you think of something like:
# define CAN_MIGRATE_TASK(p,rq,this_cpu) \ (HOMENODE_UNSET(p) && \ //<-- (jiffies - (p)->last_run > cache_decay_ticks) && \ !task_running(rq, p) && \ ((p)->cpus_allowed & (1UL << (this_cpu))))curr = curr->prev; if (!CAN_MIGRATE_TASK(tmp, busiest, this_cpu) || !numa_should_migrate(tmp, busiest, this_cpu)) { if (curr != head) goto skip_queue; idx++; goto skip_bitmap; } if (HOMENODE_UNSET(tmp)) //<-- set_task_node(tmp,cpu_to_node(this_cpu)); //<-- pull_task(busiest, array, tmp, this_rq, this_cpu); if (!idle && --imbalance) { ...
Quoted 3 lines
?
Guess this would help a bit for multithreaded jobs. Chosing the homenode more carefully here would be pretty expensive.
My first instinct is that #define'ing CAN_MIGRATE_TASK in the midst of a function needs to die a horrible death ;-) But you didn't start that one, so other than that ...
My instinct would tell me the first expression should be ||, not && but I'm not 100% sure. And is this restricted to just clones? Doesn't seem to be, unless that's implicit in homenode_unset?
M.
Quoted 8 lines · Martin J. Bligh
Quoted 8 lines
Do you think of something like:
# define CAN_MIGRATE_TASK(p,rq,this_cpu) \ (HOMENODE_UNSET(p) && \ //<-- (jiffies - (p)->last_run > cache_decay_ticks) && \ !task_running(rq, p) && \ ((p)->cpus_allowed & (1UL << (this_cpu))))
...
Quoted 3 lines
My instinct would tell me the first expression should be ||, not && but I'm not 100% sure.
You're right.
Quoted 2 lines
And is this restricted to just clones? Doesn't seem to be, unless that's implicit in
homenode_unset?
Hmmm... That's actually the difficult issue with fork vs. clone and migrating or not. When you clone a small task, you'd usually like to keep it on the same node. If it's a big task and fault-in a lot of memory, it could make sense to let it migrate to another node. For forked tasks it's the same, you mighthave some more COW memory movement but after that you'll usually be happy if the child went away from the parent's node if it is a long-running child. Not so for a short running child. The current compromise:
- start children (no matter whether forked or cloned) on the same CPU
- allow other CPUs to steal freshly forked children by reducing the cache affinity until the first steal/migration
- ok with chidren who exec soon, they might exec before anyone can steal them, drop all the pages and find anew life on the optimal node
This way exec'd tasks get properly baklanced, forked/cloned ones get a better start than in the current scheduler. I'll post a patch on top of the node affine scheduler doing this in 1-2 days.
Regards,
Erich
Quoted 11 lines
Quoted 2 lines
And is this restricted to just clones? Doesn't seem to be, unless that's implicit in
homenode_unset?Hmmm... That's actually the difficult issue with fork vs. clone and migrating or not. When you clone a small task, you'd usually like to keep it on the same node. If it's a big task and fault-in a lot of memory, it could make sense to let it migrate to another node. For forked tasks it's the same, you mighthave some more COW memory movement but after that you'll usually be happy if the child went away from the parent's node if it is a long-running child. Not so for a short running child.
Can you define what you mean by big vs small? I presume you mean RSS? There are several factors that come into play here, at least:
1. RSS (and which bits of this lie on which node)
2. CPU utilisation of the task
3. Task duration
4. Cache warmth
5. the current balance situation.
I'm not convinced there's anything we can do about 3, since it's mostly unpredicatable, and I don't have crystal_ball.o ... we can kind of predict 2, at least for running tasks (not sure it makes much sense over fork). For 1, we can kind of use that over a fork, though as we have no idea whether it'll exec or not, I'm not sure it's much use *unless* we're cloning.
Quoted 10 lines
The current compromise:
- start children (no matter whether forked or cloned) on the same CPU
- allow other CPUs to steal freshly forked children by reducing the cache affinity until the first steal/migration
- ok with chidren who exec soon, they might exec before anyone can steal them, drop all the pages and find anew life on the optimal nodeThis way exec'd tasks get properly baklanced, forked/cloned ones get a better start than in the current scheduler. I'll post a patch on top of the node affine scheduler doing this in 1-2 days.
Turning on child-runs-first would instinctively be good as well, though I have no benchmarks to prove it ... would be nice to get the load balance situation fixed asap by running the exec. That's not on right now, IIRC.
M.
Can you define what you mean by big vs small? I presume you mean RSS? There are several factors that come into play here, at least:
1. RSS (and which bits of this lie on which node)
2. CPU utilisation of the task
3. Task duration
4. Cache warmth
5. the current balance situation.
Along the same lines, would it make sense to *permit* imbalances for some classes of tasks? It may be worth it, for example, to let three threads sharing a lot of data to saturate one cpu because what they lose from their self-competition is saved from the extremely warm cache.
So you leave cpu0 at 7 tasks even though cpu1 only has 4, because the 7 are "related" and the 4 are "dissimilar"? The equation changes dramatically, perhaps, once their is an idle cpu, but if everything is busy does it make sense to weight the items in the runqueues in any way?
Rick
Quoted 14 lines
Can you define what you mean by big vs small? I presume you mean RSS? There are several factors that come into play here, at least:
1. RSS (and which bits of this lie on which node)
2. CPU utilisation of the task
3. Task duration
4. Cache warmth
5. the current balance situation.Along the same lines, would it make sense to *permit* imbalances for some classes of tasks? It may be worth it, for example, to let three threads sharing a lot of data to saturate one cpu because what they lose from their self-competition is saved from the extremely warm cache.
Quoted 4 lines
So you leave cpu0 at 7 tasks even though cpu1 only has 4, because the 7 are "related" and the 4 are "dissimilar"? The equation changes dramatically, perhaps, once their is an idle cpu, but if everything is busy does it make sense to weight the items in the runqueues in any way?
It'd make sense ... but I think it would be a bitch to implement ;-) How do you know when it's worth it?
M.