Can you as a human implement Xorshiro256ss using SIMD

[Xyncgas]

Here's source : https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/Random.Xoshiro256StarStarImpl.cs,bb77e610694e64ca

Here's ChatGPT

using System;
using System.Numerics;

public class Xorshiro256ss
{
    private Vector<ulong> state;

    public Xorshiro256ss(ulong seed)
    {
        state = new Vector<ulong>(seed);
    }

    public ulong Next()
    {
        Vector<ulong> result = state ^ (state << 17);
        result = result ^ (result >> 31);
        result = result ^ (result << 8);

        state = result;
        return result[0];
    }

    // You can add more methods if needed, like generating random doubles or floats.
}

[huoyaoyuan]

I don't trust ChatGPT at all on (non-well known) algorithm.

Only this part is transformable into SIMD:

                    s2 ^= s0;
                    s3 ^= s1;
                    s1 ^= s2;
                    s0 ^= s3;

into

Vector128<ulong> lower = Create(s0, s1);
Vector128<ulong> upper = Create(s2, s3);
upper ^= lower;
lower ^= upper.Shuffle([1, 0]);

Every other steps heavily depends on the results of last step, and are asymmetric on 4 state values. It's not candidate for SIMD at all.

[Xyncgas]

The algorithm itself can't be parallelized at all because of the serial dependencies.

I do see the possibility of putting 2 Xorshiro256** at minimum together, and vectorize it, making calls to .NextBytes likely ~4x boost in throughput compared to current none-vectorized implementation

because Vector128<ulong> lower = Create(s0, s1) is 128 bits and giving 2x the throughput, modern intel processor usually has AVX256 which is supported by .NET, so two Vector128<ulong> lower = Create(s0, s1) can be processed together

.NET support for AVX512 is coming eventually and that can be 4 rng put together, rumors has it intel is giving AVX1024 next year, that makes 8 rng put together therefore is 16x the throughput ideally (given NextBytes(Span) is called on a span that has at least 2048 length, but AVX512 + 4 rng => 1024 bytes can still be useful because kernal code usually warns 1024 bytes stackalloc

[huoyaoyuan]

I do see the possibility of putting 2 Xorshiro256** at minimum together

That's actionable. You just need to replace the ulongs to Vector256<ulong> or Vector512<ulong>, and use the corresponding element-wise operators.

Just be aware to the deterministic of randoms. Different parallelism will lead to different results.

[tannergooding]

I do see the possibility of putting 2 Xorshiro256** at minimum together, and vectorize it, making calls to .NextBytes likely ~4x boost in throughput compared to current none-vectorized implementation

CPUs can already "parallelize" (pipelining) many scalar instructions. For example, add takes 1 cycle latency and has a reciprocal throughput of 0.25 cycles. This means that you can dispatch up to 4x add instructions in a single cycle, provided that they don't depend on eachother.

SIMD makes this explicit and can help avoid false dependencies and can often be pipelined themselves leading to better throughput, but not everything is trivially vectorizable and when there is cross element dependencies, then your options are more limited. For example, Sum requires you to do vector[0] + vector[1] + ... + vector[n], which means that it really requires multiple instructions to handle and is more expensive than element-wise operations.

giving 2x the throughput

Twice as many bits is not always twice the throughput. You can potentially get up to 2x in an ideal scenario, but in practice you tend to get a bit less. Vector512 is likewise not strictly 4x faster than Vector128, there are many cases where it may only be marginally faster or where its better to not use it.

.NET support for AVX512 is coming eventually

It already exists and shipped yesterday with .NET 8.

rumors has it intel is giving AVX1024 next year,

AVX10 and APX were the two big announcements a couple months back. If 1024-bit SIMD support were coming, I would've expected it to be announced at the same time so that compilers could get all the support done at once. As it stands, AVX10.1 and AVX10.2 do not have 1024-bit support.

[Xyncgas]

Meanwhile I mentioned within an email sent to the author of the xorshiro256** rng, SEBASTIANO VIGNA :

1. SIMD version of rng similar to SFMT or dSFMT
2. Even at the cost of a larger state the throughput gained via SIMD capable variant is appealing
3. If interested, I can use whatever pseudo code you provide, translate it to C# and post it here

The author recommended a look at xorshiro256++ after 1 short exchange of rephrasing where optimization was needed, saying the rng was easily vectorizable

Quote :

If you want to use SIMD, you should use xoshiro256++, which is easily vectorizable (see https://prng.di.unimi.it/).

Ciao,

                                                         seba

https://prng.di.unimi.it/xoshiro256plusplus.c

[Xyncgas]

As always thanks @huoyaoyuan and @tannergooding for your expertise and professional answers