Skip to contentSkip to conversation

sched,numa: task placement for complex NUMA topologies

PATCH In review [email protected] 2 participants 16 messages May 8, 2014 – May 9, 2014

Subsystems (3)
x86 Scheduler x86 MM
lore
Share & tools
lore

[email protected]

author
#0 lore raw

cover sched,numa: task placement for complex NUMA topologies

This patch series adds code for placement of tasks on a NUMA system with complex NUMA topology. The code is fairly well isolated, and does not impact things on systems with directly connected NUMA topology.

The strategy is to adjust the score of each node, by the score of nearby NUMA nodes, weighed by the numa distance of that node from the other nearby nodes.

One of the main reasons for choosing this strategy is that it allows the current code to stay the same, and simply add one extra call, which does nothing on systems with simple NUMA topologies.

There is a tradeoff between performance and complexity, which is why performance tests were done with patches 1-2, and with the whole series of 1-4.

SPECjbb2005 throughput on an 8 node system:

average bops standard deviation

vanilla 857814 53528
patches 1-2 926053 26590
patches 1-4 931791 13874

Full test results, 10 runs of 2 4-node wide instances. Throughput and distribution of each JVM across memory nodes.

1) kernel without patches:

                                                                    Nodes
                                                                    -----
spec1.txt:           throughput =     901782.00 SPECjbb2005 bops   0,1,4,5
spec2.txt:           throughput =     861272.25 SPECjbb2005 bops   2,3,6,7
spec1.txt:           throughput =     828895.46 SPECjbb2005 bops   3,5,6,7
spec2.txt:           throughput =     834569.91 SPECjbb2005 bops   0,1,2,4
spec1.txt:           throughput =     798582.97 SPECjbb2005 bops   2,4,5,6
spec2.txt:           throughput =     856616.41 SPECjbb2005 bops   0,1,3,7
spec1.txt:           throughput =     805044.62 SPECjbb2005 bops   0,2,4,5
spec2.txt:           throughput =     827402.54 SPECjbb2005 bops   1,3,6,7
spec1.txt:           throughput =     836735.76 SPECjbb2005 bops   2,4,6,7
spec2.txt:           throughput =     830288.17 SPECjbb2005 bops   0,1,3,5
spec1.txt:           throughput =     856434.61 SPECjbb2005 bops   3,4,5,6
spec2.txt:           throughput =     831602.46 SPECjbb2005 bops   0,1,2,7
spec1.txt:           throughput =     796366.70 SPECjbb2005 bops   0,4,6,7
spec2.txt:           throughput =     829059.05 SPECjbb2005 bops   1,2,3,5
spec1.txt:           throughput =     820001.99 SPECjbb2005 bops   1,4,5,7
spec2.txt:           throughput =     836664.23 SPECjbb2005 bops   0,2,3,6
spec1.txt:           throughput =     950736.30 SPECjbb2005 bops   4,5,6,7
spec2.txt:           throughput =     931937.24 SPECjbb2005 bops   0,1,2,3
spec1.txt:           throughput =     956298.83 SPECjbb2005 bops   4,5,6,7
spec2.txt:           throughput =     965984.19 SPECjbb2005 bops   0,1,2,3

2) kernel with patches 1 - 2:

                                                                   nodes
                                                                   ------
spec1.txt:           throughput =     923364.71 SPECjbb2005 bops  0,1,2,3
spec2.txt:           throughput =     912929.23 SPECjbb2005 bops  4,5,6,7
spec1.txt:           throughput =     889254.77 SPECjbb2005 bops  0,1,6,7
spec2.txt:           throughput =     870275.31 SPECjbb2005 bops  2,3,4,5
spec1.txt:           throughput =     950790.19 SPECjbb2005 bops  4,5,6,7
spec2.txt:           throughput =     940626.50 SPECjbb2005 bops  0,1,2,3
spec1.txt:           throughput =     915422.01 SPECjbb2005 bops  4,5,6,7
spec2.txt:           throughput =     934301.50 SPECjbb2005 bops  0,1,2,3
spec1.txt:           throughput =     934467.57 SPECjbb2005 bops  4,5,6,7
spec2.txt:           throughput =     923753.88 SPECjbb2005 bops  0,1,2,3
spec1.txt:           throughput =     951261.79 SPECjbb2005 bops  0,1,2,3
spec2.txt:           throughput =     950683.73 SPECjbb2005 bops  4,5,6,7
spec1.txt:           throughput =     954495.68 SPECjbb2005 bops  0,1,2,3
spec2.txt:           throughput =     943342.78 SPECjbb2005 bops  4,5,6,7
spec1.txt:           throughput =     943429.43 SPECjbb2005 bops  0,1,2,3
spec2.txt:           throughput =     924885.84 SPECjbb2005 bops  4,5,6,7
spec1.txt:           throughput =     962104.96 SPECjbb2005 bops  4,5,6,7
spec2.txt:           throughput =     924263.56 SPECjbb2005 bops  0,1,2,3
spec1.txt:           throughput =     901460.65 SPECjbb2005 bops  2,3,6,7
spec2.txt:           throughput =     869961.50 SPECjbb2005 bops  0,1,4,5

