Matriz sistólica

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 en función de los datos recibidos de sus vecinos anteriores, almacena el resultado en sí mismo y lo pasa a los siguientes. Los principios del flujo de datos tipo sistólico se vieron por primera vez en Colossus , una computadora temprana utilizada para descifrar los cifrados alemanes de Lorenz durante la Segunda Guerra Mundial . ^[¹^] Debido a la naturaleza clasificada de Colossus, fueron inventados independientemente por HT Kung y Charles Leiserson, quienes describieron matrices para muchos cálculos de álgebra lineal densa (producto de matrices, resolución de sistemas de ecuaciones lineales , descomposición LU , etc.) para matrices de banda. Las primeras aplicaciones incluyen el cálculo del máximo común divisor de enteros y polinomios. ^[²^] Hoy en día, se pueden encontrar en NPU y aceleradores de hardware basados en diseños espaciales . A veces se clasifican como arquitecturas de instrucciones múltiples y datos únicos (MISD, por sus siglas en inglés) según la taxonomía de Flynn , pero esta clasificación es cuestionable porque se puede argumentar con firmeza que las matrices sistólicas pueden pertenecer a 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 procesamiento cableados , que combinan, procesan, fusionan o clasifican los datos de entrada para obtener un resultado. 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 término «sistólico» proviene de la terminología médica. El nombre deriva de «sístole» , en analogía con el bombeo regular de sangre por el corazón.

Aplicaciones

Los arreglos sistólicos suelen estar cableados para operaciones específicas, como multiplicación y acumulación , para realizar tareas de integración, convolución , correlación , multiplicación de matrices o clasificación de datos en paralelo masivo . También se utilizan para algoritmos de programación dinámica , empleados en el análisis de secuencias de ADN y proteínas .

Arquitectura

Un arreglo sistólico generalmente consta de una gran red monolítica de nodos de computación 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, emplean nodos sofisticados y programables individualmente que pueden ser monolíticos o no, según el tamaño del arreglo y los parámetros de diseño. Otra diferencia radica en que los arreglos sistólicos se basan en transferencias de datos síncronas , mientras que los de frente de onda tienden a funcionar de forma asíncrona .

A diferencia de la arquitectura Von Neumann , más común , donde la ejecución del programa sigue un guion de instrucciones almacenadas en 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 los procesan exactamente de la misma manera. El procesamiento real dentro de cada nodo puede estar cableado o microcodificado por bloques , en cuyo caso la personalidad común del nodo puede programarse por bloques.

El paradigma de matriz sistólica con flujos de datos controlados por contadores de datos es la contraparte de la arquitectura Von Neumann con flujo de instrucciones controlado por un contador de programa. Dado 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, admite paralelismo de datos .

Objetivos y beneficios

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 ni cachés internas durante cada operación, como ocurre 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, ya que las dependencias de datos se gestionan implícitamente mediante la interconexión de nodos programables y no existen pasos secuenciales en la gestión del flujo de datos altamente paralelo.

Por lo tanto, los conjuntos sistólicos son extremadamente eficaces en inteligencia artificial, procesamiento de imágenes, reconocimiento de patrones, visión artificial y otras tareas que los cerebros animales realizan especialmente bien. Los procesadores de frente de onda en general también pueden ser muy eficaces en aprendizaje automático mediante la implementación de redes neuronales autoconfigurables en hardware.

Controversia sobre la clasificación

Si bien los arreglos sistólicos se clasifican oficialmente como MISD , su clasificación resulta algo problemática. Dado que la entrada suele ser un vector de valores independientes, el arreglo sistólico no es SISD . Como estos valores de entrada se fusionan y combinan en el resultado o resultados y no mantienen su independencia como lo harían en una unidad de procesamiento vectorial SIMD , el arreglo no puede clasificarse como tal. En consecuencia, tampoco puede clasificarse como MIMD , ya que MIMD puede considerarse simplemente una 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 por la matriz de nodo en nodo, los múltiples nodos no operan 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 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 vector de entrada dado es un único elemento de datos.

A pesar de todo lo anterior, los arreglos sistólicos suelen presentarse como un ejemplo clásico de arquitectura MISD en libros de texto sobre computación paralela y en clases de ingeniería. Si se considera el arreglo como atómico desde fuera, quizás debería clasificarse como SFMuDMeR = función única, datos múltiples, resultado(s) combinado(s).

Las redes sistólicas utilizan un grafo de flujo computacional predefinido que conecta sus nodos. Las redes de procesos de Kahn utilizan un grafo de flujo similar, pero se distinguen porque los nodos trabajan de forma sincronizada en la red sistólica: en una red de Kahn, existen colas FIFO entre cada nodo.

Descripción detallada

Una matriz sistólica está compuesta por filas de unidades de procesamiento de datos llamadas celdas, dispuestas como una matriz. 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 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 ella entre DPU vecinas , a menudo con datos diferentes fluyendo en direcciones distintas. 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 sistemas embebidos, un flujo de datos también puede recibir y/o enviarse a una fuente externa.

Ejemplos de multiplicación de matrices de 2x2 en la matriz sistólica

Algoritmo de matriz sistólica que acumula valores de salida dentro de las DPU .

El algoritmo de matriz sistólica precarga y mantiene un operando fijo dentro de las DPU durante el cálculo. En el ejemplo, la matriz verde se precarga en la matriz y puede reutilizarse para multiplicaciones posteriores.

Un ejemplo de algoritmo sistólico podría diseñarse para la multiplicación de matrices . Una matriz se introduce fila por fila desde la parte superior del array y se pasa hacia abajo; la otra matriz se introduce columna por columna desde la parte izquierda del array y se pasa de izquierda a derecha. A continuación, se introducen valores ficticios hasta que cada procesador haya procesado una fila y una columna completas. En este punto, el resultado de la multiplicación se almacena en el array y se puede mostrar fila por fila o columna por columna, recorriendo el array horizontal o verticalmente. ^{[ 4 ]}

Los arreglos sistólicos son conjuntos de DPUs conectadas a un pequeño número de DPUs vecinas en una topología de malla. Las DPUs realizan una secuencia de operaciones sobre los datos que fluyen entre ellas. Debido a que los métodos tradicionales de síntesis de arreglos sistólicos se han basado en algoritmos algebraicos, solo se pueden obtener arreglos uniformes con tuberías lineales, de modo que las arquitecturas son idénticas en todas las DPUs. En consecuencia, solo las aplicaciones con dependencias de datos regulares pueden implementarse en arreglos sistólicos clásicos. Al igual que las máquinas SIMD , los arreglos sistólicos síncronos computan en "paso a paso", con cada procesador realizando fases alternas de cómputo y comunicación. Sin embargo, los arreglos sistólicos con comunicación asíncrona entre DPUs se denominan arreglos de frente de onda . Un ejemplo conocido de arreglo sistólico es el procesador iWarp de la Universidad Carnegie Mellon , fabricado por Intel. Un sistema iWarp cuenta con un procesador de arreglo lineal conectado mediante buses de datos bidireccionales.

Historia

Los arreglos sistólicos (también conocidos como procesadores de frente de onda ) fueron descritos por primera vez por HT Kung y Charles E. Leiserson , quienes publicaron el primer artículo que los describía en 1979. Sin embargo, la primera máquina conocida que utilizó una técnica similar fue el Colossus Mark II en 1944. El Colossus utilizaba registros de desplazamiento paralelos para procesar datos mediante pulsos, lo cual es funcionalmente similar a un arreglo sistólico, pero carecía de los "elementos de procesamiento" (PE) interconectados que definen la arquitectura Kung-Leiserson de 1978.

La primera máquina diseñada explícitamente como una matriz sistólica fue la computadora WARP en 1984.

Ejemplos

Evaluación polinómica

La regla de Horner para evaluar un polinomio es:

y=(\ldots (((a_{n}\cdot x+a_{n-1})\cdot x+a_{n-2})\cdot x+a_{n-3})\cdot x+\ldots +a_{1})\cdot x+a_{0}.

Una matriz sistólica lineal en la que los procesadores están dispuestos en pares: uno multiplica su entrada por $x$ y pasa el resultado a la derecha, el siguiente suma $a_{j}$ y pasa el resultado a la derecha.

Circunvolución

