Skip to contentSkip to conversation

1 cpu/node scheduler fix

PATCH In review Erich Focht 4 participants 5 messages Aug 24, 2003 – Sep 2, 2003

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 1 cpu/node scheduler fix

This is the 1 cpu/node fix of the NUMA scheduler rewritten for the new cpumask handling. The previous version was a bit too aggressive with cross node balancing so I changed the default timings a bit such that the behavior is very similar to the old one.

Here is what the patch does:
- Links the frequency of cross-node balances to the number of failed local balance attempts. This simplifies the code by removing the too rigid cross-node balancing dependency of the timer interrupts.

- Fixes the 1 CPU/node issue, i.e. eliminates local balance attempts for the nodes which have only one CPU. Can happen on any NUMA platform (playing around with a 2 CPU/node box and have a flaky CPU, so I have sometimes a node with only one CPU), is a major issue on AMD64.

- Makes the cross-node balance frequency tunable by the parameter NUMA_FACTOR_BONUS. Its default setting is such that the scheduler behaves like before: cross node balance every 5 local node balances on an idle CPU, every 2 local node balances on a busy CPU. This parameter should be tuned for each platform depending on its NUMA factor.

This simple patch is not meant as opposition to Andrew's attempt to NUMAize the whole scheduler. That one will definitely make NUMA coders' lives easier but I fear that it is a bit too complex for 2.6. The attached small incremental change is sufficient to solve the main problem. Besides, the change of the cross-node scheduling is compatible with Andrew's scheduler structure. I really don't like the timer-based cross-node balancing because it is too unflexible (no way to have different balancing intervals for each node) and I'd really like to get back to just one single point of entry for load balancing:
the routine load_balance(), no matter whether we balance inside a timer interrupt or while the CPU is going idle.

Erich

include/linux/topology.h +9 -0
diff -urNp 2.6.0-test4/include/linux/topology.h 2.6.0-test4-1cpuf/include/linux/topology.h
@@ -54,4 +54,13 @@ static inline int __next_node_with_cpus(
 #define for_each_node_with_cpus(node) \
 	for (node = 0; node < numnodes; node = __next_node_with_cpus(node))
 
+#ifndef NUMA_FACTOR_BONUS
+/*
+ * High NUMA_FACTOR_BONUS means rare cross-node load balancing. The default
+ * value of 3 means idle_node_rebalance after 5 (failed) local balances,
+ * busy_node_rebalance after 2 failed local balances. Should be tuned for
+ * each platform in asm/topology.h.
+ */
+#define NUMA_FACTOR_BONUS 3
+#endif
 #endif /* _LINUX_TOPOLOGY_H */
kernel/sched.c +52 -33

144 lines not on this page · raw message

#1 lore raw
Quoted 11 lines · Erich Focht

This simple patch is not meant as opposition to Andrew's attempt to NUMAize the whole scheduler. That one will definitely make NUMA coders' lives easier but I fear that it is a bit too complex for 2.6. The attached small incremental change is sufficient to solve the main problem. Besides, the change of the cross-node scheduling is compatible with Andrew's scheduler structure. I really don't like the timer-based cross-node balancing because it is too unflexible (no way to have different balancing intervals for each node) and I'd really like to get back to just one single point of entry for load balancing: the routine load_balance(), no matter whether we balance inside a timer interrupt or while the CPU is going idle.

your patch clearly simplifies things. Would you mind to also extend the rebalance-frequency based balancing to the SMP scheduler, and see what effect that has? Ie. to remove much of the 'tick' component from the SMP scheduler as well, and make it purely frequency based.

I'm still afraid of balancing artifacts if we lose track of time (which the tick thing is about, and which cache affinity is a function of), but maybe not. It would certainly unify things more. If it doesnt work out then we can still do your stuff for the cross-node balancing only.

Ingo

#2 lore raw

Hi Ingo,

thanks for the reply and sorry for the late reaction. I've been away for a week and (unexpectedly) didn't have email/internet connectivity during this time.

Quoted 10 lines · Ingo Molnar
Quoted 4 lines · Erich Focht

different balancing intervals for each node) and I'd really like to get back to just one single point of entry for load balancing: the routine load_balance(), no matter whether we balance inside a timer interrupt or while the CPU is going idle.

your patch clearly simplifies things. Would you mind to also extend the rebalance-frequency based balancing to the SMP scheduler, and see what effect that has? Ie. to remove much of the 'tick' component from the SMP scheduler as well, and make it purely frequency based.

Actually I didn't remove the tick-based load-balancing, just simplified it and wanted to have only one load_balance() call instead of separate load_balance(), node_balance(), load_balance_in_timer_interrupt_when_idle() and load_balance_in_timer_interrupt_when_busy().

