node affine NUMA scheduler
Subsystems (7)
PATCH 1/2 node affine NUMA scheduler
Hi,
here is an update of the NUMA scheduler for the 2.5.37 kernel. It contains some bugfixes and the coupling to discontigmem memory allocation (memory is allocated from the processes' homenode).
The node affine NUMA scheduler is targeted for multi-node platforms and built on top of the O(1) scheduler. Its main objective is to keep the memory access latency for each task as low as possible by scheduling it on or near the node on which its memory is allocated. This should achieve the hard-affinity benefits automatically.
The patch comes in two parts. The first part is the core NUMA scheduler, it is functional without the second part and provides following features:
- Node aware scheduler (implemented CPU pools).
- Scheduler behaves like O(1) scheduler within a node.
- Equal load among nodes is targeted, stealing tasks from remote nodes is delayed more if the current node is averagely loaded, less if it's unloaded.
- Multi-level node hierarchies are supported by stealing delays adjusted by the relative "node-distance" (memory access latency ratio).
The second part of the patch extends the pooling NUMA scheduler to have node affine tasks:
- Each process has a homenode assigned to it at creation time (initial load balancing). Memory will be allocated from this node.
- Each process is preferentially scheduled on its homenode and attracted back to it if scheduled away for some reason. For multi-level node hierarchies the task is attracted to its supernode, too.
The patch was tested on IA64 platforms but should work on NUMAQ i386, too. Similar code for 2.4.18 (cf. http://home.arcor.de/efocht/sched)
runs in production environments since months.
Comments, tests, ports to other platforms/architectures are very welcome!
Regards,
Erich
arch/i386/config.in +1 -0
@@ -177,6 +177,7 @@ else fi # Common NUMA Features if [ "$CONFIG_X86_NUMAQ" = "y" ]; then + bool 'Enable NUMA scheduler' CONFIG_NUMA_SCHED bool 'Numa Memory Allocation Support' CONFIG_NUMA if [ "$CONFIG_NUMA" = "y" ]; then define_bool CONFIG_DISCONTIGMEM y
arch/i386/kernel/smpboot.c +18 -1
@@ -765,6 +765,8 @@ static int __init wakeup_secondary_via_Iextern unsigned long cpu_initialized; +static int __initdata nr_lnodes =0 ; +static void __init do_boot_cpu (int apicid)/* * NOTE - on most systems this is a PHYSICAL apic ID, but on multiquad
@@ -773,11 +775,17 @@ static void __init do_boot_cpu (int apic {struct task_struct *idle;unsigned long boot_error =0 ; -int timeout, cpu; +int timeout, cpu, cell;unsigned long start_eip;unsigned short nmi_high, nmi_low; cpu = ++cpucount; +#ifdef CONFIG_NUMA_SCHED + cell =SAPICID_TO_PNODE (apicid); +if (pnode_to_lnode[cell] <0 ) { + pnode_to_lnode[cell] = nr_lnodes++; + } +#endif /* * We can't use kernel_thread since we must avoid to * reschedule the child.
@@ -996,6 +1004,10 @@ static void __init smp_boot_cpus(unsigneset_bit (0 , &cpu_callout_map); boot_cpu_logical_apicid =logical_smp_processor_id ();map_cpu_to_boot_apicid (0 , boot_cpu_apicid); +#ifdef CONFIG_NUMA_SCHED + pnode_to_lnode[SAPICID_TO_PNODE (boot_cpu_apicid)] = nr_lnodes++; +printk ("boot_cpu_apicid = %d, nr_lnodes = %d, lnode = %d\n" , boot_cpu_apicid, nr_lnodes, pnode_to_lnode[0 ]); +#endif current_thread_info ()->cpu =0 ;smp_tune_scheduling ();
@@ -1194,6 +1206,11 @@ int __devinit __cpu_up(unsigned int cpu)void __init smp_cpus_done (unsigned int max_cpus) {zap_low_mappings (); +#ifdef CONFIG_NUMA_SCHED +pooldata_lock (); +bld_pools (); +pooldata_unlock (); +#endif }void __init smp_intr_init ()
arch/ia64/config.in +2 -0
@@ -67,11 +67,13 @@ fi if [ "$CONFIG_IA64_GENERIC" = "y" -o "$CONFIG_IA64_DIG" = "y" -o "$CONFIG_IA64_HP_ZX1" = "y" ]; then bool ' Enable IA-64 Machine Check Abort' CONFIG_IA64_MCA + bool ' Enable NUMA scheduler' CONFIG_NUMA_SCHED define_bool CONFIG_PM y fi if [ "$CONFIG_IA64_SGI_SN1" = "y" -o "$CONFIG_IA64_SGI_SN2" = "y" ]; then define_bool CONFIG_IA64_SGI_SN y + bool ' Enable NUMA scheduler' CONFIG_NUMA_SCHED bool ' Enable extra debugging code' CONFIG_IA64_SGI_SN_DEBUG bool ' Enable SGI Medusa Simulator Support' CONFIG_IA64_SGI_SN_SIM bool ' Enable autotest (llsc). Option to run cache test instead of booting' \
arch/ia64/kernel/smpboot.c +22 -2
@@ -16,6 +16,7 @@#include <linux/config.h> +#include <linux/acpi.h> #include <linux/bootmem.h> #include <linux/delay.h> #include <linux/init.h>
@@ -364,11 +365,22 @@ fork_by_hand (void)return do_fork (CLONE_VM |CLONE_IDLETASK ,0 ,0 ,0 ); } +#ifdef CONFIG_NUMA_SCHED +static int __initdata nr_lnodes=0 ; +#endif +static int __init do_boot_cpu (int sapicid,int cpu) {struct task_struct *idle; -int timeout; +int timeout, cell; + +#ifdef CONFIG_NUMA_SCHED + cell =SAPICID_TO_PNODE (sapicid); +if (pnode_to_lnode[cell] <0 ) { + pnode_to_lnode[cell] = nr_lnodes++; + } +#endif /* * We can't use kernel_thread since we must avoid to reschedule the child.
@@ -421,7 +433,7 @@ unsigned long cache_decay_ticks; /* # ofstatic void smp_tune_scheduling (void ) { - cache_decay_ticks =10 ;/* XXX base this on PAL info and cache-bandwidth estimate */ + cache_decay_ticks =8 ;/* XXX base this on PAL info and cache-bandwidth estimate */ printk ("task migration cache decay timeout: %ld msecs.\n" , (cache_decay_ticks +1 ) *1000 /HZ );
@@ -474,6 +486,9 @@ smp_prepare_cpus (unsigned int max_cpus) local_cpu_data->loops_per_jiffy = loops_per_jiffy; ia64_cpu_to_sapicid[0 ] = boot_cpu_id; +#ifdef CONFIG_NUMA_SCHED + pnode_to_lnode[SAPICID_TO_PNODE (boot_cpu_id)] = nr_lnodes++; +#endif printk ("Boot processor id 0x%x/0x%x\n" ,0 , boot_cpu_id);
@@ -506,6 +521,11 @@ smp_cpus_done (unsigned int dummy)printk (KERN_INFO "Total of %d processors activated (%lu.%02lu BogoMIPS).\n" ,num_online_cpus (), bogosum/(500000 /HZ ), (bogosum/(5000 /HZ ))%100 ); +#ifdef CONFIG_NUMA_SCHED +pooldata_lock (); +bld_pools (); +pooldata_unlock (); +#endif }int __devinit
include/asm-i386/atomic.h +12 -0
@@ -111,6 +111,18 @@ static __inline__ void atomic_inc(atomic }/** +* atomic_inc_return - increment atomic variable and return new value +* @v: pointer of type atomic_t +* +* Atomically increments @v by 1 and return it's new value. Note that +* the guaranteed useful range of an atomic_t is only 24 bits. +*/ +static inline int atomic_inc_return (atomic_t *v){ +atomic_inc (v); +return v->counter; +} + +/** * atomic_dec - decrement atomic variable * @v: pointer of type atomic_t *
include/asm-i386/smp.h +6 -0
@@ -124,5 +124,11 @@ static inline int num_booting_cpus(void)#define NO_PROC_ID 0xFF/* No processor magic marker */ +#ifdef CONFIG_NUMA_SCHED +#define NR_NODES 8 +#define cpu_physical_id (cpuid) (cpu_to_physical_apicid(cpuid)) +#define SAPICID_TO_PNODE (hwid) (hwid >> 4) +#endif +#endif #endif
include/asm-ia64/smp.h +26 -0
@@ -13,6 +13,7 @@#ifdef CONFIG_SMP +#include <linux/cache.h> #include <linux/init.h> #include <linux/threads.h> #include <linux/kernel.h>
@@ -130,6 +131,31 @@ extern void __cpu_die (unsigned int cpu)extern int __cpu_up (unsigned int cpu);extern void __init smp_build_cpu_map (void ); +#ifdef CONFIG_NUMA_SCHED +#ifdef CONFIG_IA64_DIG +/* sooner or later this should be a configurable parameter [EF] */ +#define NR_NODES 8 +/* +* This is the node ID on the NEC AzusA, +* on LION and BigSur it correctly initializes to node 0 +*/ +#define SAPICID_TO_PNODE (hwid) ((hwid >> 12) & 0xff) + +#elif defined(CONFIG_IA64_SGI_SN ) + +/* +* SGI SN1 & SN2 specific macros +*/ +#define NR_NODES 32 +#define SAPICID_TO_PNODE (hwid) cpuid_to_cnodeid(hwid) + +#endif + +#else /* CONFIG_NUMA_SCHED */ +#define NR_NODES 1 +#define SAPICID_TO_PNODE (hwid) 0 +#endif /* CONFIG_NUMA_SCHED */ +extern void __init init_smp_config (void );extern void smp_do_timer (struct pt_regs *regs);
include/linux/sched.h +41 -1
54 lines not on this page · raw message
kernel/ksyms.c +12 -0
@@ -606,6 +606,18 @@ EXPORT_SYMBOL(init_task);EXPORT_SYMBOL (init_thread_union);EXPORT_SYMBOL (tasklist_lock); + +#ifdef CONFIG_NUMA_SCHED +#include <linux/sched.h> +EXPORT_SYMBOL (runqueues_address); +EXPORT_SYMBOL (numpools); +EXPORT_SYMBOL (pool_ptr); +EXPORT_SYMBOL (pool_cpus); +EXPORT_SYMBOL (pool_nr_cpus); +EXPORT_SYMBOL (pool_mask); +EXPORT_SYMBOL (sched_migrate_task); +#endif +#if defined(CONFIG_SMP ) && defined(__GENERIC_PER_CPU)EXPORT_SYMBOL (__per_cpu_offset);#endif
kernel/sched.c +432 -121
690 lines not on this page · raw message
Here comes the second part of the node affine NUMA scheduler.
Quoted 10 lines
The patch comes in two parts. The first part is the core NUMA scheduler, it is functional without the second part and provides following features:
- Node aware scheduler (implemented CPU pools).
- Scheduler behaves like O(1) scheduler within a node.
- Equal load among nodes is targeted, stealing tasks from remote nodes is delayed more if the current node is averagely loaded, less if it's unloaded.
- Multi-level node hierarchies are supported by stealing delays adjusted by the relative "node-distance" (memory access latency ratio).
Quoted 8 lines
The second part of the patch extends the pooling NUMA scheduler to have node affine tasks:
- Each process has a homenode assigned to it at creation time (initial load balancing). Memory will be allocated from this node.
- Each process is preferentially scheduled on its homenode and attracted back to it if scheduled away for some reason. For multi-level node hierarchies the task is attracted to its supernode, too.
Regards,
Erich
arch/i386/config.in +1 -1
@@ -177,7 +177,7 @@ else fi # Common NUMA Features if [ "$CONFIG_X86_NUMAQ" = "y" ]; then - bool 'Enable NUMA scheduler' CONFIG_NUMA_SCHED + bool 'Enable node affine NUMA scheduler' CONFIG_NUMA_SCHED bool 'Numa Memory Allocation Support' CONFIG_NUMA if [ "$CONFIG_NUMA" = "y" ]; then define_bool CONFIG_DISCONTIGMEM y
arch/ia64/config.in +2 -2
@@ -67,13 +67,13 @@ fi if [ "$CONFIG_IA64_GENERIC" = "y" -o "$CONFIG_IA64_DIG" = "y" -o "$CONFIG_IA64_HP_ZX1" = "y" ]; then bool ' Enable IA-64 Machine Check Abort' CONFIG_IA64_MCA - bool ' Enable NUMA scheduler' CONFIG_NUMA_SCHED + bool ' Enable node affine NUMA scheduler' CONFIG_NUMA_SCHED define_bool CONFIG_PM y fi if [ "$CONFIG_IA64_SGI_SN1" = "y" -o "$CONFIG_IA64_SGI_SN2" = "y" ]; then define_bool CONFIG_IA64_SGI_SN y - bool ' Enable NUMA scheduler' CONFIG_NUMA_SCHED + bool ' Enable node affine NUMA scheduler' CONFIG_NUMA_SCHED bool ' Enable extra debugging code' CONFIG_IA64_SGI_SN_DEBUG bool ' Enable SGI Medusa Simulator Support' CONFIG_IA64_SGI_SN_SIM bool ' Enable autotest (llsc). Option to run cache test instead of booting' \
fs/exec.c +3 -0
@@ -995,6 +995,9 @@ int do_execve(char * filename, char ** aint retval;int i; +if (current->node_policy ==NODPOL_EXEC ) +sched_balance_exec (); + file =open_exec (filename); retval =PTR_ERR (file);
include/asm-i386/mmzone.h +4 -0
@@ -20,7 +20,11 @@#endif /* CONFIG_X86_NUMAQ */ #ifdef CONFIG_NUMA +#ifdef CONFIG_NUMA_SCHED +#define numa_node_id () (current->node) +#else #define numa_node_id () _cpu_to_node(smp_processor_id()) +#endif #endif /* CONFIG_NUMA */ extern struct pglist_data *node_data[];
include/linux/prctl.h +6 -0
@@ -34,4 +34,10 @@# define PR_FP_EXC_ASYNC 2/* async recoverable exception mode */ # define PR_FP_EXC_PRECISE 3/* precise exception mode */ +/* Get/set node for node-affine scheduling */ +#define PR_GET_NODE 16 +#define PR_SET_NODE 17 +#define PR_GET_NODPOL 18 +#define PR_SET_NODPOL 19 +#endif /* _LINUX_PRCTL_H */
include/linux/sched.h +15 -0
@@ -159,6 +159,15 @@ extern void update_one_process(struct ta unsigned long system, int cpu);extern void scheduler_tick (int user_tick,int system);extern unsigned long cache_decay_ticks; +#ifdef CONFIG_NUMA_SCHED +extern void sched_balance_exec (void ); +extern void sched_balance_fork (task_t *p); +extern void set_task_node (task_t *p,int node); +#else +#define sched_balance_exec () {} +#define sched_balance_fork (p) {} +#define set_task_node (p,n) {} +#endif extern void sched_migrate_task (task_t *p,int cpu);#define MAX_SCHEDULE_TIMEOUT LONG_MAX
@@ -293,6 +302,8 @@ struct task_struct {unsigned long policy;unsigned long cpus_allowed;unsigned int time_slice, first_time_slice; +int node; +int node_policy;struct list_head tasks;struct list_head ptrace_children;
@@ -484,9 +495,13 @@ extern char lnode_number[NR_CPUS] __cachextern void pooldata_lock (void );extern void pooldata_unlock (void ); +# define HOMENODE_INC (rq,node) (rq)->nr_homenode[node]++ +# define HOMENODE_DEC (rq,node) (rq)->nr_homenode[node]--#else # define POOL_DELAY (x,y) (0)# define CPU_TO_NODE (cpu) (0) +# define HOMENODE_INC (rq,node) {} +# define HOMENODE_DEC (rq,node) {}#endif extern void set_user_nice (task_t *p,long nice);
kernel/fork.c +3 -0
@@ -701,6 +701,9 @@ static struct task_struct *copy_process(#ifdef CONFIG_SMP {int i; +if (p->node_policy ==NODPOL_FORK_ALL || + (p->node_policy ==NODPOL_FORK && !(clone_flags &CLONE_VM ))) +sched_balance_fork (p);/* ?? should we just memset this ?? */ for (i =0 ; i <NR_CPUS ; i++)
kernel/sched.c +198 -0
276 lines not on this page · raw message
kernel/softirq.c +1 -0
@@ -365,6 +365,7 @@ static int ksoftirqd(void * __bind_cpu)set_cpus_allowed (current,1UL << cpu);if (smp_processor_id () != cpu)BUG (); +set_task_node (current,CPU_TO_NODE (cpu));sprintf (current->comm,"ksoftirqd_CPU%d" , cpu);
kernel/sys.c +59 -0
71 lines not on this page · raw message
Quoted 5 lines
The second part of the patch extends the pooling NUMA scheduler to have node affine tasks:
- Each process has a homenode assigned to it at creation time (initial load balancing). Memory will be allocated from this node.
Hmmm ... I was wondering how you achieved that without modifying alloc_pages ... until I saw this bit.
#ifdef CONFIG_NUMA
+#ifdef CONFIG_NUMA_SCHED
+#define numa_node_id() (current->node)
+#else
#define numa_node_id() _cpu_to_node(smp_processor_id())
+#endif
#endif /* CONFIG_NUMA */
I'm not convinced it's a good idea to modify this generic function, which was meant to tell you what node you're running on. I can't see it being used anywhere else right now, but wouldn't it be better to just modify alloc_pages instead to use current->node, and leave this macro as intended? Or make a process_node_id or something?
Anyway, I'm giving your code a quick spin ... will give you some results later ;-)
M.
Quoted 2 lines
Anyway, I'm giving your code a quick spin ... will give you some results later ;-)
Hmmm .... well I ran the One True Benchmark (tm). The patch *increased* my kernel compile time from about 20s to about 28s. Not sure I like that idea ;-) Anything you'd like tweaked, or more info? Both user and system time were up ... I'll grab a profile of kernel stuff.
M.
Quoted 10 lines
Quoted 2 lines
Anyway, I'm giving your code a quick spin ... will give you some results later ;-)
Hmmm .... well I ran the One True Benchmark (tm). The patch *increased* my kernel compile time from about 20s to about 28s. Not sure I like that idea ;-) Anything you'd like tweaked, or more info? Both user and system time were up ... I'll grab a profile of kernel stuff.
From the below, I'd suggest you're getting pages off the wrong
nodes: do_anonymous_page is page zeroing, and rmqueue the buddy allocator. Are you sure the current->node thing is getting set correctly? I'll try backing out your alloc_pages tweaking, and see what happens.
An old compile off 2.5.31-mm1 + extras (I don't have 37, but similar)
87elapse133639 total 0.1390
74447 default_idle
6887 do_anonymous_page
4456 page_remove_rmap
4082 handle_mm_fault
3733 .text.lock.namei
2512 page_add_rmap
2187 __generic_copy_from_user
1989 rmqueue
1964 .text.lock.dec_and_lock
1761 vm_enough_memory
1631 file_read_actor
1599 zap_pte_range
1507 __free_pages_ok
1323 find_get_page
1117 do_no_page
1097 get_empty_filp
1023 link_path_walk
2.5.37-mm1
256745 total 0.2584
82934 default_idle
38978 do_anonymous_page
36533 rmqueue
35099 __free_pages_ok
5551 page_remove_rmap
4694 handle_mm_fault
3166 page_add_rmap
2904 do_no_page
2674 .text.lock.namei
2566 __alloc_pages
2526 zap_pte_range
2306 __generic_copy_from_user
2218 file_read_actor
1803 vm_enough_memory
1789 do_wp_page
1557 .text.lock.dec_and_lock
1414 find_get_page
1251 do_softirq
1123 release_pages
1086 link_path_walk
1072 get_empty_filp
1038 schedule
Quoted 5 lines
From the below, I'd suggest you're getting pages off the wrong
nodes:do_anonymous_pageis page zeroing, and rmqueue the buddy allocator. Are you sure thecurrent->nodething is getting set correctly? I'll try backing out youralloc_pagestweaking, and see what happens.
OK, well removing that part of the patch gets us back from 28s to about 21s (compared to 20s virgin), total user time compared to virgin is up from 59s to 62s, user from 191 to 195. So it's still a net loss, but not by nearly as much. Are you determining target node on fork or exec ? I forget ...
Profile is more comparible. Nothing sticks out any more, but maybe it just needs some tuning for balance intervals or something.
153385 total 0.1544
91219 default_idle
7475 do_anonymous_page
4564 page_remove_rmap
4167 handle_mm_fault
3467 .text.lock.namei
2520 page_add_rmap
2112 rmqueue
1905 .text.lock.dec_and_lock
1849 zap_pte_range
1668 vm_enough_memory
1612 __free_pages_ok
1504 file_read_actor
1484 find_get_page
1381 __generic_copy_from_user
1207 do_no_page
1066 schedule
1050 get_empty_filp
1034 link_path_walk
Hi Martin,
thanks for the comments and the testing!
Quoted 5 lines · Martin J. Bligh
Quoted 5 lines
From the below, I'd suggest you're getting pages off the wrong
nodes:do_anonymous_pageis page zeroing, and rmqueue the buddy allocator. Are you sure thecurrent->nodething is getting set correctly? I'll try backing out youralloc_pagestweaking, and see what happens.
The current->node is most probably wrong for most of the kernel threads, except for migration_thread and ksoftirqd. But it should be fine for user processes.
Might also be that the __node_distance matrix which you might use by default is not optimal for NUMAQ. It is fine for our remote/local latency ratio of 1.6. Yours is maybe an order of magnitude larger? Try replacing: 15 -> 50, guess you don't go beyond 4 nodes now...
Quoted 5 lines
OK, well removing that part of the patch gets us back from 28s to about 21s (compared to 20s virgin), total user time compared to virgin is up from 59s to 62s, user from 191 to 195. So it's still a net loss, but not by nearly as much. Are you determining target node on fork or exec ? I forget ...
The default is exec(). You can use
http://home.arcor.de/efocht/sched/nodpol.c
to set the node_policy to do initial load_balancing in fork(). Just do "nodpol -P 2" in the shell before starting the job/task. This is VERY reccomended if you are creating many tasks/threads. The default behavior is fine for MPI jobs or users starting serial processes.
Quoted 2 lines
Profile is more comparible. Nothing sticks out any more, but maybe it just needs some tuning for balance intervals or something.
Hmmm... There are two changes which might lead to lower performance:
1. load_balance() is not inlined any more.
2. pull_task steals only one task at a load_balance() call. It was maximally imbalance/2 (if I remember correctly).
And of course, there is some real additional overhead due to the initial load balancing which one feels for short living tasks... So please try "nodpol -P 2" (and reset to default by "nodpol -P 0".
Did you try the first patch alone? I mean the pooling-only scheduler?
Thanks,
Erich
Quoted 19 lines
153385 total 0.1544
91219default_idle
7475do_anonymous_page
4564page_remove_rmap
4167handle_mm_fault
3467 .text.lock.namei
2520page_add_rmap
2112 rmqueue
1905 .text.lock.dec_and_lock
1849zap_pte_range
1668vm_enough_memory
1612__free_pages_ok
1504file_read_actor
1484find_get_page
1381__generic_copy_from_user
1207do_no_page
1066 schedule
1050get_empty_filp
1034link_path_walk
Signature · 4 lines
Dr. Erich Focht <[email protected]> NEC European Supercomputer Systems, European HPC Technology Center Hessbruehlstr. 21B, 70565 Stuttgart, Germany phone: +49-711-78055-15 fax : +49-711-78055-25
Quoted 4 lines · Erich Focht
Might also be that the
__node_distancematrix which you might use by default is not optimal for NUMAQ. It is fine for our remote/local latency ratio of 1.6. Yours is maybe an order of magnitude larger? Try replacing: 15 -> 50, guess you don't go beyond 4 nodes now...
I'm running with 8 over the weekend, and by and large we go to 16, though we rarely put all our eggs in one basket.
I'll take it for a spin.
Cheers,
Bill
Quoted 1 line · Martin J. Bligh
An old compile off 2.5.31-mm1 + extras (I don't have 37, but similar)
Some 8-quad numbers for 2.5.37 (virgin) follow.
I'll get dcache_rcu and NUMA sched stuff in on the act for round 2. This is more fs transaction-based (and VM process-spawning overhead) and not pure I/O throughput so there won't be things like "but everybody's running at peak I/O bandwidth" obscuring the issues.
real 0m30.854s
c01053ec 16963617 89.009 poll_idle c0114a48 452526 2.37443 load_balance c013962c 253666 1.331 get_page_state c01466de 177354 0.930586 .text.lock.file_table c0114ec0 150583 0.790117 scheduler_tick c01547b3 116144 0.609414 .text.lock.namei c01422ac 94042 0.493444 page_remove_rmap c0138c24 83293 0.437043 rmqueue c0141e48 51963 0.272653 page_add_rmap c012d5ec 37086 0.194592 do_anonymous_page c01391d0 34454 0.180782 __alloc_pages c0130e08 32111 0.168488 find_get_page c0139534 29222 0.153329 nr_free_pages c012df4c 26734 0.140275 handle_mm_fault c0146070 25881 0.135799 get_empty_filp c01a0d2c 25250 0.132488 __generic_copy_from_user c0111728 22018 0.11553 smp_apic_timer_interrupt c0112b90 20777 0.109018 pfn_to_nid c0136238 18410 0.0965983 kmem_cache_free c0113270 17494 0.091792 do_page_fault c0138900 17282 0.0906796 __free_pages_ok c01a0f90 17160 0.0900395 atomic_dec_and_lock c01a100b 16937 0.0888694 .text.lock.dec_and_lock
Quoted 1 line · Martin J. Bligh
Quoted 1 line
An old compile off 2.5.31-mm1 + extras (I don't have 37, but similar)
Quoted 1 line · William Lee Irwin III
Some 8-quad numbers for 2.5.37 (virgin) follow.
Okay, 2.5.37 virgin with overcommit_memory set to 1 this time. (compiles with -j256 seem to do better than -j32 or -j48, here is -j256):
... will follow up with 2.5.38-mm1 with and without NUMA sched, at least if the arrival rate of releases doesn't exceed the benchtime.
c01053ec 1605553 95.6785 poll_idle c0114a48 7611 0.453556 load_balance c0114ec0 5303 0.316018 scheduler_tick c01422ac 5017 0.298974 page_remove_rmap c01466de 4026 0.239918 .text.lock.file_table c012d5ec 3290 0.196058 do_anonymous_page c0141e48 3211 0.191351 page_add_rmap c012df4c 2920 0.174009 handle_mm_fault c010d6e8 2844 0.16948 timer_interrupt c01547b3 2080 0.123952 .text.lock.namei c0146070 1934 0.115251 get_empty_filp c01a0d2c 1591 0.0948112 __generic_copy_from_user c0111728 1477 0.0880177 smp_apic_timer_interrupt c014633c 1437 0.085634 __fput c01a0ce0 1346 0.0802111 __generic_copy_to_user c0138c24 1249 0.0744307 rmqueue c012e450 1169 0.0696633 vm_enough_memory c012b694 1056 0.0629294 zap_pte_range c0130e08 997 0.0594135 find_get_page c014427c 950 0.0566126 dentry_open c01391d0 949 0.056553 __alloc_pages c0151424 892 0.0531563 link_path_walk c01a0f90 834 0.0496999 atomic_dec_and_lock
Bill,
would you please check the boot messages for the NUMA scheduler before doing the run. Martin sent me an example where he has:
CPU pools : 1
pool 0 :0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
node level 0 : 10pool_delay matrix:
129
which is clearly wrong. In that case we need to fix the cpu-pools setup first.
Regards,
Erich
Quoted 11 lines · William Lee Irwin III
Quoted 1 line · Martin J. Bligh
Quoted 1 line
An old compile off 2.5.31-mm1 + extras (I don't have 37, but similar)
Quoted 1 line · William Lee Irwin III
Some 8-quad numbers for 2.5.37 (virgin) follow.
Okay, 2.5.37 virgin with
overcommit_memoryset to 1 this time. (compiles with -j256 seem to do better than -j32 or -j48, here is -j256):... will follow up with 2.5.38-mm1 with and without NUMA sched, at least if the arrival rate of releases doesn't exceed the benchtime.
Quoted 11 lines
would you please check the boot messages for the NUMA scheduler before doing the run. Martin sent me an example where he has:
CPU pools : 1
pool 0 :0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
node level 0 : 10pool_delaymatrix:
129which is clearly wrong. In that case we need to fix the cpu-pools setup first.
OK, well I hacked this for now:
sched.c somewhere:
- lnode_number[i] = pnode_to_lnode[SAPICID_TO_PNODE(cpu_physical_id(i))];
+ lnode_number[i] = i/4;
Which makes the pools work properly. I think you should just use the cpu_to_node macro here, but the hack will allow us to do some testing.
Results, averaged over 5 kernel compiles:
Before:
Elapsed: 20.82s User: 191.262s System: 59.782s CPU: 1206.4% After:
Elapsed: 21.918s User: 190.224s System: 59.166s CPU: 1137.4%
So you actually take a little less horsepower to do the work, but don't utilize the CPUs quite as well, so elapsed time is higher. I seem to recall getting better results from Mike's quick hack though ... that was a long time back. What were the balancing issues you mentioned?
M.
I tried putting back the current->node logic now that we have the correct node IDs, but it made things worse (not as bad as before, but ... looks like we're still allocing off the wrong node.
This run is the last one in the list.
Virgin:
Elapsed: 20.82s User: 191.262s System: 59.782s CPU: 1206.4%
7059 do_anonymous_page
4459 page_remove_rmap
3863 handle_mm_fault
3695 .text.lock.namei
2912 page_add_rmap
2458 rmqueue
2119 vm_enough_memory
Both numasched patches, just compile fixes:
Elapsed: 28.744s User: 204.62s System: 173.708s CPU: 1315.8%
38978 do_anonymous_page
36533 rmqueue
35099 __free_pages_ok
5551 page_remove_rmap
4694 handle_mm_fault
3166 page_add_rmap
Both numasched patches, alloc from local node
Elapsed: 21.094s User: 195.808s System: 62.41s CPU: 1224.4%
7475 do_anonymous_page
4564 page_remove_rmap
4167 handle_mm_fault
3467 .text.lock.namei
2520 page_add_rmap
2112 rmqueue
1905 .text.lock.dec_and_lock
1849 zap_pte_range
1668 vm_enough_memory
Both numasched patches, hack node IDs, alloc from local node
Elapsed: 21.918s User: 190.224s System: 59.166s CPU: 1137.4%
5793 do_anonymous_page
4475 page_remove_rmap
4281 handle_mm_fault
3820 .text.lock.namei
2625 page_add_rmap
2028 .text.lock.dec_and_lock
1748 vm_enough_memory
1713 file_read_actor
1672 rmqueue
Both numasched patches, hack node IDs, alloc from current->node
Elapsed: 24.414s User: 194.86s System: 98.606s CPU: 1201.6%
30317 do_anonymous_page
6962 rmqueue
5190 page_remove_rmap
4773 handle_mm_fault
3522 .text.lock.namei
3161 page_add_rmap
Quoted 4 lines · Martin J. Bligh
I tried putting back the
current->nodelogic now that we have the correct node IDs, but it made things worse (not as bad as before, but ... looks like we're still allocing off the wrong node.
Thanks a lot for the testing! It looks like something is still wrong. NUMAQ suffers a lot more from hops across the nodes than the Azusa therefore I expect it is more sensitive to initial load balancing errors.
The easiest thing to try is "nodpol -P 2" in the shell before running the test. This changes the initial load balancing policy from exec() to fork() ("nodpol -P 0" gets you back to the default).
A bit more difficult is tuning the scheduler parameters which can be done pretty simply by changing the __node_distance matrix. A first attempt could be: 10 on the diagonal, 100 off-diagonal. This leads to larger delays when stealing from a remote node.
Anyhow, it would be good to understand what is going on and maybe simpler tests than a kernel compile can reveal something. Or looking into at the /proc/sched/load/rqNN files (you need the patch I posted a few mails ago).
I'll modify alloc_pages not to take into acount the kernel threads in the mean time.
Regards,
Erich
Quoted 45 lines
This run is the last one in the list.
Virgin:
Elapsed: 20.82s User: 191.262s System: 59.782s CPU: 1206.4%
7059do_anonymous_page
4459page_remove_rmap
3863handle_mm_fault
3695 .text.lock.namei
2912page_add_rmap
2458 rmqueue
2119vm_enough_memoryBoth numasched patches, just compile fixes:
Elapsed: 28.744s User: 204.62s System: 173.708s CPU: 1315.8%
38978do_anonymous_page
36533 rmqueue
35099__free_pages_ok
5551page_remove_rmap
4694handle_mm_fault
3166page_add_rmapBoth numasched patches, alloc from local node
Elapsed: 21.094s User: 195.808s System: 62.41s CPU: 1224.4%
7475do_anonymous_page
4564page_remove_rmap
4167handle_mm_fault
3467 .text.lock.namei
2520page_add_rmap
2112 rmqueue
1905 .text.lock.dec_and_lock
1849zap_pte_range
1668vm_enough_memoryBoth numasched patches, hack node IDs, alloc from local node
Elapsed: 21.918s User: 190.224s System: 59.166s CPU: 1137.4%
5793do_anonymous_page
4475page_remove_rmap
4281handle_mm_fault
3820 .text.lock.namei
2625page_add_rmap
2028 .text.lock.dec_and_lock
1748vm_enough_memory
1713file_read_actor
1672 rmqueue
Quoted 8 lines
Both numasched patches, hack node IDs, alloc from
current->node
Elapsed: 24.414s User: 194.86s System: 98.606s CPU: 1201.6%
30317do_anonymous_page
6962 rmqueue
5190page_remove_rmap
4773handle_mm_fault
3522 .text.lock.namei
3161page_add_rmap
/*-------------------------------------------------------------------------
Read and set the homenode and the node_policy used for node affine scheduling.
(c) Erich Focht <[email protected]>
$Id:$
$Revision:$
$Log:$
-------------------------------------------------------------------------*/
#include <linux/config.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
#include <errno.h>
#include <pwd.h>
#include <sys/prctl.h>
#include <string.h>
static char VersionString[] = "$Revision:$";
void usage(char *exe)
{
printf("Usage: %s [-n] [-N node] [-p] [-P policy] [pid]\n",
exe);
printf(" -n : get preferred node for process pid\n");
printf(" -N : set preferred node for process pid\n");
printf(" -p : get scheduler node_policy for process pid\n");
printf(" -P : set scheduler node_policy for process pid\n");
printf(" pid : process ID of targetted process (default: parent)\n");
printf("\n%s\n\n",VersionString);
}#define MAXPIDS 256
int main(int argc,char *argv[])
{
int ierr=0, pid[MAXPIDS], policy, numpids=0, i;
int result;
extern char *optarg;
extern int optind;
int c;
int getpol=0, getnod=0, setnod=0, setpol=0, help=0, node;
// set PID to parent process ID of current process, this is what we
// usually mean to change
pid[numpids++]=getppid();
// parse options
while (( c = getopt(argc, argv, "nN:pP:h")) != EOF ) {
switch( c ) {
case 'n': /* get task->node value */
getnod=1;
break;
case 'N': /* set task->node value */
setnod=1;
sscanf(optarg,"%d",&node);
break;
case 'p': /* get task->node_policy value */
getpol=1;
break;
case 'P': /* set task->node_policy value */
setpol=1;
sscanf(optarg,"%d",&policy);
break;
case 'h':
help=1;
break;
default:
printf("Unknown option %s\n",optarg);
}
}
if (optind<argc) numpids=0;
while (optind<argc && numpids<MAXPIDS-1)
sscanf(argv[optind++],"%d",&pid[numpids++]);
if (help) {
usage(argv[0]);
exit(0);
}
if (getnod)
printf("pid \t node\n");
if (getpol)
printf("pid \t policy\n");
for (i=0;i<numpids;i++) {
if (getnod)
if((ierr = prctl(PR_GET_NODE,&result,pid[i])) == 0)
printf("%d\t%d\n",pid[i],result);
if (setnod)
ierr = prctl(PR_SET_NODE,(int)node,pid[i]);
if (getpol)
if((ierr = prctl(PR_GET_NODPOL,&result,pid[i])) == 0)
printf("%d\t%d\n",pid[i],result);
if (setpol)
ierr = prctl(PR_SET_NODPOL,(int)policy,pid[i]);
}
exit(ierr);
} Quoted 4 lines · Erich Focht
A bit more difficult is tuning the scheduler parameters which can be done pretty simply by changing the
__node_distancematrix. A first attempt could be: 10 on the diagonal, 100 off-diagonal. This leads to larger delays when stealing from a remote node.
This is not entirely reflective of our architecture. Node-to-node latencies vary as well. Some notion of whether communication must cross a lash at the very least should be present.
Cheers,
Bill
Quoted 9 lines · Erich Focht
Quoted 4 lines
A bit more difficult is tuning the scheduler parameters which can be done pretty simply by changing the
__node_distancematrix. A first attempt could be: 10 on the diagonal, 100 off-diagonal. This leads to larger delays when stealing from a remote node.This is not entirely reflective of our architecture. Node-to-node latencies vary as well. Some notion of whether communication must cross a lash at the very least should be present.
Ummm ... I think it's just flat on or off node, presumably Erich has "on the diagonal" meaning they're on the same node, and "off-diagonal" meaning they're not. In which case, what he suggested seems fine ... it's really about 20:1 ratio so I might use 10 and 200, but other than that, it seems correct to me.
M.
node affine NUMA scheduler: simple benchmark
In reply to Martin J. BlighHere is a simple benchmark which is NUMA sensitive and simulates a simple but normal situation in an environment running number crunching jobs. It starts N independent tasks which access a large array in a random manner. This is both bandwidth and latency sensitive. The output shows on which node(s) the tasks have spent their lives. Additionally it shows (on a NUMA scheduler kernel) the homenode (iSched).
Could you please run it on the virgin kernel and on the "Both numasched patches, hack node IDs, alloc from current->node" one?
Maybe we see what's wrong...
Thanks,
Erich
Quoted 11 lines · Martin J. Bligh
Quoted 5 lines
Hmmm .... well I ran the One True Benchmark (tm). The patch *increased* my kernel compile time from about 20s to about 28s. Not sure I like that idea ;-) Anything you'd like tweaked, or more info? Both user and system time were up ... I'll grab a profile of kernel stuff.
From the below, I'd suggest you're getting pages off the wrong
nodes:do_anonymous_pageis page zeroing, and rmqueue the buddy allocator. Are you sure thecurrent->nodething is getting set correctly? I'll try backing out youralloc_pagestweaking, and see what happens.
Could you please check in dmesg whether the CPU pools are initialised correctly? Maybe something goes wrong for your platform.
The node_distance is most probably non-optimal for NUMAQ, that might need some tuning. The default is set for maximum 8 nodes, nodes 1-4 and 5-8 being in separate supernodes, with the latency ratios 1:1.5:2.
You could use the attached patch for getting an idea about the load distribution. It's a quick&dirty hack which creates files called /proc/sched/load/rqNN :load of RQs, including info on tasks not running
on their homenode/proc/sched/history/ilbNN : history of last 25 initial load balancing
decisions for runqueue NN/proc/sched/history/lbNN : last 25 load balancing decisions on rq NN.
It should be possible to find the reason for the poor performance by looking at the nr_homenode entries in /proc/sched/load/rqNN.
Thanks,
best regards,
Erich
kernel/sched.c +176 -4
@@ -677,6 +677,175 @@ static inline unsigned int double_lock_breturn nr_running; } +#define HISTORY_RING_SIZE 25 +/* load balancing history entry */ +struct lb_hist_entry { +unsigned long time;/* jiffy */ +int pid;/* stolen task (0 if none) */ +int busiest_cpu;/* busiest RQ */ +}; +/* load balancing history ring */ +struct lb_hist_ring { +int curr;/* current pointer */ +struct lb_hist_entry data[HISTORY_RING_SIZE ]; +}____cacheline_aligned ; +/* per CPU history ring array */ +struct lb_hist_ring lb_ring[NR_CPUS ]; + +/* initial load balancing decision entry */ +struct ilb_hist_entry { +unsigned long time;/* jiffy */ +int pid; +int node;/* selected homenode */ +int load[NR_NODES ];/* node loads at decision time */ +}; +/* initial load balancing history ring */ +struct ilb_hist_ring { +int curr;/* current pointer */ +struct ilb_hist_entry data[HISTORY_RING_SIZE ]; +}____cacheline_aligned ; +/* per CPU history ring array */ +struct ilb_hist_ring ilb_ring[NR_CPUS ]; + +/* add entry to lb_ring */ +void lb_ring_add (int cpu,int pid,int busiest_cpu) +{ +int next=(lb_ring[cpu].curr +1 ) %HISTORY_RING_SIZE ; + + lb_ring[cpu].data[next].time = jiffies; + lb_ring[cpu].data[next].pid = pid; + lb_ring[cpu].data[next].busiest_cpu = busiest_cpu; + lb_ring[cpu].curr = next; +} + +/* add entry to ilb_ring */ +void ilb_ring_add (int cpu,int pid,int node,int *load) +{ +int i, next=(ilb_ring[cpu].curr +1 ) %HISTORY_RING_SIZE ; + + ilb_ring[cpu].data[next].time = jiffies; + ilb_ring[cpu].data[next].pid = pid; + ilb_ring[cpu].data[next].node = node; +for (i=0 ; i<numpools; i++) + ilb_ring[cpu].data[next].load[i] = load[i]; + ilb_ring[cpu].curr = next; +} + +/* print lb history ring buffer */ +int lb_ring_read_proc (char *page,char **start,off_t off, +int count,int *eof,void *data) +{ +int i, len, entry; +char *buff=page; +int cpu=(int )data; + + buff +=sprintf (buff," tick pid from_cpu\n" ); + entry = lb_ring[cpu].curr; +for (i=0 ; i<HISTORY_RING_SIZE ; i++) { + entry = (entry +1 ) %HISTORY_RING_SIZE ; + buff +=sprintf (buff,"%12ld %6d %2d\n" , + lb_ring[cpu].data[entry].time, + lb_ring[cpu].data[entry].pid, + lb_ring[cpu].data[entry].busiest_cpu); + } + len = buff-page; +if (len <= off+count) *eof =1 ; + len -= off; +if (len>count) len = count; +if (len<0 ) len =0 ; +return len; +} + +/* print initial lb history ring buffer */ +int ilb_ring_read_proc (char *page,char **start,off_t off, +int count,int *eof,void *data) +{ +int i, j, len, entry; +char *buff=page; +int cpu=(int )data; + + buff +=sprintf (buff," tick pid node node_loads\n" ); + entry = ilb_ring[cpu].curr; +for (i=0 ; i<HISTORY_RING_SIZE ; i++) { + entry = (entry +1 ) %HISTORY_RING_SIZE ; + buff +=sprintf (buff,"%12ld %6d %2d" , + ilb_ring[cpu].data[entry].time, + ilb_ring[cpu].data[entry].pid, + ilb_ring[cpu].data[entry].node); +for (j=0 ; j<numpools; j++) + buff +=sprintf (buff," %3d" , + ilb_ring[cpu].data[entry].load[j]); + buff +=sprintf (buff,"\n" ); + } + len = buff-page; +if (len <= off+count) *eof =1 ; + len -= off; +if (len>count) len = count; +if (len<0 ) len =0 ; +return len; +} + +/* print runqueue load */ +int rq_load_read_proc (char *page,char **start,off_t off, +int count,int *eof,void *data) +{ +int i, len; +runqueue_t *rq; +char *buff=page; +int cpu=(int )data; + + rq=cpu_rq (cpu); + buff +=sprintf (buff,"cpu %d : " ,cpu); + buff +=sprintf (buff,"curr: %d %s\n" ,rq->curr->pid,rq->curr->comm); + buff +=sprintf (buff,"running uninter nr_homenode\n" ); + buff +=sprintf (buff,"%7d %7d" ,rq->nr_running,rq->nr_uninterruptible); +for (i=0 ; i<numpools; i++) + buff +=sprintf (buff," %4d" ,rq->nr_homenode[i]); + buff +=sprintf (buff,"\n" ); + + len = buff-page; +if (len <= off+count) *eof =1 ; + len -= off; +if (len>count) len = count; +if (len<0 ) len =0 ; +return len; +} + +#include <linux/proc_fs.h> +/* initialize /proc entries */ +void init_sched_proc (void ) +{ +int i; +char name[12 ]; +struct proc_dir_entry *p, *hist, *sched, *load; + + sched =proc_mkdir ("sched" ,&proc_root); + hist =proc_mkdir ("history" ,sched); +for (i=0 ; i<smp_num_cpus; i++) { +sprintf (name,"lb%02d" ,i); + p =create_proc_entry (name,S_IRUGO ,hist); +if (p) { + p->read_proc = lb_ring_read_proc; + p->data = (long )i; + } +sprintf (name,"ilb%02d" ,i); + p =create_proc_entry (name,S_IRUGO ,hist); +if (p) { + p->read_proc = ilb_ring_read_proc; + p->data = (long )i; + } + } + load =proc_mkdir ("load" ,sched); +for (i=0 ; i<smp_num_cpus; i++) { +sprintf (name,"rq%02d" ,i); + p =create_proc_entry (name,S_IRUGO ,load); +if (p) { + p->read_proc = rq_load_read_proc; + p->data = (long )i; + } + } +} +/* * Calculate load of a CPU pool, store results in data[][NR_CPUS]. * Return the index of the most loaded runqueue.
@@ -961,6 +1130,7 @@ static void load_balance(runqueue_t *thi tmp =task_to_steal (busiest, this_cpu);if (!tmp) goto out_unlock; +lb_ring_add (smp_processor_id (), tmp->pid, tmp->thread_info->cpu);pull_task (busiest, tmp->array, tmp, this_rq, this_cpu); out_unlock:spin_unlock (&busiest->lock);
@@ -2051,7 +2221,7 @@ static int sched_best_cpu(struct task_st*/ static int sched_best_node (struct task_struct *p,int flag) { -int n, best_node=0 , min_load, pool_load, min_pool=p->node; +int n, best_node=0 , min_load, min_pool=p->node;int pool, load[NR_NODES ];unsigned long mask = p->cpus_allowed & cpu_online_map;
@@ -2079,13 +2249,14 @@ static int sched_best_node(struct task_s min_load =100000000 ;for (n =0 ; n < numpools; n++) { pool = (best_node + n) % numpools; - pool_load = (100 *load[pool])/pool_nr_cpus[pool]; -if ((pool_load < min_load) && (pool_mask[pool] & mask)) { - min_load = pool_load; + load[pool] = (100 *load[pool])/pool_nr_cpus[pool]; +if ((load[pool] < min_load) && (pool_mask[pool] & mask)) { + min_load = load[pool]; min_pool = pool; } }atomic_set (&sched_node, min_pool); +ilb_ring_add (smp_processor_id (), p->pid, min_pool, load);return min_pool; }
@@ -2282,6 +2453,7 @@ void bld_pools(void)find_node_levels (numpools);init_pool_weight ();init_pool_delay (); +init_sched_proc (); }void set_task_node (task_t *p,int node)
Quoted 2 lines · Martin J. Bligh
Quoted 2 lines
- Each process has a homenode assigned to it at creation time (initial load balancing). Memory will be allocated from this node.
...
Quoted 8 lines
#ifdef
CONFIG_NUMAinclude/linux/sched.h +4
-0+#ifdef CONFIG_NUMA_SCHED +#define numa_node_id () (current->node) +#else #define numa_node_id () _cpu_to_node(smp_processor_id()) +#endif #endif /* CONFIG_NUMA */
Quoted 5 lines
I'm not convinced it's a good idea to modify this generic function, which was meant to tell you what node you're running on. I can't see it being used anywhere else right now, but wouldn't it be better to just modify
alloc_pagesinstead to usecurrent->node, and leave this macro as intended? Or make aprocess_node_idor something?
OK, I see your point and I agree that numa_node_is() should be similar to smp_processor_id(). I'll change the alloc_pages instead.
Do you think it makes sense to get memory from the homenode only for user processes? Many kernel threads have currently the wrong homenode, for some of them it's unclear which homenode they should have...
There is an alternative idea (we discussed this at OLS with Andrea, maybe you remember): allocate memory from the current node and keep statistics on where it is allocated. Determine the homenode from this (from time to time) and schedule accordingly. This eliminates the initial load balancing and leaves it all to the scheduler, but has the drawback that memory can be somewhat scattered across the nodes. Any comments?
Regards,
Erich
Quoted 6 lines
OK, I see your point and I agree that
numa_node_is()should be similar tosmp_processor_id(). I'll change thealloc_pagesinstead.Do you think it makes sense to get memory from the homenode only for user processes? Many kernel threads have currently the wrong homenode, for some of them it's unclear which homenode they should have...
Well yes ... if you can keep things pretty much on their home nodes. That means some sort of algorithm for updating it, which may be fairly complex (and doesn't currently seem to work, but maybe that's just because I only have 1 pool)
Quoted 6 lines
There is an alternative idea (we discussed this at OLS with Andrea, maybe you remember): allocate memory from the current node and keep statistics on where it is allocated. Determine the homenode from this (from time to time) and schedule accordingly. This eliminates the initial load balancing and leaves it all to the scheduler, but has the drawback that memory can be somewhat scattered across the nodes. Any comments?
Well, that's a lot simpler. Things should end up running on their home node, and thus will allocate pages from their home node, so it should be self-re-enforcing. The algorithm for the home node is then implicitly worked out from the scheduler itself, and its actions, so it's one less set of stuff to write. Would suggest we do this at first, to keep things as simple as possible so you have something mergeable.
M.
Quoted 7 lines · Martin J. Bligh
Quoted 6 lines
There is an alternative idea (we discussed this at OLS with Andrea, maybe you remember): allocate memory from the current node and keep statistics on where it is allocated. Determine the homenode from this (from time to time) and schedule accordingly. This eliminates the initial load balancing and leaves it all to the scheduler, but has the drawback that memory can be somewhat scattered across the nodes. Any comments?
Quoted 6 lines
Well, that's a lot simpler. Things should end up running on their home node, and thus will allocate pages from their home node, so it should be self-re-enforcing. The algorithm for the home node is then implicitly worked out from the scheduler itself, and its actions, so it's one less set of stuff to write. Would suggest we do this at first, to keep things as simple as possible so you have something mergeable.
OK, sounds encouraging. So here is my first attempt (attached). You'll have to apply it on top of the two NUMA scheduler patches and hack SAPICID_TO_PNODE again.
The patch adds a node_mem[NR_NODES] array to each task. When allocating memory (in rmqueue) and freeing it (in free_pages_ok) the number of pages is added/subtracted from that array and the homenode is set to the node having the largest entry. Is there a better place where to put this in (other than rmqueue/free_pages_ok)?
I have two problems with this approach:
1: Freeing memory is quite expensive, as it currently involves finding the maximum of the array node_mem[].
2: I have no idea how tasks sharing the mm structure will behave. I'd like them to run on different nodes (that's why node_mem is not in mm), but they could (legally) free pages which they did not allocate and have wrong values in node_mem[].
Comments?
Regards,
Erich
fs/exec.c +0 -3
@@ -995,9 +995,6 @@ int do_execve(char * filename, char ** aint retval;int i; -if (current->node_policy ==NODPOL_EXEC ) -sched_balance_exec (); - file =open_exec (filename); retval =PTR_ERR (file);
include/asm-i386/mmzone.h +0 -4
@@ -20,11 +20,7 @@#endif /* CONFIG_X86_NUMAQ */ #ifdef CONFIG_NUMA -#ifdef CONFIG_NUMA_SCHED -#define numa_node_id () (current->node) -#else #define numa_node_id () _cpu_to_node(smp_processor_id()) -#endif #endif /* CONFIG_NUMA */ extern struct pglist_data *node_data[];
include/linux/prctl.h +0 -2
@@ -37,7 +37,5 @@/* Get/set node for node-affine scheduling */ #define PR_GET_NODE 16#define PR_SET_NODE 17 -#define PR_GET_NODPOL 18 -#define PR_SET_NODPOL 19#endif /* _LINUX_PRCTL_H */
include/linux/sched.h +5 -5
@@ -160,13 +160,13 @@ extern void update_one_process(struct taextern void scheduler_tick (int user_tick,int system);extern unsigned long cache_decay_ticks;#ifdef CONFIG_NUMA_SCHED -extern void sched_balance_exec (void ); -extern void sched_balance_fork (task_t *p);extern void set_task_node (task_t *p,int node); +extern void inc_node_mem (int node,int blocks); +extern void dec_node_mem (int node,int blocks);#else -#define sched_balance_exec () {} -#define sched_balance_fork (p) {}#define set_task_node (p,n) {} +#define inc_node_mem (node,blocks) {} +#define dec_node_mem (node,blocks) {}#endif extern void sched_migrate_task (task_t *p,int cpu);
@@ -303,7 +303,7 @@ struct task_struct {unsigned long cpus_allowed;unsigned int time_slice, first_time_slice;int node; -int node_policy; +int node_mem[NR_NODES ];struct list_head tasks;struct list_head ptrace_children;
kernel/fork.c +0 -3
@@ -701,9 +701,6 @@ static struct task_struct *copy_process(#ifdef CONFIG_SMP {int i; -if (p->node_policy ==NODPOL_FORK_ALL || - (p->node_policy ==NODPOL_FORK && !(clone_flags &CLONE_VM ))) -sched_balance_fork (p);/* ?? should we just memset this ?? */ for (i =0 ; i <NR_CPUS ; i++)
kernel/sched.c +42 -86
145 lines not on this page · raw message
kernel/sys.c +0 -28
@@ -1400,34 +1400,6 @@ asmlinkage long sys_prctl(int option, unread_unlock (&tasklist_lock);break ; -case PR_GET_NODPOL : - pid = (int ) arg3; -read_lock (&tasklist_lock); - child =find_task_by_pid (pid); -if (child) { - error =put_user (child->node_policy,(int *)arg2); - }else { -printk ("prctl: could not find pid %d\n" ,pid); - error = -EINVAL ; - } -read_unlock (&tasklist_lock); -break ; -case PR_SET_NODPOL : - pid = (int ) arg3; -read_lock (&tasklist_lock); - child =find_task_by_pid (pid); -if (child) { -if (child->uid == current->uid || \ - current->uid ==0 ) { -printk ("setting node policy of process %d to %d\n" ,pid,(int )arg2); - child->node_policy = (int ) arg2; - } - }else { -printk ("prctl: could not find pid %d\n" ,pid); - error = -EINVAL ; - } -read_unlock (&tasklist_lock); -break ;default : error = -EINVAL ;break ;
mm/page_alloc.c +2 -0
@@ -146,6 +146,7 @@ void __free_pages_ok (struct page *page, }list_add (&(base + page_idx)->list, &area->free_list);spin_unlock_irqrestore (&zone->lock, flags); +dec_node_mem (zone->zone_pgdat->node_id,1 <<order); out:return ; }
@@ -222,6 +223,7 @@ static struct page *rmqueue(struct zoneif (bad_range (zone, page))BUG ();prep_new_page (page); +inc_node_mem (zone->zone_pgdat->node_id,1 <<order);return page; } curr_order++;
Quoted 10 lines
OK, sounds encouraging. So here is my first attempt (attached). You'll have to apply it on top of the two NUMA scheduler patches and hack
SAPICID_TO_PNODEagain.The patch adds a node_mem[NR_NODES] array to each task. When allocating memory (in rmqueue) and freeing it (in
free_pages_ok) the number of pages is added/subtracted from that array and the homenode is set to the node having the largest entry. Is there a better place where to put this in (other than rmqueue/free_pages_ok)?
Quoted 3 lines
I have two problems with this approach:
1: Freeing memory is quite expensive, as it currently involves finding the maximum of the array node_mem[].
Bleh ... why? This needs to be calculated much more lazily than this, or you're going to kick the hell out of any cache affinity. Can you recalc this in the rebalance code or something instead?
Quoted 4 lines
2: I have no idea how tasks sharing the mm structure will behave. I'd like them to run on different nodes (that's why
node_memis not in mm), but they could (legally) free pages which they did not allocate and have wrong values in node_mem[].
Yes, that really ought to be per-process, not per task. Which means locking or atomics ... and overhead. Ick.
For the first cut of the NUMA sched, maybe you could just leave page allocation alone, and do that seperately? or is that what the second patch was meant to be?
M.
Quoted 7 lines · Martin J. Bligh
Quoted 3 lines
I have two problems with this approach:
1: Freeing memory is quite expensive, as it currently involves finding the maximum of the array node_mem[].Bleh ... why? This needs to be calculated much more lazily than this, or you're going to kick the hell out of any cache affinity. Can you recalc this in the rebalance code or something instead?
You're right, that would be too slow. I think of marking the tasks needing recalculation and update their homenode when their runqueue is scanned for a task to be stolen.
Quoted 7 lines
Quoted 4 lines
2: I have no idea how tasks sharing the mm structure will behave. I'd like them to run on different nodes (that's why
node_memis not in mm), but they could (legally) free pages which they did not allocate and have wrong values in node_mem[].Yes, that really ought to be per-process, not per task. Which means locking or atomics ... and overhead. Ick.
Hmm, I think it is sometimes ok to have it per task. For example OpenMP parallel jobs working on huge arrays. The "first-touch" of these arrays leads to pagefaults generated by the different tasks and thus different node_mem[] arrays for each task. As long as they just allocate memory, all is well. If they only release it at the end of the job, too. This probably goes wrong if we have a long running task that spawns short living clones. They inherit the node_mem from the parent but pages added by them to the common mm are not reflected in the parent's node_mem after their death.
Quoted 3 lines
For the first cut of the NUMA sched, maybe you could just leave page allocation alone, and do that seperately? or is that what the second patch was meant to be?
The first patch needs a correction, add in load_balance()
if (!busiest) goto out;
after the call to find_busiest_queue. This works alone. On top of this pooling NUMA scheduler we can put the node affinity approach that fits best. With or without memory allocation. I'll update the patches and their setup code (thanks for the comments!) and resend them.
Regards,
Erich
Quoted 8 lines
Quoted 7 lines
Quoted 4 lines
2: I have no idea how tasks sharing the mm structure will behave. I'd like them to run on different nodes (that's why
node_memis not in mm), but they could (legally) free pages which they did not allocate and have wrong values in node_mem[].Yes, that really ought to be per-process, not per task. Which means locking or atomics ... and overhead. Ick.
Quoted 9 lines
Hmm, I think it is sometimes ok to have it per task. For example OpenMP parallel jobs working on huge arrays. The "first-touch" of these arrays leads to pagefaults generated by the different tasks and thus different node_mem[] arrays for each task. As long as they just allocate memory, all is well. If they only release it at the end of the job, too. This probably goes wrong if we have a long running task that spawns short living clones. They inherit the
node_memfrom the parent but pages added by them to the common mm are not reflected in the parent'snode_memafter their death.
But you're left with a choice whether to base it on the per-task or per-process information when you make decisions.
1. per-process requires cross-node collation for a data read. Bad.
2. per-task leads to obviously bad decision cases when there's significant amounts of shared data between the tasks of a process (which was often the point of making them threads in the first place).
Yes, I can imagine a situation for which it would work, as you describe above ... but that's not the point - this is a general policy, and I don't think it works in general ... as you say yourself "it is *sometimes* ok" ;-)
Quoted 6 lines
The first patch needs a correction, add in
load_balance()if (!busiest) goto out;after the call to
find_busiest_queue. This works alone. On top of this pooling NUMA scheduler we can put the node affinity approach that fits best. With or without memory allocation. I'll update the patches and their setup code (thanks for the comments!) and resend them.
Excellent! Will try out the correction above and get back to you. Might be a day or so, I'm embroiled in some other code at the moment.
M.
A few comments ... mainly just i386 arch things (which aren't really your fault, was just a lack of the mechanisms being in mainline), and a request to push a couple of things down into the arch trees from rearing their ugly head into generic code ;-)
M.
arch/i386/kernel/smpboot.c static int __init wakeup_secondary_via_I · line 769
Quoted 2 lines
arch/i386/kernel/smpboot.c +2
-0+static int __initdata nr_lnodes =0 ; +
Use numnodes.
arch/i386/kernel/smpboot.c static void __init do_boot_cpu (int apic · line 788
Quoted 7 lines
arch/i386/kernel/smpboot.c +6
-0cpu = ++cpucount; +#ifdef CONFIG_NUMA_SCHED + cell =SAPICID_TO_PNODE (apicid); +if (pnode_to_lnode[cell] <0 ) { + pnode_to_lnode[cell] = nr_lnodes++; + } +#endif
pnodes and lnodes are all 1-1, so they're just called nodes for i386, and there's no such thing as a SAPICID on this platform.
arch/i386/kernel/smpboot.c static void __init smp_boot_cpus(unsigne · line 1010
Quoted 11 lines
arch/i386/kernel/smpboot.c +4
-0/* * We can't use kernel_thread since we must avoid to * reschedule the child. @@ -996,6 +1004,10 @@ static void __init smp_boot_cpus(unsigneset_bit (0 , &cpu_callout_map); boot_cpu_logical_apicid =logical_smp_processor_id ();map_cpu_to_boot_apicid (0 , boot_cpu_apicid); +#ifdef CONFIG_NUMA_SCHED + pnode_to_lnode[SAPICID_TO_PNODE (boot_cpu_apicid)] = nr_lnodes++; +printk ("boot_cpu_apicid = %d, nr_lnodes = %d, lnode = %d\n" , boot_cpu_apicid, nr_lnodes, pnode_to_lnode[0 ]); +#endif
Ditto. All these mappings exist already. No need to reinvent them. The -mm tree has a generic cpu_to_node macro, which keys off the logical_apic_id.
http://www.zipworld.com.au/~akpm/linux/patches/2.5/2.5.37/2.5.37-mm1/broken-out/topology-api.patch
Review static void __init smp_boot_cpus(unsigne · line 1012
Quoted 2 lines
(quoted diff) +2
-0+#ifdef CONFIG_NUMA_SCHED +#define NR_NODES 8
MAX_NUMNODES exists for every arch (except maybe ia64 ;-))
include/asm-i386/smp.h static inline int num_booting_cpus(void) · line 129
Quoted 1 line
include/asm-i386/smp.h +1
-0+#define cpu_physical_id (cpuid) (cpu_to_physical_apicid(cpuid))
Not needed, should be buried within a wrapper, not exposed to generic code.
Quoted 1 line
+#define
SAPICID_TO_PNODE(hwid)(hwid >> 4)
Grrr. No such thing.
include/linux/sched.h extern void set_cpus_allowed(task_t *p, · line 482
Quoted 4 lines
diff -urNp
a/include/linux/sched.hb/include/linux/sched.hinclude/linux/sched.h +2
-0+extern int pnode_to_lnode[NR_NODES ]; +extern char lnode_number[NR_CPUS] __cacheline_aligned;
Can't you push all this down into the arch ....
Quoted 1 line
+#define
CPU_TO_NODE(cpu)lnode_number[cpu]
... by letting them define cpu_to_node() themselves? (most people don't have lnodes and pnodes, etc).
kernel/ksyms.c EXPORT_SYMBOL(init_task); · line 618
Quoted 7 lines
kernel/ksyms.c +7
-0+EXPORT_SYMBOL (runqueues_address); +EXPORT_SYMBOL (numpools); +EXPORT_SYMBOL (pool_ptr); +EXPORT_SYMBOL (pool_cpus); +EXPORT_SYMBOL (pool_nr_cpus); +EXPORT_SYMBOL (pool_mask); +EXPORT_SYMBOL (sched_migrate_task);
Aren't these internal scheduler things?
kernel/sched.c static struct runqueue runqueues[NR_CPUS · line 207
Quoted 4 lines
diff -urNp
a/kernel/sched.cb/kernel/sched.ckernel/sched.c +2
-0+int pnode_to_lnode[NR_NODES ] = { [0 ...NR_NODES -1 ] =-1 }; +char lnode_number[NR_CPUS] __cacheline_aligned;
Ditto.
Review
Quoted 2 lines
(quoted diff) +2
-0+ int this_pool = CPU_TO_NODE(this_cpu); + int this_pool=CPU_TO_NODE(this_cpu), weight, maxweight=0;
Howcome you can use the CPU_TO_NODE abstraction here ...
kernel/sched.c void show_state(void) · line 2115
Quoted 4 lines
kernel/sched.c +4
-0+/* build translation table for CPU_TO_NODE macro */ +for (i =0 ; i <NR_CPUS ; i++) +if (cpu_online (i)) + lnode_number[i] = pnode_to_lnode[SAPICID_TO_PNODE (cpu_physical_id (i))];
But not here?
Quoted 11 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ int this_pool = CPU_TO_NODE(this_cpu); + int this_pool=CPU_TO_NODE(this_cpu), weight, maxweight=0;Howcome you can use the
CPU_TO_NODEabstraction here ...kernel/sched.c void show_state(void) · line 2115
Quoted 4 lines
kernel/sched.c +4
-0+/* build translation table for CPU_TO_NODE macro */ +for (i =0 ; i <NR_CPUS ; i++) +if (cpu_online (i)) + lnode_number[i] = pnode_to_lnode[SAPICID_TO_PNODE (cpu_physical_id (i))];But not here?
Doh! Because you're building the list to use for CPU_TO_NODE, obviously ;-) Sorry.
Should still get buried back down into the arch code though.
M.
Quoted 4 lines · Martin J. Bligh
A few comments ... mainly just i386 arch things (which aren't really your fault, was just a lack of the mechanisms being in mainline), and a request to push a couple of things down into the arch trees from rearing their ugly head into generic code ;-)
<SNIP>
Quoted 9 lines
include/linux/sched.h extern void set_cpus_allowed(task_t *p, · line 482
Quoted 2 lines
include/linux/sched.h +2
-0+extern int pnode_to_lnode[NR_NODES ]; +extern char lnode_number[NR_CPUS] __cacheline_aligned;Can't you push all this down into the arch ....
Quoted 1 line
+#define
CPU_TO_NODE(cpu)lnode_number[cpu]... by letting them define
cpu_to_node()themselves? (most people don't have lnodes and pnodes, etc).
Yep... Sorry to get into the thread late, but Erich, you should really look at the latest in-kernel topology API stuff in the mm tree. I'd be happy to discuss it with you over email... Plus, I'd get another user of the topology (to help push it into mainline) and ia64 support, and you'd get a generic topology mechanism that works (err, will work?) for all architectures. Email me for more info, or just check out the patch that Martin pointed to! :)
Cheers!
-Matt