La máquina de flujo de datos modular binario ( BMDFM ) es un software que permite ejecutar una aplicación en paralelo en computadoras de multiprocesamiento simétrico (SMP) de memoria compartida que utilizan múltiples procesadores para acelerar la ejecución de aplicaciones individuales. BMDFM identifica y explota automáticamente el paralelismo debido a la programación estática y principalmente dinámica de las secuencias de instrucciones de flujo de datos derivadas del programa anteriormente secuencial.
El subsistema de programación dinámica BMDFM realiza una emulación de multiprocesamiento simétrico (SMP) de una máquina de flujo de datos de token etiquetado para proporcionar la semántica de flujo de datos transparente para las aplicaciones. No se necesitan directivas para la ejecución en paralelo.
Fondo
Hoy en día, los multiprocesadores simétricos de memoria compartida (SMP) en paralelo son máquinas complejas, donde una gran cantidad de aspectos arquitectónicos deben abordarse simultáneamente para lograr un alto rendimiento. Las máquinas SMP de productos básicos recientes para la informática técnica pueden tener muchos núcleos estrechamente acoplados (buenos ejemplos son las máquinas SMP basadas en procesadores multinúcleo de Intel ( Pentium ) o IBM ( POWER )). Se prevé que la cantidad de núcleos por nodo SMP se duplique cada pocos años, según los anuncios de los fabricantes de computadoras.
Los procesadores de varios núcleos están destinados a explotar un paralelismo a nivel de subprocesos, identificado por el software. Por lo tanto, la tarea más desafiante es encontrar una manera eficiente de aprovechar la potencia de los procesadores de múltiples núcleos para procesar un programa de aplicación en paralelo. El paradigma OpenMP existente de la paralelización estática con una biblioteca de tiempo de ejecución de unión de bifurcación funciona bastante bien solo para cálculos basados en matrices regulares intensivos en bucles, sin embargo, los métodos de paralelización en tiempo de compilación son débiles en general y casi inaplicables para aplicaciones irregulares:
- Hay muchas operaciones que requieren una cantidad de tiempo no determinista, lo que dificulta saber exactamente cuándo estarán disponibles ciertos datos.
- Una jerarquía de memoria con cachés de varios niveles tiene latencias de acceso a la memoria impredecibles.
- Un modo multiusuario, los códigos de otras personas pueden consumir recursos o ralentizar una parte del cálculo de una manera que el compilador no puede explicar.
- Las optimizaciones entre condicional y entre procedimientos en tiempo de compilación son difíciles (muy a menudo imposibles) porque los compiladores no pueden averiguar en qué dirección irá un condicional o no pueden optimizar en una llamada de función.
Semántica de flujo de datos transparente de BMDFM
Una nueva tecnología BMDFM (Binary Modular Data-Flow Machine) utiliza principalmente la programación dinámica para explotar el paralelismo de un programa de aplicación, por lo que BMDFM evita las desventajas mencionadas de los métodos de tiempo de compilación. [1] [2] BMDFM es un entorno de programación en paralelo para SMP de varios núcleos que proporciona:
- Paradigma de programación convencional que no requiere directivas para la ejecución en paralelo.
- Explotación transparente (implícita) del paralelismo de una manera natural y con carga equilibrada utilizando automáticamente todos los procesadores multinúcleo disponibles en el sistema.
BMDFM combina las ventajas de los principios arquitectónicos conocidos en una única arquitectura híbrida que es capaz de explotar el paralelismo implícito de las aplicaciones con una sobrecarga de programación dinámica insignificante y sin cuellos de botella. Principalmente, se utiliza el principio básico de flujo de datos. El principio del flujo de datos dice: "Una instrucción o una función se puede ejecutar tan pronto como todos sus argumentos estén listos. Una máquina de flujo de datos administra las etiquetas para cada pieza de datos en tiempo de ejecución. Los datos se marcan con la etiqueta lista cuando se han calculado los datos. Instrucciones con los argumentos listos se ejecutan marcando sus datos de resultado listos ".
La característica principal de BMDFM es proporcionar un paradigma de programación convencional en el nivel superior, la denominada semántica de flujo de datos transparente. Un usuario entiende BMDFM como una máquina virtual (VM), que ejecuta todas las declaraciones de un programa de aplicación en paralelo, teniendo todos los mecanismos de sincronización y paralelización totalmente transparentes. Las declaraciones de un programa de aplicación son operadores normales, en los que puede consistir cualquier programa de un solo subproceso; incluyen asignaciones de variables, procesamiento condicional, bucles, llamadas a funciones, etc.
Supongamos que tenemos el fragmento de código que se muestra a continuación:
( setq a ( foo0 i )) # a = foo0 ( i ); ( setq b ( foo1 ( + i 1 ))) # b = foo1 ( i + 1 ); ( setq b ( ++ b )) # b ++ ; ( outf "a =% d \ n " a ) # printf ( "a =% d \ n " , a ); ( outf "b =% d \ n " b ) # printf ( "b =% d \ n " , b );
Las dos primeras declaraciones son independientes, por lo que un motor de flujo de datos de BMDFM puede ejecutarlas en diferentes procesadores o núcleos de procesador. Las dos últimas declaraciones también se pueden ejecutar en paralelo, pero solo después de que se hayan calculado "a" y "b". El motor de flujo de datos reconoce las dependencias automáticamente debido a su capacidad para crear un gráfico de flujo de datos de forma dinámica en tiempo de ejecución. Además, el motor de flujo de datos ordena correctamente el flujo de salida para generar los resultados de forma secuencial. Por lo tanto, incluso después del procesamiento fuera de orden, los resultados aparecerán de forma natural.
Supongamos que el fragmento de código anterior ahora está anidado en un bucle:
( para i 1 1 N ( progn # para ( i = 1 ; i <= N ; i ++ ) { ( setq a ( foo0 i )) # a = foo0 ( i ); ( setq b ( foo1 ( + i 1 ))) # b = foo1 ( i + 1 ); ( setq b ( ++ b )) # b ++ ; ( outf "a =% d \ n " a ) # printf ( "a =% d \ n " , a ); ( outf "b =% d \ n " b ) # printf ( "b =% d \ n " , b ); )) # }
El motor de flujo de datos de BMDFM mantendrá las variables "a" y "b" en contextos únicos para cada iteración. En realidad, son copias diferentes de las variables. Una variable de contexto existe hasta que los consumidores de instrucciones la referencian. Los contextos posteriores no referenciados se recolectarán como basura en tiempo de ejecución. Por lo tanto, el motor de flujo de datos puede aprovechar tanto el paralelismo local dentro de la iteración como el paralelismo global, así como ejecutar múltiples iteraciones simultáneamente.
Arquitectura de BMDFM
El concepto básico de BMDFM se muestra en la siguiente figura. El enfoque propuesto se basa en hardware SMP básico subyacente, que está disponible en el mercado. Normalmente, los proveedores de SMP proporcionan su propio sistema operativo (SO) SMP con una interfaz SVR4 / POSIX UNIX (Linux, HP-UX, SunOS / Solaris, Tru64OSF1, IRIX, AIX, BSD, MacOS, etc.). En la parte superior de un sistema operativo SMP, el motor de tiempo de ejecución de flujo de datos multiproceso realiza una emulación de software de la máquina de flujo de datos. Dicha máquina virtual tiene interfaces con el lenguaje de la máquina virtual y con C, lo que proporciona la semántica transparente del flujo de datos para la programación convencional.
Como puede verse, BMDFM está construido como un híbrido de varios principios arquitectónicos:
- MIMD (Flujos de instrucciones múltiples, flujos de datos múltiples), que se sustenta en SMP básico.
- La ejecución paralela implícita está garantizada por la emulación de flujo de datos.
- El principio computacional de Von-Neumann es bueno para implementar la máquina virtual de control de front-end.
La siguiente figura presenta una vista más detallada de la arquitectura BMDFM:
Un programa de aplicación (programa secuencial de entrada) se procesa en tres etapas: reorganización preliminar del código (reorganizador de código), programación estática de las declaraciones (programador estático) y compilación / carga (compilador, cargador). La salida después de las etapas de programación estática es un flujo de múltiples clústeres que alimenta el motor multiproceso a través de la interfaz diseñada para evitar cuellos de botella. El flujo de múltiples clústeres puede considerarse como un programa de entrada compilado dividido en clústeres ordenados, en los que todas las direcciones se resuelven y amplían con información de contexto. Dividir en clústeres ordenados permite cargarlos de manera múltiple. La información de contexto permite que las iteraciones se procesen en paralelo. El hilo de escucha ordena el flujo de salida después del procesamiento fuera de orden.
El subsistema de programación dinámica BMDFM es un emulador SMP eficiente de la máquina de flujo de datos de tokens etiquetados. El grupo de memoria compartida se divide en tres partes principales: puerto de búfer de anillo de entrada / salida (IORBP), búfer de datos (DB) y cola de operaciones (OQ). La máquina virtual de control de front-end programa un programa de aplicación de entrada de forma estática y coloca instrucciones y datos agrupados del programa de entrada en el IORBP. Los procesos del servicio de búfer de anillo (IORBP PROC) mueven datos a la base de datos y las instrucciones a la OQ. Los procesos del servicio de cola de operaciones (OQ PROC) etiquetan las instrucciones como listas para su ejecución si se puede acceder a los datos de los operandos requeridos. Los procesos de ejecución (CPU PROC) ejecutan instrucciones, que se etiquetan como listas y envían los datos calculados al DB o al IORBP. Además, IORBP PROC y OQ PROC son responsables de liberar memoria después de que se hayan procesado los contextos. El contexto es un identificador único especial que representa una copia de datos dentro de diferentes cuerpos de iteración de acuerdo con la arquitectura de flujo de datos de token etiquetado. Esto permite que el planificador dinámico maneje varias iteraciones en paralelo.
Al ejecutarse en un sistema operativo SMP, los procesos ocuparán todos los procesadores y núcleos de procesadores de máquinas reales disponibles. Para permitir que varios procesos accedan a los mismos datos al mismo tiempo, el programador dinámico BMDFM bloquea objetos en el grupo de memoria compartida a través de operaciones de semáforo SVR4 / POSIX. La política de bloqueo proporciona múltiples accesos de solo lectura y acceso exclusivo para modificaciones.
Plataformas compatibles
Todas las máquinas compatibles con ANSI C y POSIX - UNIX System V (SVR4) pueden ejecutar BMDFM.
BMDFM se proporciona como versiones completas de subprocesos múltiples para:
- x86 : Linux / 32, FreeBSD / 32, OpenBSD / 32, NetBSD / 32, MacOS / 32, SunOS / 32, UnixWare / 32, Minix / 32, Android / 32, Win-Cygwin / 32, Win-UWIN / 32, Win-SFU-SUA / 32;
- x86-64 : Linux / 64, FreeBSD / 64, OpenBSD / 64, NetBSD / 64, MacOS / 64, SunOS / 64, Android / 64, Win-Cygwin / 64;
- VAX : Ultrix / 32;
- Alfa : Tru64OSF1 / 64, Linux / 64, FreeBSD / 64, OpenBSD / 64;
- IA-64 : HP-UX / 32, HP-UX / 64, Linux / 64, FreeBSD / 64;
- XeonPhiMIC : Linux / 64;
- MCST-Elbrus : Linux / 32, Linux / 64;
- PA-RISC : HP-UX / 32, HP-UX / 64, Linux / 32;
- SPARC : SunOS / 32, SunOS / 64, Linux / 32, Linux / 64, FreeBSD / 64, OpenBSD / 64;
- MIPS : IRIX / 32, IRIX / 64, Linux / 32, Linux / 64;
- MIPSel : Linux / 32, Linux / 64, Android / 32, Android / 64;
- PowerPC : AIX / 32, AIX / 64, MacOS / 32, MacOS / 64, Linux / 32, Linux / 64, FreeBSD / 32, FreeBSD / 64;
- PowerPCle : Linux / 32, Linux / 64;
- S / 390 : Linux / 32, Linux / 64;
- M68000 : Linux / 32;
- BRAZO : Linux / 32, Linux / 64, FreeBSD / 64, Android / 32, Android / 64, MacOS / 64;
- ARMbe : Linux / 64;
- RISC-V : Linux / 32, Linux / 64;
- y una versión limitada de un solo subproceso para x86 : Win / 32.
Resumen
Los sistemas de flujo de datos probablemente merecen otra mirada en este momento. La comunidad ha pasado por un ciclo de implementación de hardware compartido-distribuido-compartido desde el pico de la actividad del flujo de datos y parece apropiado aplicar algo de lo aprendido en ese tiempo a los sistemas basados en software.
BMDFM es un entorno de programación paralelo conveniente y un motor de tiempo de ejecución eficiente para SMP multinúcleo debido a la unificación MIMD de varios paradigmas arquitectónicos (von-Neumann, SMP y flujo de datos):
- Al principio, es un emulador de flujo de datos híbrido que se ejecuta de forma múltiple en SMP básico. El SMP asegura MIMD mientras que el flujo de datos explota el paralelismo implícito.
- En segundo lugar, es un motor de tiempo de ejecución de flujo de datos híbrido multiproceso controlado por una VM de front-end de von-Neumann. El motor de tiempo de ejecución de flujo de datos ejecuta instrucciones paralelas contextuales de token etiquetado (opuesto al paradigma de unión de bifurcación restringida) mientras que la VM de front-end de von-Neumann inicializa contextos y alimenta el motor de tiempo de ejecución de flujo de datos con grupos de instrucciones ordenadas.
- En tercer lugar, es un híbrido de paralelización estática y dinámica. La VM de front-end de von-Neumann intenta dividir estáticamente una aplicación en grupos de instrucciones ordenadas en paralelo, mientras que el motor de tiempo de ejecución de flujo de datos complementa los métodos de paralelización estática de forma dinámica.
BMDFM está diseñado para usarse en una función del motor de tiempo de ejecución paralelo (en lugar de la biblioteca de tiempo de ejecución de unión de bifurcación convencional) capaz de ejecutar aplicaciones irregulares automáticamente en paralelo. Debido a la semántica de flujo de datos transparente en la parte superior, BMDFM es una técnica de paralelización simple para programadores de aplicaciones y, al mismo tiempo, es una tecnología de compilación y programación paralela mucho mejor para computadoras SMP de múltiples núcleos.
Ver también
Referencias
- ^ "BMDFM: un entorno de paralelización de tiempo de ejecución de flujo de datos híbrido para multiprocesadores de memoria compartida" . Universidad Técnica de Munich (TUM), Alemania. 25 de febrero de 2006.
- ^ "urn: nbn: de: bvb: 91-diss20060316-1748151609" . URN NBN Resolver para Alemania y Suiza. 22 de marzo de 2006.
enlaces externos
- Página web oficial
- Sitio web oficial , alemán