LLaMA NUMA could be better

[zrm]

llama.cpp is memory bound, let's see what has a lot of memory bandwidth:

NVIDIA V100 32GB: 900GB/s
2S Epyc 9000 (12xDDR5-4800/S): 922GB/s
NVIDIA A100 40GB: 1555GB/s
2S Xeon Max (HBM): 2TB/s
NVIDIA A100 80GB: 2TB/s
8S Xeon Scalable v4 (8xDDR5-4800/S): 2.45TB/s

NUMA systems have a lot because there are memory channels (or HBM for Xeon Max) on each socket. Okay, but the cheapest thing there is ~$6000. What if I'm not rich?

(~$350 w/ 16GB, max ~128GB) common PC (2xDDR4-3200): 51GB/s
(~$450 w/ 8GB, ~$600 w/ 16GB) Mac Mini M1: 68GB/s
(~$600 w/ 8GB, ~$800 w/ 16GB) Mac Mini M2: 100GB/s
(~$200 w/ 64GB, max ~768GB) 2S Xeon E5 v1 (4xDDR3-1600/S): 102GB/s [no F16C so f16 models slower]
(~$250 w/ 64GB, max ~768GB) 2S Xeon E5 v2 (4xDDR3-1866/S): 119GB/s
(~$350 w/ 128GB, max ~3000GB) 2S Xeon E5 v4 (4xDDR4-2400/S): 154GB/s

Hmm. Xeon E5-2690 v1 for $9 each on eBay. Let's see how we do.

$ lscpu
...
CPU(s): 16
On-line CPU(s) list: 0-15
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1

$ ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:"
...
llama_print_timings: sample time = 406.79 ms / 512 runs ( 0.79 ms per token)
llama_print_timings: prompt eval time = 27899.73 ms / 271 tokens ( 102.95 ms per token)
llama_print_timings: eval time = 74773.93 ms / 510 runs ( 146.62 ms per token)

Not terrible for 11-year-old hardware. Let's try it with two sockets:

$ lscpu
...
CPU(s): 32
On-line CPU(s) list: 0-31
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 2
NUMA node(s): 2

$ ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:"
...
llama_print_timings: sample time = 438.34 ms / 512 runs ( 0.86 ms per token)
llama_print_timings: prompt eval time = 27083.17 ms / 271 tokens ( 99.94 ms per token)
llama_print_timings: eval time = 129373.98 ms / 510 runs ( 253.67 ms per token)

Twice as many cores, twice as much memory bandwidth, and it's slower.
Oh, get_num_physical_cores() is broken, it's only returning 8/16 physical cores because "cpu cores" in /proc/cpuinfo is per-socket. I submitted a pull request.

$ ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:" -t 16
...
llama_print_timings: sample time = 451.48 ms / 512 runs ( 0.88 ms per token)
llama_print_timings: prompt eval time = 16092.04 ms / 271 tokens ( 59.38 ms per token)
llama_print_timings: eval time = 102018.05 ms / 510 runs ( 200.04 ms per token)

Well, the prompt eval time is better. Maybe it benefits from hyperthreading?

$ ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:" -t 32
...
llama_print_timings: sample time = 399.47 ms / 512 runs ( 0.78 ms per token)
llama_print_timings: prompt eval time = 14734.68 ms / 271 tokens ( 54.37 ms per token)
llama_print_timings: eval time = 97250.82 ms / 510 runs ( 190.69 ms per token)

Still something's not right.

$ numactl -H
available: 2 nodes (0-1)
node 0 cpus: 0 1 2 3 4 5 6 7 16 17 18 19 20 21 22 23
node 0 size: 96609 MB
node 0 free: 96320 MB
node 1 cpus: 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31
node 1 size: 64506 MB
node 1 free: 60183 MB
node distances:
node 0 1
0: 10 20
1: 20 10

There it is. The whole model is loaded into the memory of one node. Let's try node interleave.

# echo 3 > /proc/sys/vm/drop_caches

$ numactl --interleave=0-1 ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:" -t 32
...
llama_print_timings: sample time = 397.83 ms / 512 runs ( 0.78 ms per token)
llama_print_timings: prompt eval time = 14894.56 ms / 271 tokens ( 54.96 ms per token)
llama_print_timings: eval time = 57045.66 ms / 510 runs ( 111.85 ms per token)

That's an improvement. Now it's >30% faster than a single socket and basically the same speed as my Ryzen 5 5600G from 2021, for about half the price. Let's see what happens on a machine with 4 NUMA nodes (16C/32T):

$ ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:" -t 16
...
llama_print_timings: sample time = 456.06 ms / 512 runs ( 0.89 ms per token)
llama_print_timings: prompt eval time = 13954.33 ms / 271 tokens ( 51.49 ms per token)
llama_print_timings: eval time = 108925.89 ms / 510 runs ( 213.58 ms per token)

$ ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:" -t 32
...
llama_print_timings: sample time = 514.30 ms / 512 runs ( 1.00 ms per token)
llama_print_timings: prompt eval time = 14288.35 ms / 271 tokens ( 52.72 ms per token)
llama_print_timings: eval time = 109354.09 ms / 510 runs ( 214.42 ms per token)

# echo 3 > /proc/sys/vm/drop_caches

$ numactl --interleave=0-3 ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:" -t 16
...
llama_print_timings: sample time = 477.99 ms / 512 runs ( 0.93 ms per token)
llama_print_timings: prompt eval time = 14164.87 ms / 271 tokens ( 52.27 ms per token)
llama_print_timings: eval time = 67402.83 ms / 510 runs ( 132.16 ms per token)

$ numactl --interleave=0-3 ./main -m models/7B/ggml-model-q4_0.bin -n 512 -p "Building a website can be done in 10 simple steps:" -t 32
...
llama_print_timings: sample time = 489.53 ms / 512 runs ( 0.96 ms per token)
llama_print_timings: prompt eval time = 14511.16 ms / 271 tokens ( 53.55 ms per token)
llama_print_timings: eval time = 48623.21 ms / 510 runs ( 95.34 ms per token)

125% faster is alright.

I can submit a pull request that does the same thing (with a dependency on libnuma) if you want it.

But this is not the best we can do. Interleave spreads the model across all nodes randomly and there is still heavy slow cross-node memory access, that's just better than all the cores contending for the memory of one node.

The better way is to explicitly load 1/Nth of the model on each node and then have a thread pool per node which is assigned the operations on that subset of the model.

[ggerganov]

Dependency to libnuma in ggml is not an option. I guess it could be added as a llama.cpp example, depending on the complexity

But this analysis alone is very informative - thank you for posting this.

Might be interesting to see how some of the AVX-512 formats in #1073 perform with this NUMA fine-tuning

A LLAMA_NUMA=on compile option with libnuma might work for this case, considering how this looks like a decent performance improvement. I'm actually surprised that no one else saw this considering I've seen other 2S systems being discussed in previous issues.

Also I'm finding it interesting that hyper-threading is actually improving inference speeds in this example, since the general consensus in the past was that it degrades performance. Perhaps the high memory bandwidth is a factor here?

[constasmile]

I have 2S Xeon E5 2680 v4 256Gb DDR4-2400. I also encountered this problem. It would be great to make NUMA support. I can't help with the code, I'm not a programmer, but I can test it on my machine if needed. Maybe try to use something like "gpu-layers" just for each NUMA node? Then the memory bandwidth will be fully utilized. Good luck to you guys.

[gjmulder]

Most generic motherboards are two channel, with 1 NUMA node. I have a four channel 1 NUMA node board, but that comes at a cost. If you can afford to care about NUMA, then GPUs are always going to provide better performance IMNSHO.

[rankaiyx]

Why do your 2 NUMA and 4 NUMA have similar speeds?
Is the total memory bandwidth similar? Can you provide some information about the memory bandwidth of your machines?

[Sciumo]

So TR Pro 3995 shows only 1 NUMA nodes, 128 CPU.
Memory bound, then?
Caches (sum of all):
L1d: 2 MiB (64 instances)
L1i: 2 MiB (64 instances)
L2: 32 MiB (64 instances)
L3: 256 MiB (16 instances)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-127

[gjmulder]

So TR Pro 3995 shows only 1 NUMA nodes, 128 CPU.

128 hypercores. 64 physical cores.

I've observed using hypercores tends to slow things down. The theory behind hypercores is that if one thread is waiting on memory I/O another thread can be scheduled, however if all threads are memory I/O bound then hyperthreading simply causes a lot of context switching overhead. Linux's perf stat can show you how much time cores are waiting on memory. IPC for memory bound code like llama.cpp is usually around 1.0, indicating those L1d, L2 and L3 caches are all probably idling waiting on main memory access as well.

[zrm]

LLaMA 65B-f16 is ~122GB. You can get 128GB of DDR4-2400 for around $150 and a 2S 8-channel Xeon E5 v4 to put it in for around $200. How much is any GPU with 128GB of RAM?

Also I'm finding it interesting that hyper-threading is actually improving inference speeds in this example, since the general consensus in the past was that it degrades performance. Perhaps the high memory bandwidth is a factor here?