Consideremos una cadena de elementos de procesamiento (PE), cada uno de los cuales realiza una operación de multiplicación y acumulación . Procesa datos de entrada ( $x_{i}$ ) y pesos ( $w_{i}$ ) sistólicamente, lo que significa que los datos fluyen a través de la matriz de manera regular y rítmica. Los pesos permanecen estacionarios dentro de cada PE, mientras que los datos de entrada y las sumas parciales ( $y_{i}$ ) se mueven en direcciones opuestas.

Cada PE realiza la siguiente operación: ${\begin{aligned}y_{out}&=y_{in}+w\cdot x_{in}\\x_{out}&=x_{in}\end{aligned}}$ dónde:

$x_{en}$ son los datos de entrada.
$y_{en}$ es la suma parcial entrante.
$w$ es el peso almacenado en el PE.
$x_{out}$ son los datos de salida (que se pasan al siguiente PE).
$y_{out}$ es la suma parcial actualizada.

Desde la izquierda, el flujo de entrada es $\dots ,x_{3},0,x_{2},0,x_{1}$ y desde la derecha, el flujo de salida es ${\ Displaystyle y_ {1}, y_ {2}, y_ {3}, \ puntos}$ . Si $y_{1},x_{1}$ ingrese el PE más a la derecha simultáneamente, luego el PE más a la izquierda emite ${\begin{aligned}y_{1}&=w_{1}x_{1}+w_{2}x_{2}+w_{3}x_{3}+\cdots \\y_{2}&=w_{1}x_{2}+w_{2}x_{3}+w_{3}x_{4}+\cdots \\&\vdots \end{aligned}}$ Esta es la convolución unidimensional. De manera similar, la convolución n-dimensional se puede calcular mediante una matriz n-dimensional de PE.

Existen muchas otras implementaciones de las convoluciones 1D, con diferentes flujos de datos. ^{[ 5 ]}

Consulte ^{[ 5 ]} la Figura 12 para ver un algoritmo que realiza mínimos cuadrados sobre la marcha utilizando matrices sistólicas unidimensionales y bidimensionales.

Clasificación

El ordenamiento de burbuja también es un ejemplo de computación sistólica 1D, ^{[ 6 ]} aunque aplica N-1 pasadas para una matriz de tamaño N. Cada pasada mueve sistólicamente el elemento máximo de una subsecuencia hacia su ubicación final en el resultado ordenado.

Si se utilizan N/2 elementos de procesamiento (EP), cada uno con un comparador y dos registros, dispuestos en forma de pila, se puede ordenar una matriz (o flujo) de tamaño N en 2N tiempo insertando sus elementos mientras que en cada nivel de la pila sistólica se desplaza hacia abajo el máximo del par de elementos almacenados en cada EP. Una vez insertados todos los elementos, el proceso se invierte extrayendo (o "desplazando hacia arriba") el mínimo de cada EP, lo que da como resultado un flujo de elementos ordenados en orden ascendente. ^{[ 7 ]}

Ordenar matrices de entrada de mayor tamaño (N > P) que el número de elementos de procesamiento (P) resulta algo complejo de realizar de forma eficiente con un sistema de este tipo, pero puede lograrse (añadiendo un procesador serie externo) en un tiempo de O(N log N/log P). El procesador serie debe gestionar un "árbol B de cubetas", donde cada nodo del árbol B tiene P "cubetas" que, finalmente, se ordenan en un tiempo de O(P) utilizando los PE. ^{[ 8 ]}

Implementaciones

Transputador Inmos ^{[ 9 ]}
El procesador de red Cisco PXF está organizado internamente como una matriz sistólica. ^{[ 10 ]}
La TPU de Google también está diseñada en torno a una matriz sistólica.
Sistema de búsqueda de texto Paracel FDF4T TestFinder ^{[ 11 ]}
Sistema de búsqueda biológica (ADN y proteínas) Paracel FDF4G GeneMatcher
Chips de arquitectura AWS Neuron (Inferentia y Trainium) en Amazon Web Services ^{[ 12 ]}^{[ 13 ]}
Acelerador basado en matriz sistólica Gemmini desarrollado en UC Berkeley ^{[ 14 ]}

Véase también