3) kernel with patches 1 - 4:

                                                                    Nodes
                                                                    -----
spec1.txt:           throughput =     929011.11 SPECjbb2005 bops   4,5,6,7
spec2.txt:           throughput =     955879.30 SPECjbb2005 bops   0,1,2,3
spec1.txt:           throughput =     902287.44 SPECjbb2005 bops   4,5,6,7
spec2.txt:           throughput =     932429.31 SPECjbb2005 bops   0,1,2,3
spec1.txt:           throughput =     909671.34 SPECjbb2005 bops   0,1,2,3
spec2.txt:           throughput =     934057.16 SPECjbb2005 bops   4,5,6,7
spec1.txt:           throughput =     940457.57 SPECjbb2005 bops   0,1,2,3
spec2.txt:           throughput =     951272.07 SPECjbb2005 bops   4,5,6,7
spec1.txt:           throughput =     936920.56 SPECjbb2005 bops   0,1,2,3
spec2.txt:           throughput =     947703.47 SPECjbb2005 bops   4,5,6,7
spec1.txt:           throughput =     924643.52 SPECjbb2005 bops   4,5,6,7
spec2.txt:           throughput =     939721.24 SPECjbb2005 bops   0,1,2,3
spec1.txt:           throughput =     935592.32 SPECjbb2005 bops   0,1,2,3
spec2.txt:           throughput =     930367.11 SPECjbb2005 bops   4,5,6,7
spec1.txt:           throughput =     949498.38 SPECjbb2005 bops   0,1,2,3
spec2.txt:           throughput =     933686.74 SPECjbb2005 bops   4,5,6,7
spec1.txt:           throughput =     924315.44 SPECjbb2005 bops   0,1,2,3
spec2.txt:           throughput =     919825.21 SPECjbb2005 bops   4,5,6,7
spec1.txt:           throughput =     917190.04 SPECjbb2005 bops   0,1,2,3
spec2.txt:           throughput =     921301.56 SPECjbb2005 bops   4,5,6,7
author
#1 lore raw

PATCH 1/4 numa,x86: store maximum numa node distance

From: Rik van Riel <[email protected]>

Store the maximum node distance, so the numa placement code can do better placement on systems with complex numa topology.

The function max_node_distance will return LOCAL_DISTANCE if the system has simple NUMA topology, with only a single level of remote distance.

Signed-off-by Rik van Riel <[email protected]>
Tested-by Chegu Vinod <[email protected]>
---
 arch/x86/include/asm/topology.h |  3 +++
 arch/x86/mm/numa.c              | 25 +++++++++++++++++++++++++
 include/linux/topology.h        |  3 +++
 3 files changed, 31 insertions(+)
arch/x86/include/asm/topology.h +3 -0
index 0e8f04f..3ed2464 100644
@@ -95,6 +95,9 @@ extern void setup_node_to_cpumask_map(void);
 extern int __node_distance(int, int);
 #define node_distance(a, b) __node_distance(a, b)
 
+extern int max_node_distance(void);
+#define max_node_distance max_node_distance
+
 #else /* !CONFIG_NUMA */
 
 static inline int numa_node_id(void)
arch/x86/mm/numa.c +25 -0
index 1d045f9..525cde9 100644
@@ -34,6 +34,8 @@ __initdata
 
 static int numa_distance_cnt;
 static u8 *numa_distance;
