14
$\begingroup$

C and C++ have no vector types or operations but many compilers offer their own non-portable extensions such as __attribute__((__ext_vector_type__())). The issue is vector types corresponding to vector registers and specific CPU vector instructions are not portable and the semantics vary for different CPUs.

However all SIMD implementations are conceptually the same: Applying the same operation to many different values at a time. What semantics could a language include that supports vectorization or constructs that could be trivially vectorized by a compiler and would be more or less independent of the underlying SIMD semantics of the CPU? What would be a good abstraction for vector operations that a language could provide?

$\endgroup$
1
  • $\begingroup$ I don't know if any of the documentation has been archived online, but you might want to search for the languages developed at Thinking Machines Corporation for the massively parallel Connection Machine: C*, *Lisp, CM Lisp, and CM Fortran. While we had a web site, this was the early days of the web and we didn't have tools for moving this stuff online at the time. $\endgroup$
    – Barmar
    Aug 25, 2023 at 0:42

7 Answers 7

7
$\begingroup$

The way GLSL does SIMD is by having vectorized primitives (float3, float4, etc) that you can do operations on, or access individual elements. I figure a templatized version of it that can expand to however many elements the user wants is probably the best way, and then the compiler can reduce that to however many elements the CPU can vectorize.

One example is std::experimental::simd<> in C++ (experimental) SIMD library:

The SIMD library provides portable types for explicitly stating data-parallelism and structuring data for more efficient SIMD access.

$\endgroup$
3
  • $\begingroup$ “a templatized version of that…” Like C# Vector<T>? $\endgroup$
    – Bbrk24
    May 16, 2023 at 18:11
  • $\begingroup$ I was thinking of it being templated on the vector length instead of the type, so there could be a FloatVec<C> type that can be used as FloatVec<4> | FloatVec<5> etc. That seems to me like the best way to support it compiler side instead of passing that work on to the standard library like I believe C# does. $\endgroup$
    – kouta-kun
    May 16, 2023 at 18:12
  • 1
    $\begingroup$ These days, shader float3/etc types are not typically compiled to SIMD operations in the way you might expect. Instead, shader compilers exploit the fact that the program is written in terms of a single vertex/fragment/etc but intended to run on a large number of them independently. The SIMD lanes are used to parallelize across those, rather than anything within the source program. This is typically referred to as "SPMD." $\endgroup$
    – rpjohnst
    Aug 29, 2023 at 1:49
9
$\begingroup$

What semantics could a language include that supports vectorization or constructs that could be trivially vectorized by a compiler and would be more or less independent of the underlying SIMD semantics of the CPU?

The SPMD paradigm enables source code to express vectorizable code without committing to any particular vector size. Although the Wikipedia page mostly talks about using multiple cores, the parallelism it implicitly exposes can be used in any way you like, including using it for vectorization, as for example Intel's ISPC does.

However all SIMD implementations are conceptually the same: Applying the same operation to many different values at a time.

I would like to push back on this a bit. There is a purely vertical "core" in all SIMD implementations, but a lot of the power of SIMD in practice comes from other operations. For example, various versions of multiply-vertically-and-add-horizontal-pairs are staples of multi-media processing, and shuffles are also crucial. And vector table-lookup/shuffle-by-variable (TBX,PSHUFB, VPERMB) forms the basis of many advanced SIMD tricks. Purely vertical SIMD covers a not-insignificant subset of SIMD uses, but it is a subset, one that leaves out some of the most powerful uses.

The SPMD paradigm does not by itself address those kinds of operations either, but various languages that use that paradigm (eg CUDA, sufficiently modern OpenCL, ISPC) offer at least some forms of cross-instance data movement (other than by going through memory) via built-in functions.

$\endgroup$
2
  • $\begingroup$ Could you give an example (or many) of advanced SIMD tricks? $\endgroup$
    – Pablo H
    Aug 23, 2023 at 15:43
  • 3
    $\begingroup$ @PabloH for example: the character classification trick in simdjson, bit-reversing integers, bit-counting integers, a trick for small DFAs, (un)packing data with "holes", arbitrary functions on small integers, it keeps showing up all over the place in different contexts because it's such a general and powerful operation $\endgroup$
    – user1030
    Aug 23, 2023 at 16:04
6
$\begingroup$

Probably the most portable way to do this is to leverage the very sophisticated optimisations, including automatic vectorisation, provided by established compiler backends such as LLVM. For the vast majority of language implementors, compiling to a suitable IR and then letting a third-party backend perform the low-level optimisations will be a much better trade-off of implementor effort to program performance, than implementing such optimisations oneself, especially if there is a need to support multiple target architectures (i.e. portability).

For example, here's a Rust function which naively adds four floats:

