Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fundamental flaws of SIMD ISAs (2021)

bitsnbites.eu

Post reply on HN
Print view View original

131–140 of 146 posts

Re: Fundamental flaws of SIMD ISAs (2021)

#131

Post by magicalhippo »

kjs3 wrote: post #109
immibis wrote: post #94

Earlier quoted context omitted.

If you pay attention this isn't a UTF-8 decoder. It might be some other encoding, or a complete misunderstanding of how UTF-8 works, or an AI hallucination. It also doesn't talk about how to handle the variable number of output bytes or the possibility of a continuation sequence split between input chunks.

I paid attention and I don't see where Daniel claimed that this a complete UTF-8 decoder. He's illustrating a programming technique using a simplified use case, not solving the worlds problems. And I don't think Daniel Lemire lacks an understanding of the concept or needs an AI to code it.

Agreed, but the points raised by GP are valid in terms of using that article as an argument that AVX-512 can decode UTF-8 well.

It might be fast, but it's not a UTF-8 decoder. It's a transcoder to a fixed, and very limited, target encoding.

Re: Fundamental flaws of SIMD ISAs (2021)

#132

Post by janwas »

camel-cdr wrote: post #25
jcranmer wrote: post #17

Earlier quoted context omitted.

There's a category of autovectorization known as Superword-Level Parallelism (SLP) which effectively scavenges an entire basic block for individual instruction sequences that might be squeezed together into a SIMD instruction. This kind of vectorization doesn't work well with vector-length-agnostic ISAs, because you generally can't scavenge more than a few elements anyways, and inducing any sort of dynamic vector len…

The SLP vectorizer is a good point, but I think it's, in comparison with x86, more a problem of the float and vector register files not being shared (in SVE and RVV). You don't need to reconfigure the vector length; just use it at the full width. > Something like abseil's hash table If I remember this correctly, the abseil lookup does scale with vector length, as long as you use the native data path width. (albeit wi…

(For other readers:) This is what our Highway library does - wrapper functions around intrinsics, plus a (constexpr if possible) Lanes() function to query the length.

For very many cases, writing the code once for an 'unknown to the programmer' vector length indeed works.

One example that doesn't work so well is a sorting network; its size depends on the vector length. (I see you mention this below.)

Re: Fundamental flaws of SIMD ISAs (2021)

#133

Post by janwas »

jcranmer wrote: post #17
camel-cdr wrote: post #12

Earlier quoted context omitted.

> I prefer fixed width Do you have examples for problems that are easier to solve in fixed-width SIMD? I maintain that most problems can be solved in a vector-length-agnostic manner. Even if it's slightly more tricky, it's certainly easier than restructuring all of your memory allocations to add padding and implementing three versions for all the differently sized SIMD extensions your target may support. And you can…

There's a category of autovectorization known as Superword-Level Parallelism (SLP) which effectively scavenges an entire basic block for individual instruction sequences that might be squeezed together into a SIMD instruction. This kind of vectorization doesn't work well with vector-length-agnostic ISAs, because you generally can't scavenge more than a few elements anyways, and inducing any sort of dynamic vector len…

I advised the Abseil design and regret not pointing this out earlier: changing the interface to insert/query batches of items would be considerably more efficient, especially for databases. Whenever possible, 'vertical' algorithms (independent SIMD elements) usually scale better than 'horizontal' (pick one element within a vector).

Re: Fundamental flaws of SIMD ISAs (2021)

#134

Post by janwas »

camel-cdr wrote: post #36
pkhuong wrote: post #21

Earlier quoted context omitted.

> Do you have examples for problems that are easier to solve in fixed-width SIMD? Regular expression matching and encryption come to mind.

> Regular expression matching That's probably true. Last time I looked at it, it seemed like parts of vectorscan could be vectorized VLA, but from my, very limited, understanding of the main matching algorithm, it does seem to require specialization on vector length. It should be possible to do VLA in some capacity, but it would probably be slower and it's too much work to test. > encryption From the things I've look…

On vqsort: yes, the current RVV set of shuffles is awfully limited and several implementations produce one element per cycle. We also saw excessive VSETVLI, though I understand that has been fixed by an extra compiler pass. Could be interesting to retry with a uarch having O(1) shuffles.

Re: Fundamental flaws of SIMD ISAs (2021)

#135

Post by janwas »

pornel wrote: post #6

There are alternative universes where these wouldn't be a problem. For example, if we didn't settle on executing compiled machine code exactly as-is, and had a instruction-updating pass (less involved than a full VM byte code compilation), then we could adjust SIMD width for existing binaries instead of waiting decades for a new baseline or multiversioning faff. Another interesting alternative is SIMT. Instead of hav…

hm. Doesn't the existence of Vulkan subgroups and CUDA shuffle/ballot poke huge holes in their 'SIMT' model? From where I sit, that looks a lot like SIMD. The only difference seems to be that SIMT professes to hide (or use HW support for) divergence. Apart from that, reductions and shuffles are basically SIMD.

Re: Fundamental flaws of SIMD ISAs (2021)

#136

Post by camel-cdr »

janwas wrote: post #132
camel-cdr wrote: post #25

Earlier quoted context omitted.

The SLP vectorizer is a good point, but I think it's, in comparison with x86, more a problem of the float and vector register files not being shared (in SVE and RVV). You don't need to reconfigure the vector length; just use it at the full width. > Something like abseil's hash table If I remember this correctly, the abseil lookup does scale with vector length, as long as you use the native data path width. (albeit wi…