+static int numa_max_distance;
+static bool numa_complex_topology;
 
 static __init int numa_setup(char *opt)
 {

@@ -357,6 +359,19 @@ void __init numa_reset_distance(void)
 		memblock_free(__pa(numa_distance), size);
 	numa_distance_cnt = 0;
 	numa_distance = NULL;	/* enable table creation */
+	numa_max_distance = LOCAL_DISTANCE;
+	numa_complex_topology = false;
+}
+
+static void __init numa_set_max_distance(int distance)
+{
+	/* Remember the maximum node distance seen. */
+	if (distance > numa_max_distance)
+		numa_max_distance = distance;
+
+	/* Do we see any values in-between local distance and the maximum? */
+	if (distance != LOCAL_DISTANCE && distance != numa_max_distance)
+		numa_complex_topology = true;
 }
 
 static int __init numa_alloc_distance(void)

@@ -437,6 +452,16 @@ void __init numa_set_distance(int from, int to, int distance)
 	}
 
 	numa_distance[from * numa_distance_cnt + to] = distance;
+
+	numa_set_max_distance(distance);
+}
+
+int max_node_distance(void)
+{
+	if (!numa_complex_topology)
+		return LOCAL_DISTANCE;
+
+	return numa_max_distance;
 }
 
 int __node_distance(int from, int to)
include/linux/topology.h +3 -0
index 7062330..6781b8d 100644
@@ -54,6 +54,9 @@ int arch_update_cpu_topology(void);
 #ifndef node_distance
 #define node_distance(from,to)	((from) == (to) ? LOCAL_DISTANCE : REMOTE_DISTANCE)
 #endif