pub struct Vec4 {
    x: f32, y: f32, z: f32, w: f32,
}

impl Vec4 {
    pub fn add(self, other: Self) -> Self {
        Self {
            x: self.x + other.x,
            y: self.y + other.y,
            z: self.z + other.z,
            w: self.w + other.w,
        }
    }
}

Rust's compiler uses LLVM as a backend. Here's the output from Godbolt Compiler Explorer, with optimisations enabled:

example::Vec4::add:
        mov     rax, rdi
        movups  xmm0, xmmword ptr [rsi]
        movups  xmm1, xmmword ptr [rdx]
        addps   xmm1, xmm0
        movups  xmmword ptr [rdi], xmm1
        ret

The addition is done by the addps instruction, which:

Adds four, eight or sixteen packed single-precision floating-point values from the first source operand with the second source operand, and stores the packed single-precision floating-point result in the destination operand.

So the programmer didn't need to give any extra context or hints in the source code, the LLVM backend was smart enough to vectorise it anyway.

$\endgroup$
4
  • $\begingroup$ I would not necessarily say this is portable, as unfortunately depending on the whims of the optimizer is rather brittle. That is, while LLVM may auto-vectorize this version of the code: it could fail to auto-vectorize the next version, GCC could fail to auto-vectorize this version, and of course it could also fail on some platforms... $\endgroup$ Sep 8, 2023 at 14:16
  • $\begingroup$ @MatthieuM. That's a fair point, but I think for major compiler backends like LLVM and GCC, the failure to vectorise this kind of code (when compiling with suitable optimisation flags enabled) would be considered a bug. I don't have enough experience with either to confirm this, but I'd be surprised if that kind of optimisation wasn't tested for in those projects' automated tests. $\endgroup$
    – kaya3
    Sep 8, 2023 at 17:13
  • $\begingroup$ I wouldn't regard this as a reliable means of allowing programmers to write efficient code in implementation-agnostic fashion. If a program would require that a compiler find a particular optimization in order to yield good performance, there should be a means of explicitly inviting that optimization. In many cases, performing optimizing transforms is very easy compared with identifying cases where they will be worthwhile, and validating that the transforms will not affect behavior in ways contrary to application requirements. $\endgroup$
    – supercat
    Sep 18, 2023 at 15:36
  • $\begingroup$ If a programming language has a construct which specifies that a range of code should be executed once for each value of i within a certain range, but the loop iterations may be performed in any order, and a break may skip any, all, or none, of the remaining iterations, a compiler will be able to transform to use vector or parallel operations much more easily, safely, and effectively, than it could parallelize a "for" loop written via in conventional fashion. $\endgroup$
    – supercat
    Sep 18, 2023 at 15:41
6
$\begingroup$

Array Programming

One possible way is to have arrays similar to C++ std::valarray or Fortran arrays. Including semantics to perform operations on an entire array would be higher level than the compiler-specific SIMD types but could easily be implemented with SIMD.

An example of array programming semantics in a C-style language:

int array_1[4] = {1, 2, 3, 4};
int array_2[4] = {5, 6, 7, 8};
int array_3 = array_1+array_2; // {6, 8, 10, 12}
// Array-wise operations could be trivially identified and implemented with SIMD instructions
$\endgroup$
1
  • 3
    $\begingroup$ This "hypothetical language", of course, is older than a lot of people here: Fortran 77. $\endgroup$
    – Pseudonym
    May 17, 2023 at 0:55
6
$\begingroup$

One important consideration is how your language handles aliasing. This is a major killer of auto-vectorization opportunities for C and C++.

For example, in the following function:

void add(float *out, const float *a, const float *b, size_t count) {
    for (size_t i = 0; i < count; i++) {
        out[i] = a[i] + b[i];
    }
}

the compiler must not emit the obvious vectorized code, because the caller is allowed to pass a pointer for out that overlaps one of the input arrays. Sometimes they can vectorize by adding code to compare the pointers for overlap, and falling back to a naive scalar implementation if they do.

C99 tried to ameliorate this with restrict, with which you can promise the compiler that the buffers will not overlap. But its definition involves complicated semantics for when an access occurs indirectly "through" the pointer out. Moreover, it's up to you, the programmer, to ensure that all callers keep that promise, on pain of undefined behavior, and the compiler can't necessarily detect violations.

On the other hand, in Rust, the equivalent code can be auto-vectorized easily and safely. You have to borrow the output array in order to pass its reference to add, and this guarantees that no other reference (such as to the input arrays) can alias it. The compiler can and does ensure that callers keep this promise.

$\endgroup$
4
  • $\begingroup$ Good point, but in some cases the input and output arrays are the same, or overlapping. The programmer needs to ensure that the algorithm is correct in both cases, pointers aliasing and not aliasing. The compiler typically does alias analysis and emits different code for the "may-alias" and "cannot-alias" cases. $\endgroup$ Sep 8, 2023 at 15:31
  • $\begingroup$ @MartinBerger: Yes, that's exactly the point I am making. $\endgroup$ Sep 8, 2023 at 15:33
  • $\begingroup$ @NateEldredge: The C99 rules could have been simple if it recognized a three-way split of objects definitely based on P, objects definitely not based on P, and objects that might be based on P, with aliasing restricted only between the first two, and accepting that not all objects could be classified into the first two categories (though any and all objects could safely be classified into the third). Worse than the complexity, however, is the fact that the rules even as implemented have weird and bizarre corner cases which result in equality comparisons having side effects. $\endgroup$
    – supercat
    Sep 18, 2023 at 15:44
  • $\begingroup$ @MartinBerger: Indeed, many optimizations rely upon a compiler's ability to safely assume that arr1[i] will not alias arr2[i+n] for a constant non-zero n. Such an assumption might not hold if arr1 and arr2 are different and identify overlapping regions of storage, but would hold in both the "pointers equal" and "storage is disjoint" cases, without code needing to distinguish between them. Worse, the way clang and gcc process restrict means that even code that specially handles the "pointers are equal" case may be transformed in breaking fashion. $\endgroup$
    – supercat
    Sep 18, 2023 at 16:08
3
$\begingroup$

TL;DR: This is very much an open question.

Challenges

There are two challenges:

  1. The varying size of registers: some CPU only allow specific fixed-sizes (Intel CPUs go 128 bits, 256 bits, 512 bits) while others allow variable-sizes (up to a maximum).
  2. Various CPU families, and various CPUs within a family, have different sets of instructions, and while vector addition is a mainstay and fairly uniform, shuffle or lookup-table instructions are quite disparate.

The problem, therefore, is that given the incredible diversity of the instructions, it is hard to come up with an abstraction.

Partial Handling of Size Differences

Handling the varying sizes of common instructions (vector addition, vector multiplication) is perhaps the simplest task.

Apart from built-in language/compiler features, the use of generics allows the user to express a transformation regardless of the vector size. Combined with a library that handles the selection of the size -- with a mix of compile-time and run-time -- this works fairly well.

As an example consider the faster library (Rust):

let lots_of_3s = (&[-123.456f32; 128][..]).simd_iter()
    .simd_map(f32s(0.0), |v| {
        f32s(9.0) * v.abs().sqrt().rsqrt().ceil().sqrt() - f32s(4.0) - f32s(2.0)
    })
    .scalar_collect();

And note how the users is manipulating f32s without specifying the number of lanes.

This works because the language provides:

  • Generics.
  • Compile-time detection of the set of number of lanes potentially available.
  • Run-time detection (standard library) of the set of number of lanes actually available.
  • Intrinsics, mapping to the desired SIMD instructions.

Unfortunately, this solution is only partial because it only uses "input-driven" number of lanes picking. If the user wished to avail themselves from table-lookup instructions, then it would be harder to abstract that -- as the very way the table is populated depends on the number of lanes actually available.

In such cases, the user essentially needs to construct multiple code-paths, each for a given number of lanes, or restrict execution to the lowest common denominator. And even then, the user should beware of semantic differences between instructions sets.

Language (& Run-time)

In the end, a power-user will, today, outshine any auto-vectorization... because a power-user can use SIMD instructions in ways that boggle the mind (see simdjson) and no compiler has optimizations that are that sophisticated.

To support a power-user, then a language should provide:

  • Intrinsics: so that the power-user can directly call the vector instruction.
  • Compile-time/Run-time detection/selection facilities: so that the power-user can choose which code-path to use based on the current CPU model (and generic CPU family) and possibly refuse to use older models.
$\endgroup$
1
  • $\begingroup$ Agreed, this is very much not a solved problem. You can also see this from the many ISA extensions the processor designers have been cooking up. $\endgroup$ Sep 8, 2023 at 15:32
1
$\begingroup$

First, you make it part of the language, so it isn't non-portable because some compilers don't support it or use different syntax.

Now lets say processor A has vector registers containing two single precision numbers, while processors B, C and D have vector registers with 4, 8, or 16 single precision numbers. How do you do this portably? You can allow declaring a type "array of 16 single precision numbers" or "array of 17 single precision numbers" everywhere and the compiler produces for example code for 8, 4, 2 or 1 operations, or for one additional operation.

The programmer can look at the size of a register and create different instructions depending on the register size.

And every processor has some instructions that don't fit into any scheme in the language, in that case there could be intrinsic functions that work at differnt speeds depending on the processor.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .