Algoritmo Paralelo - Multiplicação de Matriz

Uma matriz é um conjunto de dados numéricos e não numéricos organizados em um número fixo de linhas e colunas. A multiplicação de matrizes é um projeto de multiplicação importante na computação paralela. Aqui, discutiremos a implementação da multiplicação de matrizes em várias redes de comunicação como malha e hipercubo. Malha e hipercubo têm maior conectividade de rede, portanto, permitem algoritmo mais rápido do que outras redes, como rede em anel.

Malha de rede

Uma topologia em que um conjunto de nós forma uma grade p-dimensional é chamada de topologia de malha. Aqui, todas as arestas são paralelas ao eixo da grade e todos os nós adjacentes podem se comunicar entre si.

Número total de nós = (número de nós na linha) × (número de nós na coluna)

Uma rede mesh pode ser avaliada usando os seguintes fatores -

  • Diameter
  • Largura da bissecção

Diameter - Em uma rede mesh, o mais longo distanceentre dois nós é o seu diâmetro. Uma rede de malha p-dimensional tendokP nós tem um diâmetro de p(k–1).

Bisection width - A largura da bissecção é o número mínimo de arestas necessárias a serem removidas de uma rede para dividir a rede em duas metades.

Multiplicação de matriz usando rede Mesh

Consideramos um modelo SIMD de rede em malha 2D com conexões envolventes. Projetaremos um algoritmo para multiplicar duas matrizes n × n usando n 2 processadores em um determinado período de tempo.

As matrizes A e B têm os elementos a ij e b ij respectivamente. O elemento de processamento PE ij representa a ij e b ij . Organize as matrizes A e B de forma que cada processador tenha um par de elementos para multiplicar. Os elementos da matriz A se moverão para a esquerda e os elementos da matriz B se moverão para cima. Essas mudanças na posição dos elementos da matriz A e B apresentam a cada elemento de processamento, PE, um novo par de valores a multiplicar.

Etapas no algoritmo

  • Alterne duas matrizes.
  • Calcule todos os produtos, a ik × b kj
  • Calcule as somas quando a etapa 2 estiver concluída.

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

Rede Hypercube

Um hipercubo é uma construção n-dimensional em que as arestas são perpendiculares entre si e têm o mesmo comprimento. Um hipercubo n-dimensional também é conhecido como cubo n ou cubo n-dimensional.

Características do hipercubo com nó de 2 k

  • Diâmetro = k
  • Largura da bissecção = 2 k – 1
  • Número de arestas = k

Multiplicação de matriz usando rede hipercubo

Especificação geral de redes Hypercube -

  • Deixei N = 2mser o número total de processadores. Sejam os processadores P 0, P 1 … ..P N-1 .

  • Sejam i e i b dois inteiros, 0 <i, i b <N-1 e sua representação binária difere apenas na posição b, 0 <b <k – 1.

  • Vamos considerar duas matrizes n × n, matriz A e matriz B.

  • Step 1- Os elementos da matriz A e da matriz B são atribuídos aos n 3 processadores de forma que o processador na posição i, j, k terá a ji e b ik .

  • Step 2 - Todo o processador na posição (i, j, k) calcula o produto

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

  • Step 3 - A soma C (0, j, k) = ΣC (i, j, k) para 0 ≤ i ≤ n-1, onde 0 ≤ j, k <n – 1.

Matriz de Bloco

Matriz de bloco ou matriz particionada é uma matriz em que cada elemento representa uma matriz individual. Essas seções individuais são conhecidas comoblock ou sub-matrix.

Exemplo

Na Figura (a), X é uma matriz de bloco onde A, B, C, D são as próprias matrizes. A Figura (f) mostra a matriz total.

Multiplicação de matriz de bloco

Quando duas matrizes de bloco são matrizes quadradas, elas são multiplicadas da mesma forma que fazemos a multiplicação de matrizes simples. Por exemplo,