+#ifndef max_node_distance
+#define max_node_distance() (LOCAL_DISTANCE)
+#endif
 #ifndef RECLAIM_DISTANCE
 /*
  * If the distance between nodes in a system is larger than RECLAIM_DISTANCE
Signature · 1 line
1.8.5.3
maintainer
#2 lore raw

Re: [PATCH 1/4] numa,x86: store maximum numa node distance

Quoted 9 lines · On Thu, May 08, 2014 at 01:23:28PM -0400, [email protected] wrote:

From: Rik van Riel <[email protected]>

Store the maximum node distance, so the numa placement code can do better placement on systems with complex numa topology.

The function max_node_distance will return LOCAL_DISTANCE if the system has simple NUMA topology, with only a single level of remote distance.

Quoted 8 lines
Signed-off-by Rik van Riel <[email protected]>
Tested-by Chegu Vinod <[email protected]>
---
 arch/x86/include/asm/topology.h |  3 +++
 arch/x86/mm/numa.c              | 25 +++++++++++++++++++++++++
 include/linux/topology.h        |  3 +++
 3 files changed, 31 insertions(+)

Why are you doing this in arch code? I would've expected some extra code to sched_init_numa() which is generic code that analyses the distance table and reconstructs the actual topology from it.

author
#3 lore raw

Re: [PATCH 1/4] numa,x86: store maximum numa node distance

Quoted 19 lines · Peter Zijlstra
Quoted 9 lines · On Thu, May 08, 2014 at 01:23:28PM -0400, [email protected] wrote:

From: Rik van Riel <[email protected]>

Store the maximum node distance, so the numa placement code can do better placement on systems with complex numa topology.

The function max_node_distance will return LOCAL_DISTANCE if the system has simple NUMA topology, with only a single level of remote distance.

Quoted 8 lines
Signed-off-by Rik van Riel <[email protected]>
Tested-by Chegu Vinod <[email protected]>
---
  arch/x86/include/asm/topology.h |  3 +++
  arch/x86/mm/numa.c              | 25 +++++++++++++++++++++++++
  include/linux/topology.h        |  3 +++
  3 files changed, 31 insertions(+)
Quoted 3 lines

Why are you doing this in arch code? I would've expected some extra code to sched_init_numa() which is generic code that analyses the distance table and reconstructs the actual topology from it.

The only reason it is in the arch code is that node_distance() is in arch code today.

If there is no good reason for node_distance and the node distances array to be in arch code, I could take a stab at making it generic...

author
#4 lore raw

PATCH 2/4 sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

In reply to [email protected]

From: Rik van Riel <[email protected]>

Workloads that span multiple NUMA nodes benefit greatly from being placed on nearby nodes. There are two common configurations on 8 node NUMA systems. One has four "islands" of 2 tighly coupled nodes, another has two "islands" of 4 tightly coupled nodes.

When dealing with 2 4-node wide workloads on such a system, the current NUMA code relies on luck. When a workload is placed on adjacent nodes, performance is great. When a workload is spread across far-away nodes, performance sucks.

This patch adjusts the numa scores of each node by adding the scores of nearby nodes, weighted by the NUMA distance. This results in workloads being pulled together on nearby nodes, and improved performance for workloads that span multiple nodes, on larger NUMA systems.

This patch does nothing on machines with simple NUMA topologies.

On an 8 node system, this patch manages to correctly place 2 4-node wide SPECjbb2005 instances on adjacent nodes around 80% of the time, improving average performance from 857814 to 926054 bops.

Signed-off-by Rik van Riel <[email protected]>
Tested-by Chegu Vinod <[email protected]>
---
 kernel/sched/fair.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 78 insertions(+), 4 deletions(-)
kernel/sched/fair.c +78 -4
index 302facf..5925667 100644
@@ -923,6 +923,63 @@ static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
 }
 
 /*
+ * On systems with complex NUMA topology, we deal with the local node,
+ * far-away nodes, and nodes that are somewhere in-between. The goal is
+ * to pull workloads that span multiple nodes to nodes that are near each
+ * other. This is accomplished adding calculating a score for nearby nodes,
+ * to the local node score, based on the faults on those nearby nodes, and
+ * the proximity of those nodes.
+ */
+static inline unsigned long nearby_nodes_score(struct task_struct *p, int nid,
+						bool task)
+{
+	int max_distance = max_node_distance();
+	unsigned long score = 0;
+	int node;
+
+	/*
+	 * No need to calculate a score if the system has a simple NUMA
+	 * topology, with no node distances between "local" and "far away".
+	 */
+	if (max_distance == LOCAL_DISTANCE)
+		return 0;
+
+	for_each_online_node(node) {
+		int distance;
+		unsigned long faults;
+
+		/* Already scored by the calling function. */
+		if (node == nid)
+			continue;
+
+		/* Skip far-away nodes. We only care about nearby ones. */
+		distance = node_distance(node, nid);
+		if (distance == max_distance)
+			continue;
+
+		/*
+		 * For nodes with distances in-between LOCAL_DISTANCE
+		 * and max_distance, we count the faults on those nodes
+		 * in proportion to their distance, using this formula:
+		 *
+		 * max_distance - node_distance
+		 * -----------------------------
+		 * max_distance - LOCAL_DISTANCE
+		 */
+		if (task)
+			faults = task_faults(p, node);
+		else
+			faults = group_faults(p, node);
+
+		score += 1000 * faults *
+				(max_distance - distance) /
+				(max_distance - LOCAL_DISTANCE);
+	}
+
+	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
  * larger multiplier, in order to group tasks together that are almost

@@ -930,7 +987,7 @@ static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
  */
 static inline unsigned long task_weight(struct task_struct *p, int nid)
 {
-	unsigned long total_faults;
+	unsigned long total_faults, score;
 
 	if (!p->numa_faults_memory)
 		return 0;

@@ -940,15 +997,32 @@ static inline unsigned long task_weight(struct task_struct *p, int nid)
 	if (!total_faults)
 		return 0;
 
-	return 1000 * task_faults(p, nid) / total_faults;
+	score = 1000 * task_faults(p, nid);
+	score += nearby_nodes_score(p, nid, true);
+
+	score /= total_faults;
+
+	return score;
 }
 
 static inline unsigned long group_weight(struct task_struct *p, int nid)
 {
-	if (!p->numa_group || !p->numa_group->total_faults)
+	unsigned long total_faults, score;
+
+	if (!p->numa_group)
+		return 0;
+
+	total_faults = p->numa_group->total_faults;
+
+	if (!total_faults)
 		return 0;
 
-	return 1000 * group_faults(p, nid) / p->numa_group->total_faults;
+	score = 1000 * group_faults(p, nid);
+	score += nearby_nodes_score(p, nid, false);
+
+	score /= total_faults;
+
+	return score;
 }
 
 bool should_numa_migrate_memory(struct task_struct *p, struct page * page,
Signature · 1 line
1.8.5.3
maintainer
#5 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

Quoted 7 lines · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:
kernel/sched/fair.c +7 -0
+		/*
+		 * For nodes with distances in-between LOCAL_DISTANCE
+		 * and max_distance, we count the faults on those nodes
+		 * in proportion to their distance, using this formula:
+		 *
+		 * max_distance - node_distance
+		 * -----------------------------

kernel/sched/fair.c static inline unsigned long group_faults_cpu(struct numa_group *group, int nid) · line 976

Quoted 10 lines
kernel/sched/fair.c +10 -0
+		 * max_distance - LOCAL_DISTANCE
+		 */
+		if (task)
+			faults = task_faults(p, node);
+		else
+			faults = group_faults(p, node);
+
+		score += 1000 * faults *
+				(max_distance - distance) /
+				(max_distance - LOCAL_DISTANCE);

OK that makes sense, except I would suggest you use a power-of-two scale factor :-)

author
#6 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:
kernel/sched/fair.c +12 -0
+		/*
+		 * For nodes with distances in-between LOCAL_DISTANCE
+		 * and max_distance, we count the faults on those nodes
+		 * in proportion to their distance, using this formula:
+		 *
+		 * max_distance - node_distance
+		 * -----------------------------
+		 * max_distance - LOCAL_DISTANCE
+		 */
+		if (task)
+			faults = task_faults(p, node);
+		else
Quoted 8 lines

kernel/sched/fair.c static inline unsigned long group_faults_cpu(struct numa_group *group, int nid) · line 976

Quoted 5 lines
kernel/sched/fair.c +5 -0
+			faults = group_faults(p, node);
+
+		score += 1000 * faults *
+				(max_distance - distance) /
+				(max_distance - LOCAL_DISTANCE);

OK that makes sense, except I would suggest you use a power-of-two scale factor :-)

