Looking for status of SIMD implementation

[Richard Sandiford]

"Bin.Cheng" <amker.cheng@gmail.com> writes:
> On Thu, Jun 24, 2021 at 4:50 PM Matthias Kretz <m.kretz@gsi.de> wrote:
>>
>> CC'ing libstdc++, to discuss stdx::simd design in public.
>>
>> I discussed variable length vectors at length in the C++ committee and so far
>> I've not seen any useful progress that could make it work for vector *types*.
>> The main issue is that C++ itself would require support for runtime-sized
>> types throughout the language. E.g.
>>
>> template <class T>
>> struct Point {
>>   T x, y, z;
>> };
>>
>> Now:
>> sizeof(Point<float>) == 3 * sizeof(float)
>> sizeof(Point<simd<float>>) == 3 * sizeof(simd<float>)
>> should both hold. And the expectation is that it holds at compile time.
>>
>> If sizeof(simd<float>) is not a constant expression this breaks a lot of
>> assumptions compilers currently make when constructing types. Suddenly
>> offsetof(Point<simd<float>>, y) also isn't a constant expression. This affects
>> how members are accessed: everything must be computed at runtime or possibly
>> cached somewhere.
>>
>> Since the simd<T> type's strength, compared to loop vectorization, is the
>> ability to define data structures that depend on sizeof(simd<T>) - like
>> Point<simd<float>> - it's a non-starter to propose that runtime sized simd<T>
>> cannot be used to compose data structures anymore. In a way std::valarray is
>> that type which works in C++: if you need something with a size that's only
>> known at runtime you have to malloc the memory, you can't use the stack.
>>
>> So unless C++ solves the runtime sized types issue in general (basically
>> support VLAs in C++), I don't see runtime sized std::simd happening.

I agree with this FWIW.  But I think there's a risk that this strength
could be counterproductive in some cases.

Taking the easy case first: if an algorithm needs to operate on
N-element vectors for some fixed N (e.g. because it's processing data
that occurs in fixed-size chunks) then being able to compose those types
in the same way as (say) a std::array<T, N> is clearly useful.  It also
seems reasonable that the N-element types might occur in general data
structures.  That part seems uncontroversial.

But AIUI stdx::simd (and particularly stdx::native_simd) is also
designed to be used by code that is agnostic about the length of the
vectors.  Such code can adapt to whatever vectors the target provides.
That's the case I want to talk about below (let's call it case B).

It might just be a factor of who I've talked to, but I get the
impression that people who want to use case B are accelerating
the internals of an algorithm, rather than using vectors as part
of the main interface or using vectors for long-term storage.

For case B we generally have an algorithm that is conceptually agnostic
about the size of stdx::(native_)simd.  When using SVE, we also have a
target architecture that is agnostic about the runtime length of the
vectors.  This means that the length-agnostic algorithm could in
principle be realised by a single piece of length-agnostic SVE code.
However, the type system explicitly prevents this by forcing a length
to be chosen at compile time, even though neither the algorithm nor the
object code require that.

If an algorithm is sufficiently general that it can cope with any
vector length, then IMO it's counterproductive to write it in a
way that explicitly divides the problem up into constant-size chunks.
Case B in general requires a high degree of data parallelism and IMO
it would be better to describe that parallelism directly.

>> My plan for SVE (and RISC-V V) was that in the first iteration you have to
>> decide at compile time what vector width you want to compile for. My
>> understanding, where SVE will be usable, is that you typically have a
>> homogeneous cluster or a single machine where you can make this work. In
>> engineering and research settings it is often possible to compile for the
>> machine you'll work on. The problem becomes harder once a company wants to
>> release binaries that are supposed to work on a wide range of customer setups.
>> With this model you'd have one binary per supported SVE vector width or it
>> would require "fat" binaries that contain a combination of many vector widths.

I think using fat binaries for this use case is a non-starter though.
It would increase the size of binaries fivefold.  It also feels like the
tail wagging the dog: as mentioned above, the architecture itself is
designed around having one piece of length-agnostic code, and it's the
type system (rather than the architecture) that is preventing that from
happening.

To put it another way: if the stdx::simd code was written as normal
scalar code, there would be no need to use fat binaries in this way.
So I think using stdx::simd would in that sense be a regression
for this use case.

Having the option to use -msve-vector-bits=N is useful in principle,
but we shouldn't require it.  In an OS distro setting,
-msve-vector-bits= is going to be very much the exception rather
than the rule.  I think we should treat it as a niche option for
power users only.

>> But there's more we could do if the library and compiler work together. Like
>> compile SVE code in such a way that data structures are "compiled" for many
>> different vector widths while algorithms that work on the data structures are
>> compiled in a vector width agnostic way. The novel (AFAIK) problem to solve is
>> how to dispatch and combine these. Probably the best way to make progress is
>> to compile everything for multiple vector widths, taking care to not use the
>> knowledge about vector widths wherever possible, and then try to shrink the
>> resulting "fat" binary by eliminating the resulting duplicated machine code
>> regions. How this can move up to higher abstraction levels in the compiler, I
>> have no idea...

I'm not sure that's feasible though.  Like you say, sizeof(std::simd<T>)
is just a constant like any other.  It can in principle leak anywhere,
including into the size of static data (which is harder to version than
functions).

>> So -msve-vector-bits=<some number> might be a prerequisite for the first
>> stdx::simd implementation.
> Hi Matthias,
> Thanks for the explanation, actually -msve-vector-bits=128*N is the
> method I am using in my prototype implementation.  Considering SIMD
> library itself guarantees source code level portability, it might be
> fine to do this in the first version implementation.  Although here we
> are breaking sub-target binary portability which SVE tries to achieve.

Yeah, the last bit is my concern too.

I think the way to handle stdx::simd for SVE is to implement stdx::simd
for arm_neon.h vector types and use SVE to accelerate 64-bit and 128-bit
operations that arm_neon.h can't do as efficiently.  Any SVE implementation
can operate on 64-bit and 128-bit vectors by using an appropriate predicate.

Then we should try to get the compiler to revectorise stdx::simd
algorithms to take advantage of length-agnosticism where possible.
We could do this by scalarising the stdx::simd code and then vectorising
it in the same way as “normal” scalar code.  Alternatively, we could try
to vectorise the existing vector code directly: convert operations on
single 128-bit vectors into operations on multiple 128-bit vectors.

My worry is that this might be harder to do than it would be on the
equivalent scalar code.

Thanks,
Richard