Algorytm równoległy - mnożenie macierzy

Macierz to zestaw danych liczbowych i nienumerycznych ułożonych w ustalonej liczbie wierszy i kolumn. Mnożenie macierzy jest ważnym projektem mnożenia w obliczeniach równoległych. Tutaj omówimy implementację mnożenia macierzy w różnych sieciach komunikacyjnych, takich jak siatka i hipersześcian. Mesh i hypercube mają wyższą łączność sieciową, więc pozwalają na szybszy algorytm niż inne sieci, takie jak sieć pierścieniowa.

Siatka stacji

Topologia, w której zestaw węzłów tworzy p-wymiarową siatkę, nazywana jest topologią siatki. Tutaj wszystkie krawędzie są równoległe do osi siatki i wszystkie sąsiednie węzły mogą się ze sobą komunikować.

Całkowita liczba węzłów = (liczba węzłów w rzędzie) × (liczba węzłów w kolumnie)

Sieć kratową można ocenić na podstawie następujących czynników -

Diameter
Szerokość przekroju poprzecznego

Diameter - Najdłuższy w sieci kratowej distancemiędzy dwoma węzłami jest jego średnica. P-wymiarowa sieć kratowa posiadającakP węzły mają średnicę p(k–1).

Bisection width - Szerokość podziału to minimalna liczba krawędzi potrzebnych do usunięcia z sieci, aby podzielić sieć kratową na dwie połowy.

Mnożenie macierzy za pomocą sieci kratowej

Rozważaliśmy model SIMD sieci kratowej 2D z połączeniami zawijanymi. Zaprojektujemy algorytm mnożący dwie tablice n × n przy użyciu n ² procesorów w określonym czasie.

Macierze A i B mają odpowiednio elementy a _ij i b _ij . Element przetwarzający PE _ij reprezentuje a _ij oraz b _ij . Ułóż macierze A i B w taki sposób, aby każdy procesor miał parę elementów do pomnożenia. Elementy macierzy A będą poruszać się w lewo, a elementy macierzy B będą poruszać się w górę. Te zmiany położenia elementów w macierzy A i B przedstawiają każdemu elementowi przetwarzającemu PE nową parę wartości do pomnożenia.

Kroki w algorytmie

Rozłóż dwie macierze.
Oblicz wszystkie produkty, a _ik × b _kj
Oblicz sumy po zakończeniu kroku 2.

Algorytm

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

Sieć Hypercube

Hipersześcian jest n-wymiarową konstrukcją, w której krawędzie są prostopadłe do siebie i mają tę samą długość. N-wymiarowy hipersześcian jest również znany jako n-sześcian lub n-wymiarowy sześcian.

Cechy Hypercube z węzłem 2 ^k

Średnica = k
Szerokość przekroju poprzecznego = 2 ^{k – 1}
Liczba krawędzi = k

Mnożenie macierzy za pomocą Hypercube Network

Ogólna specyfikacja sieci Hypercube -

Pozwolić N = 2^mbyć całkowitą liczbą procesorów. Niech procesorami będą P _0, P ₁ … ..P _N-1 .
Niech i i i ^b będą dwoma liczbami całkowitymi, 0 <i, i ^b <N-1, a jego binarna reprezentacja różni się tylko pozycją b, 0 <b <k – 1.
Rozważmy dwie macierze n × n, macierz A i macierz B.
Step 1- Elementy macierzy A i macierzy B są przypisane do n ³ procesorów w taki sposób, że procesor w pozycji i, j, k będzie miał _ji i b _ik .
Step 2 - Cały procesor na pozycji (i, j, k) oblicza iloczyn

C (i, j, k) = A (i, j, k) × B (i, j, k)
Step 3 - Suma C (0, j, k) = ΣC (i, j, k) dla 0 ≤ i ≤ n-1, gdzie 0 ≤ j, k <n – 1.

Block Matrix

Macierz blokowa lub macierz podzielona na partycje to macierz, w której każdy element sam reprezentuje indywidualną macierz. Te poszczególne sekcje są znane jakoblock lub sub-matrix.