I guess we could build a NUMA distance table that counts the number of hops, and use that.

That is likely to result in better/easier values for grouping than the (somewhat arbitrary) distances in the SLIT table, anyway...

maintainer
#7 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

In reply to [email protected]

kernel/sched/fair.c static inline unsigned long group_faults_cpu(struct numa_group *group, int nid) · line 945

Quoted 6 lines · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:
kernel/sched/fair.c +6 -0
+	/*
+	 * No need to calculate a score if the system has a simple NUMA
+	 * topology, with no node distances between "local" and "far away".
+	 */
+	if (max_distance == LOCAL_DISTANCE)
+		return 0;

That's basically !numa and we shouldn't be getting here, so I think you can make that a WARN_ON_ONCE().

maintainer
#8 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

In reply to [email protected]
Quoted 9 lines · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:

static inline unsigned long task_weight(struct task_struct *p, int nid) {

kernel/sched/fair.c +1 -1
-	unsigned long total_faults;
+	unsigned long total_faults, score;
 
 	if (!p->numa_faults_memory)
 		return 0;

@@ -940,15 +997,32 @@ static inline unsigned long task_weight(struct task_struct *p, int nid)
 	if (!total_faults)

kernel/sched/fair.c static inline unsigned long task_weight(struct task_struct *p, int nid) · line 1006

Quoted 10 lines
kernel/sched/fair.c +6 -1
 		return 0;
 
-	return 1000 * task_faults(p, nid) / total_faults;
+	score = 1000 * task_faults(p, nid);
+	score += nearby_nodes_score(p, nid, true);
+
+	score /= total_faults;
+
+	return score;
 }

So you add an O(nr_nodes) loop to task_weight(), but that in itself is already called from O(nr_nodes) loops, yielding a total complexity of O(nr_nodes^2).

This might be fine, but algorithmic complexity should very much be a part of the changelog I think.

author
#9 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:

