Skip to contentSkip to conversation

node affine NUMA scheduler

PATCH In review Erich Focht 4 participants 27 messages Sep 21, 2002 – Sep 24, 2002

Subsystems (7)
lore
Share & tools
lore
#0 lore raw

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
diff -urNp a/arch/i386/config.in b/arch/i386/config.in
@@ -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
diff -urNp a/arch/i386/kernel/smpboot.c b/arch/i386/kernel/smpboot.c
@@ -765,6 +765,8 @@ static int __init wakeup_secondary_via_I
 
 extern 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(unsigne
 	set_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
diff -urNp a/arch/ia64/config.in b/arch/ia64/config.in
@@ -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
diff -urNp a/arch/ia64/kernel/smpboot.c b/arch/ia64/kernel/smpboot.c
@@ -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;	/* # of
 static 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
diff -urNp a/include/asm-i386/atomic.h b/include/asm-i386/atomic.h
@@ -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
diff -urNp a/include/asm-i386/smp.h b/include/asm-i386/smp.h
@@ -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
diff -urNp a/include/asm-ia64/smp.h b/include/asm-ia64/smp.h
@@ -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
diff -urNp a/kernel/ksyms.c b/kernel/ksyms.c
@@ -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

#1 lore raw

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
diff -urNp a/arch/i386/config.in b/arch/i386/config.in
@@ -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
diff -urNp a/arch/ia64/config.in b/arch/ia64/config.in
@@ -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
diff -urNp a/fs/exec.c b/fs/exec.c
@@ -995,6 +995,9 @@ int do_execve(char * filename, char ** a
 	int 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
diff -urNp a/include/asm-i386/mmzone.h b/include/asm-i386/mmzone.h
@@ -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
diff -urNp a/include/linux/prctl.h b/include/linux/prctl.h
@@ -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
diff -urNp a/include/linux/sched.h b/include/linux/sched.h
@@ -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] __cach
 
 extern 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
diff -urNp a/kernel/fork.c b/kernel/fork.c
@@ -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
diff -urNp a/kernel/softirq.c b/kernel/softirq.c
@@ -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

#2 lore raw
In reply to Erich Focht
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.

#3 lore raw
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.

#4 lore raw
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

#5 lore raw
Quoted 5 lines

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.

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

#6 lore raw

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_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.

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
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

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
#7 lore raw
Quoted 4 lines · Erich Focht

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...

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

#8 lore raw
In reply to Martin J. Bligh
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
#9 lore raw
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
#10 lore raw

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 : 10
pool_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_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.

#11 lore raw
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 : 10
pool_delay matrix:
129

which 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.

#12 lore raw

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

#13 lore raw
Quoted 4 lines · Martin J. Bligh

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.

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%
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

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%
30317 do_anonymous_page
6962 rmqueue
5190 page_remove_rmap
4773 handle_mm_fault
3522 .text.lock.namei
3161 page_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);
}				
#14 lore raw
Quoted 4 lines · Erich Focht

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.

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

#15 lore raw
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_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.

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.

#16 lore raw

node affine NUMA scheduler: simple benchmark

In reply to Martin J. Bligh

Here 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

#17 lore raw
In reply to Martin J. Bligh
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_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.

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
diff -urNp 2.5.37-node-affine/kernel/sched.c 2.5.37-node-affine-mon/kernel/sched.c
@@ -677,6 +677,175 @@ static inline unsigned int double_lock_b
 	return 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)
#18 lore raw
In reply to Martin J. Bligh
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_NUMA

include/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_pages instead to use current->node, and leave this macro as intended? Or make a process_node_id or 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

#19 lore raw
Quoted 6 lines

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...

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.

#20 lore raw
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
diff -urNp 2.5.37-node-affine/fs/exec.c 2.5.37-node-affine-v2/fs/exec.c
@@ -995,9 +995,6 @@ int do_execve(char * filename, char ** a
 	int 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
diff -urNp 2.5.37-node-affine/include/asm-i386/mmzone.h 2.5.37-node-affine-v2/include/asm-i386/mmzone.h
@@ -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
diff -urNp 2.5.37-node-affine/include/linux/prctl.h 2.5.37-node-affine-v2/include/linux/prctl.h
@@ -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
diff -urNp 2.5.37-node-affine/include/linux/sched.h 2.5.37-node-affine-v2/include/linux/sched.h
@@ -160,13 +160,13 @@ extern void update_one_process(struct ta
 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);
+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
diff -urNp 2.5.37-node-affine/kernel/fork.c 2.5.37-node-affine-v2/kernel/fork.c
@@ -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
diff -urNp 2.5.37-node-affine/kernel/sys.c 2.5.37-node-affine-v2/kernel/sys.c
@@ -1400,34 +1400,6 @@ asmlinkage long sys_prctl(int option, un
 			read_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
diff -urNp 2.5.37-node-affine/mm/page_alloc.c 2.5.37-node-affine-v2/mm/page_alloc.c
@@ -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 zone 
 			if (bad_range(zone, page))
 				BUG();
 			prep_new_page(page);
+			inc_node_mem(zone->zone_pgdat->node_id, 1<<order);
 			return page;	
 		}
 		curr_order++;
#21 lore raw
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_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)?

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_mem is 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.

#22 lore raw
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_mem is 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

#23 lore raw
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_mem is 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_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.

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.

#24 lore raw
In reply to Erich Focht

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 -0
 	cpu = ++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(unsigne
 	set_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.h b/include/linux/sched.h

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).

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.c b/kernel/sched.c

kernel/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?

#25 lore raw
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_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?

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.

#26 lore raw
In reply to Martin J. Bligh
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