(For other readers:) This is what our Highway library does - wrapper functions around intrinsics, plus a (constexpr if possible) Lanes() function to query the length. For very many cases, writing the code once for an 'unknown to the programmer' vector length indeed works. One example that doesn't work so well is a sorting network; its size depends on the vector length. (I see you mention this below.)

I quite like highway.

As mentioned, last time I tried vqsort for RVV it was surprisingly slow.

I tried to replicate it yesterday, but noticed that vqsort is now disabled for RVV: https://github.com/google/highway/blob/400fbf20f2e40b984be12...

Does highway support sorting networks for non-128-bit vector registers?

When I tried to compile it for AVX512, the BaseCase seems to only use xmm registers: https://godbolt.org/z/qr9xoTGKn

Re: Fundamental flaws of SIMD ISAs (2021)

#137

Post by janwas »

camel-cdr wrote: post #136
janwas wrote: post #132

Earlier quoted context omitted.

(For other readers:) This is what our Highway library does - wrapper functions around intrinsics, plus a (constexpr if possible) Lanes() function to query the length. For very many cases, writing the code once for an 'unknown to the programmer' vector length indeed works. One example that doesn't work so well is a sorting network; its size depends on the vector length. (I see you mention this below.)

I quite like highway. As mentioned, last time I tried vqsort for RVV it was surprisingly slow. I tried to replicate it yesterday, but noticed that vqsort is now disabled for RVV: https://github.com/google/highway/blob/400fbf20f2e40b984be12... Does highway support sorting networks for non-128-bit vector registers? When I tried to compile it for AVX512, the BaseCase seems to only use xmm registers: https://godbolt.org/…

:) Yes, vqsort recently tickled a bug in clang. I've seen a steady stream of issues, many caused by SLP or the seeming absence of CI. You might try re-enabling it on GCC.

Yes, the issue with the sorting network is that it is limited to 16x16 to reduce code explosion. With uint16_t, XMM are sufficient for the 8-column case; your Godbolt link does have some YMM for the 16-column case. When changing the type to sort to uint32_t, we see ZMM as expected.

Re: Fundamental flaws of SIMD ISAs (2021)

#138

Post by camel-cdr »

janwas wrote: post #137
camel-cdr wrote: post #136

Earlier quoted context omitted.

I quite like highway. As mentioned, last time I tried vqsort for RVV it was surprisingly slow. I tried to replicate it yesterday, but noticed that vqsort is now disabled for RVV: https://github.com/google/highway/blob/400fbf20f2e40b984be12... Does highway support sorting networks for non-128-bit vector registers? When I tried to compile it for AVX512, the BaseCase seems to only use xmm registers: https://godbolt.org/…

:) Yes, vqsort recently tickled a bug in clang. I've seen a steady stream of issues, many caused by SLP or the seeming absence of CI. You might try re-enabling it on GCC. Yes, the issue with the sorting network is that it is limited to 16x16 to reduce code explosion. With uint16_t, XMM are sufficient for the 8-column case; your Godbolt link does have some YMM for the 16-column case. When changing the type to sort to…

Btw, here is a VLA vector register sort: https://godbolt.org/z/Env64961q

It has a few more instructions then the VLS version, but the critical dependency chain is the same.

It's also slightly less optimal on x86, because it alway uses lane crossing permutes. For AVX512 that is 5 out of 15 permutations that are vperm, but could've been vshuf. (if the loop isn't unrolled and optimized by the compiler)

I wasn't able to figure out how to implement the multi vector register sort in a VLA way.

Re: Fundamental flaws of SIMD ISAs (2021)

#139

Post by janwas »

camel-cdr wrote: post #138
janwas wrote: post #137

Earlier quoted context omitted.

:) Yes, vqsort recently tickled a bug in clang. I've seen a steady stream of issues, many caused by SLP or the seeming absence of CI. You might try re-enabling it on GCC. Yes, the issue with the sorting network is that it is limited to 16x16 to reduce code explosion. With uint16_t, XMM are sufficient for the 8-column case; your Godbolt link does have some YMM for the 16-column case. When changing the type to sort to…

Btw, here is a VLA vector register sort: https://godbolt.org/z/Env64961q It has a few more instructions then the VLS version, but the critical dependency chain is the same. It's also slightly less optimal on x86, because it alway uses lane crossing permutes. For AVX512 that is 5 out of 15 permutations that are vperm, but could've been vshuf. (if the loop isn't unrolled and optimized by the compiler) I wasn't able to…

Nice work :) Clang x86 indeed unrolls, which is good. But setting the CC and AA mask constants looks fairly expensive compared to fixed-pattern shuffles.

Yes, the 2D aspect of the sorting network complicates things. Transposing is already harder to make VLA and fusing it with the other shuffles certainly doesn't help.

Re: Fundamental flaws of SIMD ISAs (2021)

#140

Post by Narishma »

IshKebab wrote: post #101
tonetegeatinst wrote: post #26

Earlier quoted context omitted.

AFAIK about every modern CPU uses out of order von Neumann architecture. The only people who don't are the handful of researchers and people who work with the government research into non van Neumann designed systems.

Microcontrollers are often in-order.

Are there any microcontrollers that aren't in-order?
Post reply on HN