static inline unsigned long task_weight(struct task_struct *p, int nid) {

kernel/sched/fair.c +1 -1
-	unsigned long total_faults;
+	unsigned long total_faults, score;
 
  	if (!p->numa_faults_memory)
  		return 0;

@@ -940,15 +997,32 @@ static inline unsigned long task_weight(struct task_struct *p, int nid)
  	if (!total_faults)
  		return 0;
Quoted 12 lines

kernel/sched/fair.c static inline unsigned long task_weight(struct task_struct *p, int nid) · line 1006

Quoted 8 lines
kernel/sched/fair.c +6 -1
-	return 1000 * task_faults(p, nid) / total_faults;
+	score = 1000 * task_faults(p, nid);
+	score += nearby_nodes_score(p, nid, true);
+
+	score /= total_faults;
+
+	return score;
  }

So you add an O(nr_nodes) loop to task_weight(), but that in itself is already called from O(nr_nodes) loops, yielding a total complexity of O(nr_nodes^2).

However, it only does actual calculations for nodes that are closer by than the furthest away nodes in the system.

Hopefully on even the largest systems, that will mean an "island" of a handful of nodes, with everything else being at the same large distance.

Quoted 2 lines

This might be fine, but algorithmic complexity should very much be a part of the changelog I think.

Agreed, I do need to document this kind of thing better, if only because it gives people a chance to verify my assumptions.

maintainer
#10 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

In reply to [email protected]
Quoted 33 lines · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:
kernel/sched/fair.c +15 -3
@@ -930,7 +987,7 @@ static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
  */
 static inline unsigned long task_weight(struct task_struct *p, int nid)
 {
-	unsigned long total_faults;
+	unsigned long total_faults, score;
 
 	if (!p->numa_faults_memory)
 		return 0;

@@ -940,15 +997,32 @@ static inline unsigned long task_weight(struct task_struct *p, int nid)
 	if (!total_faults)
 		return 0;
 
-	return 1000 * task_faults(p, nid) / total_faults;
+	score = 1000 * task_faults(p, nid);
+	score += nearby_nodes_score(p, nid, true);
+
+	score /= total_faults;
+
+	return score;
 }
 
 static inline unsigned long group_weight(struct task_struct *p, int nid)
 {
-	if (!p->numa_group || !p->numa_group->total_faults)
+	unsigned long total_faults, score;
+
+	if (!p->numa_group)
+		return 0;
+
+	total_faults = p->numa_group->total_faults;
+
+	if (!total_faults)

kernel/sched/fair.c static inline unsigned long task_weight(struct task_struct *p, int nid) · line 1026

Quoted 10 lines
kernel/sched/fair.c +6 -1
 		return 0;
 
-	return 1000 * group_faults(p, nid) / p->numa_group->total_faults;
+	score = 1000 * group_faults(p, nid);
+	score += nearby_nodes_score(p, nid, false);
+
+	score /= total_faults;
+
+	return score;
 }

OK, and that's just sad..

See task_numa_placement(), which does:

	for_each_online_node(nid) {
		weight = task_weight(p, nid) + group_weight(p, nid);
		if (weight > max_weight) {
			max_weight = weight;
			max_nid = nid;
		}
	}

So not only is that loop now O(nr_nodes^2), the inner loops doubly iterates all nodes.

Also, {task,group}_weight() functions were like cheap-ish (/me mumbles something about people using !2^n scaling factors for no sane reason). And they're used all over with that in mind.

But look what you did to migrate_improves_locality(), that will now iterate all nodes _4_ times, and its called for every single task we try and migrate during load balance, while holding rq->lock.

author
#11 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

Quoted 57 lines · Peter Zijlstra
Quoted 33 lines · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:
kernel/sched/fair.c +15 -3
@@ -930,7 +987,7 @@ static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
   */
  static inline unsigned long task_weight(struct task_struct *p, int nid)
  {
-	unsigned long total_faults;
+	unsigned long total_faults, score;
 
  	if (!p->numa_faults_memory)
  		return 0;

@@ -940,15 +997,32 @@ static inline unsigned long task_weight(struct task_struct *p, int nid)
  	if (!total_faults)
  		return 0;
 
-	return 1000 * task_faults(p, nid) / total_faults;
+	score = 1000 * task_faults(p, nid);
+	score += nearby_nodes_score(p, nid, true);
+
+	score /= total_faults;
+
+	return score;
  }
 
  static inline unsigned long group_weight(struct task_struct *p, int nid)
  {
-	if (!p->numa_group || !p->numa_group->total_faults)
+	unsigned long total_faults, score;
+
+	if (!p->numa_group)
+		return 0;
+
+	total_faults = p->numa_group->total_faults;
+
+	if (!total_faults)

kernel/sched/fair.c static inline unsigned long task_weight(struct task_struct *p, int nid) · line 1026

Quoted 10 lines
kernel/sched/fair.c +6 -1
  		return 0;
 
-	return 1000 * group_faults(p, nid) / p->numa_group->total_faults;
+	score = 1000 * group_faults(p, nid);
+	score += nearby_nodes_score(p, nid, false);
+
+	score /= total_faults;
+
+	return score;
  }

OK, and that's just sad..

See task_numa_placement(), which does:

	for_each_online_node(nid) {
		weight = task_weight(p, nid) + group_weight(p, nid);
		if (weight > max_weight) {
			max_weight = weight;
			max_nid = nid;
		}
	}
Quoted 2 lines

So not only is that loop now O(nr_nodes^2), the inner loops doubly iterates all nodes.

I am not too worried about task_numa_placement, but you are right that this may well be much too expensive for more frequently called code like migrate_improves_locality.

Having said that, grouping related tasks together on nearby nodes does seem to bring significant performance gains.

Do you have any ideas on other ways we can achieve that grouping?

Quoted 9 lines

Also, {task,group}_weight() functions were like cheap-ish (/me mumbles something about people using !2^n scaling factors for no sane reason). And they're used all over with that in mind.

But look what you did to migrate_improves_locality(), that will now iterate all nodes _4_ times, and its called for every single task we try and migrate during load balance, while holding rq->lock.

maintainer
#12 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

In reply to [email protected]
Quoted 1 line · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:

This patch does nothing on machines with simple NUMA topologies.

Was this:

kernel/sched/fair.c static inline unsigned long group_faults_cpu(struct numa_group *group, int nid) · line 945

Quoted 6 lines
kernel/sched/fair.c +6 -0
+	/*
+	 * No need to calculate a score if the system has a simple NUMA
+	 * topology, with no node distances between "local" and "far away".
+	 */
+	if (max_distance == LOCAL_DISTANCE)
+		return 0;

Supposed to make that true?

It doesn't. That test is a !numa test, not a fully connected test.

author
#13 lore raw

Re: [PATCH 2/4] sched,numa: weigh nearby nodes for task placement on complex NUMA topologies

Quoted 14 lines · Peter Zijlstra
Quoted 1 line · On Thu, May 08, 2014 at 01:23:29PM -0400, [email protected] wrote:

This patch does nothing on machines with simple NUMA topologies.

Was this:

kernel/sched/fair.c static inline unsigned long group_faults_cpu(struct numa_group *group, int nid) · line 945

Quoted 6 lines
kernel/sched/fair.c +6 -0
+	/*
+	 * No need to calculate a score if the system has a simple NUMA
+	 * topology, with no node distances between "local" and "far away".
+	 */
+	if (max_distance == LOCAL_DISTANCE)
+		return 0;

Supposed to make that true?

Quoted 2 lines

It doesn't. That test is a !numa test, not a fully connected test.

Look at patch 1/4. I only set max_distance to !LOCAL_DISTANCE if the system has multiple different distances in the SLIT table.

I guess that needs to be cleaned up :)

author
#14 lore raw

PATCH 3/4 sched,numa: store numa_group's preferred nid

In reply to [email protected]

From: Rik van Riel <[email protected]>

Store a numa_group's preferred nid. Used by the next patch to pull workloads towards their preferred nodes.

Signed-off-by Rik van Riel <[email protected]>
Tested-by Chegu Vinod <[email protected]>
---
 kernel/sched/fair.c | 3 +++
 1 file changed, 3 insertions(+)