The current change keeps track of the number of failed load_balance attempts and does cross-node balancing after a certain number of failed attempts. If I understand you correctly you'd like to test this concept also on a lower level? So keep track of the number of schedules and context switches and call the SMP load balancer after a certain number of schedules? This could work, though on idle CPUs I'm more comfortable with the timer tick... The logic of cpu_idle() would need a change, too. Do you expect an impact on the latency issue? Would you mind doing these changes in two steps: first the simple NUMA one, later the radical SMP change?

Quoted 4 lines

I'm still afraid of balancing artifacts if we lose track of time (which the tick thing is about, and which cache affinity is a function of), but maybe not. It would certainly unify things more. If it doesnt work out then we can still do your stuff for the cross-node balancing only.

With the small fix for NUMA there's no problem because the CAN_MIGRATE_TASK macro really compares times/jiffies for getting an idea about the cache coolness. This wouldn't change even with the elimination of the timer based load_balance calls.

Regards,
Erich

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Hi Ingo,

thanks for the reply and sorry for the late reaction. I've been away for a week and (unexpectedly) didn't have email/internet connectivity during this time.

Quoted 10 lines · Ingo Molnar
Quoted 4 lines · Erich Focht

different balancing intervals for each node) and I'd really like to get back to just one single point of entry for load balancing: the routine load_balance(), no matter whether we balance inside a timer interrupt or while the CPU is going idle.

your patch clearly simplifies things. Would you mind to also extend the rebalance-frequency based balancing to the SMP scheduler, and see what effect that has? Ie. to remove much of the 'tick' component from the SMP scheduler as well, and make it purely frequency based.

Actually I didn't remove the tick-based load-balancing, just simplified it and wanted to have only one load_balance() call instead of separate load_balance(), node_balance(), load_balance_in_timer_interrupt_when_idle() and load_balance_in_timer_interrupt_when_busy().

The current change keeps track of the number of failed load_balance attempts and does cross-node balancing after a certain number of failed attempts. If I understand you correctly you'd like to test this concept also on a lower level? So keep track of the number of schedules and context switches and call the SMP load balancer after a certain number of schedules? This could work, though on idle CPUs I'm more comfortable with the timer tick... The logic of cpu_idle() would need a change, too. Do you expect an impact on the latency issue? Would you mind doing these changes in two steps: first the simple NUMA one, later the radical SMP change?

Quoted 4 lines

I'm still afraid of balancing artifacts if we lose track of time (which the tick thing is about, and which cache affinity is a function of), but maybe not. It would certainly unify things more. If it doesnt work out then we can still do your stuff for the cross-node balancing only.

With the small fix for NUMA there's no problem because the CAN_MIGRATE_TASK macro really compares times/jiffies for getting an idea about the cache coolness. This wouldn't change even with the elimination of the timer based load_balance calls.

Regards,
Erich

#3 lore raw
In reply to Erich Focht
Quoted 4 lines

This simple patch is not meant as opposition to Andrew's attempt to NUMAize the whole scheduler. That one will definitely make NUMA coders' lives easier but I fear that it is a bit too complex for 2.6.

I would agree, it's probably too much to change this late in 2.6. Eventually (2.7) I think we should revisit this and try for a more unified approach.

Quoted 8 lines

The attached small incremental change is sufficient to solve the main problem. Besides, the change of the cross-node scheduling is compatible with Andrew's scheduler structure. I really don't like the timer-based cross-node balancing because it is too unflexible (no way to have different balancing intervals for each node) and I'd really like to get back to just one single point of entry for load balancing:
the routine load_balance(), no matter whether we balance inside a timer interrupt or while the CPU is going idle.

Looks good to me. One other thing your patch fixes: Once in a while we called load_balance in rebalance_tick with the wrong 'idle' value. Occasionally we would be on an idle_node and idle_cpu rebalance tick, the idle cpu would [possibly] pull a task, become non-idle, then we would call load_balance again, but still have idle=1 for the intranode balance.

#4 lore raw
In reply to Erich Focht
Quoted 16 lines

This is the 1 cpu/node fix of the NUMA scheduler rewritten for the new cpumask handling. The previous version was a bit too aggressive with cross node balancing so I changed the default timings a bit such that the behavior is very similar to the old one.

Here is what the patch does:
- Links the frequency of cross-node balances to the number of failed local balance attempts. This simplifies the code by removing the too rigid cross-node balancing dependency of the timer interrupts.

- Fixes the 1 CPU/node issue, i.e. eliminates local balance attempts for the nodes which have only one CPU. Can happen on any NUMA platform (playing around with a 2 CPU/node box and have a flaky CPU, so I have sometimes a node with only one CPU), is a major issue on AMD64.

Quoted 5 lines

- Makes the cross-node balance frequency tunable by the parameter NUMA_FACTOR_BONUS. Its default setting is such that the scheduler behaves like before: cross node balance every 5 local node balances on an idle CPU, every 2 local node balances on a busy CPU. This parameter should be tuned for each platform depending on its NUMA factor.

This seems to clear up the low end stuff I was seeing before - thanks.

Did you (or anyone else) get a chance to test this on AMD? Would be nice to confirm that's fixed ...

M.