6 ms·

How is vector different from simd?

IshKebab 3y ago
The RISC-V Vector extension allows the vector length to vary at runtime whereas with SIMD the vector length is fixed at compile time (128 bit, 256 bit etc.). It means the code is more portable basically. With x86 SIMD the standard solution is to compile the same code multiple times for different SIMD widths (using different instructions) and then detect the CPU at runtime. Though that is such a pain that it's only really done in explicitly numerical libraries (Numpy, Eigen, etc.). In theory with Vector you can compile once, run anywhere.
- dan-robertson 3y ago
  That design seems like a reasonable thing for a high level language that could then be converted to different architectures’ simd widths. But I’m kinda surprised it’s good at the ISA level. Eg for something like a vectorized strlen, mightn’t one worry that the cpu would choose vlen[1] too large causing you to load from cache lines (or pages!) that turn out to be unnecessary for finding the length of the string. With the various simd extensions on x86 or arm, such a routine could be carefully written to align with cache lines and so avoid depending on reading the next line when the string ends before it. I also worry about various simd tricks that seem to rely on the width. Eg I think there’s some instruction to interpret each half-byte of one vector as an index into some vector of 16 things. How could these be ported to risc-v? Or maybe that’s not the sort of thing their vector extensions are meant for. I guess part of my thinking here is that the ISA designers at intel, arm, aren’t stupid, but they ended up with fixed widths for sse, neon, knights landing, avx, avx-512. Presumably they had reasons to prefer that to the dynamic risc-v style thing. So I wonder: are there some risc-v constraints the push this design (eg maybe low-power environments presumably pushed neon to have a small width and this made higher-power environments suffer; having a dynamic length might allow both to use the same machine code), or were there some reasons intel preferred to stick with fixed widths, eg making something that could only work on more expensive chips and thereby having something people can pay more for? Is there something reasonable written about why risc-v went with this design. [1] what do you even pass to vsetvl in this case as you don’t know your string length.
  - imtringued 3y ago
    I'm not sure it is difficult to see why variable length SIMD makes sense. If you want to process 15 elements with a width of 8, you will need the function twice, once with SIMD processing whole batches of 8 elements and a scalar version of the same function to process the last 7 elements. This makes it inherently difficult to write SIMD code even in the simple and happy case of data parallelism. With RISC-V all you do is set vlen to 7 in the last iteration. >what do you even pass to vsetvl in this case as you don’t know your string length. I'm not sure what you are trying to say here. You must know the length of the buffer, if you don't know the length of the buffer, then processing the string is inherently sequential, just like reading from a linked list, since accessing even a single byte beyond the null terminator risks a buffer overflow. Why pick an example that can't be vectorized by definition?
    - dfox 3y ago
      Another point is that the CPU can sequence the multiple calls to its internal SIMD unit internally without that having to be done by user code. This in extreme case degrades to the Cray-1-like vector unit, which still has measurable preformance impact and can be implementated even in very resource constrained environments.
    - dan-robertson 3y ago
      I wonder if you’re using a different definition of ‘vectorized’ from the one I would use. For example glibc provides a vectorized strlen. Here is the sse version: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/multiarch/strlen-sse2.S https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/m... It’s pretty simple to imagine how to write an unoptimized version: read a vector from the start of the string, compare it to 0, convert that to a bitvector, test for equal to zero, then loop or clz and finish. I would call this vectorized because it operates on 16 bytes (sse) at a time. There are a few issues: 1. You’re still spending a lot of time in the scalar code checking loop conditions. 2. You’re doing unaligned reads which are slower on old processors 3. You may read across a cache line forcing you to pull a second line into cache even if the string ends before then. 4. You may read across a page boundary which could cause a segfault if the next page is not accessible So the fixes are to do 64-byte (ie cache line) aligned accesses which also means page-aligned (so you won’t read from a page until you know the string doesn’t end in the previous page). That deals with alignment problems. You read four vector registers at a time but this doesn’t really cost much more if the string is shorter as it all comes from one cache line. Another trick in the linked code is that it first finds the cache line by reading the first 16 bytes then merging in the next 3 groups with unsigned-min, so it only requires one test against a zero vector instead of 4. Then it finds the zero in the cache line. You need to do a bit of work in the first iteration to become aligned. With AVX, you can use mask registers on reads to handle that first step instead.

