En las arquitecturas informáticas paralelas , una matriz sistólica es una red homogénea de unidades de procesamiento de datos (DPU) estrechamente acopladas llamadas células o nodos . Cada nodo o DPU calcula de forma independiente un resultado parcial en función de los datos recibidos de sus vecinos ascendentes, almacena el resultado dentro de sí mismo y lo pasa hacia abajo. Las matrices sistólicas se utilizaron por primera vez en Colossus , que fue una de las primeras computadoras utilizadas para descifrar los cifrados de Lorenz alemanes durante la Segunda Guerra Mundial . [1] Debido a la naturaleza clasificada de Colossus, fueron inventados o redescubiertos de forma independiente por HT Kung y Charles Leiserson, quienes describieron matrices para muchos cálculos de álgebra lineal densa (producto matricial, resolución de sistemas de ecuaciones lineales , descomposición LU , etc.) para bandas. matrices. Las primeras aplicaciones incluyen el cálculo de los 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 paralelos fluyen a través de una red de nodos procesadores cableados , que combinan, procesan, fusionan u clasifican los datos de entrada en un resultado derivado. Debido a que la propagación ondulatoria de los datos a través de una matriz sistólica se asemeja al pulso del sistema circulatorio humano, el nombre sistólica se acuñó a partir de la terminología médica. El nombre se deriva de sístole como analogía con el bombeo regular de sangre por parte del corazón.
Las matrices sistólicas a menudo están programadas para operaciones específicas, como "multiplicar y acumular", para realizar tareas masivamente paralelas de integración, 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 análisis de secuencias de ADN y proteínas .
Una matriz sistólica generalmente consta de una gran red monolítica de nodos informáticos primitivos que pueden estar cableados o configurados por software para una aplicación específica. Los nodos suelen ser 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 frentes 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 procesarlos siempre exactamente de la misma manera. El procesamiento real dentro de cada nodo puede estar cableado o microcodificado en bloque , en cuyo caso la personalidad del nodo común puede programarse en bloque.
El paradigma de matriz sistólica con flujos de datos impulsados por contadores de datos es la contraparte de la arquitectura de Von Neumann con flujo de instrucciones impulsado 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 .
Un beneficio importante de las matrices sistólicas es que todos los datos de operandos y los resultados parciales se almacenan dentro (a través de) la matriz del procesador. No es necesario acceder a buses externos, memoria principal o cachés internos durante cada operación como es el caso de las máquinas secuenciales de Von Neumann o Harvard . Los límites secuenciales sobre el rendimiento paralelo dictados por la Ley de Amdahl tampoco se aplican de la misma manera, porque las dependencias de datos son manejadas implícitamente por la interconexión de nodos programables y no hay pasos secuenciales en la gestión del flujo de datos altamente paralelo.
Por lo tanto, las matrices sistólicas son extremadamente buenas en inteligencia artificial, procesamiento de imágenes, reconocimiento de patrones, visión por computadora y otras tareas que los cerebros animales realizan particularmente bien. Los procesadores Wavefront en general también pueden ser muy buenos en el aprendizaje automático al implementar redes neuronales autoconfigurables en el hardware.
Si bien las matrices sistólicas se clasifican oficialmente como MISD , su clasificación es algo problemática. Debido a que la entrada suele ser 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 puede clasificarse como MIMD , porque MIMD puede verse como una mera colección de máquinas SISD y SIMD más pequeñas.
Finalmente, 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 operan con 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 descalifica de la categoría SISD: los datos de entrada suelen ser un vector, no un único valor de datos , aunque se podría argumentar que cualquier entrada dada El vector es un solo 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, quizás debería clasificarse como SFMuDMeR = función única, datos múltiples, resultado(s) combinado(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 al mismo tiempo en la matriz sistólica: en una red de Kahn, hay colas FIFO entre cada nodo.
Una matriz sistólica se compone de filas en forma de matriz de unidades de procesamiento de datos llamadas celdas. Las unidades de procesamiento de datos (DPU) son similares a las unidades centrales de procesamiento (CPU) (excepto por la habitual falta de un contador de programa , [3] ya que la operación se activa mediante el 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 se generan mediante 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 ingresarse y/o enviarse a una fuente externa.
Se podría diseñar un ejemplo de algoritmo sistólico para la multiplicación de matrices . Una matriz se alimenta en una fila a la vez desde la parte superior de la matriz y se pasa hacia abajo en la matriz, la otra matriz se alimenta 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 completa y una columna completa. En este punto, el resultado de la multiplicación se almacena en la matriz y ahora se puede generar una fila o 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 tuberías lineales, de modo que las arquitecturas sean las mismas en todas las DPU. La consecuencia es que sólo 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 se calculan en "paso cerrado" y cada procesador realiza cálculos alternativos. comunicar fases. Pero las matrices sistólicas con protocolo de enlace asincrónico entre DPU se denominan matrices de frente de onda . Una matriz sistólica muy conocida es el procesador iWarp de la Universidad Carnegie Mellon , 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 describía 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 y pasa el resultado a la derecha, el siguiente suma y pasa el resultado a la derecha.
Ventajas
Contras