MISD – instrucciones múltiples, datos únicos, ejemplo: matrices sistólicas
iWarp – computadora de matriz sistólica, VLSI, Intel/CMU
WARP (matriz sistólica) – computadora de matriz sistólica, GE/CMU
Unidad de Procesamiento Tensorial (TPU): ASIC acelerador de IA
Arquitectura espacial : clase de arquitecturas informáticas que engloban matrices sistólicas.

Notas

↑ Colossus: El mayor secreto de la historia de la informática en YouTube
↑ Brent, Richard P.; Kung, HT (agosto de 1984). "Matrices VLSI sistólicas para el cálculo del MCD polinomial" (PDF) . www.eecs.harvard.edu .
↑ La serie de procesadores de matrices sistólicas Paracel GeneMatcher sí cuenta con un contador de programa . Los algoritmos más complejos se implementan como una serie de pasos simples, con desplazamientos especificados en las instrucciones.
↑ "Multiplicación de matrices de arreglo sistólico" (PDF) .
1 2 Kung (enero de 1982). "¿Por qué arquitecturas sistólicas?". Computer . 15 (1): 37– 46. Bibcode : 1982Compr..15a..37K . doi : 10.1109/MC.1982.1653825 . ISSN 0018-9162 . S2CID 1858965 .
↑ CL Britton, Jr., MN Ericson y DW Bouldin, "Una matriz de clasificación sistólica monolítica de tiempo cero virtual", 1989 https://www.osti.gov/servlets/purl/6004774
↑ MH Alsuwaiyel, *Algoritmos paralelos*, World Scientific, 2022, Sec. 9.5 "Un clasificador de burbujas en chip" (en Cap. 9 "Computación sistólica").
↑ Mikhail J. Atallah, Greg N. Frederickson, S. Rao Kosaraju, "Clasificación con uso eficiente de clasificadores de propósito especial", Information Processing Letters 1988 https://doi.org/10.1016/0020-0190(88)90075-0 ; también como Purdue CSD-TR 87-695 https://docs.lib.purdue.edu/cstech/602/
↑ "Arreglos sistólicos" en *Manual de sistemas de procesamiento de señales* (3.ª ed.), 2018 https://link.springer.com/chapter/10.1007/978-3-319-91734-4_26
↑ "Instalación del motor de enrutamiento de rendimiento del router Cisco Serie 10000" . Consultado el 3 de agosto de 2020 .
↑ "Acerca de Paracel" . brandprosgroup.com . Paracel . Consultado el 4 de mayo de 2018 .
↑ "Anuncio de la disponibilidad de instancias Inf1 en Amazon SageMaker para inferencia de aprendizaje automático de alto rendimiento y rentable" . 14 de agosto de 2020. Consultado el 15 de agosto de 2020 .
↑ "Autosuficiencia de la IA de Amazon | Arquitectura y redes de Trainium2" . 3 de diciembre de 2024. Archivado del original el 3 de febrero de 2026. Consultado el 3 de febrero de 2026 .
↑ Genc, Hasan; Kim, Seah; Amid, Alon; Haj-Ali, Ameer; Iyer, Vighnesh; Prakash, Pranav; Zhao, Jerry; Grubb, Daniel; Liew, Harrison; Mao, Howard; Ou, Albert; Schmidt, Colin; Steffl, Samuel; Wright, John; Stoica, Ion; Ragan-Kelley, Jonathan; Asanovic, Krste; Nikolic, Borivoje; Shao, Yakun Sophia (2021). "Gemmini: Facilitando la evaluación sistemática de arquitecturas de aprendizaje profundo mediante la integración de pila completa". 58.ª Conferencia de Automatización de Diseño ACM/IEEE (DAC) de 2021. págs. 769–774 . arXiv : 1911.09925 . doi : 10.1109/DAC18074.2021.9586216 . ISBN 978-1-6654-3274-0.

Referencias

HT Kung, CE Leiserson: Algoritmos para matrices de procesadores VLSI; en: C. Mead, L. Conway (eds.): Introducción a los sistemas VLSI; Addison-Wesley, 1979.
SY Kung: Procesadores de matrices VLSI; Prentice-Hall, Inc., 1988
N. Petkov: Procesamiento paralelo sistólico; North Holland Publishing Co, 1992