It's not surprising SMT usually doesn't help. On my 6-core Ryzen 5 5600G the "prompt eval" time goes up proportionally from -t 6 to -t 4 but the "eval" time stays the same. It takes -t 3 before it even goes up a little. Presumably completely memory bound, what are more threads going to do? But slower CPUs with more memory channels might actually get compute-bound sometimes.

Why do your 2 NUMA and 4 NUMA have similar speeds?
Is the total memory bandwidth similar? Can you provide some information about the memory bandwidth of your machines?

The 2N and 4N systems both have 8 memory channels total. The 4N system is DDR4 instead of DDR3, so it has about 2/3rds more memory bandwidth, but because it's 4N, 3/4ths of random memory accesses will be off the local node instead of 1/2. Node interleave doesn't change that, it just stops all the accesses from being to the same node, which is a larger improvement on the 4N system.

So TR Pro 3995 shows only 1 NUMA nodes, 128 CPU.

Threadripper 3000 series sort of has two memory nodes but is effectively configured for node interleave: https://www.anandtech.com/show/15044/the-amd-ryzen-threadripper-3960x-and-3970x-review-24-and-32-cores-on-7nm/3

Epyc and older Threadripper (and basically anything with multiple sockets) show the NUMA nodes unless the user enables node interleave in the BIOS. Interleave is a bandwidth/latency trade off, but turning it on at the system level prevents applications from doing any further optimization. The performance hierarchy for multi-threaded applications is like this: worst) threads on every node accessing data on a single node; better) node interleave; best) threads on each node accessing data on the local node.

System-level interleave removes the possibility for the worst thing by removing the possiblity for the best thing.

It looks like the biggest thing degrading performance on NUMA here is actually preload. The default memory policy is to prefer to load pages into the node of the thread that first accessed it. Call mmap() with MAP_POPULATE and the system will by default try to put the whole model on the node of the calling thread. Using 'numactl --interleave=all' changes the memory policy so that mmap stripes the allocation across all the nodes. We can get the same result by calling 'set_mempolicy(MPOL_INTERLEAVE, numa_all_nodes_ptr->maskp, numa_all_nodes_ptr->size)' at the beginning of main(), but set_mempolicy() requires -lnuma. (It's annoying that they put a syscall wrapper in a library that isn't installed by default. In theory we could use syscall(2) instead.)

But blind interleave still isn't optimal, it's just better than what's happening now. And we can get a similar result without -lnuma just by not using preload on NUMA systems. Then the mapping gets faulted in during first use by all the different work threads, which spreads it out across different nodes. Better yet, the way matrix multiplication is currently done by ggml is already not far from what we want -- the section of the model assigned to each thread is always the same. What happens if we pin work threads to nodes with pthread_setaffinity_np() so each thread is always on the same node it was when that page of the model was first faulted in? Now ye olde pair of $9 CPUs is here:

llama_print_timings: sample time = 399.99 ms / 512 runs ( 0.78 ms per token)
llama_print_timings: prompt eval time = 14904.62 ms / 271 tokens ( 55.00 ms per token)
llama_print_timings: eval time = 49917.59 ms / 510 runs ( 97.88 ms per token)

At least for the first batch of 512. After that it slows down some:

llama_print_timings: sample time = 1594.96 ms / 2048 runs ( 0.78 ms per token)
llama_print_timings: prompt eval time = 99318.38 ms / 1813 tokens ( 54.78 ms per token)
llama_print_timings: eval time = 224513.88 ms / 2040 runs ( 110.06 ms per token)

It could be that at the end of the first batch it generates some new soon-to-be frequently accessed data that all gets stuck on one node again.

Currently the fastest thing to do is run once without preload or interleave so the model gets paged in with some relation to the access pattern, then after the OS has it in the page cache, use interleave so mutable state gets spread across nodes:

llama_print_timings: sample time = 1593.20 ms / 2048 runs ( 0.78 ms per token)
llama_print_timings: prompt eval time = 99734.43 ms / 1813 tokens ( 55.01 ms per token)
llama_print_timings: eval time = 196720.76 ms / 2040 runs ( 96.43 ms per token)

But that's only until we can figure out which data is causing the detriment without interleave. We can preferentially load data into any node we want without third party dependencies by setting thread affinity for the current thread to the cores on that node right before first access to that memory. Or if there is some specific data which inherently has to be accessed repeatedly by threads on multiple nodes, it may be faster to keep a copy of it on each node.

I'm still trying to understand some of this code. Like this:

ggml_lock_lock  (&state_shared.spin);
ggml_lock_unlock(&state_shared.spin);

There are no operations while the lock is held?

[ggerganov]

I'm still trying to understand some of this code. Like this:

ggml_lock_lock  (&state_shared.spin);
ggml_lock_unlock(&state_shared.spin);

There are no operations while the lock is held?

