Skip to contentSkip to conversation

Migrate pages from a ccNUMA node to another

DISCUSSION Zoltan Menyhart 4 participants 6 messages Mar 26, 2004 – Mar 30, 2004

lore
Share & tools
lore
#2 lore raw
In reply to Robin Holt
Quoted 8 lines · On Fri, 26 Mar 2004 04:39:59 -0600 Robin Holt <[email protected]> wrote:

One thing that would probably help considerably, in addition to the syscall you seem to be proposing, would be an addition to the task_struct. The new field would specify which node to attempt allocations on. Before doing a fork, the parent would do a syscall to set this field to the node the child will target. It would then call fork. The PGDs et al and associated memory, including the task struct and pages would end up being allocated based upon that numa node's allocation preference.

You just described the process policy of NUMA API.

-Andi

#0 lore raw

Migrate pages from a ccNUMA node to another.
======================

Version 0.1, 25th of March 2004
By Zoltan Menyhart, Bull S.A. <[email protected]> The usual GPL applies.

What is it all about ?
----------------------

The old golden days of the Symmetrical Multi-Processor systems are over. Gone forever.
We are left with (cache coherent) Non Uniform Memory Architectures. I can see the future.
I can see systems with hundreds, thousands of processors, with less and less uniform memory architectures.
The "closeness" of a processor to its working set of memory will have the most important effect on the performance.

You can make use of the forthcoming NUMA APIs to set up your NUMA environment:
to bind processes to (groups of ) processors, to define the memory placement policy, etc.

Yes, the initial placement is very much important. It affects tremendously the performance you obtain.

Yet, what if
- the application changes its behavior over time ?
(which processor uses which part of the memory)
- you have not got the source of the application ?
- you cannot add the NUMA services to it ?
- you are not authorized to touch it ? (e.g. it is a reference benchmark)

Page migration tries to help you out in these situations.

What can this service do ?
--------------------------

- Migrate pages identified by their physical addresses to another NUMA node
- Migrate pages of a virtual user address range to another NUMA node

How can it be used ?
--------------------

1. Hardware assisted migration
..............................

As you can guess, it is very much platform dependent.
I can only give you an example. Any advice on how to define a platform independent interface will be appreciated.

We've got an Intel IA64 based machine for development / testing.
It consists of 4 "Tiger boxes" connected together by a pair of Scalability Port Switches. A "Tiger box" is built around a Scalable Node Controller (SNC), and includes 4 Itanium-2 processors and some Gbytes of memory.
The NUMA factor is 1 : 2.25.
The SNC contains 2048 counters which allow us to count how many times these 2048 zones of memory are touched from each node in a given observation period. An "artificial intelligence" can make predictions from these usage statistics and decide what pages are to be migrated and where.

