En informática , el procesamiento de flujo (también conocido como procesamiento de flujo de eventos , procesamiento de flujo de datos o procesamiento de flujo distribuido ) es un paradigma de programación que considera los flujos , o secuencias de eventos en el tiempo, como los objetos centrales de entrada y salida del cálculo . El procesamiento de flujo abarca la programación de flujo de datos , la programación reactiva y el procesamiento de datos distribuido . [1] Los sistemas de procesamiento de flujo tienen como objetivo exponer el procesamiento paralelo para flujos de datos y se basan en algoritmos de transmisión para una implementación eficiente. La pila de software para estos sistemas incluye componentes como modelos de programación y lenguajes de consulta , para expresar el cálculo; sistemas de gestión de flujo , para distribución y programación ; y componentes de hardware para aceleración, incluyendo unidades de punto flotante , unidades de procesamiento de gráficos y matrices de puertas programables en campo . [2]
El paradigma de procesamiento de flujo simplifica el software y hardware paralelos al restringir el cálculo paralelo que se puede realizar. Dada una secuencia de datos (un flujo ), se aplica una serie de operaciones ( funciones de kernel ) a cada elemento del flujo. Las funciones de kernel suelen canalizarse y se intenta una reutilización óptima de la memoria local en el chip, con el fin de minimizar la pérdida de ancho de banda asociada con la interacción de la memoria externa. El streaming uniforme , donde se aplica una función de kernel a todos los elementos del flujo, es típico. Dado que las abstracciones de kernel y flujo exponen dependencias de datos, las herramientas de compilación pueden automatizar y optimizar por completo las tareas de gestión en chip. El hardware de procesamiento de flujo puede utilizar el marcador , por ejemplo, para iniciar un acceso directo a memoria (DMA) cuando se conocen las dependencias. La eliminación de la gestión manual de DMA reduce la complejidad del software y una eliminación asociada para la E/S en caché de hardware reduce la extensión del área de datos que debe involucrarse con el servicio por parte de unidades computacionales especializadas, como las unidades lógicas aritméticas .
Durante la década de 1980, el procesamiento de flujos se exploró en la programación de flujos de datos . Un ejemplo es el lenguaje SISAL (Streams and Iteration in a Single Assignment Language).
El procesamiento de flujo es esencialmente un compromiso, impulsado por un modelo centrado en los datos que funciona muy bien para aplicaciones tradicionales de tipo DSP o GPU (como procesamiento de imágenes, video y señales digitales ), pero no tanto para el procesamiento de propósito general con acceso a datos más aleatorio (como bases de datos). Al sacrificar cierta flexibilidad en el modelo, las implicaciones permiten una ejecución más fácil, rápida y eficiente. Dependiendo del contexto, el diseño del procesador puede ajustarse para lograr la máxima eficiencia o una compensación por la flexibilidad.
El procesamiento de flujo es especialmente adecuado para aplicaciones que presentan tres características de aplicación: [ cita requerida ]
Algunos ejemplos de registros dentro de secuencias incluyen:
Para cada registro, solo podemos leer la entrada, realizar operaciones en ella y escribir en la salida. Se permite tener múltiples entradas y múltiples salidas, pero nunca un fragmento de memoria que sea legible y escribible.
A modo de ejemplo, los siguientes fragmentos de código demuestran la detección de patrones dentro de secuencias de eventos. El primero es un ejemplo de procesamiento de una secuencia de datos mediante una consulta SQL continua (una consulta que se ejecuta de forma continua y procesa los datos que llegan en función de las marcas de tiempo y la duración de la ventana). Este fragmento de código ilustra una UNIÓN de dos secuencias de datos, una para las órdenes de acciones y otra para las transacciones de acciones resultantes. La consulta genera una secuencia de todas las órdenes que coinciden con una transacción en el plazo de un segundo desde que se realiza la orden. La secuencia de salida se ordena por marca de tiempo, en este caso, la marca de tiempo de la secuencia de órdenes.
SELECCIONAR DataStream Órdenes . Marca de tiempo , Órdenes . orderId , Órdenes . ticker , Órdenes . importe , Operación . importe DE Órdenes UNIR Operaciones SOBRE ( RANGO INTERVALO '1' SEGUNDO SIGUIENTE ) EN Órdenes . orderId = Operaciones . orderId ; Otro fragmento de código de muestra detecta bodas entre un flujo de "eventos" externos, como el sonido de las campanas de una iglesia, la aparición de un hombre con esmoquin o traje de mañana, una mujer con un vestido blanco suelto y arroz volando por el aire. Un evento "complejo" o "compuesto" es lo que se infiere de los eventos simples individuales: se está celebrando una boda.
CUANDO Persona . Género ES IGUAL A " hombre" Y Persona . Ropa ES IGUAL A "esmoquin" SEGUIDO DE Persona . Ropa ES IGUAL A "vestido" Y ( Campana_de_iglesia O Arroz_volando ) DENTRO DE 2 horas ACCIÓN Boda Las computadoras básicas comenzaron a partir de un paradigma de ejecución secuencial. Las CPU tradicionales se basan en SISD , lo que significa que conceptualmente realizan solo una operación a la vez. A medida que evolucionaron las necesidades informáticas del mundo, la cantidad de datos a gestionar aumentó muy rápidamente. Era obvio que el modelo de programación secuencial no podía hacer frente a la mayor necesidad de potencia de procesamiento. Se han dedicado varios esfuerzos a encontrar formas alternativas de realizar cantidades masivas de cálculos, pero la única solución era explotar algún nivel de ejecución paralela. El resultado de esos esfuerzos fue SIMD , un paradigma de programación que permitía aplicar una instrucción a múltiples instancias de datos (diferentes). La mayor parte del tiempo, SIMD se usaba en un entorno SWAR . Al usar estructuras más complicadas, también se podía tener paralelismo MIMD .
Aunque esos dos paradigmas eran eficientes, las implementaciones en el mundo real estaban plagadas de limitaciones, desde problemas de alineación de memoria hasta problemas de sincronización y paralelismo limitado. Solo unos pocos procesadores SIMD sobrevivieron como componentes independientes; la mayoría estaban integrados en CPU estándar.
Considere un programa simple que suma dos matrices que contienen 100 vectores de 4 componentes (es decir, 400 números en total).
para ( int i = 0 ; i < 400 ; i ++ ) resultado [ i ] = fuente0 [ i ] + fuente1 [ i ]; Este es el paradigma secuencial más conocido. Existen variaciones (como bucles internos, estructuras, etc.), pero en última instancia se reducen a ese constructo.
for ( int el = 0 ; el < 100 ; el ++ ) // para cada vector vector_sum ( resultado [ el ], fuente0 [ el ], fuente1 [ el ]); En realidad, esto es una simplificación excesiva. Se supone que la instrucción vector_sumfunciona. Aunque esto es lo que sucede con los intrínsecos de la instrucción , en realidad no se tiene en cuenta mucha información aquí, como la cantidad de componentes vectoriales y su formato de datos. Esto se hace para mayor claridad.
Sin embargo, se puede observar que este método reduce la cantidad de instrucciones decodificadas de numElements * componentPerElement a numElements . La cantidad de instrucciones de salto también disminuye, ya que el bucle se ejecuta menos veces. Estas ganancias son el resultado de la ejecución paralela de las cuatro operaciones matemáticas.
Sin embargo, lo que sucedió es que el registro SIMD empaquetado contiene una cierta cantidad de datos, por lo que no es posible obtener más paralelismo. La aceleración está algo limitada por la suposición que hicimos de realizar cuatro operaciones en paralelo (tenga en cuenta que esto es común tanto para AltiVec como para SSE ).
// Este es un lenguaje ficticio para fines de demostración. elements = array streamElement ([ number , number ] )[ 100 ] kernel = instance streamKernel ( "@arg0[@iter]" ) result = kernel .invoke ( elements ) En este paradigma, se define el conjunto de datos completo, en lugar de que cada bloque de componentes se defina por separado. Se supone que la descripción del conjunto de datos se encuentra en las dos primeras filas. Después de eso, el resultado se infiere a partir de las fuentes y el núcleo. Para simplificar, existe una correlación 1:1 entre los datos de entrada y de salida, pero no es necesario que sea así. Los núcleos aplicados también pueden ser mucho más complejos.
Una implementación de este paradigma puede "desenrollar" un bucle internamente. Esto permite que el rendimiento se adapte a la complejidad del chip, utilizando fácilmente cientos de unidades de procesamiento automático. [3] [4] La eliminación de patrones de datos complejos hace que gran parte de esta potencia adicional esté disponible.
Si bien el procesamiento de flujo es una rama del procesamiento SIMD/MIMD, no deben confundirse. Si bien las implementaciones SIMD a menudo pueden funcionar de manera "de flujo", su rendimiento no es comparable: el modelo prevé un patrón de uso muy diferente que permite un rendimiento mucho mayor por sí solo.
Se ha observado que cuando se aplica en procesadores genéricos como la CPU estándar, solo se puede alcanzar una aceleración de 1,5x. [5] Por el contrario, los procesadores de flujo ad-hoc alcanzan fácilmente un rendimiento de más de 10x, atribuido principalmente al acceso a la memoria más eficiente y a niveles más altos de procesamiento paralelo. [6]
Aunque el modelo permite diversos grados de flexibilidad, los procesadores de flujo suelen imponer algunas limitaciones en el tamaño del núcleo o del flujo. Por ejemplo, el hardware de consumo a menudo carece de la capacidad de realizar operaciones matemáticas de alta precisión, carece de cadenas de indirección complejas o presenta límites inferiores en la cantidad de instrucciones que se pueden ejecutar.
Los proyectos de procesamiento de flujo de la Universidad de Stanford incluyeron el Proyecto de sombreado programable en tiempo real de Stanford, que comenzó en 1999. [7] En 2002 se desarrolló un prototipo llamado Imagine. [8] Un proyecto llamado Merrimac funcionó hasta aproximadamente 2004. [9] AT&T también investigó procesadores mejorados para flujo, ya que las unidades de procesamiento de gráficos evolucionaron rápidamente tanto en velocidad como en funcionalidad. [1] Desde esos primeros días, se han desarrollado docenas de lenguajes de procesamiento de flujo, así como hardware especializado.
El desafío más inmediato en el ámbito del procesamiento paralelo no radica tanto en el tipo de arquitectura de hardware utilizada, sino en lo fácil que será programar el sistema en cuestión en un entorno del mundo real con un rendimiento aceptable. Las máquinas como Imagine utilizan un modelo sencillo de un solo subproceso con dependencias automatizadas, asignación de memoria y programación DMA . Esto en sí mismo es el resultado de la investigación en el MIT y Stanford para encontrar una estratificación óptima de tareas entre el programador, las herramientas y el hardware. Los programadores superan a las herramientas en la asignación de algoritmos a hardware paralelo, y las herramientas superan a los programadores en la determinación de los esquemas de asignación de memoria más inteligentes, etc. De particular preocupación son los diseños MIMD como Cell , para los cuales el programador necesita lidiar con la partición de aplicaciones en múltiples núcleos y lidiar con la sincronización de procesos y el equilibrio de carga.
Una desventaja de la programación SIMD era el problema de las matrices de estructuras (AoS) y las estructuras de matrices (SoA) . Los programadores suelen crear representaciones de entidades en la memoria, por ejemplo, la ubicación de una partícula en el espacio 3D, el color de la pelota y su tamaño, como se muestra a continuación:
// Una partícula en un espacio tridimensional. struct particle_t { float x , y , z ; // ¡ni siquiera es una matriz! unsigned byte color [ 3 ]; // 8 bits por canal, digamos que solo nos importa RGB float size ; // ... y pueden seguir muchos otros atributos... }; Cuando existen varias de estas estructuras en la memoria, se colocan de extremo a extremo creando una matriz en una topología de matriz de estructuras (AoS). Esto significa que si se aplica algún algoritmo a la ubicación de cada partícula, a su vez, debe omitir las ubicaciones de memoria que contienen los otros atributos. Si estos atributos no son necesarios, esto da como resultado un uso innecesario de la memoria caché de la CPU. Además, una instrucción SIMD normalmente esperará que los datos sobre los que operará sean contiguos en la memoria; es posible que también sea necesario alinear los elementos . Al mover la ubicación de memoria de los datos fuera de la estructura, los datos se pueden organizar mejor para un acceso eficiente en un flujo y para que las instrucciones SIMD operen uno. Una estructura de matrices (SoA), como se muestra a continuación, puede permitir esto.
struct particle_t { float * x , * y , * z ; byte sin signo * colorRojo , * colorAzul , * colorVerde ; float * tamaño ; }; En lugar de almacenar los datos en la estructura, solo almacena punteros (ubicaciones de memoria) para los datos. Las deficiencias son que si se deben operar varios atributos de un objeto, es posible que ahora estén distantes en la memoria y, por lo tanto, se produzca un error de caché. La alineación y cualquier relleno necesario conducen a un mayor uso de memoria. En general, la gestión de la memoria puede ser más complicada si se agregan y eliminan estructuras, por ejemplo.
En el caso de los procesadores de flujo, se fomenta el uso de estructuras. Desde el punto de vista de la aplicación, todos los atributos se pueden definir con cierta flexibilidad. Si tomamos las GPU como referencia, hay un conjunto de atributos (al menos 16) disponibles. Para cada atributo, la aplicación puede indicar la cantidad de componentes y el formato de los componentes (pero por ahora solo se admiten tipos de datos primitivos). Luego, los diversos atributos se adjuntan a un bloque de memoria, posiblemente definiendo un paso entre elementos "consecutivos" de los mismos atributos, lo que permite intercalar datos de manera efectiva. Cuando la GPU comienza el procesamiento del flujo, reunirá todos los diversos atributos en un solo conjunto de parámetros (generalmente parece una estructura o una "variable global mágica"), realizará las operaciones y dispersará los resultados en algún área de memoria para su posterior procesamiento (o recuperación).
Los marcos de procesamiento de flujo más modernos proporcionan una interfaz similar a FIFO para estructurar los datos como un flujo literal. Esta abstracción proporciona un medio para especificar dependencias de datos de manera implícita, al tiempo que permite que el entorno de ejecución/hardware aproveche al máximo ese conocimiento para un cálculo eficiente. Una de las modalidades de procesamiento de flujo más simples [ cita requerida ] y más eficientes [ cita requerida ] hasta la fecha para C++ es RaftLib , que permite vincular núcleos de cómputo independientes entre sí como un gráfico de flujo de datos utilizando operadores de flujo de C++. A modo de ejemplo:
#include <raft> #include <raftio> #include <cstdlib> #include <string> clase hi : balsa pública :: kernel { pública : hi () : balsa :: kernel () { salida.addPort < std :: string > ( " 0 " ); } balsa virtual :: kstatus run () { salida [ "0" ]. push ( std :: string ( "Hola mundo \n " )); retorno balsa :: detener ; } }; int main ( int argc , char ** argv ) { /** instanciar print kernel **/ raft :: print < std :: string > p ; /** instanciar hello world kernel **/ hi hello ; /** crear un objeto de mapa **/ raft :: map m ; /** agregar núcleos a map, tanto hello como p se ejecutan simultáneamente **/ m += hello >> p ; /** ejecutar el mapa **/ m . exe (); return EXIT_SUCCESS ; } Además de especificar aplicaciones de streaming en lenguajes de alto nivel, los modelos de computación (MoC) también se han utilizado ampliamente como modelos de flujo de datos y modelos basados en procesos.
Históricamente, las CPU comenzaron a implementar varios niveles de optimización de acceso a la memoria debido al rendimiento cada vez mayor en comparación con el ancho de banda de la memoria externa, que crecía relativamente lento. A medida que esta brecha se amplió, se dedicaron grandes cantidades de área de matriz a ocultar latencias de memoria. Dado que obtener información y códigos de operación para esas pocas ALU es costoso, muy poca área de matriz se dedica a la maquinaria matemática real (como una estimación aproximada, considere que es menos del 10%).
Existe una arquitectura similar en los procesadores de flujo, pero gracias al nuevo modelo de programación, la cantidad de transistores dedicados a la gestión es en realidad muy pequeña.
Si comenzamos desde el punto de vista del sistema completo, los procesadores de flujo suelen existir en un entorno controlado. Las GPU existen en una placa complementaria (esto también parece aplicarse a Imagine). Las CPU continúan realizando la tarea de administrar los recursos del sistema, ejecutar aplicaciones, etc.
El procesador de flujo suele estar equipado con un bus de memoria propietario, rápido y eficiente (los conmutadores de barra cruzada son ahora comunes, en el pasado se han utilizado multibuses). La cantidad exacta de líneas de memoria depende del mercado. En el momento de escribir esto, todavía hay interconexiones de 64 bits de ancho (nivel de entrada). La mayoría de los modelos de gama media utilizan una matriz de conmutación de barra cruzada rápida de 128 bits (4 o 2 segmentos), mientras que los modelos de gama alta utilizan enormes cantidades de memoria (en realidad hasta 512 MB) con una barra cruzada ligeramente más lenta de 256 bits de ancho. Por el contrario, los procesadores estándar, desde Intel Pentium hasta algunos Athlon 64, tienen solo un bus de datos de 64 bits de ancho.
Los patrones de acceso a la memoria son mucho más predecibles. Si bien existen matrices, su dimensión se fija en la invocación del núcleo. Lo que más se asemeja a una indirección de puntero múltiple es una cadena de indirección , que sin embargo está garantizada para leer o escribir en un área de memoria específica (dentro de un flujo).
Debido a la naturaleza SIMD de las unidades de ejecución del procesador de flujo (grupos de ALU), se espera que las operaciones de lectura y escritura se realicen en masa, por lo que las memorias se optimizan para un ancho de banda alto en lugar de una latencia baja (esta es una diferencia con Rambus y DDR SDRAM , por ejemplo). Esto también permite negociaciones eficientes del bus de memoria.
La mayor parte (90%) del trabajo de un procesador de flujo se realiza en el chip, por lo que solo se requiere que el 1% de los datos globales se almacenen en la memoria. Aquí es donde resulta útil conocer los datos temporales y las dependencias del núcleo.
En el interior, un procesador de flujo cuenta con algunos circuitos de comunicación y gestión inteligentes, pero lo que resulta interesante es el archivo de registro de flujo (SRF, Stream Register File ). Se trata, conceptualmente, de una gran caché en la que se almacenan los datos de flujo para transferirlos a la memoria externa en grandes cantidades. Como estructura controlada por software similar a una caché para las distintas ALU , el SRF se comparte entre todos los distintos clústeres de ALU. El concepto clave y la innovación que se ha realizado aquí con el chip Imagine de Stanford es que el compilador puede automatizar y asignar memoria de forma óptima, totalmente transparente para el programador. Las dependencias entre las funciones del núcleo y los datos se conocen a través del modelo de programación, lo que permite al compilador realizar un análisis de flujo y empaquetar de forma óptima los SRF. Por lo general, esta gestión de caché y DMA puede ocupar la mayor parte de la programación de un proyecto, algo que el procesador de flujo (o al menos Imagine) automatiza por completo. Las pruebas realizadas en Stanford demostraron que el compilador hacía un trabajo igual de bueno o mejor en la programación de la memoria que si se ajustara manualmente con mucho esfuerzo.
Hay pruebas de que puede haber muchos clústeres porque se supone que la comunicación entre clústeres es poco frecuente. Sin embargo, internamente, cada clúster puede explotar de manera eficiente una cantidad mucho menor de ALU porque la comunicación dentro de un clúster es común y, por lo tanto, debe ser altamente eficiente.
Para mantener esas ALU cargadas de datos, cada ALU está equipada con archivos de registro locales (LRF), que son básicamente sus registros utilizables.
Este patrón de acceso a datos de tres niveles facilita mantener los datos temporales alejados de las memorias lentas, lo que hace que la implementación de silicio sea altamente eficiente y ahorre energía.
Aunque se puede esperar razonablemente una aceleración de un orden de magnitud (incluso de las GPU convencionales cuando se computa en modo streaming), no todas las aplicaciones se benefician de esto. Las latencias de comunicación son en realidad el mayor problema. Aunque PCI Express mejoró esto con las comunicaciones full-duplex, hacer que funcione una GPU (y posiblemente un procesador de flujo genérico) posiblemente llevará mucho tiempo. Esto significa que suele ser contraproducente usarlos para conjuntos de datos pequeños. Debido a que cambiar el núcleo es una operación bastante costosa, la arquitectura de flujo también incurre en penalizaciones para flujos pequeños, un comportamiento conocido como el efecto de flujo corto .
El pipeline es una práctica muy extendida y muy utilizada en los procesadores de flujo, con GPU que cuentan con pipelines que superan las 200 etapas. El costo de cambiar los ajustes depende de la configuración que se modifique, pero ahora se considera que siempre es caro. Para evitar esos problemas en varios niveles del pipeline, se han implementado muchas técnicas, como "ultrashaders" y "atlases de texturas". Esas técnicas están orientadas a los juegos debido a la naturaleza de las GPU, pero los conceptos también son interesantes para el procesamiento de flujo genérico.
La mayoría de los lenguajes de programación para procesadores de flujo comienzan con Java, C o C++ y agregan extensiones que brindan instrucciones específicas para permitir que los desarrolladores de aplicaciones etiqueten núcleos y/o flujos. Esto también se aplica a la mayoría de los lenguajes de sombreado , que pueden considerarse lenguajes de programación de flujo hasta cierto punto.
Algunos ejemplos no comerciales de lenguajes de programación de streaming incluyen:
Las implementaciones comerciales son de propósito general o están vinculadas a un hardware específico por parte de un proveedor. Algunos ejemplos de lenguajes de propósito general son:
Los idiomas específicos del proveedor incluyen:
Procesamiento basado en eventos
Procesamiento basado en archivos por lotes (emula parte del procesamiento de flujo real, pero con un rendimiento mucho menor en general [ aclaración necesaria ] [ cita necesaria ] )
Procesamiento continuo de flujo de operadores [ aclaración necesaria ]
Servicios de procesamiento de flujo: