Adaptive vector lengths without global state

[sunfishcode]

Context: #4, #20. Global state is problematic, but even if we make it explicit, the ability to have arbitrary length switches is hard to implement on many architectures. The following is a sketch of a design which avoids both of these, while preserving some key advantages of flexible vectors.

Similar to the explicit loop variant of @aardappel's post here, it has a vec_loop, but this proposal is lower-level, making state explicit and avoiding unnecessary restrictions, while still hiding information as needed by implementations. I haven't prototyped this, but in theory it should be implementable on RISC-V V, SVE, AVX-512, as well as simd128-style architectures.

Implementations with dynamic vectors or masking could use them. But implementations could also chose to emit multiple loops, to handle alignments or remainders. Such implementations could also chose to run some vector loops at twice or more the hardware length, making a register-pressure vs. speed tradeoff as they see fit.

New Types:

• vec<n>: a flexible vector of element bitwidth n
• vec_len<n>: a scalar but opaque element count, limited to n as the widest bitwidth

New Opcodes:

• vec_loop<vl, n>: like loop but

  • vl: immediate identifying a local variable to set to the number of elements being processed within an iteration of the loop, with type vec_len<n>. Using this local outside of a vec_loop is prohibited.
  • n: immediate which declares the bitwidth of the widest element type which will be processed in the loop
  • has one operand, the total number of elements the program wants to process in the loop

• vec_step<vl, scale>: (i32) -> (i32)

  • vl: immediate identifying a vec_len local variable
  • scale: immediate scaling factor
  • computes operand + vl * scale

