En arquitecturas de computadoras paralelas , una matriz sistólica es una red homogénea de unidades de procesamiento de datos (DPU) estrechamente acopladas llamadas celdas o nodos . Cada nodo o DPU calcula de forma independiente un resultado parcial como una función de los datos recibidos de sus vecinos ascendentes, almacena el resultado dentro de sí mismo y lo pasa descendentemente. Las matrices sistólicas se utilizaron por primera vez en Colossus , que fue una de las primeras computadoras utilizadas para descifrar los cifrados alemanes de Lorenz durante la Segunda Guerra Mundial . [1] Debido a la naturaleza clasificada de Colossus, fueron inventadas o redescubiertas de forma independiente por HT Kung y Charles Leiserson, quienes describieron las matrices para muchos cálculos de álgebra lineal densa (producto matricial, resolución de sistemas de ecuaciones lineales , descomposición LU , etc.) para matrices en bandas. Las primeras aplicaciones incluyen el cálculo de máximos divisores comunes de números enteros y polinomios. [2] A veces se clasifican como arquitecturas de datos únicos de instrucciones múltiples (MISD) según la taxonomía de Flynn , pero esta clasificación es cuestionable porque se puede presentar un argumento sólido para distinguir las matrices sistólicas de cualquiera de las cuatro categorías de Flynn: SISD , SIMD , MISD , MIMD , como se analiza más adelante en este artículo.
Los datos de entrada en paralelo fluyen a través de una red de nodos de procesadores cableados , que combinan, procesan, fusionan u ordenan los datos de entrada para obtener un resultado derivado. Debido a que la propagación de datos en forma de onda a través de una matriz sistólica se asemeja al pulso del sistema circulatorio humano, el nombre sistólico se acuñó a partir de la terminología médica. El nombre se deriva de sístole como analogía al bombeo regular de sangre por parte del corazón.
Las matrices sistólicas suelen estar programadas para operaciones específicas, como "multiplicar y acumular", para realizar tareas de integración masiva en paralelo , convolución , correlación , multiplicación de matrices o clasificación de datos. También se utilizan para algoritmos de programación dinámica , utilizados en el análisis de secuencias de ADN y proteínas .
Una matriz sistólica consiste típicamente en una gran red monolítica de nodos de computación primitivos que pueden ser cableados o configurados por software para una aplicación específica. Los nodos son generalmente fijos e idénticos, mientras que la interconexión es programable. Los procesadores de frente de onda más generales , por el contrario, emplean nodos sofisticados y programables individualmente que pueden o no ser monolíticos, dependiendo del tamaño de la matriz y los parámetros de diseño. La otra distinción es que las matrices sistólicas dependen de transferencias de datos sincrónicas , mientras que los de frente de onda tienden a funcionar de forma asincrónica.
A diferencia de la arquitectura Von Neumann más común , donde la ejecución del programa sigue un guión de instrucciones almacenadas en la memoria común, direccionadas y secuenciadas bajo el control del contador de programa (PC) de la CPU , los nodos individuales dentro de una matriz sistólica se activan con la llegada de nuevos datos y siempre procesan los datos exactamente de la misma manera. El procesamiento real dentro de cada nodo puede estar cableado o microcodificado en bloques , en cuyo caso la personalidad del nodo común puede ser programable en bloques.
El paradigma de matriz sistólica con flujos de datos controlados por contadores de datos es la contraparte de la arquitectura de Von Neumann con flujo de instrucciones controlado por un contador de programa. Debido a que una matriz sistólica generalmente envía y recibe múltiples flujos de datos y se necesitan múltiples contadores de datos para generar estos flujos de datos, admite el paralelismo de datos .
Una de las principales ventajas de las matrices sistólicas es que todos los datos de los operandos y los resultados parciales se almacenan dentro de la matriz del procesador (pasando a través de ella). No es necesario acceder a buses externos, memoria principal o cachés internos durante cada operación, como sucede con las máquinas secuenciales de Von Neumann o Harvard . Los límites secuenciales del rendimiento paralelo dictados por la Ley de Amdahl tampoco se aplican de la misma manera, porque las dependencias de los datos son manejadas implícitamente por la interconexión de nodos programables y no hay pasos secuenciales para gestionar el flujo de datos altamente paralelo.
Por lo tanto, las matrices sistólicas son extremadamente buenas para la inteligencia artificial, el procesamiento de imágenes, el reconocimiento de patrones, la visión artificial y otras tareas que los cerebros animales realizan particularmente bien. Los procesadores de frente de onda en general también pueden ser muy buenos para el aprendizaje automático al implementar redes neuronales autoconfigurables en el hardware.
Aunque las matrices sistólicas se clasifican oficialmente como MISD , su clasificación es algo problemática. Debido a que la entrada es típicamente un vector de valores independientes, la matriz sistólica definitivamente no es SISD . Dado que estos valores de entrada se fusionan y combinan en los resultados y no mantienen su independencia como lo harían en una unidad de procesamiento vectorial SIMD , la matriz no se puede clasificar como tal. En consecuencia, la matriz tampoco se puede clasificar como MIMD , porque MIMD se puede ver como una mera colección de máquinas SISD y SIMD más pequeñas .
Por último, debido a que el enjambre de datos se transforma a medida que pasa a través de la matriz de un nodo a otro, los múltiples nodos no están operando sobre los mismos datos, lo que hace que la clasificación MISD sea un nombre inapropiado . La otra razón por la que una matriz sistólica no debería calificar como MISD es la misma que la que la descalifica de la categoría SISD: los datos de entrada son típicamente un vector, no un único valor de datos , aunque se podría argumentar que cualquier vector de entrada dado es un único elemento de datos.
A pesar de todo lo anterior, las matrices sistólicas se ofrecen a menudo como un ejemplo clásico de arquitectura MISD en los libros de texto sobre computación paralela y en las clases de ingeniería. Si la matriz se ve desde fuera como atómica, tal vez debería clasificarse como SFMuDMeR = función única, múltiples datos, resultado(s) fusionado(s).
Las matrices sistólicas utilizan un gráfico de flujo computacional predefinido que conecta sus nodos. Las redes de procesos de Kahn utilizan un gráfico de flujo similar, pero se distinguen por los nodos que trabajan en sincronía en la matriz sistólica: en una red de Kahn, hay colas FIFO entre cada nodo.
Una matriz sistólica está compuesta por filas de unidades de procesamiento de datos similares a matrices llamadas celdas. Las unidades de procesamiento de datos (DPU) son similares a las unidades centrales de procesamiento (CPU), (excepto por la falta habitual de un contador de programa , [3] ya que la operación se activa por transporte , es decir, por la llegada de un objeto de datos). Cada celda comparte la información con sus vecinas inmediatamente después del procesamiento. La matriz sistólica suele ser rectangular donde los datos fluyen a través de la matriz entre las DPU vecinas , a menudo con diferentes datos fluyendo en diferentes direcciones. Los flujos de datos que entran y salen de los puertos de la matriz son generados por unidades de memoria de secuenciación automática, ASM. Cada ASM incluye un contador de datos . En los sistemas integrados, un flujo de datos también puede ingresar desde y/o enviar a una fuente externa.
Un ejemplo de un algoritmo sistólico podría ser el de la multiplicación de matrices . Una matriz se introduce en una fila a la vez desde la parte superior de la matriz y se pasa hacia abajo, la otra matriz se introduce en una columna a la vez desde el lado izquierdo de la matriz y pasa de izquierda a derecha. Luego se pasan valores ficticios hasta que cada procesador haya visto una fila y una columna completas. En este punto, el resultado de la multiplicación se almacena en la matriz y ahora se puede generar una fila o una columna a la vez, fluyendo hacia abajo o a través de la matriz. [4]
Las matrices sistólicas son matrices de DPU que están conectadas a una pequeña cantidad de DPU vecinas más cercanas en una topología similar a una malla. Las DPU realizan una secuencia de operaciones sobre los datos que fluyen entre ellas. Debido a que los métodos tradicionales de síntesis de matrices sistólicas se han practicado mediante algoritmos algebraicos, solo se pueden obtener matrices uniformes con solo tuberías lineales, de modo que las arquitecturas son las mismas en todas las DPU. La consecuencia es que solo se pueden implementar aplicaciones con dependencias de datos regulares en matrices sistólicas clásicas. Al igual que las máquinas SIMD , las matrices sistólicas sincronizadas calculan en "paso cerrado" y cada procesador realiza fases de cálculo y comunicación alternativas. Pero las matrices sistólicas con protocolo de enlace asincrónico entre DPU se denominan matrices de frente de onda . Una matriz sistólica bien conocida es el procesador iWarp de la Universidad Carnegie Mellon , que ha sido fabricado por Intel. Un sistema iWarp tiene un procesador de matriz lineal conectado por buses de datos que van en ambas direcciones.
Las matrices sistólicas (también conocidas como procesadores de frente de onda ) fueron descritas por primera vez por HT Kung y Charles E. Leiserson , quienes publicaron el primer artículo que describe las matrices sistólicas en 1979. Sin embargo, la primera máquina que se sabe que utilizó una técnica similar fue la Colossus Mark II en 1944.
La regla de Horner para evaluar un polinomio es:
Una matriz sistólica lineal en la que los procesadores están dispuestos en pares: uno multiplica su entrada por y pasa el resultado a la derecha, el siguiente suma y pasa el resultado a la derecha.
