r/simd • • 5d ago

Optimizing a Reduction Algorithm with AVX

An example of optimizing a reduction algorithm using AVX-512 compiler intrinsics and std::experimental::native_simd types.

https://github.com/AndrewOfC/vector_reduction

The speedup is evaluated against a trivial implementation:

template<typename T>
T generic_reduction(T *src, size_t len, T initial)
{
    for(size_t i = 0; i < len; i++)
    {
        initial += src[i];
    }
    return initial;
}

And against the C++ standard library std::reduce.

Three approaches are used, but yield similar results in the 'sweet spot' between 1000 and 6000 samples.

Intrinsics and the stdx:native_simd have the same basic structure of:

NOTE: some blocks are not shown for the sake of brevity; full code is in the public GitHub repo.

while( len >= 8 * 8 ) {
    __m512d r000 = _mm512_load_pd(&src[0]);
    __m512d r001 = _mm512_load_pd(&src[8]);
    __m512d r002 = _mm512_load_pd(&src[16]);
    __m512d r003 = _mm512_load_pd(&src[24]);
    __m512d r004 = _mm512_load_pd(&src[32]);
    __m512d r005 = _mm512_load_pd(&src[40]);
    __m512d r006 = _mm512_load_pd(&src[48]);
    __m512d r007 = _mm512_load_pd(&src[56]);
    
    r000 = _mm512_add_pd(r000, r004);
    r001 = _mm512_add_pd(r001, r005);
    r002 = _mm512_add_pd(r002, r006);
    r003 = _mm512_add_pd(r003, r007);
    
    r000 = _mm512_add_pd(r000, r002);
    r001 = _mm512_add_pd(r001, r003);
    
    r000 = _mm512_add_pd(r000, r001);

    initial += _mm512_reduce_add_pd(r000) ;
    

    len -= 8 * 8 ;
    src += 8 * 8  ;
} 
// while
/*
 * 
 */
while( len >= 4 * 8 ) {
    __m512d r000 = _mm512_load_pd(&src[0]);
    __m512d r001 = _mm512_load_pd(&src[8]);
    __m512d r002 = _mm512_load_pd(&src[16]);
    __m512d r003 = _mm512_load_pd(&src[24]);
    
    r000 = _mm512_add_pd(r000, r002);
    r001 = _mm512_add_pd(r001, r003);
    
    r000 = _mm512_add_pd(r000, r001);

    initial += _mm512_reduce_add_pd(r000) ;
    

    len -= 4 * 8 ;
    src += 4 * 8  ;
} 
// while

The stdx::native_simd allows the use of templates for other datatypes.

template<typename T>
using vector_t = std::experimental::native_simd<T>;



while( len >= 8 * sz ) {
    vector_t<T> r00, r01, r02, r03, r04, r05, r06, r07 ;
    r00.copy_from(&src[0 * sz], stdx::vector_aligned) ;
    r01.copy_from(&src[1 * sz], stdx::vector_aligned) ;
    r02.copy_from(&src[2 * sz], stdx::vector_aligned) ;
    r03.copy_from(&src[3 * sz], stdx::vector_aligned) ;
    r04.copy_from(&src[4 * sz], stdx::vector_aligned) ;
    r05.copy_from(&src[5 * sz], stdx::vector_aligned) ;
    r06.copy_from(&src[6 * sz], stdx::vector_aligned) ;
    r07.copy_from(&src[7 * sz], stdx::vector_aligned) ;
    
    r00 += r04 ;
    r01 += r05 ;
    r02 += r06 ;
    r03 += r07 ;
    
    r00 += r02 ;
    r01 += r03 ;
    
    r00 += r01 ;

    initial += stdx::reduce(r00) ;

    len -= 8 * sz ;
    src += 8 * sz ;
} // while

while( len >= 4 * sz ) {
    vector_t<T> r00, r01, r02, r03 ;
    r00.copy_from(&src[0 * sz], stdx::vector_aligned) ;
    r01.copy_from(&src[1 * sz], stdx::vector_aligned) ;
    r02.copy_from(&src[2 * sz], stdx::vector_aligned) ;
    r03.copy_from(&src[3 * sz], stdx::vector_aligned) ;
    
    r00 += r02 ;
    r01 += r03 ;
    
    r00 += r01 ;

    initial += stdx::reduce(r00) ;

    len -= 4 * sz ;
    src += 4 * sz ;
} // while

There's a third approach that uses a recursive C++ template expressing the reduction algorithm. Suprisingly this formed as well as the intrinsic implementation and templated simd, where the trivial loop did not.

template<typename T>
inline static vector_t<T> reduce(vector_t<T> a, T *srcB) 
// terminal case for recursion
{
    vector_t<T> b ;
    b.copy_from(srcB, stdx::
vector_aligned
);
    return a + b ;
}

inline static auto reduce(auto a, auto srcB, auto... args) 
// consume argument and recurse
{
    return reduce(reduce(a, srcB), args...) ;
}

vinitial = 0 ;
while( len >= 8 * sz ) {
    vinitial += reduce(vector_t<T>(0), &src[0 * sz], &src[1 * sz], &src[2 * sz], &src[3 * sz], &src[4 * sz], &src[5 * sz], &src[6 * sz], &src[7 * sz]) ;
    len -= 8 * sz ;
    src += 8 * sz ;
} 
// while

initial += stdx::reduce(vinitial) ;
/*
 *
 */
vinitial = 0 ;
while( len >= 4 * sz ) {
    vinitial += reduce(vector_t<T>(0), &src[0 * sz], &src[1 * sz], &src[2 * sz], &src[3 * sz]) ;
    len -= 4 * sz ;
    src += 4 * sz ;
} 
// while

initial += stdx::reduce(vinitial) ;
10 Upvotes

5 comments sorted by

3

u/TQ_GPU 5d ago

Why don't you do

_mm512_add_pd

only after all SIMD lanes are accumulated for whole input array? Reduction in each step adds more latency, increases rounding error too.

2

u/AndrewOfC 3d ago

I've been focusing on std::experimental::simd, I have to circle back and revisit intrinsics for sve/sve2. I'll look into that then.

2

u/AndrewOfC 1d ago

Yes, I can see where I can keep accumulating in r000 until the end. I'll work that into the templates

1

u/TQ_GPU 21h ago

Either way its memory-bandwidth bottlenecked algorithm and RAM would be probably fully utilized by just 2-3 cores imo. You can optimize it by prefetching the elements before accessing them.

2

u/BlockOfDiamond 1d ago

As for this:

while( len >= 8 * 8 ) {
    __m512d r000 = _mm512_load_pd(&src[0]);
    __m512d r001 = _mm512_load_pd(&src[8]);
    __m512d r002 = _mm512_load_pd(&src[16]);
    __m512d r003 = _mm512_load_pd(&src[24]);
    __m512d r004 = _mm512_load_pd(&src[32]);
    __m512d r005 = _mm512_load_pd(&src[40]);
    __m512d r006 = _mm512_load_pd(&src[48]);
    __m512d r007 = _mm512_load_pd(&src[56]);

    r000 = _mm512_add_pd(r000, r004);
    r001 = _mm512_add_pd(r001, r005);
    r002 = _mm512_add_pd(r002, r006);
    r003 = _mm512_add_pd(r003, r007);

    r000 = _mm512_add_pd(r000, r002);
    r001 = _mm512_add_pd(r001, r003);

    r000 = _mm512_add_pd(r000, r001);

    initial += _mm512_reduce_add_pd(r000);

    len -= 8 * 8;
    src += 8 * 8;
}

I would probably have an 8-wide accumulator, and then do one reduce at the end instead of reducing once per iteration.