Algoritmo paralelo: multiplicación de matrices

Una matriz es un conjunto de datos numéricos y no numéricos dispuestos en un número fijo de filas y columnas. La multiplicación de matrices es un diseño de multiplicación importante en el cálculo paralelo. Aquí, discutiremos la implementación de la multiplicación de matrices en varias redes de comunicación como malla e hipercubo. La malla y el hipercubo tienen una mayor conectividad de red, por lo que permiten un algoritmo más rápido que otras redes como la red en anillo.

Red de malla

Una topología en la que un conjunto de nodos forma una cuadrícula p-dimensional se denomina topología de malla. Aquí, todos los bordes son paralelos al eje de la cuadrícula y todos los nodos adyacentes pueden comunicarse entre sí.

Número total de nodos = (número de nodos en fila) × (número de nodos en columna)

Una red de malla se puede evaluar utilizando los siguientes factores:

  • Diameter
  • Ancho de bisección

Diameter - En una red de malla, la más larga distanceentre dos nodos es su diámetro. Una red de malla p-dimensional que tienekP nodos tiene un diámetro de p(k–1).

Bisection width - El ancho de bisección es el número mínimo de bordes necesarios que se deben eliminar de una red para dividir la red de malla en dos mitades.

Multiplicación de matrices utilizando una red de malla

Hemos considerado un modelo SIMD de red de malla 2D que tiene conexiones envolventes. Diseñaremos un algoritmo para multiplicar dos matrices n × n usando n 2 procesadores en una cantidad de tiempo particular.

Las matrices A y B tienen elementos a ij y b ij respectivamente. El elemento de procesamiento PE ij representa a ij y b ij . Disponga las matrices A y B de tal forma que cada procesador tenga un par de elementos para multiplicar. Los elementos de la matriz A se moverán hacia la izquierda y los elementos de la matriz B se moverán hacia arriba. Estos cambios en la posición de los elementos en la matriz A y B presentan a cada elemento de procesamiento, PE, un nuevo par de valores a multiplicar.

Pasos en el algoritmo

  • Alterne dos matrices.
  • Calcule todos los productos, a ik × b kj
  • Calcule las sumas cuando complete el paso 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

Red de hipercubo

Un hipercubo es una construcción n-dimensional donde los bordes son perpendiculares entre sí y tienen la misma longitud. Un hipercubo de n dimensiones también se conoce como un cubo de n o un cubo de n dimensiones.

Características de Hypercube con nodo 2 k

  • Diámetro = k
  • Ancho de bisección = 2 k – 1
  • Número de aristas = k

Multiplicación de matrices mediante Hypercube Network

Especificación general de las redes Hypercube -

  • Dejar N = 2msea ​​el número total de procesadores. Sean los procesadores P 0, P 1 … ..P N-1 .

  • Sean i e i b dos números enteros, 0 <i, i b <N-1 y su representación binaria difiera sólo en la posición b, 0 <b <k – 1.

  • Consideremos dos matrices n × n, la matriz A y la matriz B.

  • Step 1- Los elementos de la matriz A y la matriz B se asignan a los n 3 procesadores de manera que el procesador en la posición i, j, k tendrá a ji y b ik .

  • Step 2 - Todo el procesador en posición (i, j, k) calcula el producto

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

  • Step 3 - La suma C (0, j, k) = ΣC (i, j, k) para 0 ≤ i ≤ n-1, donde 0 ≤ j, k <n – 1.

Matriz de bloques

Block Matrix o matriz particionada es una matriz donde cada elemento en sí mismo representa una matriz individual. Estas secciones individuales se conocen comoblock o sub-matrix.

Ejemplo

En la Figura (a), X es una matriz de bloques donde A, B, C, D son matrices ellos mismos. La figura (f) muestra la matriz total.

Multiplicación de matriz de bloques

Cuando dos matrices de bloque son matrices cuadradas, entonces se multiplican de la misma manera que realizamos la multiplicación de matrices simple. Por ejemplo,