En informática , el procesamiento de flujos (también conocido como procesamiento de flujos de eventos , procesamiento de flujos de datos o procesamiento de flujos distribuidos ) 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 de la computación . El procesamiento de flujo abarca la programación de flujo de datos , la programación reactiva y el procesamiento de datos distribuidos . [1] Los sistemas de procesamiento de flujos tienen como objetivo exponer el procesamiento paralelo de flujos de datos y dependen de algoritmos de flujo 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 la computación; sistemas de gestión de flujos , para distribución y programación ; y componentes de hardware para aceleración , incluidas 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 el hardware paralelos al restringir el cálculo paralelo que se puede realizar. Dada una secuencia de datos (una secuencia ), se aplica una serie de operaciones ( funciones del núcleo ) a cada elemento de la secuencia. Las funciones del kernel generalmente se canalizan y se intenta la reutilización óptima de la memoria local en el chip para minimizar la pérdida de ancho de banda asociada con la interacción de la memoria externa. Es típico el streaming uniforme , donde se aplica una función del núcleo a todos los elementos del flujo. Dado que las abstracciones del kernel y del flujo exponen dependencias de datos, las herramientas de compilación pueden automatizar y optimizar completamente las tareas de administración en el chip. El hardware de procesamiento de flujo puede utilizar marcadores , por ejemplo, para iniciar un acceso directo a la memoria (DMA) cuando se conocen las dependencias. La eliminación de la gestión manual de DMA reduce la complejidad del software y la eliminación asociada de las E/S almacenadas en caché del hardware reduce la extensión del área de datos que debe estar involucrada con el servicio de unidades computacionales especializadas, como las unidades aritméticas lógicas .
Durante la década de 1980, el procesamiento de flujos se exploró dentro de la programación de flujo 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 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 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 sacrificar flexibilidad.
El procesamiento de flujo es especialmente adecuado para aplicaciones que exhiben tres características de aplicación: [ cita necesaria ]
Ejemplos de registros dentro de transmisiones incluyen:
Para cada registro solo podemos leer desde la entrada, realizar operaciones en ella y escribir en la salida. Está permitido tener múltiples entradas y múltiples salidas, pero nunca una parte de la memoria que sea a la vez legible y escribible.
A modo de ilustración, los siguientes fragmentos de código demuestran la detección de patrones dentro de flujos de eventos. El primero es un ejemplo de procesamiento de un flujo de datos utilizando una consulta SQL continua (una consulta que se ejecuta indefinidamente procesando los datos que llegan según las marcas de tiempo y la duración de la ventana). Este fragmento de código ilustra una UNIÓN de dos flujos de datos, uno para órdenes de acciones y otro para las operaciones de acciones resultantes. La consulta genera un flujo de todas las Órdenes coincidentes con una Operación dentro de un segundo de haberse realizado la Orden. El flujo de salida se ordena por marca de tiempo, en este caso, la marca de tiempo del flujo de Órdenes.
SELECCIONE Órdenes de DataStream . Marca de tiempo , Órdenes . ID de pedido , Órdenes . ticker , Órdenes . cantidad , comercio . cantidad DESDE Órdenes UNIR Operaciones SUPERIORES ( RANGO INTERVALO '1' SEGUNDO SIGUIENTE ) EN Órdenes . orderId = Operaciones . Solicitar ID ; Otro fragmento de código de muestra detecta bodas entre un flujo de "eventos" externos, como el repique de campanas de 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 acontecimiento "complejo" o "compuesto" es lo que se infiere de los acontecimientos simples individuales: se está celebrando una boda.
CUANDO Persona . Género IGUAL A "hombre" Y Persona . Ropa IGUAL "esmoquin" SEGUIDO - POR Persona . Ropa IGUAL A "vestido" Y ( Church_Bell O Rice_Flying ) DENTRO DE 2 horas ACCIÓN Boda Las computadoras básicas partieron de un paradigma de ejecución secuencial. Las CPU tradicionales están basadas en SISD , lo que significa que conceptualmente realizan sólo 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 creciente necesidad de potencia de procesamiento. Se han realizado varios esfuerzos para encontrar formas alternativas de realizar cantidades masivas de cálculos, pero la única solución fue 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 utilizaba en un entorno SWAR . Al utilizar estructuras más complicadas, también se podrí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 la memoria hasta problemas de sincronización y paralelismo limitado. Sólo unos pocos procesadores SIMD sobrevivieron como componentes independientes; la mayoría estaban integradas 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 que resulta más familiar. Existen variaciones (como bucles internos, estructuras y demás), pero en última instancia se reducen a esa construcción.
for ( int el = 0 ; el < 100 ; el ++ ) // para cada vector vector_sum ( resultado [ el ], fuente0 [ el ], fuente1 [ el ]); En realidad, esto está demasiado simplificado. Se supone que la instrucción vector_sumfunciona. Aunque esto es lo que sucede con las instrucciones intrínsecas , aquí no se tiene en cuenta mucha información, como el número de componentes vectoriales y su formato de datos. Esto se hace para mayor claridad.
Sin embargo, puede ver que este método reduce la cantidad de instrucciones decodificadas de numElements * ComponentsPerElement a numElements . El número de instrucciones de salto también disminuye a medida que el bucle se ejecuta menos veces. Estas ganancias resultan 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 paralelas (tenga en cuenta que esto es común tanto para AltiVec como para SSE ).
// Este es un lenguaje ficticio con fines de demostración. elementos = matriz streamElement ([ número , número ])[ 100 ] kernel = instancia streamKernel ( "@arg0[@iter]" ) resultado = kernel . invocar ( elementos ) En este paradigma, se define todo el conjunto de datos, en lugar de que cada bloque de componentes se defina por separado. Se supone que la descripción del conjunto de datos está en las dos primeras filas. Después de eso, el resultado se infiere de las fuentes y del kernel. Para simplificar, existe una asignación 1:1 entre los datos de entrada y salida, pero no es necesario. 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 escale con la complejidad del chip, utilizando fácilmente cientos de ALU. [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. Aunque las implementaciones SIMD a menudo pueden funcionar en forma de "transmisión", 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 una CPU estándar, solo se puede alcanzar una aceleración de 1,5 veces. [5] Por el contrario, los procesadores de flujo ad-hoc alcanzan fácilmente un rendimiento 10 veces mayor, atribuido principalmente al acceso más eficiente a la memoria y a mayores niveles de procesamiento paralelo. [6]
Aunque el modelo permite varios grados de flexibilidad, los procesadores de flujo generalmente imponen 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 matemáticas de alta precisión, carece de cadenas de dirección indirecta complejas o presenta límites más bajos 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 iniciado 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ó el flujo Los procesadores mejorados como unidades de procesamiento de gráficos evolucionaron rápidamente tanto en velocidad como en funcionalidad. [1] Desde estos 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 reside 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. Máquinas como Imagine utilizan un modelo sencillo de subproceso único con dependencias automatizadas, asignación de memoria y programación DMA . Esto en sí mismo es el resultado de la investigación del MIT y Stanford para encontrar una estratificación óptima de tareas entre programador, herramientas y hardware. Los programadores superan a las herramientas en la asignación de algoritmos a hardware paralelo, y las herramientas superan a los programadores en el descubrimiento 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 debe ocuparse de la partición de aplicaciones en múltiples núcleos y lidiar con sincronización de procesos y equilibrio de carga.
Un inconveniente de la programación SIMD fue la cuestión de la matriz de estructuras (AoS) y la estructura 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 bola y su tamaño, como se muestra a continuación:
// Una partícula en un espacio tridimensional. estructura partícula_t { flotador x , y , z ; // ¡ni siquiera una matriz! color del byte sin firmar [ 3 ]; // 8 bits por canal, digamos que solo nos importa el tamaño flotante RGB ; // ... y muchos otros atributos pueden seguir... }; Cuando existen varias de estas estructuras en la memoria, se colocan de un extremo a otro creando matrices 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, se deben omitir las ubicaciones de memoria que contienen los otros atributos. Si estos atributos no son necesarios, se producirá un uso innecesario de la memoria caché de la CPU. Además, una instrucción SIMD normalmente esperará que los datos con los que operará sean contiguos en la memoria; es posible que también sea necesario alinear los elementos . Al mover la ubicación de la memoria de los datos fuera de la estructura, los datos se pueden organizar mejor para un acceso eficiente en una secuencia y para que las instrucciones SIMD operen una. Una estructura de matrices (SoA), como se muestra a continuación, puede permitir esto.
estructura partícula_t { flotador * x , * y , * z ; byte sin firmar * colorRojo , * colorAzul , * colorVerde ; flotador * tamaño ; }; En lugar de contener los datos en la estructura, solo contiene punteros (ubicaciones de memoria) para los datos. Las deficiencias son que si se van a operar múltiples atributos de un objeto, es posible que ahora estén distantes en la memoria y, por lo tanto, resulten en una pérdida 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 resultar más complicada si, por ejemplo, se añaden y eliminan estructuras.
Para los procesadores de flujo, se recomienda el uso de estructuras. Desde el punto de vista de la aplicación, todos los atributos se pueden definir con cierta flexibilidad. Tomando como referencia las GPU, hay un conjunto de atributos (al menos 16) disponibles. Para cada atributo, la aplicación puede indicar el número 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, permitiendo efectivamente datos entrelazados. Cuando la GPU comienza el procesamiento del flujo, reunirá todos los diversos atributos en un único conjunto de parámetros (normalmente esto parece una estructura o una "variable global mágica"), realiza las operaciones y dispersa los resultados en algún área de memoria para más adelante. 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 implícitamente las dependencias de los datos y al mismo tiempo permite que el tiempo 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 necesaria ] y más eficiente [ cita necesaria ] hasta la fecha para C++ es RaftLib , que permite vincular núcleos de cálculo independientes como un gráfico de flujo de datos utilizando operadores de flujo de C++. Como ejemplo:
#incluye <balsa> #incluye <raftio> #incluye <cstdlib> #incluye <cadena> clase hola : balsa pública :: kernel { público : hola () : balsa :: kernel () { salida . addPort < std :: cadena > ( "0" ); } balsa virtual :: kstatus run () { salida [ "0" ]. push ( std :: string ( "Hola mundo \n " )); balsa de regreso :: parada ; } }; int main ( int argc , char ** argv ) { /** instanciar print kernel **/ raft :: print < std :: string > p ; /** crear una instancia del kernel hola mundo **/ hola hola ; /** crear un objeto de mapa **/ balsa :: mapa m ; /** agregue núcleos al mapa, tanto hola como p se ejecutan simultáneamente **/ m += hola >> p ; /** ejecutar el mapa **/ m . exe (); devolver 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 optimizaciones de acceso a la memoria debido al rendimiento cada vez mayor en comparación con el ancho de banda de la memoria externa de crecimiento relativamente lento. A medida que esta brecha se amplió, se dedicaron grandes cantidades de área del troquel a ocultar las latencias de la memoria. Dado que obtener información y códigos de operación para esas pocas ALU es costoso, se dedica muy poca área del troquel a la maquinaria matemática real (como estimación aproximada, considérelo 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 realmente muy pequeña.
Desde el punto de vista de todo el sistema, los procesadores de flujo suelen existir en un entorno controlado. Las GPU existen en una placa complementaria (esto parece aplicarse también a Imagine). Las CPU continúan haciendo el trabajo de administrar los recursos del sistema, ejecutar aplicaciones y demás.
El procesador de flujo suele estar equipado con un bus de memoria patentado, rápido y eficiente (los interruptores de barra transversal ahora son comunes, en el pasado se han empleado múltiples buses). La cantidad exacta de líneas de memoria depende del rango del mercado. Mientras está escrito esto, todavía existen 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 transversal 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 transversal ligeramente más lenta de 256 bits de ancho. Por el contrario, los procesadores estándar, desde Intel Pentium hasta algunos Athlon 64, tienen sólo un único bus de datos de 64 bits de ancho.
Los patrones de acceso a la memoria son mucho más predecibles. Si bien las matrices existen, su dimensión se fija en la invocación del kernel. Lo que más se asemeja a una dirección indirecta de puntero múltiple es una cadena de dirección indirecta , que sin embargo garantiza que finalmente leerá o escribirá desde un área de memoria específica (dentro de una secuencia).
Debido a la naturaleza SIMD de las unidades de ejecución del procesador de flujo (clústeres ALU), se espera que las operaciones de lectura/escritura se realicen en masa, por lo que las memorias están optimizadas para un alto ancho de banda en lugar de una baja latencia (esta es una diferencia con Rambus y DDR SDRAM , por ejemplo). 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, lo que requiere que solo el 1% de los datos globales se almacenen en la memoria. Aquí es donde vale la pena conocer los temporales y las dependencias del kernel.
Internamente, un procesador de flujo presenta algunos circuitos inteligentes de comunicación y administración, pero lo interesante es el archivo de registro de flujo (SRF). Conceptualmente se trata de una gran caché en la que se almacenan datos de flujo para transferirlos a la memoria externa en masa. Como estructura controlada por software similar a una caché para las distintas ALU , la SRF se comparte entre todos los distintos grupos de ALU. El concepto clave y la innovación realizada aquí con el chip Imagine de Stanford es que el compilador es capaz de automatizar y asignar memoria de una manera óptima, totalmente transparente para el programador. Las dependencias entre las funciones del kernel y los datos se conocen a través del modelo de programación que permite al compilador realizar análisis de flujo y empaquetar de manera ó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 totalmente. Las pruebas realizadas en Stanford demostraron que el compilador hizo un trabajo tan bueno o mejor en la programación de la memoria que si lo ajustaras manualmente con mucho esfuerzo.
Hay pruebas; puede haber muchos grupos porque se supone que la comunicación entre grupos es rara. Sin embargo, internamente, cada clúster puede explotar eficientemente una cantidad mucho menor de ALU porque la comunicación dentro del clúster es común y, por lo tanto, debe ser altamente eficiente.
Para mantener esas ALU recuperadas con datos, cada ALU está equipada con archivos de registros 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 del 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 forma de transmisión), 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 comunicaciones full-duplex, conseguir que funcione una GPU (y posiblemente un procesador de flujo genérico) posiblemente llevará mucho tiempo. Esto significa que suele ser contraproducente utilizarlos para conjuntos de datos pequeños. Debido a que cambiar el kernel es una operación bastante costosa, la arquitectura de flujo también incurre en penalizaciones para flujos pequeños, un comportamiento conocido como efecto de flujo corto .
La canalización es una práctica muy extendida y muy utilizada en procesadores de flujo, y las GPU presentan canalizaciones que superan las 200 etapas. El costo de cambiar la configuración depende de la configuración que se modifica, pero ahora se considera que siempre es costoso. Para evitar esos problemas en varios niveles del proceso, se han implementado muchas técnicas, como "über shaders" y "atlas 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 flujos genéricos.
La mayoría de los lenguajes de programación para procesadores de flujo comienzan con Java, C o C++ y agregan extensiones que proporcionan instrucciones específicas para permitir a los desarrolladores de aplicaciones etiquetar 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.
Ejemplos no comerciales de lenguajes de programación de transmisiones incluyen:
Las implementaciones comerciales son de propósito general o están vinculadas a hardware específico por parte de un proveedor. Ejemplos de lenguajes de propósito general incluyen:
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 un rendimiento mucho menor en general [ se necesita aclaración ] [ cita requerida ] )
Procesamiento continuo del flujo de operadores [ se necesita aclaración ]
Servicios de procesamiento de flujo: