Parallélisation et vectorisation automatique

par Jean-Claude Iehl, Maître de Conférences UCBL-LIRIS

jeudi 16 janvier 2025

Le café portera sur quelques exemples de parallélisation de boucles par vectorisation automatique ou comment aider le compilateur c / c++ à générer du code utilisant les instructions vectorielles AVX des processeurs « modernes ». On pourra également jouer avec quelques exemples écrits explicitement avec stdx::simd.

En résumé : comment profiter de l’accélération des instructions vectorielles sans écrire de code vectoriel et pour les curieux, comment écrire du code vectoriel (avec une surcouche c++ standard).

Consulter le support de présentation

Indication

La présentation utilise Compiler Explorer.

Dans l’interview suivante : https://youtu.be/kvMqdLf4URI, Matt Godbolt explique l’histoire de ce compilateur interactif de C++ qui montre l’assembleur généré.

Le code est à compiler avec les paramètres suivants :

$ g++ -Wall -o simd simd.cpp -O3 -march=x86-64-v3

Le code simd.cpp :

#include <cassert>
#include <iostream>
#include <chrono>


// version classique
inline
int max2( const int *t, const unsigned N )
{
    int m= 0;
    for(unsigned i= 0; i < N; i++)
        m= std::max(m, t[i]);

    return m;
}



// version librairie standard + extension simd
#include <experimental/simd>
namespace stdx = std::experimental;

template < typename T >
void print( const stdx::native_simd<T>& a )
{
    std::cout << "size: " << a.size() << "\n";
    for(unsigned i= 0; i < a.size(); i++)
        std::cout << a[i] << " ";

    std::cout << "\n";
}

inline
int max1( const int *t, const unsigned N )
{
    stdx::native_simd<int> a= 0;
    for(unsigned i= 0; i < N; i+= a.size())
    {
        stdx::native_simd<int> b(t + i,  stdx::vector_aligned);
        a= stdx::max(a, b);
    }

    //~ int m= 0;
    //~ for(unsigned i= 0; i < a.size(); i++)
    //~ {
        //~ int x= a[i];
        //~ m= std::max(m, x);
    //~ }

    int m= stdx::hmax(a);
    return m;
}


// version explicite avec les fonctions builtin du compilateur
#if __AVX__
#include <immintrin.h>

inline
void print( __m256i x )
{
    alignas(16) int tmp[8];
    _mm256_store_si256((__m256i *) tmp, x);

    for(int i= 0; i < 8; i++)
        std::cout << tmp[i] << " ";

    std::cout << "\n";
}

inline
constexpr int shuffle( const int a, const int b, const int c, const int d) { return ((a & 3) << 6) | ((b & 3) << 4) | ((c & 3) << 2) | (d & 3); }

inline
int max3( const int *t, const unsigned N )
{
    __m256i mm= _mm256_set1_epi32(0);
    for(int i= 0; i < N; i+= 8)
    {
        __m256i x= _mm256_load_si256((__m256i *) (t + i));
        mm= _mm256_max_epi32(mm, x);
    }

    // reduction horizontale
    //~ print(mm);

    __m256i y= _mm256_shuffle_epi32(mm, shuffle(2, 3, 0, 1));
    mm= _mm256_max_epi32(mm, y);
    //~ print(y);
    //~ print(mm);

    __m256i x= _mm256_shuffle_epi32(mm, shuffle(0, 1, 2, 3));
    mm= _mm256_max_epi32(mm, x);
    //~ print(x);
    //~ print(mm);

    __m256i z= _mm256_castsi128_si256(_mm256_extracti128_si256(mm, 1));
    mm= _mm256_max_epi32(mm, z);
    //~ print(z);
    //~ print(mm);

    // extraire le max !!
    return _mm256_cvtsi256_si32(mm);
}
#endif


const unsigned N= 1024*1024;

int main( )
{
    alignas(16) int t[N];

    //~ unsigned n= 8;
    for(unsigned n= 1024; n <= N; n*= 2)
    {
        for(unsigned i= 0; i < n; i++)
            t[i]= i+1;

        auto start= std::chrono::high_resolution_clock::now();
            int m= max3(t, n);
            //~ int m= max2(t, n);
            //~ int m= max1(t, n);
        auto stop= std::chrono::high_resolution_clock::now();

        unsigned int time= std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();
        std::cout << time << "us\n";
        std::cout << m << "\n";
    }

    return 0;
}