kernel/sched/fair.c +3 -0
index 5925667..99cc829 100644
@@ -864,6 +864,7 @@ struct numa_group {
 
 	spinlock_t lock; /* nr_tasks, tasks */
 	int nr_tasks;
+	int preferred_nid;
 	pid_t gid;
 	struct list_head task_list;
 

@@ -1642,6 +1643,7 @@ static void task_numa_placement(struct task_struct *p)
 
 	if (p->numa_group) {
 		update_numa_active_node_mask(p->numa_group);
+		p->numa_group->preferred_nid = max_group_nid;
 		/*
 		 * If the preferred task and group nids are different,
 		 * iterate over the nodes again to find the best place.

@@ -1701,6 +1703,7 @@ static void task_numa_group(struct task_struct *p, int cpupid, int flags,
 		spin_lock_init(&grp->lock);
 		INIT_LIST_HEAD(&grp->task_list);
 		grp->gid = p->pid;
+		grp->preferred_nid = -1;
 		/* Second half of the array tracks nids where faults happen */
 		grp->faults_cpu = grp->faults + NR_NUMA_HINT_FAULT_TYPES *
 						nr_node_ids;
Signature · 1 line
1.8.5.3
author
#15 lore raw

PATCH 4/4 sched,numa: pull workloads towards their preferred nodes

In reply to [email protected]

From: Rik van Riel <[email protected]>

Give a bonus to nodes near a workload's preferred node. This will pull workloads towards their preferred node.

For workloads that span multiple NUMA nodes, pseudo-interleaving will even out the memory use between nodes over time, causing the preferred node to move around over time.

This movement over time will cause the preferred nodes to be on opposite sides of the system eventually, untangling workloads that were spread all over the system, and moving them onto adjacent nodes.

The perturbation introduced by this patch enables the kernel to reliably untangled 2 4-node wide SPECjbb2005 instances on an 8 node system, improving average performance from 857814 to 931792 bops.

Signed-off-by Rik van Riel <[email protected]>
Tested-by Chegu Vinod <[email protected]>
---
 kernel/sched/fair.c | 25 ++++++++++++++++++++++---
 1 file changed, 22 insertions(+), 3 deletions(-)
kernel/sched/fair.c +22 -3
index 99cc829..cffa829 100644
@@ -932,7 +932,7 @@ static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
  * the proximity of those nodes.
  */
 static inline unsigned long nearby_nodes_score(struct task_struct *p, int nid,
-						bool task)
+						bool task, bool *preferred_nid)
 {
 	int max_distance = max_node_distance();
 	unsigned long score = 0;

@@ -949,6 +949,15 @@ static inline unsigned long nearby_nodes_score(struct task_struct *p, int nid,
 		int distance;
 		unsigned long faults;
 
+		/*
+		 * Pseudo-interleaving balances out the memory use between the
+		 * nodes where a workload runs, so the preferred node should
+		 * change over time. This helps separate two workloads onto
+		 * separate sides of the system.
+		 */
+		if (p->numa_group && node == p->numa_group->preferred_nid)
+			*preferred_nid = true;
+
 		/* Already scored by the calling function. */
 		if (node == nid)
 			continue;

@@ -989,6 +998,7 @@ static inline unsigned long nearby_nodes_score(struct task_struct *p, int nid,
 static inline unsigned long task_weight(struct task_struct *p, int nid)
 {
 	unsigned long total_faults, score;
+	bool near_preferred_nid = false;
 
 	if (!p->numa_faults_memory)
 		return 0;

@@ -999,7 +1009,7 @@ static inline unsigned long task_weight(struct task_struct *p, int nid)
 		return 0;
 
 	score = 1000 * task_faults(p, nid);
-	score += nearby_nodes_score(p, nid, true);
+	score += nearby_nodes_score(p, nid, true, &near_preferred_nid);
 
 	score /= total_faults;
 

@@ -1009,6 +1019,7 @@ static inline unsigned long task_weight(struct task_struct *p, int nid)
 static inline unsigned long group_weight(struct task_struct *p, int nid)
 {
 	unsigned long total_faults, score;
+	bool near_preferred_nid = false;
 
 	if (!p->numa_group)
 		return 0;

@@ -1019,7 +1030,15 @@ static inline unsigned long group_weight(struct task_struct *p, int nid)
 		return 0;
 
 	score = 1000 * group_faults(p, nid);
-	score += nearby_nodes_score(p, nid, false);
+	score += nearby_nodes_score(p, nid, false, &near_preferred_nid);
+
+	/*
+	 * Pull workloads towards their preferred node, with the minimum
+	 * multiplier required to be a tie-breaker when two groups of nodes
+	 * have the same amount of memory.
+	 */
+	if (near_preferred_nid)
+		score *= (max_node_distance() - LOCAL_DISTANCE);
 
 	score /= total_faults;
Signature · 1 line
1.8.5.3