17 ms·

This argument is less effective given that SIMD is not always a straightforward substitute for vector processing. Sometimes we want 128, 256 or 512 bits of proc

This argument is less effective given that SIMD is not always a straightforward substitute for vector processing. Sometimes we want 128, 256 or 512 bits of processing as a unit and will follow it up with something different, not a repeated instance of that same process. We had numerous different examples of this in the Hyperscan project and I broke out something similar on my blog: https://branchfree.org/2018/05/30/smh-the-swiss-army-chainsaw-of-shuffle-based-matching-sequences/ https://branchfree.org/2018/05/30/smh-the-swiss-army-chainsa... We also used SIMD quite extensively as a 'wider GPR' - not doing stuff over tons of input characters but instead using the superior size of SIMD registers to implement things like bitwise string and NFA matchers. A SIMD instruction can be a reasonable proxy for a wide vector processor but the reverse is not true - a specialized vector architecture is unlikely to be very helpful for this kind of 'mixed' SIMD processing. Almost any "argument from DAXPY" fails for the much richer uses of SIMD processing among active practitioners using modern SIMD.

creato 8y ago
I agree. It seems like this strategy makes only the most braindead applications of SIMD better (simple loops that can be vectorized by an arbitrary factor), but doesn't really do anything to help the meatier SIMD workloads. Most SIMD code isn't as simple as this, and the code that is usually isn't a significant factor in either developer experience or runtime.
- glangdale 8y ago
  Seriously. A lot of these proposals go veering off into second-order considerations ("Easier to decode!" "A few picojoules less energy") as I'd be very surprised if the bottlenecks are going to be from SIMD vs vector architecture ISA issues - as compared to, say, memory bandwidth or multiply-add bandwidth.
  - CoolGuySteve 8y ago
    A few years ago I tried to buy a liquid cooled overclocked server for trading. Enabling AVX cost extra due to the concentrated heat output from the MMU and each core's vector unit. It was along the lines of being able to get a server that was tested stable at 5GHz without AVX vs 4.5 GHz with AVX for the same price. So at least on Intel, these vector units are apparently limiting clock speeds and yields due to power consumption.
    - kllrnohj 8y ago
      Yes, but not due to instruction decode costs, which is really all this article is talking about. The real heat comes from actually doing the work, not decoding what work to do.