• vec_load<vl, n>, vec_store<vl, n>: like load and store` but

  • vl: immediate identifying a vec_len local variable
  • n: immediate specifying the vector element bitwidth to use

• The arithmetic operations from simd128, with a similar vl immediate added.

Example

Add two arrays of length $n starting at $A and $B and store the result in an array starting at $C.

  (local $A i32) (local $B i32) (local $C i32) (local $n i32)
  (local $vl vec_len.32)
  ...

  local.get $n        ;; number of elements in array to process (passing zero is ok!)
  vec_loop 32 $vl     ;; start vector loop processing (at most) 32-bit elements

    (local.set $t0 (vec_load $vl 32 (local.get $A)))
    (local.set $t1 (vec_load $vl 32 (local.get $B)))
    (local.set $t2 (vec_add $vl (local.get $t0) (local.get $t1)))
    (vec_store $vl 32 (local.get $C) (local.get $t2))

    (local.set $A (vec_step $vl 4 (local.get $A)))
    (local.set $B (vec_step $vl 4 (local.get $B)))
    (local.set $C (vec_step $vl 4 (local.get $C)))
    (local.set $n (vec_step $vl -1 (local.get $n)))

    (br_if 0 (local.get $n) (local.get $n)) ;; pass the count back to the top
  end                ;; end vector loop

Nondeterminism

The length in each iteration of a vec_loop is nondeterministic. It's visible in vec_step, in the number of elements loaded and stored in vec_load and vec_store, and in any side effects of the loop. It's expensive to completely hide the hardware vector length with any flexible-vector proposal, so whether or not there should be nondeterminism is an independent question.

One thing this proposal does do is avoid having nondeterminism which has to be constant for the duration of the program. Wasm doesn't currently have any nondeterminism that behaves like that, and it would have implications for suspending a program and resuming it on another architecture, or for distributing a program over multiple architectures.

Vector subroutines

A call within a vec_loop could make sense if the callsite passes the vec_len value to the callee. Since vec_len is a type, it'd be part of the function signature, so implementations could compile the callee to be called from within a vector loop without whole-program analysis.

Nested vec_loops

Some architectures wouldn't be able to implement arbitrary nested vector parallelism, so one possible approach would be to prohibit it. Lexical nesting is easy to detect, and dynamic nesting -- a call inside a vec_loop calling a function that contains another vec_loop could be prohibited if we require calls in vec_loops to have exactly one vec_len argument, and prohibit vec_loop inside functions with a vec_len argument.

Masks, shuffles, extracts and inserts, strided loads/stores

There are ways this design could be extended to include these, but left them out to keep things simple to start with. It's mostly an independent question whether these can be implemented efficiently.

[penzn]

This is a good idea, definitely better than what we were able to come up with in #4. I think it should definitely investigated as a potential solution. I would still want to establish a baseline with the "exposed length" style, to have something to compare to, especially since the rest of operations (aside from the length) would not depend on this too much.

The obvious challenge from spec perspective would be introducing a new kind of non-determinism. But that should not be a deterrent, since any proposal hiding the length would have to be non-deterministic.

Another thing worth mentioning is that some work would be needed on tools producing wasm. Existing backends support vector instructions, even variable-length ones, but not the control flow we would need for this. This should not be a deterrent either - there are precedents of wasm operations diverging from what native targets do.

[lemaitre]

Such a design seems too simple to handle most SIMD/vector algorithms because of the lack of inter-lane operations. The prohibition of nested parallelism is also problematic for not so few algorithms.

Matrix multiplication is a really simple example that requires both inter-lane operations (either broadcast or reduce) and nested parallelism, and I fail to see how one would implement it with such an interface.

[sunfishcode]

The nested-SIMD restriction is mainly motivated by my understanding of the limitations of hardware platforms. It should be straightforward to lift, if we wish, since there's no global state. The question is, what algorithms would use nested-SIMD, and how would they map to various architectures?

Either way, nesting with regular loop isn't restricted, so eg. outer-loop vectorization is supported.

Broadcast and reduce would be straightforward -- broadcast would be an instruction which takes a scalar operand and produces a vec<n> result, and reductions would be instructions which take a vec<n> operand and return scalar results.

Even shuffles could work: for example, if you set the vec_loop immediate to 128, that says you want to process at least 128 bits each iteration, and then we could let you do 128-bit-wide shuffles (eg. xyzw/rgba kinds of things), while still allowing implementations to run the loop at a wider lengths when they want to.

[penzn]

Since the length is tied to lane size, how would this work for widen or narrow instructions?

[sunfishcode]

The n immediate on vec_loop declares the widest element bitwidth that will be operated on in the loop; you can operate at that width or narrrower, or both. To convert from an array of 16-bit elements to an array of 32-bit elements for example, declare a loop with n=32, the wider bitwidth, and use eg. a vec_load with n=16, and let's say we add a vec_extend_s instruction to perform a conversion, with immediates declaring its operand and result widths:

  (local $A i32) (local $C i32) (local $n i32)
  (local $vl vec_len.32)
  ...

  local.get $n
  vec_loop 32 $vl     ;; start vector loop processing (at most) 32-bit elements

    (local.set $t0 (vec_load $vl 16 (local.get $A))) ;; Load 16-bit elements; return type vec<16>
    (local.set $t2 (vec_extend_s 16 32 $vl (local.get $t0))) ;; vec<16> -> vec<32>
    (vec_store $vl 32 (local.get $C) (local.get $t2)) ;; Store with 32-bit elements

    (local.set $A (vec_step $vl 2 (local.get $A))) ;; Step by 2 bytes for the input array
    (local.set $C (vec_step $vl 4 (local.get $C))) ;; Step by 4 bytes for the output array
    (local.set $n (vec_step $vl -1 (local.get $n))) ;; Decrement the loop counter

    (br_if 0 (local.get $n) (local.get $n)) ;; pass the count back to the top
  end

[lemaitre]

The issue I see here is that you lose parallelism when processing smaller elements as your registers are not full.
The common way to handle multiple element sizes is to process multiple registers of the larger types in order to fill completely the register with the smaller type. This looks complex to implement with your design.

How would you deal with functions? if you have to pass $vlat run time, I guess you would basically lose any benefits to having such a special variable, and your implementation would be, at best, as efficient as masks.
If $vl is some kind of load-time constant, you would need to monomorphize all the functions for different sizes. That seems expensive.

Even shuffles could work: for example, if you set the vec_loop immediate to 128, that says you want to process at least 128 bits each iteration, and then we could let you do 128-bit-wide shuffles (eg. xyzw/rgba kinds of things), while still allowing implementations to run the loop at a wider lengths when they want to.

I think it would be super useful to have intra 128-bit shuffles. But if you only deal with shuffles inside 128-bit "lanes", then there is a bunch of algorithms that would not be really implementable. Prefix sum is an example.

If you want a toy program to experiment with your design, I would suggest you the following one:

static const uint8_t CNT_LUT[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; // LUT can fit into a 128-bit register
void popcount_prefixsum(const uint8_t*restrict A, uint16_t*restrict B, int n) {
  uint16_t sum = 0;
  for (int i = 0; i < n; ++i) {
    uint8_t a = A[i];
    uint8_t cnt_low = CNT_LUT[a & 0xf];
    uint8_t cnt_high = CNT_LUT[a >> 4];
    uint8_t cnt = cnt_low + cnt_high; // cnt = popcount(a)
    sum += cnt;
    B[i] = sum;
  }
}

I consider this to be a good primary test for the usefulness of a SIMD ISA as it exposes a lof of features (mixed type lengths, LUT, reduction, rotation) that people would expect from a SIMD ISA. They are a few other missing like masks, compress/expand, gather/scatter, conflict detection, but that is a good start.

In fact, SSE2 does not pass this test, which reflects the shortcomings of that ISA.

[sunfishcode]

The issue I see here is that you lose parallelism when processing smaller elements as your registers are not full.
The common way to handle multiple element sizes is to process multiple registers of the larger types in order to fill completely the register with the smaller type. This looks complex to implement with your design.

One possible way to model this would be to add a vec_half opcode, which has type (vec_len<n>) -> (vec_len<n*2>), and which conceptually divides the VL in half so that you can do half-VL-but-double-width loads with it:

(vec_loop 16 $vl
    (local.set $half_vl (half (local.get $vl))
    (local.set $t0 (vec_load $half_vl 32 (local.get $A))) ;; Load 32-bit elements; return type vec<32>
    (local.set $t1 (vec_load $half_vl 32 (local.get $A))) ;; Load more 32-bit elements; return type vec<32>
    (local.set $t2 (vec_wrap 32 16 $vl (local.get $t0) (local.get $t1))) ;; vec<32> -> vec<16>
    ...

How would you deal with functions? if you have to pass $vlat run time, I guess you would basically lose any benefits to having such a special variable, and your implementation would be, at best, as efficient as masks.
If $vl is some kind of load-time constant, you would need to monomorphize all the functions for different sizes. That seems expensive.

The key is that $vl has a distinct type, vec_len<n>. When the engine is compiling a function with a $vl argument, it knows that function is called within vector contexts, so it can use different calling conventions, and different strategies under the covers. A simple strategy for a machine with a fixed VL might be to just have the function handle one VL-length vector per call, and use a scalar remainder loop when compiling the vec_loop. On an architecture with mask registers, you could pass a mask value as an extra argument, and use that. On an architecture with a vector-length register, the function could just use it.

But if you only deal with shuffles inside 128-bit "lanes", then there is a bunch of algorithms that would not be really implementable. Prefix sum is an example.

If you want a toy program to experiment with your design, I would suggest you the following one:

I'm not very familiar with these kinds of algorithms. Has anyone prototyped this kind of prefix-sum algorithm with the other flexible SIMD proposals? I'd be curious to see how this looks.

[lemaitre]

@sunfishcode

I finally found time to give it a thought, and your design might just work. The syntax looks a bit weird, but it seems to solve the issues we are trying to solve.

The problem I see with your design is the necessity to have a remainder for some ISAs (so for all WASM codes in practice).
As I said in another issue (most of #7), scalar remainders should be avoided because its costs is higher with wider SIMD, to the point that the scalar remainder might account for the majority of the processing time for not so small loops.

If you implement a masked remainder to alleviate this issue, what is the actual gain of your vec_loop design?
Plus, you seem to propose to have masked iterations on all the iterations for for targets with native masks, but generating this mask might be not-so cheap for tiny loops. So even if you have masks, you still might want to avoid them for most of your loop, and keep them only for the remainder.

To nuance my comment, I think your main goal to avoid global state is really good, and it is one goal we have in common you and I. It's just that I think masked operations are pretty much necessary for other reasons, and could be used also for loops.
I think we could keep your idea of a special kind of mask to encode vector length (which could be implemented more optimally on archs without native support for masks), generate loop body with full width vectors, and use those special masks only for the remainder.

[sunfishcode]

The vec_loop design avoids the need to decide which remainder strategy is best by letting wasm engines pick any remainder strategy they want.

At the wasm level, vec_loop can handle any n, so wasm code doesn't need explicit remainder loops. In the implementation, implementations can chose to lower vec_loop into one loop or multiple loops. And they can pick any remainder strategy they want, such as masking in the main loop, a separate remainder loop with masking, a separate scalar remainder loop, using a vector-length register, or anything else that makes sense on the target hardware.

[lemaitre]

The vec_loop design avoids the need to decide which remainder strategy is best by letting wasm engines pick any remainder strategy they want.

In theory, I would agree. But in practice, it seems impractical to impose WASM engines to change the meaning of the code depending on if it is the remainder or not. This is better achieved by compilers because they have time to reason about the code.
Plus, this would impose to duplicate (monomorphize) functions taking a vec_len for the case where the length is known to be maximal (in loop body), and for the generic case. Otherwise, you would slow down the loop body for no good reason (especially on ISAs without native support of masks like SSE or Neon).

At the wasm level, vec_loop can handle any n, so wasm code doesn't need explicit remainder loops.

This is not compatible with something you said earlier about having vec_len being always full on some ISAs. Or maybe I misunderstood that last point. So let me ask again to ensure I understand your point correctly:

• Would you have dynamic vec_len for SSE or Neon?
• If so, how would you efficiently implement a dynamic vec_len on SSE or Neon?
• Would it be fast enough to be used for the loop body? (also a concern for AVX*)
• If it is not fast enough for the loop body, how would you handle functions? (also a concern for AVX*)
• If vec_len would not be dynamic on SSE and Neon, how would you avoid the presence of a remainder (whatever its form) in the WASM code?

And they can pick any remainder strategy they want, such as masking in the main loop, a separate remainder loop with masking, a separate scalar remainder loop, using a vector-length register, or anything else that makes sense on the target hardware.

This looks super complex to implement on a WASM engine that has basically no time to handle those. It would indeed need to rebuild the semantic of the code (building the AST and the SSA form) in order to change the meaning of the code and make the actual decision. Unless there is something I am not aware of, this looks very impractical.

Also, the are some hardware solutions that cannot fit with this model. The one I have in mind is the global vector length, because you would not be able to handle nested loops.
That being said, as long as you don't target such an architecture, that's fine. And to be fair, what I have in mind cannot handle those either.
I just wanted to highlight this limitation, to remind you that, even in theory, your proposal cannot accommodate all the architectures.

[sunfishcode]

This is better achieved by compilers because they have time to reason about the code.
[...]
This looks super complex to implement on a WASM engine that has basically no time to handle those.

In general in wasm, engine compile time is an important concern. For wasm SIMD though, there's a good argument for letting engines take (somewhat) more time. On one hand, achieving portability, efficiency, and practicality in a single SIMD design is already very difficult, and the current designs are already making some major tradeoffs. Adding stringent compile-time restrictions risks making these worse. And on the other, SIMD is typically a very small portion of most applications (in static code terms), so making SIMD compiler slower won't affect most code. So if taking additional compile time on SIMD code gives us better performance, portability, or practicality, it's worth considering.

The design proposed here would likely require JITs to build an IR to perform many of the optimizations we want here. However, all major JIT-based wasm engines' top-tier backends already build IRs.

Would you have dynamic vec_len for SSE or Neon?

Yes. Here's an overview of how vec_loop would work at different levels.

• At the wasm level, vec_loop can always be passed any arbitrary dynamic element-count. Applications don't need to provide their own remainder loops because they can just pass whatever count they have to vec_loop. vec_len<n> values are dynamic. The only platform-specific behavior is the specific number of elements vec_loop chooses to operate on in each iteration.
• In an implementation on SSE/NEON/etc.:
  • a vec_loop might be compiled into two loops, a regular vector loop and a scalar remainder loop*
  • a function with a vec_len<n> argument would then be compiled into two versions, one which operates on full vectors, and one that operates on scalars. Calls inside the regular vector loop would call the full-vector version, and calls in the scalar remainder loop would call the scalar version.
• In an implementation on AVX-512:
  • a vec_loop might be compiled into a single loop that uses masking in a dynamic-vector-length style*
  • a function with a vec_len<n> argument would then be compiled into one version, which has an extra mask argument to apply to all vector operations in the function.
• In an implementation on RISC-V V:
  • a vec_loop might be compiled into a single loop that uses the dynamic vector length hardware*
  • a function with a vec_len<n> argument would then be compiled into one version, which uses the current value of the dynamic vector length register.

* Other implementation strategies are possible; I just picked some strategies to serve as examples.

Also, the are some hardware solutions that cannot fit with this model. The one I have in mind is the global vector length, because you would not be able to handle nested loops.

I wrote a bit about this in the "Nested vec_loops" section above. vec_loop does support global-vector-length architectures such as RISC-V V, and in fact, they'd likely be the easiest platforms to support. Also, you can nest vec_loop inside loop, or loop inside vec_loop, for outer-loop vectorization. The thing that's unsupported is nesting vec_loop within vec_loop, which to my knowledge doesn't correspond to a common SIMD idiom, but if it does turn out to be important, is something I expect the design could be extended to handle.

[lemaitre]

Ok, that is much more clear to me. So you would indeed have dynamic vec_len<> objects that can encode a length from 0 up to a constant defined by the target architecture, and you would monomorphize all the functions taking a vec_len<>: one version with a dynamic value, and one version with the maximal value. The loop body would, most likely, use the specialized version, while the remainder would always use the dynamic version.

This makes total sense, and the translation overhead looks reasonable. I can know totally see how WASM code would be translated into machine code (except maybe Risc-V V, but that's because I don't know enough about it).

About nesting: yes, I was thinking about nesting vec_loops. It is a bit weird, but some algorithms actually do nest. Some implementations of the matrix product with on-the-fly transposition, for instance. But it might be reasonable to forbid it for now, and later reconsider it if we have more hindsight.

Re-reading your proposal, there is something a bit odd: "Using this local outside of a vec_loop is prohibited."
I see no reasons to forbid the use of a vec_len<> outside a vec_loop. Is it to accommodate for Risc-V V? Because I think that having to handle different type sizes would have the same implementation complexity than multiple vec_len<>, no?
One use case I see for vec_len<> outside of vec_loop is to generate loop constants from functions taking a vec_len<>.

[sunfishcode]

Indeed. And, an implementation which unrolls loops could also use lengths greater than the target architecture's nominal length on some loops.

Forbidding vec_len outside of vec_loop is because the value is only meaningful within a given iteration of a vec_loop. If you want to pre-generate a vector to pass into a vec_loop, doing it manually would require knowing how many elements to add to it, but that's tricky because the vector length might differ between vec_loop iterations. A possible alternative might be to add instructions to algorithmically describe vector values. A common example of this is a broadcast instruction, but in theory we could also add instructions to produce vector values from arithmetic sequences, even/odd patterns, or other things.

[lemaitre]

Forbidding vec_len outside of vec_loop is because the value is only meaningful within a given iteration of a vec_loop.

The thing is, if you explicitly forbid vec_len outside of vec_loop, it has to be written in the spec, and WASM compilers/engines will have to make sure it never happens. So it adds complexity at multiple levels. Adding all this complexity just because you don't see a use case is pretty pointless. That would make sense if this gave you more guarantees as a result, but I don't see it.

If you want to pre-generate a vector to pass into a vec_loop, doing it manually would require knowing how many elements to add to it, but that's tricky because the vector length might differ between vec_loop iterations.

You could want to build an in-register LUT (like for emulating popcount), and you just happen to have a function that takes a vec_len and computes popcount for all elements. If you forbid vec_len outside loops, you would not be able to call this function to build your LUT: you would have to inline it manually, or duplicate it without the vec_len.

If vec_len is allowed outside vec_loop, you could build your temporary LUT by calling the function with a maximal vec_len (and the right input vector, of course).

A possible alternative might be to add instructions to algorithmically describe vector values.

That's another problem. It is interesting and must be solved at some point, but it is orthogonal to the discussion we have now.

---

Let me explore something with you. It seems that forbidding vec_len outside of vec_loop is the same issue than nesting loops: you want to have a single "active" vec_len.

Having multiple "active" vec_len is no problem for most ISAs (SSE, AVX, AVX512, Neon, SVE, Altivec, VSX...) because they decorate operations and are not part of global state. If we decided to target only those, it would be simpler to allow vec_len outside of vec_loop and nested vec_loops. Simpler on the spec, simpler on the compilers, simpler on the engines.

Now, this design is problematic when the target architecture handles vec_len with a global state, and allowing a single "active" vec_len ensures we don't need to constantly switch between vec_lens. The only reasonable ISA like that we might target is Risc-V V, so let me continue by considering only Risc-V V and nothing else.

As I mentioned earlier, we need a way to process types with different sizes in the same loop, and you proposed vec_len<n> where n would be the size (in bits) of the type worked on, and you would have instructions to convert a vec_len<n1> into a vec_len<n2>. With this, you would have multiple vec_len inside the loop, bu they are somehow tied together.
As far as I recall, Risc-V V needs a vsetvl each time you want to process different types (with different sizes). So if we need to handle multiple types inside the loop, the WASM engine would already need to generate multiple vsetvl for the loop, namely: before each operation that use a different type size than the previous one.

In fact, this is not different than having multiple vec_len<n> (with the same n), and call vsetvl before each operation that operate with a different vec_len<n> than the previous one. So to me, the machinery to handle multiple types in Risc-V V is already enough to support multiple "active" vec_len at the same time. So we could allow it on Risc-V V, and all ISAs would benefit from it.

---

Also, I've looked back at your example with multiple type size:

(vec_loop 16 $vl
    (local.set $half_vl (half (local.get $vl))
    (local.set $t0 (vec_load $half_vl 32 (local.get $A))) ;; Load 32-bit elements; return type vec<32>
    (local.set $t1 (vec_load $half_vl 32 (local.get $A))) ;; Load more 32-bit elements; return type vec<32>
    (local.set $t2 (vec_wrap 32 16 $vl (local.get $t0) (local.get $t1))) ;; vec<32> -> vec<16>
    ...

And this example only works when $vl is maximal (full). Indeed, if the maximal vec_len<16> is 8 and $vl is 5, you need to make the first load of $A with a vec_len<32> of 4 and the second load with a vec_len<32> of 1. In theory, (3 + 2) would also be valid, but as 5 is not even, you cannot have the loads with the same vec_len<32>. This means that we really need multiple "active" vec_len<n> if we want this code to work.

And processing multiple type sizes at the same time is really common in signal processing, and also in AI if I'm not mistaken.

---

In conclusion, I really believe we need to have multiple "active" vec_len at the same time, and if we do, there is no point in forbidding either nested vec_loops or vec_len outside vec_loop. Plus, there is no implementation issue on all major platforms, and even in Risc-V V, it is solvable, and the solution is already needed for other reasons (multiple type sizes.).