Is SIMD worth the hassle?

[fuji-184]

@ZiCog

Yes, yes, I am aware of all that.

If you have not understood what I said yet, put your "memory" on a swap file, put that swap file on a network connected share, put that share on Neptune. Now fetching and writing back your 1GB is going to take many hours. Any processing speed up with SIMD or whatever will not help noticeably.

All your result has shown is that your memory system can keep up with the processing nicely. Which is great of course.

I suspect we have started to argue about different things.

That does not make the SIMD does not add speed, as I pointed out, SIMD is true parallel from the start, scalar pipeline is not, so it is stil slower

I literally showed you how the movement work

Let's say the slow RAM speed is five - , so -----
The speed of scalar is four -, ----
The speed of SIMD is two -, --
= is finish
The dot . is just space because can not produce the dhape if it is real space

Scalar pipeline :

-----.----=
......-----.----=
............-----.----=

SIMD true parallel (this is 1 SIMD register, that can load many data at same time and process it at same time) :

......--=
-----.--=
......--=

[fuji-184]

@tczajka

If you are doing a lot of operations, what is relevant isn't the latency of single operation, it's the throughput.

Latency of a single operation is the sum of fetch latency + processing latency, but the throughput is max(fetch throughput, processing throughput).

I already said SIMD is way wider than scalar. 1 scalar register can only fetch and proccess 1 data at a time, 1 SIMD register can fetch and process many data at a time. That translates to SIMD has way higher throughput

@tczajka

That's not how it works: fetch and compute happen in parallel.

1. Fetch item 1.
2. Fetch item 2 and compute on item 1.
3. Fetch item 3 and compute on item 2.
   Etc.

Clearly I puth word "no wait" there. Meaning without waiting the result, it already fetch and compute new one. It is slower than true parallel

[ZiCog]

@fuji-184

That does not make the SIMD does not add speed,

I did not say that SIMD does not add speed. But only that, as my extreme interplanetary memory example shows, if your memory is slow enough the speed up is negligible. Your example is not big enough yet.

[197g]

There are a few instructions that can change the memory interaction which are technically part of the instruction set extensions colloquially known as the SIMD sets. On x86 that is _mm_prefetch for instance or an explicit cache flush. Furthermore, we have "non-temporal" or streaming loads and stores and respectively synchronization point. And then of course we have (masked) scatters which, at least in experience, LLVM does not reliably attempt to use. Your mileage may vary in all of these in different processors.

However, it is not completely true that SIMD is fully equivalent to non-SIMD with respect to memory bandwidth use. The luxury of not touching the cache while processing large amounts of data may well speed up the other portions of your code by not clobbering precious data store there.

[fuji-184]

@ZiCog

I did not say that SIMD does not add speed. But only that, as my extreme interplanetary memory example shows, if your memory is slow enough the speed up is negligible. Your example is not big enough yet.

That still not true in my understanding. Because with scalar you just fetch data 1 by 1, so you drain the cache slower. With SIMD, for example AVX512, you fetch 16 elements at once, so it drains the cache faster. My cache has 2 read port, with scalar it only able to retrieve 2 element, with SIMD it retrieves 16 * 2 = 32 elements in parallel. Even if you use multi accumulators to get superscalar it is still not as wide (my laptop has maximum only 4 parallel superscalar, meaning only 4 elements, but the read still just 2) and not efficient as SIMD. And even my 2020 release laptop, it has RAM at speed 22GB/second. Are you just trying to say imaginary slow RAM speed?

[simonbuchan]

If you're processing slower than RAM, then you're not memory bound, sure, but that was the entire premise of the discussion.

I wouldn't be terribly surprised if even a scalar tight loop could keep up with 22GB/s; that's an IPC of only a bit above 4 for a 5GHz core which isn't that unreasonable for an ideal case. More realistically, that 22GB/s is being split up per core and peripheral, which makes it pretty simple to exceed that.

[fuji-184]

VPADDD is just 1 cycle in Intel, and can run 2 parallel at a time. So in 1 cycle, it can fetch and process 32 elements at once. If CPU freq is 2Ghz, 1 cycle is just 0.5 ns. Let's say 32.000.000 u32 = around 128MB = 0.5 ns * 1 million = 0.5 ms. The RAM 22Gbps / 128MB = around 46 ms

So the CPU is already faster than the RAM, but SIMD still show more than 4x gap for AVX512 in my benchmark above

The RAM speed is not split up, but the read ports are not unlimited

[culebron]

@kornel

If your graph is dense grid, and you're doing Dijkstra and not A*, then it's doable in batches (for a batch of nodes add cost from row above and row below).

Also check out how graph problems are solved in GPU shaders by doing them in reverse. This is a gather-scatter problem. Instead of for each node make writes to neighbors to add a cost (scatter), make each node update itself by gathering a sum of costs from its neighbouring nodes.

Yes, that's what I was going to do, pure Dijkstra. Regardng the reverse approach, it took couple of days to sink in, and now I realized how better it should be. Indeed, to reduce the sum of vectors by minimum function, is easier than to add and then write them to random places. And doing a napkin math, I see it should be faster, even if the whole matrix doesn't fit into L1. Thanks a lot!