dbaupp 8y ago
Yeah, other examples include image codecs, such as JPEG: the DCT performed on the 8x8 blocks can benefit from SIMD, but the lanes aren't independent at all (matrix transposes, various intra-block additions).
- wbl 8y ago
  Do it across blocks and you can squeeze out more parallelism.
  - Const-me 8y ago
    Only if these multiple blocks fit in the 16 registers. If they won't fit and the data will be evicted to RAM, that extra parallelism will slow down the code, not speed up.
  - dbaupp 8y ago
    I believe the blocks end up stored as an array-of-structs where the structs have 8*8 = 64 elements. Doing the DCT in multiple blocks requires somehow transposing this into a struct-of-arrays-like format, maybe a gather of every 64th element (likely a waste of memory bandwidth) or some sort of unpckl/unpckh-like instructions. Either way, this may impose non-trivial overhead, and so the benefits of extra parallelism are hidden. (And, of course, that's all assuming there's enough registers, and I don't remember enough about JPEG to make a guess.)
atq2119 8y ago
Agreed, but then again, the vector architectures have the undeniable benefit of being agnostic to the underlying hardware. With a SIMD architecture, as registers get ever wider you need to recompile your code, and binary releases require multiple code paths. With a vector architecture, the hardware designers can just increase the machine's internal vector size and existing code will benefit immediately. Furthermore, it seems reasonable to count GPU users among "active practitioners of modern SIMD". All code that is written in a GPU-style -- which admittedly isn't too common yet on CPUs, but it would certainly be feasible and is possible since ispc came along -- immediately becomes a beneficiary of a well-designed vector instruction architecture.
- skybrian 8y ago
  Yes, recompiling can be a pain, but there's an argument that we should get used to recompiling things from source and make sure this path is smooth, rather than trying making old binaries work as long as possible. Static binaries are another reason.
  - Joky 8y ago
    You lose binary portability though: what is you can write you image processing code such that it operates well whether your SIMD instructions is 4, 8, or 16 wide? (or more). Then shipping this binary for mobile phones for instance would take advantage of the wider register available on high-end device while working well on more modest CPUs.
    - CoolGuySteve 8y ago
      Shaders in games have worked this way on GPUs for probably a decade now without much issue.
      - Const-me 8y ago
        Only graphics shaders. Advanced compute shaders very often need to synchronize local data within warp. When you program such shaders you have to be aware about SIMD width (32 on NVidia and Intel, 64 on AMD), and design both algorithms and data structures accordingly. Failing to do so often have significant performance costs, I saw up to 10x speedup after implementing cooperative algorithm instead of straightforward one.
jabl 8y ago
In a vector arch like the risc-v vector extension, if you want to process exactly 256 or whatever at a time, just set the configuration or vector length register and off you go with SIMD-style programming?
- glangdale 8y ago
  It is very unlikely that such a configuration will perform remotely as fast as a native SIMD implementation, unless there is some truly heroic specialization going on under the hood. Obviously the work is still possible with vector ops, in the same way that it's still possible with scalar ops too. But will it be fast? My guess is no.
  - jabl 8y ago
    > It is very unlikely that such a configuration will perform remotely as fast as a native SIMD implementation Why? AFAICS, a "real" vector ISA is mostly a superset of a SIMD ISA. What do you think is missing? Of course, if you want to eke out the absolute maximum performance then you need to be aware of the microarchitecture you're targeting, and a length-agnostic vector ISA like SVE or RVV don't buy you that much. But I don't see how that's worse than having to redo your code whenever the vendor introduces new HW with a new SIMD ISA. I guess one could argue that an implementation of a vector ISA targeting, say, linear algebra, would be different than an implementation focusing on maximum short-vector performance. Say, by having a vector length >> execution width, and using tricks like vector pipelining etc. to get performance rather than focusing on minimizing short-vector latency. But, that's a question of what the implementation is optimized for rather than saying what the ISA is good for, no?
lallysingh 8y ago
Sounds like you're getting fixated on the example. Short vectors would do what you want. And it's a lot easier to add specific vector instructions for particular use cases than adding N of them for each use case (for N simd sizes). Are you getting hung up on the term 'vector'? That doesn't assume you're just doing linear algebra.
- bloomer 8y ago
  No he's not getting hung up on the term vector. He is saying that SIMD is fixed but wider width and that is not equivalent to arbitrary width. For example, SIMD shuffle type instructions have no arbitrary length equivalent.
  - lallysingh 8y ago
    Why not? You take the new ordering as an input vector.
    - dragontamer 8y ago
      How would you make an arbitrary shuffle between arbitrary-lengthed vectors faster than an arbitrary gather/scatter to and from L1 Cache? Its possible to have a chip code specialized transforms or have a many-to-many crossbar when N is small (ex: 16), but when N is large (ex: 1024 elements), its no longer easy to see how to build a high-speed permute operator. ----------- That's the thing. People only use vpshufb because its WAY faster than L1 cache. If Intel made a faster gather/scatter, there wouldn't be much point to the vpshufb instruction. But the vpshufb instruction is so fast, because its so specialized and small. It only has to worry about a 16-byte permute. In short: we ALREADY have an arbitrary permute instruction. Its called gather/scatter. That's not what programmers want however. (I mean, programmers want a faster gather/scatter... but... vpshufb programmers use that operator only because its faster than L1 cache)
      - glangdale 8y ago
        Seriously. Permutes get harder as you scale - VBMI on CNL is an indicator that 64-way is pretty good but it's still considerably more expensive than 4 16-way permutes on the same architecture. There's a reason that gather is hard to do; I think if you rocked up and asked the architecture guys for a gather that was competitive with small-scale permute they would reply with the time-honored Intel putdown ("You are overpaid for whatever it is you do").
arundemeure 8y ago
I completely agree in principle (some applications are good fit for traditional long vector processing, but it's a terrible fit for others). However the RISC-V Vector Extensions basically let you use the processor in "SIMD mode" by setting the vector length to a small value. It will depend on the processor architecture whether a vector length of e.g. 4 is efficient or not, but I expect for many implementations it will be relatively efficient (and you can definitely just use it as a "wider GPR" if you want to). The only catch at the ISA level is it costs an instruction to change the vector size. So if you keep swiching between e.g. 128-bit and 512-bit instructions at a very fine granularity, that might add overhead... I'm not sure that's a very common case though?
petermcneeley 8y ago
Agreed. SIMDs true competitor is ironically the super-scalar architecture itself and its relative the VLIW.
brandmeyer 8y ago
I went on a bit of a research expedition to see if there was something that scaled better a general permutation instruction for SIMD machines. General permute scales at O(log(N)) in gate delay+ and O(N^2 * log(N)) in area, where N is the vector length. Its a full crossbar, but the fanout on the wires adds an additional log(N) factor in buffers. For a while, it seemed like a set of instructions based on a rank-2 CLOS network (aka butterfly network) would get the job done. It scales at O(log(N)) in gate delay+ and O(N * log(N)) in area, and is very capable. Fanout is O(1). You can do all kinds of inter- and intra-lane swaps, rotations, and shifts with it. You can even do things like expand packed 16-bit RGB into 32-bit uniform RGBA. But things like that SMH algorithm are definitely out of scope: Each input bit can only appear in at most one output location with the butterfly. So the cost to replicate a prefix scales at O(repetitions), which is unfortunate. Some algorithms based on using general shuffle are also relying on the use of PSHUFB's functionality as a complete lookup table, which the butterfly network can't do, either. My conclusion was that you're basically stuck with a general permute instruction for a modern SIMD ISA, scaling be damned. + The latency scaling is somewhat misleading thanks to wire delay - they are both O(N) in wire delay.

creato 8y ago

I agree. It seems like this strategy makes only the most braindead applications of SIMD better (simple loops that can be vectorized by an arbitrary factor), but doesn't really do anything to help the meatier SIMD workloads. Most SIMD code isn't as simple as this, and the code that is usually isn't a significant factor in either developer experience or runtime.

glangdale 8y ago
Seriously. A lot of these proposals go veering off into second-order considerations ("Easier to decode!" "A few picojoules less energy") as I'd be very surprised if the bottlenecks are going to be from SIMD vs vector architecture ISA issues - as compared to, say, memory bandwidth or multiply-add bandwidth.
- CoolGuySteve 8y ago
  A few years ago I tried to buy a liquid cooled overclocked server for trading. Enabling AVX cost extra due to the concentrated heat output from the MMU and each core's vector unit. It was along the lines of being able to get a server that was tested stable at 5GHz without AVX vs 4.5 GHz with AVX for the same price. So at least on Intel, these vector units are apparently limiting clock speeds and yields due to power consumption.
  - kllrnohj 8y ago
    Yes, but not due to instruction decode costs, which is really all this article is talking about. The real heat comes from actually doing the work, not decoding what work to do.

dbaupp 8y ago

Yeah, other examples include image codecs, such as JPEG: the DCT performed on the 8x8 blocks can benefit from SIMD, but the lanes aren't independent at all (matrix transposes, various intra-block additions).

wbl 8y ago
Do it across blocks and you can squeeze out more parallelism.
- Const-me 8y ago
  Only if these multiple blocks fit in the 16 registers. If they won't fit and the data will be evicted to RAM, that extra parallelism will slow down the code, not speed up.
- dbaupp 8y ago
  I believe the blocks end up stored as an array-of-structs where the structs have 8*8 = 64 elements. Doing the DCT in multiple blocks requires somehow transposing this into a struct-of-arrays-like format, maybe a gather of every 64th element (likely a waste of memory bandwidth) or some sort of unpckl/unpckh-like instructions. Either way, this may impose non-trivial overhead, and so the benefits of extra parallelism are hidden. (And, of course, that's all assuming there's enough registers, and I don't remember enough about JPEG to make a guess.)

atq2119 8y ago

Agreed, but then again, the vector architectures have the undeniable benefit of being agnostic to the underlying hardware. With a SIMD architecture, as registers get ever wider you need to recompile your code, and binary releases require multiple code paths. With a vector architecture, the hardware designers can just increase the machine's internal vector size and existing code will benefit immediately. Furthermore, it seems reasonable to count GPU users among "active practitioners of modern SIMD". All code that is written in a GPU-style -- which admittedly isn't too common yet on CPUs, but it would certainly be feasible and is possible since ispc came along -- immediately becomes a beneficiary of a well-designed vector instruction architecture.

skybrian 8y ago
Yes, recompiling can be a pain, but there's an argument that we should get used to recompiling things from source and make sure this path is smooth, rather than trying making old binaries work as long as possible. Static binaries are another reason.
- Joky 8y ago
  You lose binary portability though: what is you can write you image processing code such that it operates well whether your SIMD instructions is 4, 8, or 16 wide? (or more). Then shipping this binary for mobile phones for instance would take advantage of the wider register available on high-end device while working well on more modest CPUs.
  - CoolGuySteve 8y ago
    Shaders in games have worked this way on GPUs for probably a decade now without much issue.
    - Const-me 8y ago
      Only graphics shaders. Advanced compute shaders very often need to synchronize local data within warp. When you program such shaders you have to be aware about SIMD width (32 on NVidia and Intel, 64 on AMD), and design both algorithms and data structures accordingly. Failing to do so often have significant performance costs, I saw up to 10x speedup after implementing cooperative algorithm instead of straightforward one.

jabl 8y ago

In a vector arch like the risc-v vector extension, if you want to process exactly 256 or whatever at a time, just set the configuration or vector length register and off you go with SIMD-style programming?

glangdale 8y ago
It is very unlikely that such a configuration will perform remotely as fast as a native SIMD implementation, unless there is some truly heroic specialization going on under the hood. Obviously the work is still possible with vector ops, in the same way that it's still possible with scalar ops too. But will it be fast? My guess is no.
- jabl 8y ago
  > It is very unlikely that such a configuration will perform remotely as fast as a native SIMD implementation Why? AFAICS, a "real" vector ISA is mostly a superset of a SIMD ISA. What do you think is missing? Of course, if you want to eke out the absolute maximum performance then you need to be aware of the microarchitecture you're targeting, and a length-agnostic vector ISA like SVE or RVV don't buy you that much. But I don't see how that's worse than having to redo your code whenever the vendor introduces new HW with a new SIMD ISA. I guess one could argue that an implementation of a vector ISA targeting, say, linear algebra, would be different than an implementation focusing on maximum short-vector performance. Say, by having a vector length >> execution width, and using tricks like vector pipelining etc. to get performance rather than focusing on minimizing short-vector latency. But, that's a question of what the implementation is optimized for rather than saying what the ISA is good for, no?

lallysingh 8y ago

Sounds like you're getting fixated on the example. Short vectors would do what you want. And it's a lot easier to add specific vector instructions for particular use cases than adding N of them for each use case (for N simd sizes). Are you getting hung up on the term 'vector'? That doesn't assume you're just doing linear algebra.

bloomer 8y ago
No he's not getting hung up on the term vector. He is saying that SIMD is fixed but wider width and that is not equivalent to arbitrary width. For example, SIMD shuffle type instructions have no arbitrary length equivalent.
- lallysingh 8y ago
  Why not? You take the new ordering as an input vector.
  - dragontamer 8y ago
    How would you make an arbitrary shuffle between arbitrary-lengthed vectors faster than an arbitrary gather/scatter to and from L1 Cache? Its possible to have a chip code specialized transforms or have a many-to-many crossbar when N is small (ex: 16), but when N is large (ex: 1024 elements), its no longer easy to see how to build a high-speed permute operator. ----------- That's the thing. People only use vpshufb because its WAY faster than L1 cache. If Intel made a faster gather/scatter, there wouldn't be much point to the vpshufb instruction. But the vpshufb instruction is so fast, because its so specialized and small. It only has to worry about a 16-byte permute. In short: we ALREADY have an arbitrary permute instruction. Its called gather/scatter. That's not what programmers want however. (I mean, programmers want a faster gather/scatter... but... vpshufb programmers use that operator only because its faster than L1 cache)
    - glangdale 8y ago
      Seriously. Permutes get harder as you scale - VBMI on CNL is an indicator that 64-way is pretty good but it's still considerably more expensive than 4 16-way permutes on the same architecture. There's a reason that gather is hard to do; I think if you rocked up and asked the architecture guys for a gather that was competitive with small-scale permute they would reply with the time-honored Intel putdown ("You are overpaid for whatever it is you do").

arundemeure 8y ago

I completely agree in principle (some applications are good fit for traditional long vector processing, but it's a terrible fit for others). However the RISC-V Vector Extensions basically let you use the processor in "SIMD mode" by setting the vector length to a small value. It will depend on the processor architecture whether a vector length of e.g. 4 is efficient or not, but I expect for many implementations it will be relatively efficient (and you can definitely just use it as a "wider GPR" if you want to). The only catch at the ISA level is it costs an instruction to change the vector size. So if you keep swiching between e.g. 128-bit and 512-bit instructions at a very fine granularity, that might add overhead... I'm not sure that's a very common case though?

petermcneeley 8y ago

Agreed. SIMDs true competitor is ironically the super-scalar architecture itself and its relative the VLIW.

brandmeyer 8y ago

I went on a bit of a research expedition to see if there was something that scaled better a general permutation instruction for SIMD machines. General permute scales at O(log(N)) in gate delay+ and O(N^2 * log(N)) in area, where N is the vector length. Its a full crossbar, but the fanout on the wires adds an additional log(N) factor in buffers. For a while, it seemed like a set of instructions based on a rank-2 CLOS network (aka butterfly network) would get the job done. It scales at O(log(N)) in gate delay+ and O(N * log(N)) in area, and is very capable. Fanout is O(1). You can do all kinds of inter- and intra-lane swaps, rotations, and shifts with it. You can even do things like expand packed 16-bit RGB into 32-bit uniform RGBA. But things like that SMH algorithm are definitely out of scope: Each input bit can only appear in at most one output location with the butterfly. So the cost to replicate a prefix scales at O(repetitions), which is unfortunate. Some algorithms based on using general shuffle are also relying on the use of PSHUFB's functionality as a complete lookup table, which the butterfly network can't do, either. My conclusion was that you're basically stuck with a general permute instruction for a modern SIMD ISA, scaling be damned. + The latency scaling is somewhat misleading thanks to wire delay - they are both O(N) in wire delay.