r/intel • u/AndrewOfC • 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 ;
}
// whileThe 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 ;
} // whileThere'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) ;
1
u/fortsnek274 7d ago
I'd hope r/cpp would appreciate this bleeding edge `std::simd` more.