Algorithme parallèle - Multiplication matricielle

Une matrice est un ensemble de données numériques et non numériques organisées en un nombre fixe de lignes et de colonnes. La multiplication matricielle est une conception de multiplication importante dans le calcul parallèle. Ici, nous discuterons de la mise en œuvre de la multiplication matricielle sur divers réseaux de communication comme le maillage et l'hypercube. Le maillage et l'hypercube ont une connectivité réseau plus élevée, ils permettent donc un algorithme plus rapide que d'autres réseaux comme le réseau en anneau.

Réseau maillé

Une topologie dans laquelle un ensemble de nœuds forme une grille p-dimensionnelle est appelée topologie maillée. Ici, toutes les arêtes sont parallèles à l'axe de la grille et tous les nœuds adjacents peuvent communiquer entre eux.

Nombre total de nœuds = (nombre de nœuds dans la ligne) × (nombre de nœuds dans la colonne)

Un réseau maillé peut être évalué à l'aide des facteurs suivants -

Diameter
Largeur de la coupe

Diameter - Dans un réseau maillé, le plus long distanceentre deux nœuds est son diamètre. Un réseau maillé p-dimensionnel ayantkP noeuds a un diamètre de p(k–1).

Bisection width - La largeur de bisection est le nombre minimum d'arêtes à supprimer d'un réseau pour diviser le réseau maillé en deux moitiés.

Multiplication matricielle à l'aide d'un réseau maillé

Nous avons considéré un modèle SIMD de réseau maillé 2D ayant des connexions enveloppantes. Nous allons concevoir un algorithme pour multiplier deux tableaux n × n en utilisant n ² processeurs dans un laps de temps donné.

Les matrices A et B ont respectivement les éléments a _ij et b _ij . L'élément de traitement PE _ij représente a _ij et b _ij . Disposez les matrices A et B de manière à ce que chaque processeur ait une paire d'éléments à multiplier. Les éléments de la matrice A se déplaceront vers la gauche et les éléments de la matrice B se déplaceront vers le haut. Ces changements de position des éléments dans les matrices A et B présentent à chaque élément de traitement, PE, un nouveau couple de valeurs à multiplier.

Étapes de l'algorithme

Décalez deux matrices.
Calculer tous les produits, a _ik × b _kj
Calculez les sommes lorsque l'étape 2 est terminée.

Algorithme

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Réseau Hypercube

Un hypercube est une construction à n dimensions où les arêtes sont perpendiculaires entre elles et ont la même longueur. Un hypercube à n dimensions est également appelé cube n ou cube n dimensions.

Caractéristiques de l'hypercube avec nœud 2 ^k

Diamètre = k
Largeur de coupe = 2 ^{k – 1}
Nombre d'arêtes = k

Multiplication matricielle à l'aide du réseau Hypercube

Spécification générale des réseaux Hypercube -

Laisser N = 2^mêtre le nombre total de processeurs. Soit les processeurs P _0, P ₁ … ..P _N-1 .
Soit i et i ^b deux entiers, 0 <i, i ^b <N-1 et sa représentation binaire ne diffère qu'en position b, 0 <b <k – 1.
Considérons deux matrices n × n, la matrice A et la matrice B.
Step 1- Les éléments de la matrice A et de la matrice B sont affectés aux n ³ processeurs de telle sorte que le processeur en position i, j, k aura un _ji et b _ik .
Step 2 - Tout le processeur en position (i, j, k) calcule le produit

C (i, j, k) = A (i, j, k) × B (i, j, k)
Step 3 - La somme C (0, j, k) = ΣC (i, j, k) pour 0 ≤ i ≤ n-1, où 0 ≤ j, k <n – 1.

Matrice de blocs

La matrice de blocs ou matrice partitionnée est une matrice où chaque élément lui-même représente une matrice individuelle. Ces sections individuelles sont appeléesblock ou sub-matrix.

Exemple

Sur la figure (a), X est une matrice de blocs où A, B, C, D sont eux-mêmes une matrice. La figure (f) montre la matrice totale.

Multiplication de la matrice de blocs

Lorsque deux matrices de blocs sont des matrices carrées, elles sont multipliées comme nous effectuons une multiplication matricielle simple. Par exemple,