Node affine NUMA scheduler

Erich Focht <efocht@ess.nec.de>

Background

This scheduler extension is targeted to cc-NUMA machines with CPUs grouped in multiple nodes, each node having its own memory. The example in the sketch below is a 16 CPU ccNUMA machine, each node holding 4 processors and its own memory. The nodes are connected by some interconnect over which the data for memory accesses to remote nodes is transfered and some cache coherency protocol is implemented.

Accessing the memory of a remote node implies taking penalties in memory access latency and bandwidth. Therefore it is desirable to keep processes on or near the node on which their memory (or most of it) is allocated. As an example: the small benchmark program used in the testing section needs 30% longer time to complete when running on a remote node on an NEC AzusA Itanium server though this machine has an excellent remote to local memory access latency ratio of 1.6.

Some machines implement an additional large node-level cache which tries to hide the distance to the remote nodes. Programs with small node-level cache footprint see only the latency to this cache but take a big performance hit if they get scheduled on another node. The codes running out of cache (generating many cache misses) suffer similarly as on machines without node-cache if their memory is allocated on a distant node.

Fixing the cpus_allowed mask of tasks to a particular nodes would of course be a solution but experiments show that for loads >100% this leads to poorer performance (due to bad load balancing).

In this approach each task gets a homenode on which its memory will be allocated and the scheduler will try to keep the task on its homenode or reattract it to that node if it was migrated away from it. The kernel must provide some mechanism to control the node on which memory gets allocated.

Implementation

The node affine NUMA scheduler is built on top of Ingo Molnar's O(1) scheduler which replaced the old Linux scheduler since 2.5.2 kernels. The newer versions are in the latest 2.5 kernels, I'll try to backport essential features to 2.4.X kernels, please check the Download section.

NUMA topology information

As sketched above, the CPUs of a NUMA machine are typically grouped in nodes. The node IDs are normally reflected in the (S)APIC ID of each CPU. I'll call these physical node IDs. Each platform should provide a macro SAPICID_TO_PNODE() which extracts the physical node number from the (S)APIC ID of a processor.

CPUs in a physical node are grouped in a CPU pool. The scheduler deals with pool IDs or logical node IDs , their numbering starts at 0. The following variables are used for describing the node topology:

numpools : number of pools

pool_nr_cpus[] : number of cpus per pool

pool_cpus[] : logical cpu numbers sorted by their pool id

pool_ptr[] : pointer into poo_cpus[], points to first cpu of a certain pool

pool_mask[] : cpu mask for processors in a pool

CPU_TO_NODE() / lnode_number[] : pool id of each logical cpu.

The variables pool_ptr[] and pool_cpus[] are similar to the compressed row format for matrices. A loop over the cpus of one pool can be written as:

for (i = pool_ptr[pool]; i < pool_ptr[pool+1]; i++) {
cpu = pool_cpus[i];
... // do work on the cpu
}

The CPU_TO_NODE() macro is using the array lnode_number[] which is initialized in bld_pools() (kernel/sched.c).

Homenode

The task_structure has been extended by an element int node which specifies the homenode of the task, i.e. the node on which:

the tasks memory gets allocated (if a coupling to a NUMA memory affinity patch exists),

the task should preferably run, i.e. if it gets scheduled away because of high load on its homenode, the task will be attracted back by the scheduler.

Because we have no mechanism to move the memory of one task from one node to another, it doesn't make much sense to change the homenode of a task during its lifetime. It is basically chosen shortly after the new task is created, the next section describes the details.

Additional to the number of running tasks nr_running each runqueue stores in the array nr_homenode[0 ... numpools] the number of tasks enqueued and comming from a particular node. In this way the scheduler can quickly look up whether there are tasks from other nodes running on the current cpu.

Initial load balancing

Currently the homenode of a new task can be selected either in do_execve() or in do_fork(). The choice is depending on the number of tasks assigned to each node, not on the actual load of each node, as tasks running on foreign nodes might return to their homenode. An additional task_structure element int node_policy decides on where the initial load balancing (i.e. choice of the homenode) is done:

