Vector, threads et mutex sur valeurs distinctes

Version imprimable

02/12/2016, 18h43
tickyletroll

Vector, threads et mutex sur valeurs distinctes

Bonjour à tous.

j'ai un traitement à faire sur deux vecteurs :
- l'un en entrée VectorI
- l'autre en sortie VectorO

et une fonction f qui permet pour un élément k de VectorI[k] de passer à VectorO[k]

Ma taille de vecteur étant de 15.000 éléments environs, j'applique ma fonction f 15.000 fois pour calculer VectorO à partir de VectorI
Comme le traitement de f est indépendant des éléments de VectorI et vectorO, je me suis dis que je pourrais lancer 4 threads par exemple pour accélérer le traitement de la fonction f.

genre:
thread1 s'occupe des éléments de 0 à 3750
thread2 s'occupe des éléments de 3751 à 7500
thread3 s'occupe des éléments de 7501 à 11250
thread4 s'occupe des éléments de 11251 à 15000

Question (bête):
Je sais que je dois poser des mutex normalement pour accéder aux lectures/écritures des deux vector.
Mais dans mon cas, je suis sûr que les threads ne créerons jamais de collisions (lire un truc que l'autre thread doit modifier) , dois je quand même poser des mutex ?
02/12/2016, 19h03
bacelar

Sauf si j'ai compris de travers, non, vous n'avez pas besoin de mutex, si vous gérez correctement les types de données utilisés.
Là, vous êtes dans du traitement parallèle car vous appliquez la même fonction au même moment sur des jeux de données indépendant.
Généralement, on préfère résoudre ce type d'optimisation par l'utilisation d'instructions parallèles plutôt que par des threads indépendants, plus gourmands en ressources.

Si vous avez un std::array en entrée, les lectures peuvent être parallèles.

Si vous avez une std::list en sortie, ça le fera pas.
Si vous avez un std::vector en sortie, mais avec une taille non déjà fixé à la bonne valeur, ça le fera pas.
Si vous avez un std::vector en sortie, mais avec une taille déjà fixé à la bonne valeur, ou un std::array ça le fera.

Citation:

je suis sûr que les threads ne créerons jamais de collisions (lire un truc que l'autre thread doit modifier)

Mais faites aussi attention aux contentions sur le cache.
Il faut que le placement des données en mémoire fasse en sorte que les lectures/écritures utilisent correctement le cache (pas de cache-miss, pas de verrouillage de ligne de cache, etc...).
Il n'y pas de solution toute faite, c'est fonction de appariement entre les caches et les threads(virtuel ou pas) dans les CPU.

Bonjour,

Comme l'a dit bacelar, pas besoin de mutex.

Personnellement, je te conseille de regarder du côté de std::async.

Dans la FAQ C++ de isocpp.org, il y a justement un un exemple avec std::async pour faire potentiellement 4 traitements en parallèle sur un std::vector :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        template<class T, class V> struct Accum  {  // simple accumulator function object
            T* b;
            T* e;
            V val;
            Accum(T* bb, T* ee, const V& v) : b{bb}, e{ee}, val{vv} {}
            V operator() () { return std::accumulate(b,e,val); }
        };
        double comp(vector<double>& v)
            // spawn many tasks if v is large enough
        {
            if (v.size()<10000) return std::accumulate(v.begin(),v.end(),0.0);
            auto f0 {async(Accum{&v[0],&v[v.size()/4],0.0})};
            auto f1 {async(Accum{&v[v.size()/4],&v[v.size()/2],0.0})};
            auto f2 {async(Accum{&v[v.size()/2],&v[v.size()*3/4],0.0})};
            auto f3 {async(Accum{&v[v.size()*3/4],&v[v.size()],0.0})};
            return f0.get()+f1.get()+f2.get()+f3.get();
        }

Remarque : Dans le code ci-dessus, le compilateur ne créera pas forcément des threads. Mais tu peux le forcer avec std::launch::async en premier paramètre de std::async.

03/12/2016, 09h29
Matt_Houston

Si l'utilisation d'OpenMP est envisageable, ça s'écrit en quelques lignes avec un parallel for.