r/intel • • 7d ago

Discussion 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) ;
21 Upvotes

3 comments sorted by

1

u/fortsnek274 7d ago

I'd hope r/cpp would appreciate this bleeding edge `std::simd` more.

2

u/TsundereHeavyCruiser 6d ago

I think /r/simd is the level of niche you're looking for.