(Unfortunately, the SNCs are buggy - even the version C.1 is - we've got to use a couple of work-arounds, much of the work has to be done in software. This wastes about 10 seconds of CPU time while executing a benchmark of 2 minutes. I hope, one day...)

2. Application driven migration
...............................

An application can exploit the forthcoming NUMA APIs to specify its initial memory placement policy.
Yet what if the application wants to change its behavior ?

Allocating room on the destination node, copying the data by the application itself, and finally freeing the original room of the data is not very efficient.

An application can ask the migration service to move a range of its virtual address space to the destination node.

Example:
A process of an application prepares a huge amount of data and hands it over to Its fellow processes (which happen to be bound to another NUMA node) for their (almost) exclusive usage.
Migrating a page costs 128 remote accesses (assuming a page size of 16 Kbytes and a bus transaction size of 128 bytes) + some administration. Assuming the consumers of the data will frequently touch the page (cache misses) a considerable number of times, say more that 1000 times, then the migration becomes largely profitable.

3. NUMA aware scheduler
.......................

A NUMA aware scheduler tries to keep processes on their "home" node where they have allocated (most of) their memory. What if the processors in this node are overloaded while several processors in the other nodes are largely in idle ?

Should the scheduler select some other processors in the other nodes to execute these processes, at the expense of considerable number of extra node transactions ?
Or should the scheduler leave the processors in the other nodes doing nothing ? Or should it move some processes with their memory working set to another node ? Let's leave this dilemma for the NUMA aware scheduler for the moment.

Once the scheduler has made up its mind, the migration service can move the working set of memory of the selected processes to their new "home" node.

User mode interface
-------------------

This prototype of the page migration service is implemented as a system call, the different forms of which are wrapped by use of some small, static, inline functions.

NAME
migrate_ph_pages - migrate pages to another NUMA node
migrate_virt_addr_range - migrate virtual address range to another node

SYNOPSIS

#include <sys/types.h>
#include "page_migrate.h"

int migrate_ph_pages(
const phaddr_t * const table, const size_t length,
const int node,
struct _un_success_count_ * const p, const pid_t pid);

int migrate_virt_addr_range(
const caddr_t address,
const size_t length,
const int node,
struct _un_success_count_ * const p, const pid_t pid);

DESCRIPTION

The "migrate_ph_pages()" system call is used to migrate pages - their physical addresses of "phaddr_t" type are given in "table" - to "node". "length" indicates the number of the physical addresses in "table" and should not be greater than "PAGE_SIZE / sizeof(phaddr_t)". Only the pages belonging to the process indicated by "pid" and its child processes cloned via "clone2(CLONEVM)" are treated, the other processes' pages are silently ignored.

The "migrate_virt_addr_range()" system call is used to migrate pages of a virtual address range of "length" starting at "address" to "node". The virtual address range belongs to the process indicated by "pid" and to its cloned children. If "pid" is zero then the current process's virtual address range is moved.

Some statistics are returned via "p":

struct _un_success_count_ {
unsigned int successful; // Pages successfully migrated
unsigned int failed; // Minor failures
};

RETURN VALUE

"migrate_ph_pages()" and "migrate_virt_addr_range()" return 0 on success, or -1 if a major error occurred (in which case, "errno" is set appropriately). Minor errors are silently ignored (migration continues with the rest of the pages).

ERRORS

        ENODEV:         illegal destination node
        ESRCH:          no process of "pid" can be found
        EPERM:          no permission
        EINVAL:         invalid system call parameters
        EFAULT:         illegal virtual user address
        ENOMEM:         cannot allocate memory

RESTRICTIONS

We can migrate a page if it belongs to a single "mm_struct" / PGD, i.e. it is private to a process or shared with its child processes cloned via "clone2(CLONEVM)".

Notes:

- A "major error" prevents us from carrying on the migration, but it is not a real error for the "victim" application that can continue (it is guaranteed not to be broken). The pages already migrated are left in their new node.

- Migrating a page shared among other than child processes cloned via "clone2(CLONEVM)" would require locking all the page owners' PGDs. I've got serious concerns about locking more than one PGDs:
+ It is not foreseen in the design of the virtual memory management.
+ Obviously, the PGDs have to be "trylock()"-ed in order to avoid dead locks. However, "trylock()"-ing lots of PGDs, possibly thousands of them, would lead to starvation problems. A performance enhancement tool consuming so much in the event of not concluding...

Some figures
------------

One of our customers has an OpenMP benchmark which was used to measure the machine described above. It uses 1 Gbytes of memory and runs on 16 processors, on 4 NUMA nodes.

If the benchmark is adapted to our NUMA architecture, then it takes 86 seconds to complete.

As results are not accepted if obtained by modifying the benchmark in any way, the best we can do is to use a random or round robin memory allocation policy. We end up with a locality rate of 25 % and the benchmark executes in 121 seconds.

If we had a zero-overhead migration tool, then - I estimate - it would complete In 92 seconds (the benchmark starts in a "pessimized" environment, and it takes time for the locality ramp up from 25 % to almost 100 %).

Actually it takes 2 to 3 seconds to move 750 Mbytes of memory (on a heavily loaded machine), reading out the counters of the SNCs and making some quick decisions take 1 to 2 seconds, and we lose about 10 seconds due to the buggy SNCs. We end up with 106 seconds.

Some if's
---------

- if the benchmark used more memory, then it would be more expensive to migrate all of it's pages
- if the benchmark ran for longer without changing its memory usage pattern, then it could spend a greater percentage of its lifetime in a well localized environment
- if you had a NUMA factor higher than ours, then obviously, you would gain more in performance by use of the migration service
- if we used Madison processors with 6 Mbytes of cache (twice as much we have right now), then the NUMA factor would be masked more efficiently
- if the clock frequency of the processors increases, then you run out of cached data more quickly and the NUMA factor becomes a higher performance cut factor

TODOs
------

As I have not got access to machines other than IA64 based ones, any help to test page migration on other architectures will be appreciated.

I include some demo programs:
.............................

test/ph.c: migrates some of its pages by use of their physical addresses
test/v.c: migrates a part of its virtual address range
test/vmig.c: migrates a part of the virtual address range of "test/victim.c"
test/migstat.c: displays some internal counters if the kernel has been compiled
with "_NEED_STATISTICS_" defined

I'll send the patch in the next letter.
Should the list refuse the patch due to its length, please pick it up at our anonymous FTP server: ftp://visibull.frec.bull.fr/pub/linux/migration

The patch is against:

	patch-2.6.4.-bk4 
	kdb-v4.3-2.6.3-common-b0
	kdb-v4.3-2.6.3-ia64-1

Your remarks will be appreciated.

Zoltan Menyhart

#1 lore raw
Quoted 7 lines · Zoltan Menyhart

Migrate pages from a ccNUMA node to another.
======================

1. Hardware assisted migration
..............................

We have found that "automatic" migration ends to result in the system deciding to move the wrong pieces around. Since applications can be so varied, I would recommend we let the application decide when it thinks it is beneficial to move a memory range to a nearby node.

Quoted 7 lines

2. Application driven migration
...............................

An application can exploit the forthcoming NUMA APIs to specify its initial memory placement policy.
Yet what if the application wants to change its behavior ?

The placement policy doesn't really fit the bill entirely. We are currently tracking a problem with repeatability of a benchmark. We found that the newer libc we are using used to result in a newly forked process touching a page before the parent did and therefore the page, which had been marked COW, would, on the old libc end up on the childs node for the child and parents node for the parent. After the update, both pages ended up on the parents.

If you syscall would simply do the copy to the destination node for COW pages, this would have worked terrifically in both cases.

Quoted 4 lines

3. NUMA aware scheduler
.......................

Back to my earlier comment about magic. This is a second tier of magic. Here we are talking about infering a reason to migrate based on memory access patterns, but what if that migration results in some other process being hurt more than this one is helped.

Honestly, we have beaten on the scheduler quite a bit and the "allocate memory close to my node" has helped considerably.

One thing that would probably help considerably, in addition to the syscall you seem to be proposing, would be an addition to the task_struct. The new field would specify which node to attempt allocations on. Before doing a fork, the parent would do a syscall to set this field to the node the child will target. It would then call fork. The PGDs et al and associated memory, including the task struct and pages would end up being allocated based upon that numa node's allocation preference.

What do you think of combining these two items into a single syscall?

Quoted 10 lines

User mode interface
-------------------

This prototype of the page migration service is implemented as a system call, the different forms of which are wrapped by use of some small, static, inline functions.

NAME
migrate_ph_pages - migrate pages to another NUMA node

At first, I thought "Wow, this could result in some nice admin tools." The more I scratch my head on this, the less useful I see it, but would not argue against it.

Quoted 1 line

migrate_virt_addr_range - migrate virtual address range to another node

This one sounds good.

Thanks,
Robin Holt

#3 lore raw
Quoted 6 lines · Robin Holt

We have found that "automatic" migration ends to result in the system deciding to move the wrong pieces around. Since applications can be so varied, I would recommend we let the application decide when it thinks it is beneficial to move a memory range to a nearby node.

I am not saying it is for every application
(see the paragraph of the "if's").
There are a couple of applications which run for long time, with relatively stable memory working sets. And I can help them. You launch your application with and without, and you use if you gain enough.

Quoted 7 lines

The placement policy doesn't really fit the bill entirely. We are currently tracking a problem with repeatability of a benchmark. We found that the newer libc we are using used to result in a newly forked process touching a page before the parent did and therefore the page, which had been marked COW, would, on the old libc end up on the childs node for the child and parents node for the parent. After the update, both pages ended up on the parents.

I haven't modified anything in the existing page fault handler. Nor I've changed the placement policy.
You need to specify explicitly where the pages go for my proposed syscall.

Quoted 2 lines

If you syscall would simply do the copy to the destination node for COW pages, this would have worked terrifically in both cases.

The COW pages are referenced by more than one PGDs (by that of the parent and its children). As I state in RESTRICTIONS, I skip these pages.

I think this issue with the COW pages is a fork() - exec() placement problem, i do not address it with my stuff.

Quoted 22 lines
Quoted 4 lines

3. NUMA aware scheduler
.......................

Back to my earlier comment about magic. This is a second tier of magic. Here we are talking about infering a reason to migrate based on memory access patterns, but what if that migration results in some other process being hurt more than this one is helped.

Honestly, we have beaten on the scheduler quite a bit and the "allocate memory close to my node" has helped considerably.

One thing that would probably help considerably, in addition to the syscall you seem to be proposing, would be an addition to the task_struct. The new field would specify which node to attempt allocations on. Before doing a fork, the parent would do a syscall to set this field to the node the child will target. It would then call fork. The PGDs et al and associated memory, including the task struct and pages would end up being allocated based upon that numa node's allocation preference.

Quoted 1 line

What do you think of combining these two items into a single syscall?

I can agree with Robin Holt, it's NUMA API issue.
I just give a tool, if someone somehow knows that this piece of memory would be better on another node, I can do it.

Quoted 6 lines
Quoted 2 lines

NAME
migrate_ph_pages - migrate pages to another NUMA node

At first, I thought "Wow, this could result in some nice admin tools." The more I scratch my head on this, the less useful I see it, but would not argue against it.

We are working on the prototype of a device driver to read out the "hot page" counters on n-th Scalable Node Controller
(say: "/dev/snc/n/hotpage").
An "artificial intelligence" can guess what to move and calls this service.

BTW Has someone a machine with a chip set other than i82870 ?

Thanks,

Zoltan Menyhart

#4 lore raw
In reply to Zoltan Menyhart

Szia Zoltan,

I like the aproach very much and was hoping that someone will bring on-demand page migration to Linux.

Quoted 1 line

- Migrate pages identified by their physical addresses to another NUMA node

You want this only for your "AI" keeping track of the hw counters in the chipset? I hope you can teach it to keep track of the bandwidth of all processes on the machine, otherwise it might disturb the processes more than it helps them... and waste the machine's bandwidth with migrating pages.

Quoted 1 line

- Migrate pages of a virtual user address range to another NUMA node

This is good. I'm thinking about the rss/node patches, they would tell you when you should think about migrating something for a process. My current usage model would be simpler: for a given mm migrate all pages currently on node A to node B. But the flexibility of your API will certainly not remain unused.

...

Quoted 1 line

BTW Has someone a machine with a chip set other than i82870 ?

??? As far as I know SGI, HP, NEC and IBM have all their own NUMA chipsets for IA64. Was this the question? Are you looking for hardware counters?

Regards,
Erich

#5 lore raw
Quoted 9 lines · Erich Focht

Szia Zoltan,

Quoted 1 line

- Migrate pages identified by their physical addresses to another NUMA node

You want this only for your "AI" keeping track of the hw counters in the chipset? I hope you can teach it to keep track of the bandwidth of all processes on the machine, otherwise it might disturb the processes more than it helps them... and waste the machine's bandwidth with migrating pages.

Szervusz Erich,

I put AI between quotation marks because it is not a real intelligence. It should not waste much time on being intelligent :-)
At least we have not managed to find out a general purpose solution that could cope with no matter what application.
We try to tune parameters, like sampling period / time, how many pages are checked, when we consider a page as "hot", how many % or # cycles distant vs. local justifies the migration...
We try to set up a "profile" for an application.
The launcher of the application takes into account the profile and the AI evaluates the HW counters according this profile info. I think most of the huge applications of our clients will run several times with different data but with the data of similar behavior. The clients will have the ability to tune their application profiles.

Quoted 6 lines
Quoted 1 line

- Migrate pages of a virtual user address range to another NUMA node

This is good. I'm thinking about the rss/node patches, they would tell you when you should think about migrating something for a process. My current usage model would be simpler: for a given mm migrate all pages currently on node A to node B. But the flexibility of your API will certainly not remain unused.

You should migrate if it worth the cost of the migration to do (private malloc()-ed data, stack,...).

Do you mean to guess in the kernel what pages to move ?

I need "real information" :-)) to decide, this is either I ask the HW or I wait the application to tell me its requirement.

Quoted 4 lines
Quoted 1 line

BTW Has someone a machine with a chip set other than i82870 ?

??? As far as I know SGI, HP, NEC and IBM have all their own NUMA chipsets for IA64. Was this the question? Are you looking for hardware counters?

I'd like to know - and someone to try :-)) - how much it costs on another chip set to measure the page usage statistics, say for 1 Gbytes of memory...

Thanks,

Zoltán