Enlaces externos

Dorband, Ernst Nils; Hemsendorf, Marc; Merritt, David (marzo de 2003). "Algoritmos sistólicos e hipersistólicos para el problema gravitacional de n cuerpos, con una aplicación al movimiento browniano" . Journal of Computational Physics . 185 (2): 484– 511. arXiv : astro-ph/0112092 . Bibcode : 2003JCoPh.185..484D . doi : 10.1016/S0021-9991(02)00067-0 .
Matriz sistólica de instrucción (ISA)
'Una arquitectura VLSI para el registro de imágenes en tiempo real' (basada en una matriz sistólica), vol. 15, septiembre de 2007

[1] Colossus: El mayor secreto de la historia de la informática en YouTube

[2] Brent, Richard P.; Kung, HT (agosto de 1984). "Matrices VLSI sistólicas para el cálculo del MCD polinomial" (PDF) . www.eecs.harvard.edu .

[3] La serie de procesadores de matrices sistólicas Paracel GeneMatcher sí cuenta con un contador de programa . Los algoritmos más complejos se implementan como una serie de pasos simples, con desplazamientos especificados en las instrucciones.

[4] "Multiplicación de matrices de arreglo sistólico" (PDF) .

[:0-5] 1 2 Kung (enero de 1982). "¿Por qué arquitecturas sistólicas?". Computer . 15 (1): 37– 46. Bibcode : 1982Compr..15a..37K . doi : 10.1109/MC.1982.1653825 . ISSN 0018-9162 . S2CID 1858965 .

[6] CL Britton, Jr., MN Ericson y DW Bouldin, "Una matriz de clasificación sistólica monolítica de tiempo cero virtual", 1989 https://www.osti.gov/servlets/purl/6004774

[7] MH Alsuwaiyel, *Algoritmos paralelos*, World Scientific, 2022, Sec. 9.5 "Un clasificador de burbujas en chip" (en Cap. 9 "Computación sistólica").

[8] Mikhail J. Atallah, Greg N. Frederickson, S. Rao Kosaraju, "Clasificación con uso eficiente de clasificadores de propósito especial", Information Processing Letters 1988 https://doi.org/10.1016/0020-0190(88)90075-0 ; también como Purdue CSD-TR 87-695 https://docs.lib.purdue.edu/cstech/602/

[HSP-9] "Arreglos sistólicos" en *Manual de sistemas de procesamiento de señales* (3.ª ed.), 2018 https://link.springer.com/chapter/10.1007/978-3-319-91734-4_26

[10] "Instalación del motor de enrutamiento de rendimiento del router Cisco Serie 10000" . Consultado el 3 de agosto de 2020 .

[FDF4-11] "Acerca de Paracel" . brandprosgroup.com . Paracel . Consultado el 4 de mayo de 2018 .

[12] "Anuncio de la disponibilidad de instancias Inf1 en Amazon SageMaker para inferencia de aprendizaje automático de alto rendimiento y rentable" . 14 de agosto de 2020. Consultado el 15 de agosto de 2020 .

[13] "Autosuficiencia de la IA de Amazon | Arquitectura y redes de Trainium2" . 3 de diciembre de 2024. Archivado del original el 3 de febrero de 2026. Consultado el 3 de febrero de 2026 .

[14] Genc, Hasan; Kim, Seah; Amid, Alon; Haj-Ali, Ameer; Iyer, Vighnesh; Prakash, Pranav; Zhao, Jerry; Grubb, Daniel; Liew, Harrison; Mao, Howard; Ou, Albert; Schmidt, Colin; Steffl, Samuel; Wright, John; Stoica, Ion; Ragan-Kelley, Jonathan; Asanovic, Krste; Nikolic, Borivoje; Shao, Yakun Sophia (2021). "Gemmini: Facilitando la evaluación sistemática de arquitecturas de aprendizaje profundo mediante la integración de pila completa". 58.ª Conferencia de Automatización de Diseño ACM/IEEE (DAC) de 2021. págs. 769–774 . arXiv : 1911.09925 . doi : 10.1109/DAC18074.2021.9586216 . ISBN 978-1-6654-3274-0.

[

[

[ 3 ]

[ 4 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]