Algoritmo parallelo - Moltiplicazione di matrici

Una matrice è un insieme di dati numerici e non numerici disposti in un numero fisso di righe e colonne. La moltiplicazione di matrici è un importante progetto di moltiplicazione nel calcolo parallelo. Qui, discuteremo l'implementazione della moltiplicazione di matrici su varie reti di comunicazione come mesh e hypercube. Mesh e hypercube hanno una connettività di rete più elevata, quindi consentono un algoritmo più veloce rispetto ad altre reti come la rete ad anello.

Rete Mesh

Una topologia in cui un insieme di nodi forma una griglia p-dimensionale è chiamata topologia mesh. Qui, tutti i bordi sono paralleli all'asse della griglia e tutti i nodi adiacenti possono comunicare tra loro.

Numero totale di nodi = (numero di nodi nella riga) × (numero di nodi nella colonna)

Una rete mesh può essere valutata utilizzando i seguenti fattori:

  • Diameter
  • Larghezza di bisezione

Diameter - In una rete mesh, la più lunga distancetra due nodi è il suo diametro. Una rete mesh p-dimensionale aventekP nodi ha un diametro di p(k–1).

Bisection width - La larghezza della bisezione è il numero minimo di bordi che devono essere rimossi da una rete per dividere la rete mesh in due metà.

Moltiplicazione di matrici utilizzando la rete mesh

Abbiamo considerato un modello SIMD di rete mesh 2D con connessioni avvolgenti. Progetteremo un algoritmo per moltiplicare due array n × n utilizzando n 2 processori in un determinato periodo di tempo.

Le matrici A e B hanno elementi a ij e b ij rispettivamente. L'elemento di elaborazione PE ij rappresenta a ij eb ij . Disporre le matrici A e B in modo tale che ogni processore abbia una coppia di elementi da moltiplicare. Gli elementi della matrice A si muoveranno nella direzione sinistra e gli elementi della matrice B si muoveranno verso l'alto. Questi cambiamenti nella posizione degli elementi nella matrice A e B presentano ad ogni elemento di elaborazione, PE, una nuova coppia di valori da moltiplicare.

Fasi dell'algoritmo

  • Sfalsa due matrici.
  • Calcola tutti i prodotti, a ik × b kj
  • Calcola le somme al termine del passaggio 2.

Algoritmo

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

Rete Hypercube

Un ipercubo è un costrutto n-dimensionale in cui i bordi sono perpendicolari tra loro e hanno la stessa lunghezza. Un ipercubo n-dimensionale è anche noto come cubo n o cubo n-dimensionale.

Caratteristiche di Hypercube con 2 k nodi

  • Diametro = k
  • Larghezza di bisezione = 2 k – 1
  • Numero di spigoli = k

Moltiplicazione di matrici utilizzando la rete Hypercube

Specifiche generali delle reti Hypercube -

  • Permettere N = 2messere il numero totale di processori. Siano i processori P 0, P 1 … ..P N-1 .

  • Siano i e i b due numeri interi, 0 <i, i b <N-1 e la sua rappresentazione binaria differisce solo nella posizione b, 0 <b <k – 1.

  • Consideriamo due matrici n × n, matrice A e matrice B.

  • Step 1- Gli elementi della matrice A e della matrice B sono assegnati agli n 3 processori in modo tale che il processore in posizione i, j, k avrà a ji eb ik .

  • Step 2 - Tutto il processore in posizione (i, j, k) calcola il prodotto

    C (i, j, k) = A (i, j, k) × B (i, j, k)

  • Step 3 - La somma C (0, j, k) = ΣC (i, j, k) per 0 ≤ i ≤ n-1, dove 0 ≤ j, k <n – 1.

Matrice a blocchi

Block Matrix o matrice partizionata è una matrice in cui ogni elemento stesso rappresenta una matrice individuale. Queste singole sezioni sono note come fileblock o sub-matrix.

Esempio

Nella Figura (a), X è una matrice a blocchi dove A, B, C, D sono matrici stesse. La figura (f) mostra la matrice totale.

Moltiplicazione di matrici a blocchi

Quando due matrici a blocchi sono matrici quadrate, vengono moltiplicate nello stesso modo in cui eseguiamo la moltiplicazione di matrici semplice. Per esempio,