Multiplication de matrices multi-threadée

Question

Je suis en train d'écrire un code qui effectue la multiplication de matrices N par N en utilisant le parallélisme au niveau des threads.

Pour obtenir C = A X B,
d'abord j'ai transposé la matrice B, divisé les matrices en blocs.

Un thread prend un bloc de A et B et les multiplie,
puis ajoute le résultat au bloc correspondant dans C.
Toutes les matrices sont allouées dans la mémoire heap en utilisant malloc().

Mais le problème est que pour la même entrée,
la réponse est parfois incorrecte et parfois correcte.

Je ne suis pas tout à fait sûr de pourquoi cela se produit,
mais je suppose que le code doit être amélioré en termes de sécurité des threads.

Je poste une partie de mon code.
blocks est le nombre de blocs en ligne et en colonne, c'est-à-dire N / taille du bloc.
Donc le nombre total de threads est blocs^3.

while (thread_loaded < total_thread)
 {
  if (thread_count < MAX_THREAD)
  {
   p[thread_loaded].idx = thread_idx;
   p[thread_loaded].matinfo = &mi;   
   threads[thread_loaded] = CreateThread(NULL, 0, matmul_tlp, &p[thread_loaded], 0, &threadid[thread_loaded]);
   if (threads[thread_loaded] != NULL)
   {     
    thread_loaded++;
    thread_count++;
    thread_idx += blocks;
    if (thread_idx >= total_thread)
     thread_idx = (thread_idx % total_thread) + 1;
   }          
  }
 }

pour la fonction thread,

int i, j, k;  
param* p = (param*)arg; 

int blocks = BLOCKS;
int block_size = BLOCK_SIZE;
int Ar = p->idx / (blocks * blocks); 
int Ac = p->idx % blocks;
int Br = (p->idx / blocks) % blocks; 
int Bc = p->idx % blocks;
int Cr = p->idx / (blocks * blocks);
int Cc = (p->idx % (blocks * blocks)) / blocks;

double** A = p->matinfo->A;
double** B = p->matinfo->B;
double** C = p->matinfo->C;

DWORD res = WaitForSingleObject(mutex[Cr * blocks + Cc], INFINITE);
if (res != WAIT_OBJECT_0)
 perror("impossible d'acquérir le mutex.");

for (i = 0; i < block_size; i++)
{
 for (j = 0; j < block_size; j++)
 {
  for (k = 0; k < block_size; k++)
  {
   C[Cr * block_size + i][Cc * block_size + j] +=
    A[Ar * block_size + i][Ac * block_size + k] *
    B[Br * block_size + j][Bc * block_size + k];
  }
 }
}

ReleaseMutex(mutex[Cr * blocks + Cc]);

thread_count--;
return NULL;

Il serait apprécié si quelqu'un trouve une faille. :)

Answer 1

Il existe deux valeurs partagées qui sont écrites dans votre fonction threadée. La matrice C et la variable thread_count. Je ne vois rien de mal dans la synchronisation de la matrice C, mais il vaut la peine de vérifier que les valeurs Cc et Cr sont correctement calculées car c'est sur cela que repose votre choix de mutex.

La source d'erreur la plus probable est la variable thread_count qui n'est pas synchronisée. Rappelez-vous que a-- équivaut à 'a = a - 1 et consiste en une lecture suivie d'une opération d'écriture (ce n'est PAS atomique). Cela signifie que le thread est très susceptible d'être préempté entre la lecture et l'écriture et donc certains décréments des variables pourraient être perdus. Par exemple

Le thread A lit la valeur 10 de thread_count.
Le thread B lit la valeur 10 de thread_count.
Le thread B écrit la valeur 10-1 dans thread_count.
Le thread A écrit la valeur 10-1 dans thread_count.
thread_count est maintenant égal à 9 alors qu'il devrait être de 8.

Ainsi, vous venez de perdre l'un de vos signaux vers la fonction de création de threads. Cela pourrait faire en sorte que votre algorithme s'exécute avec moins de threads car vous perdez des décréments. Malheureusement, à moins que je n'ai manqué quelque chose, je ne vois pas d'explication sur pourquoi vous obtenez de mauvais résultats. Votre programme s'exécutera simplement plus lentement que ce qu'il devrait vraiment.

Le moyen le plus simple de résoudre cela serait d'utiliser une variable de condition qui est spécialement conçue pour ces types de situations et évite le problème de réveil perdu que vous avez ici.

En passant, la création de threads est généralement une opération assez coûteuse, donc un pool de threads serait préférable à la création et à la destruction de tonnes de threads. Si les pools de threads sont plus complexes que nécessaire, vous pourriez utiliser des variables de condition pour faire attendre vos threads une nouvelle tâche une fois qu'ils ont terminé la leur.

EDIT: J'ai écrit la solution un peu trop rapidement et j'ai fini par confondre deux problèmes différents.

Tout d'abord, vous voulez synchroniser vos accès à la variable thread_count à la fois dans la fonction de création de threads et dans la fonction de calcul. Pour cela, vous pouvez utiliser un mutex ou des opérandes atomiques comme InterlockedDecrement, InterlockedIncrement (j'espère que ce sont les équivalents Windows corrects). Notez que, bien que je ne vois aucun problème à utiliser des opérandes atomiques dans ce cas, ils ne sont pas aussi simples à utiliser qu'ils pourraient sembler. Assurez-vous de les comprendre pleinement avant de les utiliser.

Le deuxième problème est que vous tournez dans votre fonction de création de threads en attendant qu'un des threads se termine. Vous pouvez éviter cela en utilisant des variables de condition pour signaler au thread principal une fois que ses calculs sont terminés. De cette façon, vous n'occupez pas le processeur pour rien.

Une chose de plus, assurez-vous que votre variable thread_count est déclarée volatile pour indiquer au compilateur que l'ordre dans lequel elle est lue et écrite dans la fonction est important. Sinon, le compilateur est libre de réorganiser les opérations pour augmenter les performances.

Answer 2

Notez que la multiplication de matrices se prête à l'utilisation de plusieurs threads de manière non bloquante. La chose à retenir est que c[i,j] = sum a[i,k] * b[k,j] pour tout k. Cette action est autonome et ne nécessite aucune synchronisation dans votre code de thread. Le thread de départ aurait simplement besoin d'une référence à une classe ou une structure contenant les matrices a, b, c, un conteneur d'entrées nécessitant une synchronisation et le mutex utilisé pour synchroniser le conteneur d'entrées. Accéder à ce conteneur d'entrées nécessiterait un mutex pour y accéder mais tout le reste ne nécessiterait aucun appel de mutex. Chaque entrée dans le conteneur d'entrées contiendra la ligne actuelle et la colonne pour la matrice c qui sera calculée ensuite. Chaque thread interrogerait ensuite le conteneur d'entrées jusqu'à ce que le conteneur soit vide. La seule tâche réelle est de générer le conteneur d'entrées avant de créer/démarrer les threads.