Faster migration for automatic NUMA balancing

STREAM on 2-socket machine

                         4.19.0-rc5             4.19.0-rc5
                         numab-v1r1       noratelimit-v1r1
MB/sec copy     43298.52 (   0.00%)    44673.38 (   3.18%)
MB/sec scale    30115.06 (   0.00%)    31293.06 (   3.91%)
MB/sec add      32825.12 (   0.00%)    34883.62 (   6.27%)
MB/sec triad    32549.52 (   0.00%)    34906.60 (   7.24%

Signed-off-by Mel Gorman <[email protected]>

Rate limiting of page migrations due to automatic NUMA balancing was introduced to mitigate the worst-case scenario of migrating at high frequency due to false sharing or slowly ping-ponging between nodes. Since then, a lot of effort was spent on correctly identifying these pages and avoiding unnecessary migrations and the safety net may no longer be required.

Jirka Hladky reported a regression in 4.17 due to a scheduler patch that avoids spreading STREAM tasks wide prematurely. However, once the task was properly placed, it delayed migrating the memory due to rate limiting. Increasing the limit fixed the problem for him.

Currently, the limit is hard-coded and does not account for the real capabilities of the hardware. Even if an estimate was attempted, it would not properly account for the number of memory controllers and it could not account for the amount of bandwidth used for normal accesses. Rather than fudging, this patch simply eliminates the rate limiting.

However, Jirka reports that a STREAM configuration using multiple processes achieved similar performance to 4.16. In local tests, this patch improved performance of STREAM relative to the baseline but it is somewhat machine-dependent. Most workloads show little or not performance difference implying that there is not a heavily reliance on the throttling mechanism and it is safe to remove.

STREAM on 2-socket machine

                         4.19.0-rc5             4.19.0-rc5
                         numab-v1r1       noratelimit-v1r1
MB/sec copy     43298.52 (   0.00%)    44673.38 (   3.18%)
MB/sec scale    30115.06 (   0.00%)    31293.06 (   3.91%)
MB/sec add      32825.12 (   0.00%)    34883.62 (   6.27%)
MB/sec triad    32549.52 (   0.00%)    34906.60 (   7.24%

Signed-off-by Mel Gorman <[email protected]>

---

With this patch applied, STREAM performance is the same as 4.17 even though
processes are not spread cross-node prematurely. Other workloads showed
a mix of minor gains and losses. This is somewhat expected most workloads
are not very sensitive to the starting conditions of a process.

                         4.19.0-rc5             4.19.0-

rc5 4.17.0
numab-v1r1 fastmigrate-
v1r1 vanilla
MB/sec copy 43298.52 ( 0.00%) 47335.46
( 9.32%) 47219.24 ( 9.06%)
MB/sec scale 30115.06 ( 0.00%) 32568.12
( 8.15%) 32527.56 ( 8.01%)
MB/sec add 32825.12 ( 0.00%) 36078.94
( 9.91%) 35928.02 ( 9.45%)
MB/sec triad 32549.52 ( 0.00%) 35935.94
( 10.40%) 35969.88 ( 10.51%)

Signed-off-by Mel Gorman <[email protected]>

kernel/sched/fair.c +2 -0

index 25c7c7e09cbd..7fc4a371bdd2 100644
@@ -1392,6 +1392,17 @@ bool should_numa_migrate_memory(struct task_struct *p, struct page * page,
 	int last_cpupid, this_cpupid;
 
 	this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
+	last_cpupid = page_cpupid_xchg_last(page, this_cpupid);
+

Quoted 8 lines

kernel/sched/fair.c +0 -0

index 25c7c7e09cbd..7fc4a371bdd2 100644
@@ -1392,6 +1392,17 @@ bool should_numa_migrate_memory(struct task_struct *p, struct page * page,
 	int last_cpupid, this_cpupid;
 

kernel/sched/fair.c bool should_numa_migrate_memory(struct task_struct *p, struct page * page, · line 1406

Quoted 13 lines

kernel/sched/fair.c +11 -0

 	this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
+	last_cpupid = page_cpupid_xchg_last(page, this_cpupid);
+
+	/*
+	 * Allow first faults or private faults to migrate immediately early in
+	 * the lifetime of a task. The magic number 4 is based on waiting for
+	 * two full passes of the "multi-stage node selection" test that is
+	 * executed below.
+	 */
+	if ((p->numa_preferred_nid == -1 || p->numa_scan_seq <= 4) &&
+	    (cpupid_pid_unset(last_cpupid) || cpupid_match_pid(p, last_cpupid)))
+		return true;
 

This does have issues when using with workloads that access more shared faults than private faults.

In such workloads, this change would spread the memory causing regression in behaviour.

5 runs of on 2 socket/ 4 node power 8 box

Without this patch

./numa01.sh      Real:  382.82    454.29    422.31    29.72
./numa01.sh      Sys:   40.12     74.53     58.50     13.37
./numa01.sh      User:  34230.22  46398.84  40292.62  4915.93

With this patch

./numa01.sh      Real:  415.56    555.04    473.45    51.17    -10.8016%
./numa01.sh      Sys:   43.42     94.22     73.59     17.31    -20.5055%
./numa01.sh      User:  35271.95  56644.19  45615.72  7165.01  -11.6694%

Since we are looking at time, smaller numbers are better.

SPECJbb did show some small loss and gains.

Our numa grouping is not fast enough. It can take sometimes several iterations before all the tasks belonging to the same group end up being part of the group. With the current check we end up spreading memory faster than we should hence hurting the chance of early consolidation.

Can we restrict to something like this?

if (p->numa_scan_seq >=MIN && p->numa_scan_seq <= MIN+4 &&

    (cpupid_match_pid(p, last_cpupid)))
	return true;

meaning, we ran atleast MIN number of scans, and we find the task to be most likely task using this page.

Quoted 4 lines

This does have issues when using with workloads that access more shared faults than private faults.

Not as such. It can have issues on workloads where memory is initialised by one thread, then additional threads are created and access the same memory. They are not necessarily shared once buffers are handed over. In such a case, migrating quickly is the right thing to do. If it's truely shared pages then there may be some unnecessary migrations early in the lifetime of the task but it'll settle down quickly enough.

Is it just numa01 that was affected for you? I ask because that particular workload is an averse workload on any machine with more than sockets and your machine description says it has 4 nodes. What it is testing is quite specific to 2-node machines.

Quoted 2 lines

SPECJbb did show some small loss and gains.

That almost always shows small gains and losses so that's not too surprising.

Quoted 11 lines

Our numa grouping is not fast enough. It can take sometimes several iterations before all the tasks belonging to the same group end up being part of the group. With the current check we end up spreading memory faster than we should hence hurting the chance of early consolidation.

Can we restrict to something like this?

if (p->numa_scan_seq >=MIN && p->numa_scan_seq <= MIN+4 &&

    (cpupid_match_pid(p, last_cpupid)))
	return true;

Quoted 3 lines

meaning, we ran atleast MIN number of scans, and we find the task to be most likely task using this page.

What's MIN? Assuming it's any type of delay, note that this will regress STREAM again because it's very sensitive to the starting state.

Quoted 5 lines

Quoted 4 lines

This does have issues when using with workloads that access more shared faults than private faults.

Quoted 7 lines

Not as such. It can have issues on workloads where memory is initialised by one thread, then additional threads are created and access the same memory. They are not necessarily shared once buffers are handed over. In such a case, migrating quickly is the right thing to do. If it's truely shared pages then there may be some unnecessary migrations early in the lifetime of the task but it'll settle down quickly enough.

Do you have a workload recommendation to try for shared fault accesses.

Quoted 17 lines

Quoted 16 lines

<SNIP>

Our numa grouping is not fast enough. It can take sometimes several iterations before all the tasks belonging to the same group end up being part of the group. With the current check we end up spreading memory faster than we should hence hurting the chance of early consolidation.

Can we restrict to something like this?

if (p->numa_scan_seq >=MIN && p->numa_scan_seq <= MIN+4 &&

    (cpupid_match_pid(p, last_cpupid)))
	return true;

meaning, we ran atleast MIN number of scans, and we find the task to be most likely task using this page.

Quoted 3 lines

What's MIN? Assuming it's any type of delay, note that this will regress STREAM again because it's very sensitive to the starting state.

I was thinking of MIN as 3 to give a chance for things to settle. but that might not help STREAM as you pointed out.

Do you have a hint on which commit made STREAM regress?

if we want to prioritize STREAM like workloads (i.e private faults) one simpler fix could be to change the quadtraic equation

from:

	if (!cpupid_pid_unset(last_cpupid) &&
				cpupid_to_nid(last_cpupid) != dst_nid)
		return false;
to:
	if (!cpupid_pid_unset(last_cpupid) &&
				cpupid_to_nid(last_cpupid) == dst_nid)
		return true;

i.e to say if the group tasks likely consolidated to a node or the task was moved to a different node but access were private, just move the memory.

The drawback though is we keep pulling memory everytime the task moves across nodes. (which is probably restricted for long running tasks to some extent by your fix)

Quoted 12 lines

if we want to prioritize STREAM like workloads (i.e private faults) one simpler fix could be to change the quadtraic equation

from:

	if (!cpupid_pid_unset(last_cpupid) &&
				cpupid_to_nid(last_cpupid) != dst_nid)
		return false;
to:
	if (!cpupid_pid_unset(last_cpupid) &&
				cpupid_to_nid(last_cpupid) == dst_nid)
		return true;

Quoted 7 lines

i.e to say if the group tasks likely consolidated to a node or the task was moved to a different node but access were private, just move the memory.

The drawback though is we keep pulling memory everytime the task moves across nodes. (which is probably restricted for long running tasks to some extent by your fix)

This has way more consequences as it changes the behaviour for the entire lifetime of the workload. It could cause excessive migrations in the case where a machine is almost fully utilised and getting load balanced or in cases where tasks are pulled frequently cross-node (e.g. worker thread model or a pipelined computation).

I'm only looking to address the case where the load balancer spreads a workload early and the memory should move to the new node quickly. If it turns out there are cases where that decision is wrong, it gets remedied quickly but if your proposal is ever wrong, the system doesn't recover.

I will try to get a DayTrader run in a day or two. There JVM and db threads act on the same memory, I presume it might show some insights.

Quoted 2 lines · Srikar Dronamraju

I will try to get a DayTrader run in a day or two. There JVM and db threads act on the same memory, I presume it might show some insights.

I ran 2 runs of daytrader 7 with and without patch on a 2 node power9 PowerNv box.
https://github.com/WASdev/sample.daytrader7
In each run, has 8 JVMs.

Throughputs (Higher are better)
Without patch 19216.8 18900.7 Average: 19058.75
With patch 18644.5 18480.9 Average: 18562.70

Difference being -2.6% regression

Quoted 2 lines · Srikar Dronamraju

* Srikar Dronamraju <[email protected]> [2018-10-02 23:00:05]:

That's unfortunate.

How much does this workload normally vary between runs? If you monitor migrations over time, is there an increase spike in migration early in the lifetime of the workload?