[patch[ Simple Topology API

Comment from the x86-64 side:

Current x86-64 NUMA essentially has no 'nodes', just each CPU has local memory that is slightly faster than remote memory. This means the node number would be always identical to the CPU number. As long as the API provides it's ok for me. Just the node concept will not be very useful on that platform. memblk will also be identity mapped to node/cpu.

Some way to tell user space about memory affinity seems to be useful, but...

General comment:

I don't see what the application should do with the memblk concept currently. Just knowing about it doesn't seem too useful.
Surely it needs some way to allocate memory in a specific memblk to be useful? Also doesn't it need to know how much memory is available in each memblk? (otherwise I don't see how it could do any useful partitioning)

-Andi

[ I've been off-line for a week, so I didn't follow all of the discussion,
but here goes anyway ]

The whole "node" concept sounds broken. There is no such thing as a node, since even within nodes latencies will easily differ for different CPU's if you have local memories for CPU's within a node (which is clearly the only sane thing to do).

If you want to model memory behaviour, you should have memory descriptors (in linux parlance, "zone_t") have an array of latencies to each CPU. That latency is _not_ a "is this memory local to this CPU" kind of number, that simply doesn't make any sense. The fact is, what matters is the number of hops. Maybe you want to allow one hop, but not five.

Then, make the memory binding interface a function of just what kind of latency you allow from a set X of CPU's. Simple, straightforward, and it has a direct meaning in real life, which makes it unabiguous.

So your "memory affinity" system call really needs just one number: the acceptable latency. You may also want to have a CPU-set argument, although I suspect that it's equally correct to just assume that the CPU-set is the set of CPU's that the process can already run on.

After that, creating a new zone array is nothing more than:

- give each zone a "latency value", which is simply the minimum of all the latencies for that zone from CPU's that are in the CPU set.

- sort the zone array, lowest latency first.

- the passed-in latency is the cut-off-point - clear the end of the array (with the sanity check that you always accept one zone, even if it happens to have a latency higher than the one passed in).

End result: you end up with a priority-sorted array of acceptable zones. In other words, a zone list. Which iz _exactly_ what you want anyway (that's what the current "zone_table" is.

And then you associate that zone-list with the process, and use that zone-list for all process allocations.

Advantages:

- very direct mapping to what the hardware actually does

- no complex data structures for topology

- works for all topologies, the process doesn't even have to know, you can trivially encode it all internally in the kernel by just having the CPU latency map for each memory zone we know about.

Disadvantages:

- you cannot create "crazy" memory bindings. You can only say "I don't want to allocate from slow memory". You _can_ do crazy things by initially using a different CPU binding, then doing the memory binding, and then re-doing the CPU binding. So if you _want_ bad memory bindings you can create them, but you have to work at it.

- we have to use some standard latency measure, either purely time-based (which changes from machine to machine), or based on some notion of "relative to local memory".

My personal suggestion would be the "relative to local memory" thing, and call that 10 units. So a cross-CPU (but same module) hop might imply a latency of 15, which a memory access that goes over the backbone between modules might be a 35. And one that takes two hops might be 55.

So then, for each CPU in a machine, you can _trivially_ create the mapping from each memory zone to that CPU. And that's all you really care about.

No?

Linus

I basically agree, but then when you go for a full graph everything becomes very complex. It's not clear if that much detail is useful for the application.

Hmm - that could be a problem for applications that care less about latency, but more about equal use of bandwidth (see below). They just want their datastructures to be spread out evenly over all the available memory controllers. I don't see how that could be done with a single latency value; you really need some more complete idea about the topology.

At least on Hammer the latency difference is small enough that caring about the overall bandwidth makes more sense.

That's the basic idea sure for normal allocations from applications that do not care much about NUMA.

But "numa aware" applications want to do other things like:
- put some memory area into every node (e.g. for the numa equivalent of per CPU data in the kernel)
- "stripe" a shared memory segment over all available memory subsystems (e.g. to use memory bandwidth fully if you know your interconnect can take it; that's e.g. the case on the Hammer)

As I understood it this API is supposed to be the base of such an NUMA API for applications (just offer the information, but no way to use it usefully yet)

More comments from the NUMA gurus please.

-Andi

I agree. I will have to look closer but unless there is more juice than I have seen in Hyper-Transport it is going to become one of the architectural bottlenecks of the Hammer.

Currently you get 1600MB/s in a single direction. Not to bad. But when the memory controllers get out to dual channel DDR-II 400, the local bandwidth to that memory is 6400MB/s, and the bandwidth to remote memory 1600MB/s, or 3200MB/s (if reads are as common as writes).

So I suspect bandwidth intensive applications will really benefit from local memory optimization on the Hammer. I can buy that the latency is negligible, the fact the links don't appear to scale in bandwidth as well as the connection to memory may be a bigger issue.

The latter I really quite believe. Even dual channel PC2100 can exceed your interprocessor bandwidth.

And yes I have measured 2000MB/s memory copy with an Athlon MP and PC2100 memory.

Eric

That's on an 8-bit channel, as used on Clawhammer (AMD's lower cost CPU for desktop market). The spec allows 2, 4, 6, 16 or 32-bit channels. If I recall correctly, the AMD presentation at OLS said Sledgehammer (server market) uses 16-bit.

I'm not so sure. Clawhammer has two links, can do dual-CPU. One link to the other CPU, one for I/O. Latency may well be negligible there.

Sledgehammer has three links, can do no-glue 4-way with each CPU using two links to talk to others, one for I/O.

    I/O -- A ------ B -- I/O
           |        |
           |        |
    I/O -- C ------ D -- I/O

They can also go to no-glue 8-way:

I/O -- A ------ B ------ E ------ G -- I/O
| | | |
| | | |
I/O -- C ------ D ------ F ------ H -- I/O

I suspect latency may become an issue when more than one link is involved and there can be contention.

Beyond 8-way, you need glue logic (hypertransport switches?) and latency seems bound to become an issue.

According to the AMD talk at OLS, worst case on a 4-way is better than current best-case on a uniprocessor athlon.

Nope. Just extend the ladder. Each cpu talks to three other entities, either cpu or I/O. Can be extended arbitrarily until latencies are too high.

Chris

Chris Friesen                    | MailStop: 043/33/F10  
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: [email protected]

Thanks, my confusion. The danger is of having more bandwidth to memory than to other processors is still present, but it may be one of those places where the cpu designers are able to stay one step ahead of the problem. I will definitely agree the problem goes away for the short term with a 32bit link.

I think the 8-way topology is a little more interesting than presented. But if not it does look like you can run into issues. The more I look at it there appears to be a strong dynamic balance in the architecture between having just enough bandwidth, and low enough latency not to become a bottleneck, and having a low hardware cost.

Beyond 8-way you get into another system architecture entirely, which should be considered on it's own merits. In large part cache directories and other very sophisticated techniques are needed when you scale a system beyond the SMP point. As long as the inter-cpu bandwidth is >= the memory bandwidth on a single memory controller Hammer can probably get away with being just a better SMP, and not really a NUMA design.

Eric

IIRC

I/O -- A ------ B ------ E ------ G -- I/O
| \ / |
| \ / |
| XX |
| / \ |
| / \ |
I/O -- C ------ D ------ F ------ H -- I/O

Where B is connected to F and D to E. Obviously this setup has a maximum hop count of 3 from any cpu to any other cpu, as opposed to a maximum hop count of 4 for the simple ladder.

regards,

Rik

	http://www.linuxsymposium.org/2002/
"You're one of those condescending OLS attendants"
"Here's a nickle kid.  Go buy yourself a real t-shirt"

http://www.surriel.com/		http://distro.conectiva.com/

Whilst I don't have a definitive diagram, the "back of a napkin" sketches we came up with at an OLS dinner looked like this:

I/O -- A ------ B ---- E ------ G -- I/O
| \/ |
| /\ |
I/O -- C ------ D ---- F ------ H -- I/O

(please excuse my poor artistic skills). That reduces the max hops from 4 to 3 (if I haven't screwed something up).

M.

Define a node as a group of CPUs with the same set of latencies to memory. Then you get something that makes sense for everyone, and reduces the storage of duplicated data. If your latencies for each CPU are different, define a 1-1 mapping between nodes and CPUs. If you really want to store everthing for each CPU, that's fine.

I can't help thinking that we'd be better off making the mechanism as generic as possible, and not trying to predict all the wierd and wonderful things people might want to do (eg striping), then implement what you describe as a policy decision.

M.

If you're saying local memories for *each* CPU within a node, then no, that is not the only sane thing to do. There are some architectures that do, and some that do not. The Hammer architecture, to the best of my knowledge, has memory hanging off of each CPU, however, NUMA-Q, the main one I work with, has local memory for each group of 4 CPUs. If you're speaking only of node-local memory, ie: memory local to all the CPUs on the 'node', then all local CPUs should have the same latency to that memory.

I mostly agree with you here, except I really do believe that we should use the node abstraction. It adds little overhead, but buys us a good bit. Nodes, according to the API, are defined on a per-arch basis, allowing for us to sanely define nodes on our NUMA-Q hardware (node==4cpus), AMD people to sanely define nodes on there hardware (node==cpu), and others to define nodes to whatever they want. We will avoid redundant data in many cases, and in the simplest case, this defaults to your node==cpu behavior anyway. If we do use CPU-Mem latencies, the NUMA-Q platform (and I'm sure others) would only be able to distinguish between local and remote CPUs, not individual remote CPUs.

It seems as though you'd be throwing out some useful data. For example, imagine you have a 2 quad NUMAQ system. Each quad contains 4 CPUs and a block of memory. Now if use all of the CPUs as our CPU set, zone 0 (memory block on quad 0) will have a latency of 1 (b/c it is one hop from the first 4 cpus), as will zone 1 (memory block on quad 1), b/c it is one hop from the second 4 cpus.
Now it would appear that since these zones both have the same latency, they
would be eqally good choices. This isn't true, since if the process is on CPU 0-3, it should allocate on zone 0, and vice versa for CPUs 4-7. Latency shouldn't be the ONLY way to make decisions.

For some architectures, but for some it isn't.

Agreed.

True, but the point of this is API is to allow for processes that *DO* want to know to make intelligent decisions! Those that don't care, can still go on, blissfully unaware they are on a NUMA system.

Why limit the process? The overhead is so small to allow processes to do anything they want, why not allow them?

Absolutely true. I think that the "relative to local memory" is a great measuring stick. It is pretty much platform agnostic, assuming every platform has some concept of "local" memory.

I basically think that we should give processes that care the ability to do just about anything they want, no matter how crazy... Most processes will never even attempt to look at their default bindings, never mind change them. Plus, were making mechanism decisions that will (hopefully) be around for some time. I'm sure people will come up with things we can't even imagine, so the more powerful the API the better.

<prepares to stop, drop, and roll>

-Matt

How NUMA binding APIs have been used successfully is for a group of processes to all decide to "hang out" together in the same vicinity so that they can optimize access to shared memory. In existing NUMA systems, this has been deciding to execute on a subset of the nodes. In a system with 4 nodes, on NUMAQ machines, the latency is either local or remote. Thus if one sets a binding/latency argument such that remote accesses are allowed, then all of the nodes are fair game, otherwise only the local node is used. So a set of processes decides to occupy two nodes. Using strictly a latency argument, there is no way to specify this. One could use cpu binding to restrict the processes to the two nodes, but not the memory - unless you now associate cpus with memory/nodes and are back to maintaining topology info.

Another shortcoming of latency based binding is if a process executes on a node for awhile, then gets moved to another node. In that case the best memory allocation depends on several factors. The first is to determine where we measure latency from - the node the process is currently executing or where it had been executing? From a scheduling perspective we are playing with the idea of a home node. If a process is dispatched off of the home node should memory allocations come from the home node or the current node? If neither has available memory should latency be considered from home or current?

The other way that memory binding has been used is for a large process, typically a database, to want control over where it places memory and data structures. It is not a latency issue, but rather one of how the work is distributed across the system.

The memory binding that Matt proposed allows an architecture to define what a memory block is, and the application to determine how it wants to bind to the memory blocks. It is only intended for use by applications that are aware of the complexities involved, and these will have to be knowledgeable about the systems that they are on. Hopefully, by default, Linux will do the right things as far as memory placement for processes that choose to leave it up to the system - which will be the majority of apps. However, the apps that want to specify their memory placement, want the ability to have explicit control over the nodes it lands on. It is not strictly a latency based decision.

Michael

Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486

That shouldn't be a problem at all. Since each architecture is responsible for defining the 5 main topology functions, you could do this:

#define _cpu_to_node(cpu) (cpu)
#define _memblk_to_node(memblk) (memblk)
#define _node_to_node(node) (node)
#define _node_to_cpu(node) (node)
#define _node_to_memblk(node) (node)

For that, you need to look at the Memory Binding API that I sent out moments after this patch... It builds on top of this infrastructure to allow binding processes to individual memory blocks or groups of memory blocks.

Cheers!

-Matt