node_policy	balancing in	comment
0 (default)	do_execve()	Tasks that fork() but don't exec() end up on the same node!
1	do_fork()	New homenode is chosen only if the child has its own new mm structure!
2	do_fork()	Allways choose new homenode.

A small utility can be used to change the node_policy field of a particular task. One would typically change the node_policy of the shell from which the application is started, run it and change it back, if needed.

Dynamic load balancing

The load_balance() routine is changed as follows:

Tries to balance the load inside the own node when invoked (i.e. each tick on idle cpus, every 200ms on busy cpus). This is the same behavior as Ingo's design, but restricted to the nearest CPUs (within the current node/pool).
If the local node is balanced, finds the most loaded node and its most loaded CPU.

If the local node's load is below the machines average load, tries to steal a task after a few milliseconds from the most loaded CPU. The delay depends on the memory access latency difference between the own node and the node of the most loaded CPU. The delay will be slightly longer when trying to steal tasks from a node which is "far away".
If the local node load is (within some margins) the same as the machine's average load, remebers the most loaded node and waits before trying to steal a task from it. As all idle CPUs are racing for getting a task from the most loaded node, this gives us a chance to get better balance between nodes. The wait time depends on the "distance" between the source and target cpus. More details are in the section Multilevel node structure.

Tasks not running on their homenode are treated preferrentially by the CPUs belonging to the homenode. The load seen by a CPU is "subjective" because the tasks originating from its node are counted twice (should this be adapted for other machines?). This is one of the forces attracting the tasks back to their homenode.
The selection of the task to be stolen has been changed in order to facilitate the integration of the multilevel concept. The selection is done in the routine task_to_steal(). In a loop over all running tasks in the runqueue from which we want to steal the task with the highest weight is selected to be moved. If the runqueue is long, it takes longer to select the right task for stealing, but the decision will (hopefully) be worth it. Specially with multilevel node architectures the scan of the whole runqueue is better than just stealing the first task that fulfills the CAN_MIGRATE condition... The relevant piece of code looks as follows:

	if (CAN_MIGRATE_TASK(tmp, busiest, this_cpu)) {
		weight = (jiffies - tmp->sleep_timestamp)/cache_decay_ticks;
#ifdef CONFIG_NODE_AFFINE_SCHED
		if (weight >= MAX_CACHE_WEIGHT) weight=MAX_CACHE_WEIGHT-1;
		weight += POOL_WEIGHT(this_pool,tmp->node);
		if (tmp->node == CPU_TO_NODE(busiest->curr->cpu))
			weight -= MAX_CACHE_WEIGHT;
#endif
		if (weight > maxweight) {
			maxweight = weight;
			next = tmp;
		}
	}

The tasks can be migrated if they slept more than cache_decay_ticks. The weight contribution of the sleep time is linear up to the value MAX_CACHE_WEIGHT-1.
The weight contribution depending on homenode of the task is given by the macro POOL_WEIGHT() . The nearer the homenode of the task from the node which wants to steal it, the higher the weight contribution. This is another contribution to the force attracting the tasks back to their homenode.
Tasks running on their own node get a weight bonus.

If the load balancer fails to find a more loaded CPU, it checks whether there is only one task running on its runqueue and whether this task is running off its homenode. This is a case where the task cannot be stolen from its homenode because it is allways running. Therefore the load balancer will push the task back to its homenode if that one is unloaded (load less than 25%). A modification of the migration_thread was needed in order to allow the asynchronous push of the task.

The load_balance() routine is called in the same places as in Ingo's O(1) scheduler implementation and I kept the timings and margins for balancing close to Ingo's:

1ms or 1 tick for idle cpus, 200ms for busy cpus,

>= 25% load imbalance necessary.

Multilevel node structure

