sched,numa: task placement with complex NUMA topologies
cover sched,numa: task placement with complex NUMA topologies
This patch set integrates two algorithms I have previously tested, one for glueless mesh NUMA topologies, where NUMA nodes communicate with far-away nodes through intermediary nodes, and backplane topologies, where communication with far-away NUMA nodes happens through backplane controllers (which cannot run tasks).
Due to the inavailability of 8 node systems, and the fact that I am flying out to Linuxcon Europe / Plumbers / KVM Forum on Friday, I have not tested these patches yet. However, with a conference (and many familiar faces) coming up, it seemed like a good idea to get the code out there, anyway.
The algorithms have been tested before, on both kinds of system. The new thing about this series is that both algorithms have been integrated into the same code base, and new code to select the preferred_nid for tasks in numa groups.
Placement of tasks on smaller, directly connected, NUMA systems should not be affected at all by this patch series.
I am interested in reviews, as well as test results on larger NUMA systems :)
RFC PATCH 1/5 sched,numa: build table of node hop distance
From: Rik van Riel <[email protected]>
In order to more efficiently figure out where to place workloads that span multiple NUMA nodes, it makes sense to estimate how many hops away nodes are from each other.
Also add some comments to sched_init_numa.
--- include/linux/topology.h | 1 + kernel/sched/core.c | 35 +++++++++++++++++++++++++++++++++-- 2 files changed, 34 insertions(+), 2 deletions(-)
include/linux/topology.h +1 -0
@@ -47,6 +47,7 @@if (nr_cpus_node (node)) int arch_update_cpu_topology(void); +extern int node_hops (int i,int j);/* Conform to ACPI 2.0 SLIT distance definitions */ #define LOCAL_DISTANCE 10
kernel/sched/core.c +33 -2
@@ -6076,6 +6076,7 @@ static void claim_allocations(int cpu, struct sched_domain *sd)#ifdef CONFIG_NUMA static int sched_domains_numa_levels;static int *sched_domains_numa_distance; +static int *sched_domains_numa_hops;static struct cpumask ***sched_domains_numa_masks;static int sched_domains_curr_level;#endif
@@ -6247,6 +6248,19 @@ static void sched_numa_warn(const char *str)printk (KERN_WARNING "\n" ); } +int node_hops (int i,int j) +{ +if (!sched_domains_numa_hops) +return 0 ; + +return sched_domains_numa_hops[i * nr_node_ids + j]; +} + +static void set_node_hops (int i,int j,int hops) +{ + sched_domains_numa_hops[i * nr_node_ids + j] = hops; +} +static bool find_numa_distance (int distance) {int i;
@@ -6273,6 +6287,10 @@ static void sched_init_numa(void)if (!sched_domains_numa_distance)return ; + sched_domains_numa_hops =kzalloc (sizeof (int ) * nr_node_ids * nr_node_ids,GFP_KERNEL ); +if (!sched_domains_numa_hops) +return ; +/* * O(nr_nodes^2) deduplicating selection sort -- in order to find the * unique distances in the node_distance() table.
@@ -6340,7 +6358,7 @@ static void sched_init_numa(void)/* * Now for each level, construct a mask per node which contains all -* cpus of nodes that are that many hops away from us. +* cpus of nodes that are that many hops away from us and closer by. */ for (i =0 ; i < level; i++) { sched_domains_numa_masks[i] =
@@ -6348,6 +6366,9 @@ static void sched_init_numa(void)if (!sched_domains_numa_masks[i])return ; +/* A node is 0 hops away from itself. */ +set_node_hops (i, i,0 ); +for (j =0 ; j < nr_node_ids; j++) {struct cpumask *mask =kzalloc (cpumask_size (),GFP_KERNEL );if (!mask)
@@ -6356,10 +6377,20 @@ static void sched_init_numa(void) sched_domains_numa_masks[i][j] = mask;for (k =0 ; k < nr_node_ids; k++) { -if (node_distance (j, k) > sched_domains_numa_distance[i]) +int distance =node_distance (j, k); +if (distance > sched_domains_numa_distance[i])continue ; +/* All CPUs at distance or less. */ cpumask_or (mask, mask,cpumask_of_node (k)); + +/* +* The number of hops is one larger than i, +* because sched_domains_numa_distance[] +* excludes the local distance. +*/ +if (distance == sched_domains_numa_distance[i]) +set_node_hops (j, k, i+1 ); } } }
Signature · 1 line
1.9.3
Peter Zijlstra
maintainerRe: [PATCH RFC 1/5] sched,numa: build table of node hop distance
kernel/sched/core.c static void sched_init_numa(void) · line 6292
Quoted 3 lines · On Wed, Oct 08, 2014 at 03:37:26PM -0400, [email protected] wrote:
kernel/sched/core.c +3
-0+ sched_domains_numa_hops =kzalloc (sizeof (int ) * nr_node_ids * nr_node_ids,GFP_KERNEL ); +if (!sched_domains_numa_hops) +return ;
That's potentially a _BIG_ table (1M for a 512 node system). The node_distance has magic allocations and is of u8 size, is there any way we can re-use node_distance and avoid a second O(n^2) allocation?
Re: [PATCH RFC 1/5] sched,numa: build table of node hop distance
Quoted 8 lines · Peter Zijlstra
kernel/sched/core.c static void sched_init_numa(void) · line 6292
Quoted 3 lines · On Wed, Oct 08, 2014 at 03:37:26PM -0400, [email protected] wrote:
kernel/sched/core.c +3
-0+ sched_domains_numa_hops =kzalloc (sizeof (int ) * nr_node_ids * nr_node_ids,GFP_KERNEL ); +if (!sched_domains_numa_hops) +return ;That's potentially a _BIG_ table (1M for a 512 node system). The
node_distancehas magic allocations and is of u8 size, is there any way we can re-usenode_distanceand avoid a second O(n^2) allocation?
You are right, this should be a u8 at the least.
Beyond that, I am not convinced that merging things into the same array is worthwhile, since (IIRC) nr_node_ids should be set to the actual number of nodes on the system by then.
Peter Zijlstra
maintainerRe: [PATCH RFC 1/5] sched,numa: build table of node hop distance
Quoted 10 lines · Rik van Riel
Quoted 8 lines · Peter Zijlstra
kernel/sched/core.c static void sched_init_numa(void) · line 6292
Quoted 3 lines · On Wed, Oct 08, 2014 at 03:37:26PM -0400, [email protected] wrote:
kernel/sched/core.c +3
-0+ sched_domains_numa_hops =kzalloc (sizeof (int ) * nr_node_ids * nr_node_ids,GFP_KERNEL ); +if (!sched_domains_numa_hops) +return ;That's potentially a _BIG_ table (1M for a 512 node system). The
node_distancehas magic allocations and is of u8 size, is there any way we can re-usenode_distanceand avoid a second O(n^2) allocation?
Quoted 6 lines
You are right, this should be a u8 at the least.
Beyond that, I am not convinced that merging things into the same array is worthwhile, since (IIRC)
nr_node_idsshould be set to the actual number of nodes on the system by then.
The thing is, it looks like all you do is compare hop distance, and the order of the hop distances is the exact same order as the regular numa distance. I could not find a place where you use the actual hop value.
So if all you're interested in is the relative ordering, that should be the same for both.
Re: [PATCH RFC 1/5] sched,numa: build table of node hop distance
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Rik van Riel
Quoted 8 lines · Peter Zijlstra
kernel/sched/core.c static void sched_init_numa(void) · line 6292
Quoted 3 lines · On Wed, Oct 08, 2014 at 03:37:26PM -0400, [email protected] wrote:
kernel/sched/core.c +3
-0+ sched_domains_numa_hops =kzalloc (sizeof (int ) * nr_node_ids * nr_node_ids,GFP_KERNEL ); +if (!sched_domains_numa_hops) +return ;That's potentially a _BIG_ table (1M for a 512 node system). The
node_distancehas magic allocations and is of u8 size, is there any way we can re-usenode_distanceand avoid a second O(n^2) allocation?You are right, this should be a u8 at the least.
Quoted 8 lines
Quoted 4 lines
Beyond that, I am not convinced that merging things into the same array is worthwhile, since (IIRC)
nr_node_idsshould be set to the actual number of nodes on the system by then.The thing is, it looks like all you do is compare hop distance, and the order of the hop distances is the exact same order as the regular numa distance. I could not find a place where you use the actual hop value.
I use the actual hop distances when doing the scoring for glueless mesh topologies, in patch 4/5.
Quoted 3 lines
So if all you're interested in is the relative ordering, that should be the same for both.
RFC PATCH 2/5 sched,numa: classify the NUMA topology of a system
In reply to [email protected]From: Rik van Riel <[email protected]>
Smaller NUMA systems tend to have all NUMA nodes directly connected to each other. This includes the degenerate case of a system with just one node, ie. a non-NUMA system.
Larger systems can have two kinds of NUMA topology, which affects how tasks and memory should be placed on the system.
On glueless mesh systems, nodes that are not directly connected to each other will bounce traffic through intermediary nodes. Task groups can be run closer to each other by moving tasks from a node to an intermediary node between it and the task's preferred node.
On NUMA systems with backplane controllers, the intermediary hops are incapable of running programs. This creates "islands" of nodes that are at an equal distance to anywhere else in the system.
Each kind of topology requires a slightly different placement algorithm; this patch provides the mechanism to detect the kind of NUMA topology of a system.
--- include/linux/topology.h | 7 +++++++ kernel/sched/core.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 60 insertions(+)
include/linux/topology.h +7 -0
@@ -49,6 +49,13 @@int arch_update_cpu_topology (void );extern int node_hops (int i,int j); +enum numa_topology_type { +NUMA_DIRECT , +NUMA_GLUELESS_MESH , +NUMA_BACKPLANE , +}; +extern enum numa_topology_type sched_numa_topology_type; +/* Conform to ACPI 2.0 SLIT distance definitions */ #define LOCAL_DISTANCE 10#define REMOTE_DISTANCE 20
kernel/sched/core.c +53 -0
71 lines not on this page · raw message
Signature · 1 line
1.9.3
Peter Zijlstra
maintainerRe: [PATCH RFC 2/5] sched,numa: classify the NUMA topology of a system
Quoted 20 lines · On Wed, Oct 08, 2014 at 03:37:27PM -0400, [email protected] wrote:
kernel/sched/core.c +20
-0+static void init_numa_topology_type (void ) +{ +int a, b, c, n; + + n = sched_domains_numa_levels; + +if (n <=1 ) + sched_numa_topology_type =NUMA_DIRECT ; + +for_each_online_node (a) { +for_each_online_node (b) { +/* Find two nodes furthest removed from each other. */ +if (node_hops (a, b) < n) +continue ; + +/* Is there an intermediary node between a and b? */ +for_each_online_node (c) { +if (node_hops (a, c) < n && +node_hops (b, c) < n) { + sched_numa_topology_type =
kernel/sched/core.c static bool find_numa_distance(int distance) · line 6328
Quoted 10 lines
kernel/sched/core.c +10
-0+NUMA_GLUELESS_MESH ; +return ; + } + } + + sched_numa_topology_type =NUMA_BACKPLANE ; +return ; + } + } +}
We can find max_distance nodes in sched_init_numa(), right? Could we not avoid this second iteration?
Re: [PATCH RFC 2/5] sched,numa: classify the NUMA topology of a system
Quoted 26 lines · Peter Zijlstra
Quoted 25 lines · On Wed, Oct 08, 2014 at 03:37:27PM -0400, [email protected] wrote:
kernel/sched/core.c +25
-0+static void init_numa_topology_type (void ) +{ +int a, b, c, n; + + n = sched_domains_numa_levels; + +if (n <=1 ) + sched_numa_topology_type =NUMA_DIRECT ; + +for_each_online_node (a) { +for_each_online_node (b) { +/* Find two nodes furthest removed from each other. */ +if (node_hops (a, b) < n) +continue ; + +/* Is there an intermediary node between a and b? */ +for_each_online_node (c) { +if (node_hops (a, c) < n && +node_hops (b, c) < n) { + sched_numa_topology_type = +NUMA_GLUELESS_MESH ; +return ; + } + } +
Quoted 9 lines
kernel/sched/core.c static bool find_numa_distance(int distance) · line 6328
Quoted 5 lines
kernel/sched/core.c +5
-0+ sched_numa_topology_type =NUMA_BACKPLANE ; +return ; + } + } +}We can find
max_distancenodes insched_init_numa(), right? Could we not avoid this second iteration?
It's not about finding the max distance, but about finding two nodes that are at the maximum distance from each other, in order to see whether there are intermediate nodes between the two.
I suppose we could just directly access the node_hops tables to get two nodes that are the furthest away from each other, but I suspect that searching that table directly will not make a significant difference compared with using the macros above.
Especially since this code is only ever run once at system bootup.
RFC PATCH 3/5 sched,numa: preparations for complex topology placement
In reply to [email protected]From: Rik van Riel <[email protected]>
Preparatory patch for adding NUMA placement on systems with complex NUMA topology. Also fix a potential divide by zero in group_weight()
--- include/linux/topology.h | 1 + kernel/sched/core.c | 2 +- kernel/sched/fair.c | 57 +++++++++++++++++++++++++++++++----------------- 3 files changed, 39 insertions(+), 21 deletions(-)
include/linux/topology.h +1 -0
@@ -47,6 +47,7 @@if (nr_cpus_node (node)) int arch_update_cpu_topology(void); +extern int sched_domains_numa_levels;extern int node_hops (int i,int j);enum numa_topology_type {
kernel/sched/core.c +1 -1
@@ -6074,7 +6074,7 @@ static void claim_allocations(int cpu, struct sched_domain *sd) }#ifdef CONFIG_NUMA -static int sched_domains_numa_levels; +int sched_domains_numa_levels;enum numa_topology_type sched_numa_topology_type;static int *sched_domains_numa_distance;static int *sched_domains_numa_hops;
kernel/sched/fair.c +37 -20
123 lines not on this page · raw message
Signature · 1 line
1.9.3
Peter Zijlstra
maintainerRe: [PATCH RFC 3/5] sched,numa: preparations for complex topology placement
Quoted 18 lines · On Wed, Oct 08, 2014 at 03:37:28PM -0400, [email protected] wrote:
From: Rik van Riel <[email protected]>
Preparatory patch for adding NUMA placement on systems with complex NUMA topology. Also fix a potential divide by zero in
group_weight()Signed-off-by Rik van Riel <[email protected]>--- include/linux/topology.h | 1 + kernel/sched/core.c | 2 +- kernel/sched/fair.c | 57 +++++++++++++++++++++++++++++++----------------- 3 files changed, 39 insertions(+), 21 deletions(-)include/linux/topology.h +0
-0
include/linux/topology.h line 52
Quoted 6 lines
include/linux/topology.h +1
-0@@ -47,6 +47,7 @@if (nr_cpus_node (node)) int arch_update_cpu_topology(void); +extern int sched_domains_numa_levels;extern int node_hops (int i,int j);
I'm not sure we want to share this globally, please consider using kernel/sched/sched.h
Re: [PATCH RFC 3/5] sched,numa: preparations for complex topology placement
Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · On Wed, Oct 08, 2014 at 03:37:28PM -0400, [email protected] wrote:
From: Rik van Riel <[email protected]>
Preparatory patch for adding NUMA placement on systems with complex NUMA topology. Also fix a potential divide by zero in
group_weight()Signed-off-by Rik van Riel <[email protected]>--- include/linux/topology.h | 1 + kernel/sched/core.c | 2 +- kernel/sched/fair.c | 57 +++++++++++++++++++++++++++++++----------------- 3 files changed, 39 insertions(+), 21 deletions(-)include/linux/topology.h +0
-0@@ -47,6 +47,7 @@if (nr_cpus_node (node))
Quoted 8 lines
include/linux/topology.h line 52
Quoted 4 lines
include/linux/topology.h +1
-0int arch_update_cpu_topology (void ); +extern int sched_domains_numa_levels;extern int node_hops (int i,int j);I'm not sure we want to share this globally, please consider using
kernel/sched/sched.h
Good point. I will do that.
RFC PATCH 4/5 sched,numa: calculate node scores in complex NUMA topologies
In reply to [email protected]From: Rik van Riel <[email protected]>
In order to do task placement on systems with complex NUMA topologies, it is necessary to count the faults on nodes nearby the node that is being examined for a potential move.
In case of a system with a backplane interconnect, we are dealing with groups of NUMA nodes; each of the nodes within a group is the same number of hops away from nodes in other groups in the system. Optimal placement on this topology is achieved by counting all nearby nodes equally. When comparing nodes A and B at distance N, nearby nodes are those at distances smaller than N from nodes A or B.
Placement strategy on a system with a glueless mesh NUMA topology needs to be different, because there are no natural groups of nodes determined by the hardware. Instead, when dealing with two nodes A and B at distance N, N >= 2, there will be intermediate nodes at distance < N from both nodes A and B. Good placement can be achieved by right shifting the faults on nearby nodes by the number of hops from the node being scored. In this context, a nearby node is any node less than the maximum distance in the system away from the node. Those nodes are skipped for efficiency reasons, there is no real policy reason to do so.
Placement policy on directly connected NUMA systems is not affected.
--- kernel/sched/fair.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+)
kernel/sched/fair.c +68 -0
@@ -924,6 +924,65 @@ static inline unsigned long group_faults_cpu(struct numa_group *group, int nid) group->faults_cpu[task_faults_idx (nid,1 )]; } +/* Handle placement on systems where not all nodes are directly connected. */ +static unsigned long score_nearby_nodes (struct task_struct *p,int nid, +int hoplimit,bool task) +{ +unsigned long score =0 ; +int node; + +/* +* All nodes are directly connected, and the same distance +* from each other. No need for fancy placement algorithms. +*/ +if (sched_numa_topology_type ==NUMA_DIRECT ) +return 0 ; + +for_each_online_node (node) { +unsigned long faults; +int hops =node_hops (nid, node); + +/* +* The furthest away nodes in the system are not interesting +* for placement; nid was already counted. +*/ +if (hops == sched_domains_numa_levels || node == nid) +continue ; + +/* +* On systems with a backplane NUMA topology, compare groups +* of nodes, and move tasks towards the group with the most +* memory accesses. When comparing two nodes at distance +* "hoplimit", only nodes closer by than "hoplimit" are part +* of each group. Skip other nodes. +*/ +if (sched_numa_topology_type ==NUMA_BACKPLANE && + hops >= hoplimit) +continue ; + +/* Add up the faults from nearby nodes. */ +if (task) + faults =task_faults (p, node); +else + faults =group_faults (p, node); + +/* +* On systems with a glueless mesh NUMA topology, there are +* no fixed "groups of nodes". Instead, nodes that are not +* directly connected bounce traffic through intermediate +* nodes; a numa_group can occupy any set of nodes. Counting +* the faults on nearby hops progressively less as distance +* increases seems to result in good task placement. +*/ +if (sched_numa_topology_type ==NUMA_GLUELESS_MESH ) + faults >>= hops; + + score += faults; + } + +return score; +} +/* * These return the fraction of accesses done by a particular task, or * task group, on a particular numa node. The group weight is given a
@@ -944,6 +1003,8 @@ static inline unsigned long task_weight(struct task_struct *p, int nid,return 0 ; faults =task_faults (p, nid); + faults +=score_nearby_nodes (p, nid, hops, true); +return 1000 * faults / total_faults; }
@@ -961,6 +1022,8 @@ static inline unsigned long group_weight(struct task_struct *p, int nid,return 0 ; faults =group_faults (p, nid); + faults +=score_nearby_nodes (p, nid, hops, false); +return 1000 * faults / total_faults; }
@@ -1363,6 +1426,11 @@ static int task_numa_migrate(struct task_struct *p)continue ; hops =node_hops (env.src_nid, env.dst_nid); +if (sched_numa_topology_type ==NUMA_BACKPLANE && + hops != env.hops) { + taskweight =task_weight (p, env.src_nid, hops); + groupweight =group_weight (p, env.src_nid, hops); + }/* Only consider nodes where both task and groups benefit */ taskimp =task_weight (p, nid, hops) - taskweight;
Signature · 1 line
1.9.3
Peter Zijlstra
maintainerRe: [PATCH RFC 4/5] sched,numa: calculate node scores in complex NUMA topologies
Quoted 55 lines · On Wed, Oct 08, 2014 at 03:37:29PM -0400, [email protected] wrote:
From: Rik van Riel <[email protected]>
In order to do task placement on systems with complex NUMA topologies, it is necessary to count the faults on nodes nearby the node that is being examined for a potential move.
In case of a system with a backplane interconnect, we are dealing with groups of NUMA nodes; each of the nodes within a group is the same number of hops away from nodes in other groups in the system. Optimal placement on this topology is achieved by counting all nearby nodes equally. When comparing nodes A and B at distance N, nearby nodes are those at distances smaller than N from nodes A or B.
Placement strategy on a system with a glueless mesh NUMA topology needs to be different, because there are no natural groups of nodes determined by the hardware. Instead, when dealing with two nodes A and B at distance N, N >= 2, there will be intermediate nodes at distance < N from both nodes A and B. Good placement can be achieved by right shifting the faults on nearby nodes by the number of hops from the node being scored. In this context, a nearby node is any node less than the maximum distance in the system away from the node. Those nodes are skipped for efficiency reasons, there is no real policy reason to do so.
kernel/sched/fair.c +21
-0+/* Handle placement on systems where not all nodes are directly connected. */ +static unsigned long score_nearby_nodes (struct task_struct *p,int nid, +int hoplimit,bool task) +{ +unsigned long score =0 ; +int node; + +/* +* All nodes are directly connected, and the same distance +* from each other. No need for fancy placement algorithms. +*/ +if (sched_numa_topology_type ==NUMA_DIRECT ) +return 0 ; + +for_each_online_node (node) { + } + +return score; +}@@ -944,6 +1003,8 @@ static inline unsigned long task_weight(struct task_struct *p, int nid,return 0 ; faults =task_faults (p, nid); + faults +=score_nearby_nodes (p, nid, hops, true); +return 1000 * faults / total_faults; }
kernel/sched/fair.c static inline unsigned long group_weight(struct task_struct *p, int nid, · line 1028
Quoted 7 lines
kernel/sched/fair.c +2
-0@@ -961,6 +1022,8 @@ static inline unsigned long group_weight(struct task_struct *p, int nid,return 0 ; faults =group_faults (p, nid); + faults +=score_nearby_nodes (p, nid, hops, false); +return 1000 * faults / total_faults; }
So this makes {task,group}_weight() O(nr_nodes), and we call these function from O(nr_nodes) loops, giving a total of O(nr_nodes^2) computational complexity, right?
Seems important to mention; I realize this is only for !DIRECT, but still, I bet the real large people (those same 512 nodes we had previous) would not really appreciate this.
Re: [PATCH RFC 4/5] sched,numa: calculate node scores in complex NUMA topologies
Quoted 68 lines · Peter Zijlstra
Quoted 55 lines · On Wed, Oct 08, 2014 at 03:37:29PM -0400, [email protected] wrote:
From: Rik van Riel <[email protected]>
In order to do task placement on systems with complex NUMA topologies, it is necessary to count the faults on nodes nearby the node that is being examined for a potential move.
In case of a system with a backplane interconnect, we are dealing with groups of NUMA nodes; each of the nodes within a group is the same number of hops away from nodes in other groups in the system. Optimal placement on this topology is achieved by counting all nearby nodes equally. When comparing nodes A and B at distance N, nearby nodes are those at distances smaller than N from nodes A or B.
Placement strategy on a system with a glueless mesh NUMA topology needs to be different, because there are no natural groups of nodes determined by the hardware. Instead, when dealing with two nodes A and B at distance N, N >= 2, there will be intermediate nodes at distance < N from both nodes A and B. Good placement can be achieved by right shifting the faults on nearby nodes by the number of hops from the node being scored. In this context, a nearby node is any node less than the maximum distance in the system away from the node. Those nodes are skipped for efficiency reasons, there is no real policy reason to do so.
kernel/sched/fair.c +21
-0+/* Handle placement on systems where not all nodes are directly connected. */ +static unsigned long score_nearby_nodes (struct task_struct *p,int nid, +int hoplimit,bool task) +{ +unsigned long score =0 ; +int node; + +/* +* All nodes are directly connected, and the same distance +* from each other. No need for fancy placement algorithms. +*/ +if (sched_numa_topology_type ==NUMA_DIRECT ) +return 0 ; + +for_each_online_node (node) { + } + +return score; +}@@ -944,6 +1003,8 @@ static inline unsigned long task_weight(struct task_struct *p, int nid,return 0 ; faults =task_faults (p, nid); + faults +=score_nearby_nodes (p, nid, hops, true); +return 1000 * faults / total_faults; }kernel/sched/fair.c static inline unsigned long group_weight(struct task_struct *p, int nid, · line 1028
Quoted 7 lines
kernel/sched/fair.c +2
-0@@ -961,6 +1022,8 @@ static inline unsigned long group_weight(struct task_struct *p, int nid,return 0 ; faults =group_faults (p, nid); + faults +=score_nearby_nodes (p, nid, hops, false); +return 1000 * faults / total_faults; }So this makes {task,group}_weight()
O(nr_nodes), and we call these function fromO(nr_nodes)loops, giving a total ofO(nr_nodes^2)computational complexity, right?
Quoted 4 lines
Seems important to mention; I realize this is only for !DIRECT, but still, I bet the real large people (those same 512 nodes we had previous) would not really appreciate this.
If desired, we can set up a nodemask for each node that covers only the nodes that are less than the maximum distance away from each other.
Even on the very large systems, that is likely to be less than a dozen nodes.
I am not sure whether to add that complexity now, or whether that should be considered premature optimization :)
RFC PATCH 5/5 sched,numa: find the preferred nid with complex NUMA topology
In reply to [email protected]From: Rik van Riel <[email protected]>
On systems with complex NUMA topologies, the node scoring is adjusted to allow workloads to converge on nodes that are near each other.
The way a task group's preferred nid is determined needs to be adjusted, in order for the preferred_nid to be consistent with group_weight scoring. This ensures that we actually try to converge workloads on adjacent nodes.
--- kernel/sched/fair.c | 83 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 82 insertions(+), 1 deletion(-)
kernel/sched/fair.c +82 -1
@@ -1642,6 +1642,87 @@ static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)return delta; } +/* +* Determine the preferred nid for a task in a numa_group. This needs to +* be done in a way that produces consistent results with group_weight, +* otherwise workloads might not converge. +*/ +static int preferred_group_nid (struct task_struct *p,int nid) +{ +nodemask_t nodes; +int hops; + +/* Direct connections between all NUMA nodes. */ +if (sched_numa_topology_type ==NUMA_DIRECT ) +return nid; + +/* +* On a system with glueless mesh NUMA topology, group_weight +* scores nodes according to the number of NUMA hinting faults on +* both the node itself, and on nearby nodes. +*/ +if (sched_numa_topology_type ==NUMA_GLUELESS_MESH ) { +unsigned long score, max_score =0 ; +int node, max_node = nid; + + hops = sched_domains_numa_levels; + +for_each_online_node (node) { + score =group_weight (p, node, hops); +if (score > max_score) { + max_score = score; + max_node = node; + } + } +return max_node; + } + +/* +* Finding the preferred nid in a system with NUMA backplane +* interconnect topology is more involved. The goal is to locate +* tasks from numa_groups near each other in the system, and +* untangle workloads from different sides of the system. This requires +* searching down the hierarchy of node groups, recursively searching +* inside the highest scoring group of nodes. The nodemask tricks +* keep the complexity of the search down. +*/ + nodes = node_online_map; +for (hops = sched_domains_numa_levels; hops; hops--) { +unsigned long max_faults =0 ; +nodemask_t max_group; +int a, b; + +for_each_node_mask (a, nodes) { +unsigned long faults =0 ; +nodemask_t this_group; +nodes_clear (this_group); + +/* Sum group's NUMA faults; includes a==b case. */ +for_each_node_mask (b, nodes) { +if (node_hops (a, b) < hops) { + faults +=group_faults (p, b); +node_set (b, this_group); +node_clear (b, nodes); + } + } + +/* Remember the top group. */ +if (faults > max_faults) { + max_faults = faults; + max_group = this_group; +/* +* subtle: once hops==1 there is just one +* node left, which is the preferred nid. +*/ + nid = a; + } + } +/* Next round, evaluate the nodes within max_group. */ + nodes = max_group; + } +return nid; +} +static void task_numa_placement (struct task_struct *p) {int seq, nid, max_nid =-1 , max_group_nid =-1 ;
@@ -1724,7 +1805,7 @@ static void task_numa_placement(struct task_struct *p)if (p->numa_group) {update_numa_active_node_mask (p->numa_group);spin_unlock_irq (group_lock); - max_nid = max_group_nid; + max_nid =preferred_group_nid (p, max_group_nid); }if (max_faults) {
Signature · 1 line
1.9.3
Peter Zijlstra
maintainerRe: [PATCH RFC 5/5] sched,numa: find the preferred nid with complex NUMA topology
Quoted 19 lines · On Wed, Oct 08, 2014 at 03:37:30PM -0400, [email protected] wrote:
kernel/sched/fair.c +19
-0+static int preferred_group_nid (struct task_struct *p,int nid) +{ +nodemask_t nodes; +int hops; + +/* Direct connections between all NUMA nodes. */ +if (sched_numa_topology_type ==NUMA_DIRECT ) +return nid; + +/* +* On a system with glueless mesh NUMA topology, group_weight +* scores nodes according to the number of NUMA hinting faults on +* both the node itself, and on nearby nodes. +*/ +if (sched_numa_topology_type ==NUMA_GLUELESS_MESH ) { +unsigned long score, max_score =0 ; +int node, max_node = nid; + + hops = sched_domains_numa_levels;
kernel/sched/fair.c static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period) · line 1678
Quoted 10 lines
kernel/sched/fair.c +10
-0+ +for_each_online_node (node) { + score =group_weight (p, node, hops); +if (score > max_score) { + max_score = score; + max_node = node; + } + } +return max_node; + }
This too is O(nr_nodes^2), right?
Re: [PATCH RFC 5/5] sched,numa: find the preferred nid with complex NUMA topology
Quoted 24 lines · Peter Zijlstra
Quoted 23 lines · On Wed, Oct 08, 2014 at 03:37:30PM -0400, [email protected] wrote:
kernel/sched/fair.c +23
-0+static int preferred_group_nid (struct task_struct *p,int nid) +{ +nodemask_t nodes; +int hops; + +/* Direct connections between all NUMA nodes. */ +if (sched_numa_topology_type ==NUMA_DIRECT ) +return nid; + +/* +* On a system with glueless mesh NUMA topology, group_weight +* scores nodes according to the number of NUMA hinting faults on +* both the node itself, and on nearby nodes. +*/ +if (sched_numa_topology_type ==NUMA_GLUELESS_MESH ) { +unsigned long score, max_score =0 ; +int node, max_node = nid; + + hops = sched_domains_numa_levels; + +for_each_online_node (node) { + score =group_weight (p, node, hops); +if (score > max_score) {
Quoted 9 lines
kernel/sched/fair.c static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period) · line 1678
Quoted 6 lines
kernel/sched/fair.c +6
-0+ max_score = score; + max_node = node; + } + } +return max_node; + }This too is
O(nr_nodes^2), right?
It is, but I suspect the glueless mesh topologies are never larger than on the order of a dozen nodes or so.
Would you prefer me to make the optimization I proposed in the other email, or should I just add in a comment stating that that optimization could be made if it turns out to be necessary?
A message that is not in the archive (sent off-list or not yet received): 4168C988EBDF2141B4E0B6475B6A73D126F58E4F@G6W2504.americas.hpqcorp.net
A message that is not in the archive (sent off-list or not yet received): [email protected]
Vinod, Chegu
Tested-byQuoted 17 lines
This patch set integrates two algorithms I have previously tested, one for glueless mesh NUMA topologies, where NUMA nodes communicate with far-away nodes through intermediary nodes, and backplane topologies, where communication with far-away NUMA nodes happens through backplane controllers (which cannot run tasks).
Due to the inavailability of 8 node systems, and the fact that I am flying out to Linuxcon Europe / Plumbers / KVM Forum on Friday, I have not tested these patches yet. However, with a conference (and many familiar faces) coming up, it seemed like a good idea to get the code out there, anyway.
The algorithms have been tested before, on both kinds of system. The new thing about this series is that both algorithms have been integrated into the same code base, and new code to select the
preferred_nidfor tasks in numa groups.
Quoted 5 lines
Placement of tasks on smaller, directly connected, NUMA systems should not be affected at all by this patch series.
I am interested in reviews, as well as test results on larger NUMA systems :)
---
Hi Rik,
Applied your RFC patches along with the patch : https://lkml.org/lkml/2014/10/9/604
on a 3.17.0 kernel on ran a quick test on two platforms with different NUMA topologies:
1) 8 socket Westmere-EX system (HT-off)
2) 8 socket IvyBridge-EX prototype system (HT-on)
On both these system ran 4 instances of a 2-socket wide SpecJbb2005 workload and then ran 2 instances of a 4-socket wide SpecJbb2005 workload. Repeated the experiment 10 times.
Having these patches enabled the desired NUMA nodes to selected for both sized workloads on both these systems...which is quite an encouraging sign !
Pl. see below a sampling of memory consumed by the java processes (as reported by numastat captured 120 seconds into each of the runs).
Thanks
Vinod
---
1) 8 socket Westmere-EX system with the following SLIT table :
node distances:
node 0 1 2 3 4 5 6 7
0: 10 12 17 17 19 19 19 19 1: 12 10 17 17 19 19 19 19 2: 17 17 10 12 19 19 19 19 3: 17 17 12 10 19 19 19 19 4: 19 19 19 19 10 12 17 17 5: 19 19 19 19 12 10 17 17 6: 19 19 19 19 17 17 10 12 7: 19 19 19 19 17 17 12 10
1a) 4 x 2 socket wide instances (each instance has 20 warehouse threads)
Note: The correct NUMA nodes got picked 9 out of 10 runs..
PID Node 0 Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Total
15758 (java) 0 33 1904 1542 0 9 0 14 3503 15759 (java) 1 27 0 36 1694 1738 5 5 3506 15760 (java) 1884 1607 8 9 0 11 0 2 3521 15761 (java) 3 26 2 10 0 2 1553 1929 3525
16536 (java) 2 0 1 23 1 31 1934 1526 3517 16537 (java) 1831 1614 0 9 0 33 2 11 3501 16538 (java) 1 0 0 5 1940 1537 2 11 3497 16539 (java) 1 1 1596 1868 0 25 12 8 3511
17504 (java) 1 1 1 9 1769 1687 3 45 3516 < 17505 (java) 1 4 1 6 6 3 1522 1971 3514 17506 (java) 1413 1 9 2039 0 9 2 33 3506 < 17507 (java) 114 1887 1430 5 7 16 3 37 3500 <
17933 (java) 0 1 0 14 1707 1751 8 28 3510 17934 (java) 0 0 1745 1729 0 7 7 33 3522 17935 (java) 1700 1771 4 25 10 3 1 28 3542 17936 (java) 16 15 0 9 0 0 1702 1765 3507
18344 (java) 5 0 7 4 1567 1910 2 11 3507 18345 (java) 1 3 1557 1932 17 26 6 8 3550 18346 (java) 8 0 2 10 4 29 1317 2124 3497 18347 (java) 1591 1856 0 8 8 28 0 16 3508
18753 (java) 1737 1786 4 5 0 1 0 18 3552 18754 (java) 5 28 0 4 1617 1833 3 26 3515 18755 (java) 21 27 0 6 0 0 1518 1937 3509 18756 (java) 1 25 1690 1785 0 0 0 8 3509
19166 (java) 41 1 1829 1628 0 9 3 13 3523 19167 (java) 1737 1736 3 8 0 1 10 15 3511 19168 (java) 33 8 8 13 2 2 1546 1905 3517 19169 (java) 36 9 4 5 1634 1802 0 10 3500
19983 (java) 1617 1818 8 34 12 5 3 2 3501 19984 (java) 0 1 2 41 0 0 1724 1743 3513 19985 (java) 1 3 1901 1570 0 0 3 9 3487 19986 (java) 3 21 0 32 1634 1816 0 6 3514
20947 (java) 0 0 2 27 1652 1819 0 3 3506 20948 (java) 0 0 2 9 1 33 1848 1635 3528 20949 (java) 1 0 1873 1597 1 31 0 4 3508 20950 (java) 1624 1821 10 9 3 33 0 3 3503
21354 (java) 1 17 30 8 601 1400 1 1445 3503 < 21355 (java) 0 3 1542 1963 0 16 1 9 3536 21356 (java) 1761 1672 27 8 8 8 1 10 3494 < 21357 (java) 0 0 25 3 1221 8 1843 410 3511
1b) 2 x 4 socket wide instances (each instance has 40 warehouse threads)
Note: The correct NUMA nodes got picked 9 out of 10 runs.
PID Node 0 Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Total
21847 (java) 1 0 1 16 821 1154 1241 1330 4563
21848 (java) 1274 1497 917 807 14 3 1 25 4537
22120 (java) 1 26 1 5 860 948 1367 1348 4555
22121 (java) 1269 1392 929 896 1 1 5 13 4505
23298 (java) 847 829 1346 1470 0 30 7 3 4533
23299 (java) 3 4 0 15 876 1130 1184 1308 4521
23603 (java) 1277 1447 951 817 2 1 8 20 4521
23604 (java) 1 10 1 28 876 831 1343 1460 4551
23874 (java) 0 3 2 37 864 853 1309 1473 4542
23875 (java) 1452 1382 859 873 1 1 1 10 4579
24148 (java) 1 1 1 21 1132 1296 1084 1039 4574
24149 (java) 896 836 1223 1615 0 30 1 8 4611
24421 (java) 1447 1413 818 849 1 0 0 24 4551
24422 (java) 1 27 1 6 865 817 1420 1427 4563
25064 (java) 861 907 1344 1404 0 24 0 7 4547
25065 (java) 1 1 0 14 1197 1376 827 1168 4583
25881 (java) 1 3 0 19 1043 1204 1123 1167 4559
25882 (java) 884 874 1402 1323 0 0 1 37 4522
26150 (java) 1 1 6 781 11 886 1347 1514 4546 < 26151 (java) 1129 1322 811 459 760 11 9 29 4531 <
----
2) 8 socket IvyBridge-EX prototype system with the following SLIT table :
node distances:
node 0 1 2 3 4 5 6 7
0: 10 16 30 30 30 30 30 30 1: 16 10 30 30 30 30 30 30 2: 30 30 10 16 30 30 30 30 3: 30 30 16 10 30 30 30 30 4: 30 30 30 30 10 16 30 30 5: 30 30 30 30 16 10 30 30 6: 30 30 30 30 30 30 10 16 7: 30 30 30 30 30 30 16 10
2a) 4 x 2 socket wide instances (each instance has 60 warehouse threads)
PID Node 0 Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Total
18680 (java) 2 18 1 20 1 12 3626 4820 8500 18681 (java) 1 8 5 174 4721 3579 12 3 8504 18682 (java) 4 18 5002 3461 9 13 13 3 8523 18683 (java) 5045 3428 3 7 1 18 6 3 8511
19745 (java) 5472 2984 4 7 8 22 10 20 8527 19746 (java) 8 30 3467 4976 3 22 7 5 8519 19747 (java) 2 18 4 9 4390 4068 1 2 8493 19748 (java) 5 7 2 11 4 16 4251 4186 8482
20796 (java) 4176 4301 4 6 9 13 5 6 8517 20797 (java) 13 47 27 1 3311 5127 5 3 8535 20798 (java) 6 5 2973 5498 3 19 29 11 8544 20799 (java) 9 7 9 130 2 14 3034 5315 8519
21852 (java) 6 1 14 14 24 2043 2346 4035 8484 21853 (java) 3551 4841 10 23 4 11 86 4 8532 21854 (java) 2 1 3194 5286 2 5 17 12 8519 21855 (java) 11 3 1 12 6943 1288 166 78 8502
22907 (java) 5 1 4165 4307 8 15 21 8 8531 22908 (java) 4 10 2 2 3066 5421 4 1 8511 22909 (java) 3 2 5 8 6 16 3544 4943 8527 22910 (java) 3340 5127 1 18 6 16 9 4 8520
23955 (java) 7 2 19 3 2436 6000 2 47 8515 23956 (java) 12 2 2785 5668 25 5 3 25 8525 23957 (java) 3651 4790 15 2 24 8 1 17 8508 23958 (java) 9 4 5 1 13 5 4794 3688 8519
25011 (java) 3532 4931 1 6 8 7 3 32 8520 25012 (java) 7 14 2 8 2763 5683 1 28 8506 25013 (java) 13 12 1 11 18 5 5373 3095 8528 25014 (java) 15 9 5455 3013 4 7 8 11 8522
26060 (java) 1 1 1 3 29 28 4651 3784 8498 26061 (java) 2 1 6245 2212 13 39 0 5 8519 26062 (java) 68 5294 1 3 1879 1262 1 3 8511 26063 (java) 7522 637 1 78 107 160 1 6 8512
27116 (java) 2 37 2 2 9 5 5110 3368 8535 27117 (java) 5376 3115 12 4 10 3 5 6 8532 27118 (java) 9 22 2850 5610 4 17 1 18 8531 27119 (java) 10 26 2 3 3472 4987 1 5 8505
28162 (java) 3332 5103 1 4 8 4 7 45 8504 28163 (java) 12 4 3 18 3079 5383 1 24 8524 28164 (java) 17 9 5533 2921 9 5 1 16 8510 28165 (java) 7 2 1 16 10 7 5166 3299 8508
2b) 2 x 4 socket wide instances (each instance has 120 warehouse threads)
PID Node 0 Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Total
29228 (java) 2 8 2394 3868 15 82 1130 1085 8585
29229 (java) 2824 3773 19 6 963 923 24 59 8589
29964 (java) 1084 1080 28 31 2841 3497 8 2 8569
29965 (java) 16 18 1186 1077 3 6 2841 3436 8583
30683 (java) 19 4281 1830 2137 73 94 13 26 8472 30684 (java) 3763 31 10 10 75 56 2174 2394 8514
31399 (java) 6 25 2608 3116 10 18 1424 1388 8595
31400 (java) 1518 1532 2 12 2259 3188 20 32 8562
32113 (java) 692 620 28 18 3141 4033 25 20 8577
32114 (java) 8 8 2231 2390 3 15 1955 1974 8583
32827 (java) 2324 2663 79 3423 24 20 8 13 8554
32828 (java) 15 3 2448 26 515 855 2214 2489 8566
33543 (java) 1090 1129 3 23 22 25 2923 3366 8581
33544 (java) 12 10 2686 3375 1745 726 4 22 8580
34258 (java) 2127 1928 1924 2558 7 18 8 4 8574
34259 (java) 5 23 8 11 1182 1266 2731 3347 8572
34978 (java) 16 14 1617 1964 14 23 2258 2677 8583
34979 (java) 1721 1704 62 19 2339 2726 6 10 8588
35692 (java) 3599 2721 50 58 6 9 700 1421 8564 35693 (java) 18 49 74 83 3162 4822 309 46 8563
���{.n�+�������+%�����ݶ��w��{.n�+����{��G�����{ay�ʇڙ�,j��f���h��������z_�(�階�ݢj"���m������G������?����&���~��iO��z��v�^�m����������?�I