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,