The delay when trying to steal remote tasks in load_balance() offers an easy way to deal with ccNUMA architectures with multiple levels of memory- or node-hierarchy. As an example, let's look at the NEC TX7 (Asama). It has 32 Itanium2 CPUs grouped in eight nodes, which are grouped into two supernodes. When a node tries to steal a task it will wait longer when getting it from a node which is in another supernode. When the stealing node is (within some margine) averagely loaded, the wait time will be somewhere between 100-300ms. If the load is less than average, the wait time will be only a few milliseconds. The wait time is computed in the macro POOL_DELAY(from_node, to_node), which is basically a matrix int _pool_delay[NR_NODES][NR_NODES] initialized according to the machine topology and the memory latency differences between the nodes. For initializing the _pool_delay matrix I currently use the topology information from the SLIT table delivered by ACPI. This leads to the following delays:

node distance	avg. load	low load	comment
10	132ms	2ms	stealing from same node: handled without delays
15	199ms	3ms	stealing from same supernode
20	265ms	4ms	stealing from other supernode

The scheduler was tested on a 16 CPU Itanium server (NEC AzusA) and a 32 CPU Itanium2 server (NEC Asama). Previous versions were tested on SGI SN1/2 hardware with up to 32 Itanium CPUs and on 16 CPU IA32 NUMA-Q from IBM. Thanks to Jesse Barnes and Matt Dobson for testing and porting to their platforms.

Download

Kernel patches (for 2.4.18 kernels):

1	O1_ia64-ef7-2.4.18.patch.bz2	IA64 port of O(1) scheduler, applies cleanly to kernels with ia64-020622 patch
2	O1_i386-ef7-2.4.18.patch.bz2	i386 version of the O(1) scheduler, applies to vanilla 2.4.18 kernel
3	Nod20_2.4.18-ia64-O1ef7.patch	Node affine scheduler, apply over a kernel with O(1)-ef7 scheduler
4	proc_sched_hist_2.4.18-ia64-O1ef7.patch	Patch for runqueue load and load balancer history information in /proc/sched.
5	NodeAff_Discontig_coupling-2.patch	Ensures that memory gets allocated on the homenode. DISCONTIGMEM patch required! (This patch applies over the ia64 version of discontigmem!)

An experimental patch for 2.5.31 is available here. The BitKeeper tree bk://numa-ef.bkbits.net/2.5-numa-sched contains the same information. Thanks to Michael Hohnbaum for porting the Nod18 version of the node affine scheduler to the 2.5.25 kernel. The 2.5.X versions of the NUMA scheduler are based on this port.

nodpol.c is the utility for setting the node_policy (initial load balancing policy) and the homenode. Setting the homenode is intended only for experiments.

Testing node affinity

Here is a small test program which is sensitive to both memory latency and bandwidth. The core is an indirect update loop:

for(i=0; i<n; i++)
a[ix[i]] = a[ix[i]] + b[i];

with random ix[]. This is quite typical for simulations using unstructured grids.

There are two similar perl scripts included which can be used for submitting several such processes in parallel and formatting the output. They are hardwired for 4 nodes (sorry) and need a file describing the cpu to node assignement. It should contain the node numbers of the logical CPUs separated by one blank (sorry for the inconvenience, I was using a patch for accessing this info in /proc...).

Usage: try calling:

time ./disp 4 ./affinity 1000000

This will start 4 copies of ./affinity and collect some statistics about percentage of time spent on each node, maximum percentage spent on a node, the node number on which it spent most of the time, the initial
node, the user time. Interesting is also the elapsed time returned by the "time" command. The output looks like this:

[focht@azusa ~/affinity]> ./dispn 4 ./affinity 1000000
Executing 4 times: ./affinity 1000000
-----------------------------------------------------------------------
                % Time on Node            Scheduled node
Job        0       1       2       3       Max (m , i)      Time (s)
-----------------------------------------------------------------------
1       100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |   29.5
2         0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |   26.5
3       100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |   29.5
4         0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |   26.6
-----------------------------------------------------------------------
Average user time = 28.00 seconds