These lock / unlock are actually noops (the spin variable is an unused int).
I had some early implementations where I was trying to use spin locks to synchronize the threads. Later, I dropped this idea since busy-wait on atomic variable gives better performance. I kept the lock / unlock calls by replacing them with macros that effectively do nothing, so you can simply delete these 2 lines and the code will be equivalent:

https://github.com/ggerganov/llama.cpp/blob/d627025c36c0c8b2ec85bc060f0bdced69928dda/ggml.c#L13683-L13686

I am following your analysis with interest.
It's still a bit over my head, but I'm planning to do some tests of these NUMA settings on a 2-socket machine soon and try to understand the effects of node interleaving better

[zrm]

echo 1 > /proc/sys/vm/numa_interleave

$ numactl --interleave=all ./main -n 512 -m models/65B/ggml-model-q4_0.bin --ignore-eos -p "Someone told me there is a configuration option called \"/proc/sys/vm/numa_interleave\" -- what" -t 32
...
Someone told me there is a configuration option called "/proc/sys/vm/numa_interleave" -- what does this do?
Some of the kernel's resource management features have to deal with both "NUMA-ness" and "SMP-ness". In many cases, the kernel makes some tradeoffs between memory bandwidth (when using NUMA) versus cache performance (when using SMP). Since the kernel must make these tradeoffs at runtime, we need a way for it to get hints from userland as to how we should proceed.
The numa_interleave sysctl controls one such knob. It can be set to 0-100%, where a higher number implies more interleaving of SMP resources (CPU cores) with NUMA nodes. A setting of zero means "don't do any interleaving."
This option only affects process scheduling, not the placement of pages in memory when they are allocated. There is no current way to get hints from userland about page placement.
The default value of numa_interleave is 67%, which was chosen by trial and error on several NUMA systems (including ours) as giving the best performance for a variety of workloads. The system-wide default can be overridden on a per-process basis using the numa_interleave scheduling class hint, described in Documentation/scheduler/sched-numa.txt.
The kernel's NUMA resource management features are described in Documentation/kernel-api/numa.rst.
The scheduling class hints (including numa_interleave) are described in Documentation/scheduler/sched-bwc.txt.
If you want to tune this value, then please do some performance testing on your systems and share the results with us so that we can improve the default for future kernel releases. Please send email to linux-kernel@vger.kernel.org or file a bug at http://www.kernel.org/.
The value of numa_interleave was chosen by trial and error, and it's likely that some other value would work better on your systems. Unfortunately, I don't have access to any of the original performance testing data used to choose this number.
As for how you should test performance: a simple benchmark like bonnie++ or sysbench is probably fine. See Documentation/admin-guide/benchmarking.rst for more information about some useful performance
llama_print_timings: load time = 13041.53 ms
llama_print_timings: sample time = 466.49 ms / 512 runs ( 0.91 ms per token)
llama_print_timings: prompt eval time = 140717.11 ms / 284 tokens ( 495.48 ms per token)
llama_print_timings: eval time = 333853.21 ms / 510 runs ( 654.61 ms per token)
llama_print_timings: total time = 475246.94 ms

$ ls /proc/sys/vm/numa_interleave
ls: cannot access '/proc/sys/vm/numa_interleave': No such file or directory

/proc/sys/kernel/numa_balancing is enabled by default. Let's try turning it off:

# echo 0 > /proc/sys/kernel/numa_balancing

Now I'm not seeing any further benefit from numactl --interleave. Once you stop prefetching the model (0d23f8c), de facto turning that off was apparently the source of its advantage.

Later, I dropped this idea since busy-wait on atomic variable gives better performance.

The trouble is you're threading something with a lot of serial dependencies in it, so the amount of work each thread can do before it has to synchronize with the other threads is small and you have to do thread synchronization thousands of times a second.

[rankaiyx]

I was fooled by chatgpt's fictional method, which told me that "echo 1 > / proc/sys/vm/numa_interleave" was a kernel-level setting instead of "numactl-- interleave=all", which actually didn't seem to exist. When I realized this, I deleted the previous comments.

The method you just pull should be the right solution. I am excited about your improvement. I'm assembling a numa computer with 2 CPU and 8 channels of memory (E5-2698Bv3 x2 / DDR3 1866 32G x8), and I'll test it later.

[ggerganov]

2S Epyc 9000 (12xDDR5-4800/S): 922GB/s
2S Xeon Max (HBM): 2TB/s
8S Xeon Scalable v4 (8xDDR5-4800/S): 2.45TB/s

Does anybody know if I can rent one of these in a cloud to test?

[Sciumo]

I couldn't find any with that exact CPU config.

I'm going to try multiple processes with: https://github.com/huggingface/text-generation-inference