El algoritmo de Cannon

En ciencias de la computación , el algoritmo de Cannon es un algoritmo distribuido para la multiplicación de matrices en mallas bidimensionales, descrito por primera vez en 1969 por Lynn Elliot Cannon . ^{[ 1 ] [ 2 ]}

Es especialmente adecuado para computadoras dispuestas en una malla N × N. ^{[ 3 ]} Si bien el algoritmo de Cannon funciona bien en cuadrículas 2D homogéneas, se ha demostrado que extenderlo a cuadrículas 2D heterogéneas es difícil. ^{[ 4 ]}

La principal ventaja del algoritmo es que sus requisitos de almacenamiento permanecen constantes y son independientes del número de procesadores. ^{[ 2 ]}

El algoritmo de multiplicación de matrices universal escalable (SUMMA) ^{[ 5 ]} es un algoritmo más práctico que requiere menos espacio de trabajo y elimina la necesidad de una cuadrícula cuadrada bidimensional. Es utilizado por las bibliotecas ScaLAPACK , PLAPACK y Elemental .

Al multiplicar dos matrices A y B de n × n , necesitamos n × n nodos de procesamiento p dispuestos en una cuadrícula 2D.

// PE(i , j) k := (i + j) mod N; a := a[i][k]; b := b[k][j]; c[i][j] := 0; para (l := 0; l < N; l++) { c[i][j] := c[i][j] + a * b; concurrentemente { enviar a a PE(i, (j + N − 1) mod N); enviar b a PE((i + N − 1) mod N, j); } con { recibir a' de PE(i, (j + 1) mod N); recibir b' de PE((i + 1) mod N, j ); } a := a'; b := b'; }

Necesitamos seleccionar k en cada iteración para cada elemento procesador (PE) para que los procesadores no accedan a los mismos datos para el cálculo.${\displaystyle a_{ik}*b_{kj}}$.

Por lo tanto, los procesadores en la misma fila/columna deben comenzar la suma con índices diferentes. Si, por ejemplo, PE(0,0) calcula${\displaystyle a_{00}*b_{00}}$En el primer paso, PE(0,1) elige${\displaystyle a_{01}*b_{11}}$Primero. La selección de k  := (i + j) mod n para PE(i,j) satisface esta restricción para el primer paso.

En el primer paso distribuimos las matrices de entrada entre los procesadores según la regla anterior.

En las siguientes iteraciones elegimos un nuevo k'  := (k + 1) mod n para cada procesador. De esta manera, cada procesador seguirá accediendo a diferentes valores de las matrices. Los datos necesarios estarán entonces siempre en los procesadores vecinos. Un PE(i,j) necesita entonces el${\displaystyle a}$de PE(i,(j + 1) mod n) y el${\displaystyle b}$de PE((i + 1) mod n,j) para el siguiente paso. Esto significa que${\displaystyle a}$debe pasarse cíclicamente a la izquierda y también${\displaystyle b}$cíclicamente hacia arriba. Los resultados de las multiplicaciones se suman como de costumbre. Después de n pasos, cada procesador ha calculado todos${\displaystyle a_{ik}*b_{kj}}$una vez y su suma es así la buscada${\displaystyle c_{ij}}$.

Después de la distribución inicial de cada procesador, solo se deben almacenar los datos para el siguiente paso. Estos son el resultado intermedio de la suma anterior, un${\displaystyle a_{ik}}$y un${\displaystyle b_{kj}}$Esto significa que las tres matrices solo necesitan almacenarse en la memoria una vez, distribuidas uniformemente entre los procesadores.

• Matriz sistólica