The RISC-V Vector extension allows the vector length to vary at runtime whereas with SIMD the vector length is fixed at compile time (128 bit, 256 bit etc.). It means the code is more portable basically. With x86 SIMD the standard solution is to compile the same code multiple times for different SIMD widths (using different instructions) and then detect the CPU at runtime. Though that is such a pain that it's only really done in explicitly numerical libraries (Numpy, Eigen, etc.). In theory with Vector you can compile once, run anywhere.

dan-robertson 3y ago
That design seems like a reasonable thing for a high level language that could then be converted to different architectures’ simd widths. But I’m kinda surprised it’s good at the ISA level. Eg for something like a vectorized strlen, mightn’t one worry that the cpu would choose vlen[1] too large causing you to load from cache lines (or pages!) that turn out to be unnecessary for finding the length of the string. With the various simd extensions on x86 or arm, such a routine could be carefully written to align with cache lines and so avoid depending on reading the next line when the string ends before it. I also worry about various simd tricks that seem to rely on the width. Eg I think there’s some instruction to interpret each half-byte of one vector as an index into some vector of 16 things. How could these be ported to risc-v? Or maybe that’s not the sort of thing their vector extensions are meant for. I guess part of my thinking here is that the ISA designers at intel, arm, aren’t stupid, but they ended up with fixed widths for sse, neon, knights landing, avx, avx-512. Presumably they had reasons to prefer that to the dynamic risc-v style thing. So I wonder: are there some risc-v constraints the push this design (eg maybe low-power environments presumably pushed neon to have a small width and this made higher-power environments suffer; having a dynamic length might allow both to use the same machine code), or were there some reasons intel preferred to stick with fixed widths, eg making something that could only work on more expensive chips and thereby having something people can pay more for? Is there something reasonable written about why risc-v went with this design. [1] what do you even pass to vsetvl in this case as you don’t know your string length.
- imtringued 3y ago
  I'm not sure it is difficult to see why variable length SIMD makes sense. If you want to process 15 elements with a width of 8, you will need the function twice, once with SIMD processing whole batches of 8 elements and a scalar version of the same function to process the last 7 elements. This makes it inherently difficult to write SIMD code even in the simple and happy case of data parallelism. With RISC-V all you do is set vlen to 7 in the last iteration. >what do you even pass to vsetvl in this case as you don’t know your string length. I'm not sure what you are trying to say here. You must know the length of the buffer, if you don't know the length of the buffer, then processing the string is inherently sequential, just like reading from a linked list, since accessing even a single byte beyond the null terminator risks a buffer overflow. Why pick an example that can't be vectorized by definition?
  - dfox 3y ago
    Another point is that the CPU can sequence the multiple calls to its internal SIMD unit internally without that having to be done by user code. This in extreme case degrades to the Cray-1-like vector unit, which still has measurable preformance impact and can be implementated even in very resource constrained environments.
  - dan-robertson 3y ago
    I wonder if you’re using a different definition of ‘vectorized’ from the one I would use. For example glibc provides a vectorized strlen. Here is the sse version: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/multiarch/strlen-sse2.S https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/m... It’s pretty simple to imagine how to write an unoptimized version: read a vector from the start of the string, compare it to 0, convert that to a bitvector, test for equal to zero, then loop or clz and finish. I would call this vectorized because it operates on 16 bytes (sse) at a time. There are a few issues: 1. You’re still spending a lot of time in the scalar code checking loop conditions. 2. You’re doing unaligned reads which are slower on old processors 3. You may read across a cache line forcing you to pull a second line into cache even if the string ends before then. 4. You may read across a page boundary which could cause a segfault if the next page is not accessible So the fixes are to do 64-byte (ie cache line) aligned accesses which also means page-aligned (so you won’t read from a page until you know the string doesn’t end in the previous page). That deals with alignment problems. You read four vector registers at a time but this doesn’t really cost much more if the string is shorter as it all comes from one cache line. Another trick in the linked code is that it first finds the cache line by reading the first 16 bytes then merging in the next 3 groups with unsigned-min, so it only requires one test against a zero vector instead of 4. Then it finds the zero in the cache line. You need to do a bit of work in the first iteration to become aligned. With AVX, you can use mask registers on reads to handle that first step instead.