When a task runs alone on a node it needs 26.5s, if two tasks are running on the same node (but on different CPUs), each needs 29.5s. When running alone on the wrong node (i.e. the memory is allocated on another node) the test needs 38s, roughly 40% more.

Normally one should find:

on kernels with the old scheduler:

for #jobs < #cpus: poor balancing among nodes => bad times due to bandwidth limitations

for #jobs > #cpus: jobs are hopping from node to node: poor latency

on kernels with Ingo's scheduler:

less hopping across the nodes, but poor balance among nodes

short additional load peaks can shift jobs away from their memory to another node, from where they don't have a reason to return

on kernels with Ingo's O(1) + node affine extension:

hopefully better balanced nodes (at least in average) for #jobs < #cpus therefore better bandwidth available

better latency due to node affinity (though there is a problem when a single job is running on a remote node: it can't be taken back to the homenode even if that one is empty because a running job can't be stolen).

Below are some results for a load of 150%.

The behavior of the old Linux scheduler is illustrated in the following output of a typical run. The machine runs 24 affinity processes on 16 CPUs. One can see a nearly equal distribution of the CPU times over the nodes. The asteriscs show proceses which ran most of the time on another node than the one on which they started.

[focht@azusa ~/affinity_test]> ./dispn 24 ./affinity 1000000
Executing 24 times: ./affinity 1000000
-----------------------------------------------------------------------
                % Time on Node            Scheduled node
Job        0       1       2       3       Max  (m , i)      Time (s)
-----------------------------------------------------------------------
1        19.9    27.0    22.0    31.0   |  31.0 (3 = 3)   |  40.13
2        23.4    27.1    24.8    24.7   |  27.1 (1 = 1)   |  40.65
3        32.4    22.3    23.1    22.2   |  32.4 (0 = 2) * |  41.08
4        28.3    19.1    26.9    25.6   |  28.3 (0 = 2) * |  40.69
5        22.9    20.0    29.1    28.0   |  29.1 (2 = 3) * |  40.49
6        24.6    22.4    24.8    28.1   |  28.1 (3 = 2) * |  40.76
7        29.3    23.7    17.4    29.6   |  29.6 (3 = 0) * |  40.42
8        28.1    30.9    22.2    18.8   |  30.9 (1 = 1)   |  40.15
9        26.2    21.4    23.3    29.1   |  29.1 (3 = 3)   |  40.51
10       22.3    29.6    24.4    23.7   |  29.6 (1 = 2) * |  40.72
11       26.2    22.8    27.8    23.2   |  27.8 (2 = 0) * |  41.07
12       24.1    25.5    25.9    24.4   |  25.9 (2 = 0) * |  41.30
13       19.7    29.6    22.0    28.7   |  29.6 (1 = 2) * |  41.74
14       21.2    26.6    23.6    28.6   |  28.6 (3 = 0) * |  41.61
15       19.4    27.1    26.8    26.6   |  27.1 (1 = 1)   |  40.72
16       21.1    20.5    26.4    32.1   |  32.1 (3 = 2) * |  41.52
17       22.5    29.1    26.9    21.5   |  29.1 (1 = 2) * |  41.00
18       20.9    27.0    23.1    29.0   |  29.0 (3 = 1) * |  40.70
19       21.6    29.8    25.6    22.9   |  29.8 (1 = 3) * |  41.68
20       27.9    24.2    26.2    21.6   |  27.9 (0 = 1) * |  41.28
21       27.9    23.1    25.7    23.3   |  27.9 (0 = 2) * |  41.43
22       26.9    24.3    27.8    21.0   |  27.8 (2 = 3) * |  41.62
23       27.7    21.6    32.3    18.4   |  32.3 (2 = 3) * |  41.95
24       34.4    24.4    22.5    18.7   |  34.4 (0 = 1) * |  41.43
-----------------------------------------------------------------------
 Average user time = 41.03 seconds

