Looking for status of SIMD implementation

[Bin.Cheng]

On Tue, Jun 29, 2021 at 9:57 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> "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.
I can see possible issues in "case B" usage.  It puts burden on end
programmers to better understand parallelism in program/algorithm.  It
could end up with various small pieces of vectorized loop for
different operations on "long-term" storage/data-structure, this
requires quite powerful fusion capability from compilers.
>From the name "SIMD", I tend to think it's original motivation is to
provide a higher-level, better-portable simd feature than
intrinsic/assembly (the case A?).

>
> 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.
Hmm, seems to me this will introduce a lot of work to (not only one)
compilers, even if it's practical.  Also the fusion problem also
exists here?
Overall, we are not sure if high level abstraction of parallelism is
stx::simd's job, it does look like a job for DSL or high level program
language features (JunMa referred to something like Halide).  We do
look for comments on more possible use cases.

Thanks,
bin
>
> My worry is that this might be harder to do than it would be on the
> equivalent scalar code.
>
> Thanks,
> Richard