With the O(1) scheduler the results are better, but several processes spend most of their CPU-time on another node than the one they started to run (the lines with the asteriscs). Those tasks needed significantly more usertime than the ones which spent their lifetime on the same node.


[focht@azusa ~/affinity_test]> ./dispn 24 ./affinity 1000000
Executing 24 times: ./affinity 1000000
-----------------------------------------------------------------------
                % Time on Node            Scheduled node
Job        0       1       2       3       Max  (m , i)      Time (s)
-----------------------------------------------------------------------
1       100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |  32.64
2         0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |  31.97
3         0.0    57.2     0.0    42.8   |  57.2 (1 = 3) * |  37.28
4        41.7     0.0     0.0    58.3   |  58.3 (3 = 0) * |  38.28
5        41.5     0.0    58.5     0.0   |  58.5 (2 = 0) * |  38.05
6         0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |  32.19
7         0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |  32.15
8         0.0     0.0    42.3    57.7   |  57.7 (3 = 2) * |  37.59
9         0.0     0.0   100.0     0.0   | 100.0 (2 = 2)   |  31.88
10        0.0    56.9    43.1     0.0   |  56.9 (1 = 2) * |  37.01
11        0.0    57.0    43.0     0.0   |  57.0 (1 = 2) * |  37.09
12        0.0     0.0   100.0     0.0   | 100.0 (2 = 2)   |  32.03
13        0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |  31.78
14       99.7     0.3     0.0     0.0   |  99.7 (0 = 1) * |  37.81
15        0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |  32.30
16        0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |  32.24
17        0.0     0.5     0.0    99.5   |  99.5 (3 = 1) * |  39.97
18        0.0    57.0     0.0    43.0   |  57.0 (1 = 3) * |  37.36
19        0.0     0.0    99.5     0.5   |  99.5 (2 = 3) * |  42.47
20        0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |  31.87
21      100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |  31.90
22        0.0     0.0   100.0     0.0   | 100.0 (2 = 2)   |  31.46
23      100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |  32.67
24      100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |  32.62
-----------------------------------------------------------------------
 Average user time = 34.69 seconds

The results for the node affine scheduler (below) show an improvement. Only two tasks ran on the wrong node due to the load situation during initial scheduling.

[focht@azusa ~/affinity_test]> ./dispn 24 ./affinity 1000000
Executing 24 times: ./affinity 1000000

-----------------------------------------------------------------------
                % Time on Node            Scheduled node
Job        0       1       2       3       Max  (m , i)      Time (s)
-----------------------------------------------------------------------
1       100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |   33.3
2         0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |   32.5
3         0.0     0.0   100.0     0.0   | 100.0 (2 = 2)   |   31.7
4         0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |   32.1
5         0.0     0.0   100.0     0.0   | 100.0 (2 = 2)   |   31.1
6         0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |   32.3
7        39.3     0.0    60.7     0.0   |  60.7 (2 = 0) * |   39.8
8         0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |   32.3
9         0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |   32.2
10       38.5     0.0    61.5     0.0   |  61.5 (2 = 0) * |   39.9
11        0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |   31.9
12        0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |   32.2
13        0.0     0.0   100.0     0.0   | 100.0 (2 = 2)   |   31.8
14        0.0     0.0   100.0     0.0   | 100.0 (2 = 2)   |   31.3
15        0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |   32.2
16        0.0     0.0     0.0   100.0   | 100.0 (3 = 3)   |   31.8
17        0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |   31.8
18        0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |   31.8
19      100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |   32.9
20      100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |   32.3
21      100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |   33.0
22        0.0   100.0     0.0     0.0   | 100.0 (1 = 1)   |   32.6
23        0.0     0.0   100.0     0.0   | 100.0 (2 = 2)   |   31.7
24      100.0     0.0     0.0     0.0   | 100.0 (0 = 0)   |   33.2
-----------------------------------------------------------------------
 Average user time = 32.83 seconds

Last updated: 21.08.2002