Máquina de flujo de datos modular binaria

BMDFM ejecutándose en varios sistemas operativos

Linux

Windows 10

macOS

Androide

La Máquina de Flujo de Datos Modular Binaria ( BMDFM ) es un paquete de software que permite ejecutar una aplicación en paralelo en computadoras de procesamiento simétrico multiprocesador (SMP) con memoria compartida, utilizando múltiples procesadores para acelerar la ejecución de aplicaciones individuales. BMDFM identifica y aprovecha automáticamente el paralelismo gracias a la planificación estática y, principalmente, dinámica de las secuencias de instrucciones de flujo de datos derivadas del programa, originalmente secuencial.

El subsistema de planificación dinámica BMDFM realiza una emulación de multiprocesamiento simétrico (SMP) de una máquina de flujo de datos con tokens etiquetados para proporcionar una semántica de flujo de datos transparente para las aplicaciones. No se requieren directivas para la ejecución en paralelo.

Los sistemas SMP de memoria compartida paralela actuales son máquinas complejas, donde se deben abordar simultáneamente numerosos aspectos arquitectónicos para lograr un alto rendimiento. Los sistemas SMP comerciales recientes para computación técnica pueden tener muchos núcleos estrechamente acoplados (buenos ejemplos son los sistemas SMP basados ​​en procesadores multinúcleo de Intel ( Core o Xeon ) o IBM ( Power )). Según los anuncios de los fabricantes de computadoras, se prevé que el número de núcleos por nodo SMP se duplique cada pocos años.

Los procesadores multinúcleo están diseñados para aprovechar el paralelismo a nivel de hilos, identificado por software. Por lo tanto, la tarea más compleja consiste en encontrar una forma eficiente de aprovechar la potencia de los procesadores multinúcleo para procesar un programa de aplicación en paralelo. El paradigma OpenMP existente de paralelización estática con una biblioteca de tiempo de ejecución fork-join funciona bastante bien solo para cálculos regulares basados ​​en matrices con uso intensivo de bucles; sin embargo, los métodos de paralelización en tiempo de compilación son débiles en general y prácticamente inaplicables para aplicaciones irregulares.

• Existen muchas operaciones que requieren un tiempo no determinista, lo que dificulta saber con exactitud cuándo estarán disponibles ciertos datos.
• Una jerarquía de memoria con cachés multinivel presenta latencias de acceso a la memoria impredecibles.
• En el modo multiusuario, el código de otras personas puede consumir recursos o ralentizar parte del cálculo de una manera que el compilador no puede prever.
• Las optimizaciones interprocedimentales y entre condiciones en tiempo de compilación son difíciles (muy a menudo imposibles) porque los compiladores no pueden determinar hacia dónde se dirigirá una condición ni pueden optimizar a través de una llamada a función.

La tecnología BMDFM utiliza principalmente la planificación dinámica para aprovechar el paralelismo de un programa de aplicación, evitando así las desventajas mencionadas de los métodos de tiempo de compilación. ^{[ 1 ] [ 2 ]} BMDFM es un entorno de programación paralela para SMP multinúcleo 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 forma natural y con equilibrio de carga, utilizando automáticamente todos los procesadores multinúcleo disponibles en el sistema.

BMDFM combina las ventajas de principios arquitectónicos conocidos en una única arquitectura híbrida capaz de explotar el paralelismo implícito de las aplicaciones con una sobrecarga de planificación dinámica insignificante y sin cuellos de botella. Principalmente, se utiliza el principio básico de flujo de datos. Este principio establece: "Una instrucción o función puede ejecutarse tan pronto como todos sus argumentos estén listos. Una máquina de flujo de datos gestiona las etiquetas de cada dato en tiempo de ejecución. Los datos se marcan con la etiqueta 'listo' cuando se han procesado. Las instrucciones con argumentos listos se ejecutan marcando sus datos de resultado como listos".

La principal característica de BMDFM es proporcionar un paradigma de programación convencional en el nivel superior, denominado semántica de flujo de datos transparente. El usuario entiende BMDFM como una máquina virtual (VM) que ejecuta todas las instrucciones de un programa de aplicación en paralelo, con mecanismos de paralelización y sincronización totalmente transparentes. Las instrucciones de un programa de aplicación son operadores normales, presentes en cualquier programa de un solo hilo: 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 instrucciones son independientes, por lo que el motor de flujo de datos de BMDFM puede ejecutarlas en distintos procesadores o núcleos de procesador. Las dos últimas instrucciones también pueden ejecutarse en paralelo, pero solo después de que se hayan calculado "a" y "b". El motor de flujo de datos reconoce automáticamente las dependencias gracias a su capacidad para construir un grafo de flujo de datos dinámicamente en tiempo de ejecución. Además, ordena correctamente el flujo de salida para mostrar los resultados de forma secuencial. De este modo, 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, se trata de copias distintas de las variables. Una variable de contexto existe hasta que los consumidores de instrucciones la referencian. Los contextos que no se referencian posteriormente se eliminarán durante la 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, además de ejecutar múltiples iteraciones simultáneamente.

BMDFM es un entorno de programación paralela conveniente y un motor de tiempo de ejecución eficiente para SMP multinúcleo gracias a la unificación MIMD de varios paradigmas arquitectónicos (von-Neumann, SMP y flujo de datos):

• Inicialmente, se trata de un emulador de flujo de datos híbrido que se ejecuta de forma multihilo sobre una arquitectura SMP estándar. La arquitectura SMP garantiza la integridad de datos (MIMD), mientras que el flujo de datos aprovecha el paralelismo implícito.
• En segundo lugar, se trata de un motor de ejecución de flujo de datos híbrido multihilo controlado por una máquina virtual frontal von Neumann. El motor de ejecución de flujo de datos ejecuta instrucciones paralelas contextuales con tokens etiquetados (a diferencia del paradigma restringido de bifurcación y unión), mientras que la máquina virtual frontal von Neumann inicializa los contextos y alimenta al motor de ejecución de flujo de datos con grupos de instrucciones serializadas.
• En tercer lugar, se trata de un sistema híbrido de paralelización estática y dinámica. La máquina virtual de interfaz de von Neumann intenta dividir estáticamente una aplicación en grupos de instrucciones paralelas organizadas, mientras que el motor de ejecución de flujo de datos complementa dinámicamente los métodos de paralelización estática.

BMDFM está diseñado para funcionar como motor de ejecución paralela (en lugar de la biblioteca de ejecución convencional de bifurcación y unión), capaz de ejecutar automáticamente aplicaciones irregulares en paralelo. Gracias a su semántica de flujo de datos transparente, BMDFM es una técnica de paralelización sencilla para programadores de aplicaciones y, al mismo tiempo, una tecnología de programación y compilación paralela mucho mejor para ordenadores SMP multinúcleo.

El concepto básico de BMDFM se basa en hardware SMP estándar disponible en el mercado. Normalmente, los proveedores de SMP ofrecen su propio sistema operativo (SO) SMP con una interfaz SVR4/POSIX UNIX ( Linux , HP-UX , SunOS /Solaris, Tru64 OSF1, IRIX , AIX , BSD , macOS , etc.). Sobre este SO SMP, el motor de ejecución de flujo de datos multihilo realiza una emulación por software de la máquina de flujo de datos. Dicha máquina virtual cuenta con interfaces para el lenguaje de máquina virtual y para C, lo que proporciona la semántica de flujo de datos transparente para la programación convencional.

BMDFM se construye como un híbrido de varios principios arquitectónicos:

• MIMD (Multiple Instruction Streams, Multiple Data Streams), que se sustenta en SMP estándar.
• La emulación del flujo de datos garantiza la ejecución paralela implícita.
• El principio de cálculo de Von Neumann es adecuado para implementar la máquina virtual de control de la interfaz de usuario.

Un programa de aplicación (programa secuencial de entrada) se procesa en tres etapas: reorganización preliminar del código (reorganizador de código), planificación estática de las instrucciones (planificador estático) y compilación/carga (compilador, cargador). El resultado tras las etapas de planificación estática es un flujo de clústeres múltiples que alimenta el motor multihilo a través de una interfaz diseñada para evitar cuellos de botella. Este flujo de clústeres múltiples puede considerarse como un programa de entrada compilado dividido en clústeres serializados, en los que todas las direcciones se resuelven y se amplían con información de contexto. La división en clústeres serializados permite cargarlos de forma multihilo. La información de contexto permite procesar las iteraciones en paralelo. El hilo de escucha ordena el flujo de salida tras el procesamiento fuera de orden.

El subsistema de planificación dinámica BMDFM es un emulador SMP eficiente de la máquina de flujo de datos de token etiquetado. El grupo de memoria compartida se divide en tres partes principales: puerto de búfer circular de entrada/salida (IORBP), búfer de datos (DB) y cola de operaciones (OQ). La máquina virtual de control frontal planifica estáticamente un programa de aplicación de entrada y coloca las instrucciones y los datos agrupados del programa de entrada en el IORBP. Los procesos de servicio del búfer circular (IORBP PROC) mueven los datos al DB y las instrucciones a la OQ. Los procesos de servicio de la cola de operaciones (OQ PROC) marcan las instrucciones como listas para su ejecución si los datos de los operandos requeridos son accesibles. Los procesos de ejecución (CPU PROC) ejecutan las instrucciones marcadas como listas y envían los datos calculados al DB o al IORBP. Además, IORBP PROC y OQ PROC son responsables de liberar la memoria después de que se hayan procesado los contextos. El contexto es un identificador único especial que representa una copia de los 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 gestione varias iteraciones en paralelo.

Al ejecutarse en un sistema operativo multiprocesador (SMP), los procesos ocuparán todos los procesadores y núcleos disponibles de la máquina real. Para permitir que varios procesos accedan a los mismos datos simultáneamente, el planificador dinámico BMDFM bloquea los objetos en el grupo de memoria compartida mediante operaciones de semáforo SVR4/POSIX. La política de bloqueo proporciona acceso de solo lectura múltiple y acceso exclusivo para modificación.

Todas las máquinas compatibles con ANSI C y POSIX ; UNIX System V (SVR4) pueden ejecutar BMDFM.

BMDFM se proporciona en versiones multihilo completas 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 : zOS-USS/32, zOS-USS/64, Linux/32, Linux/64;
• M68000 : Linux/32;
• ARM : Linux/32, Linux/64, FreeBSD/64, Android/32, Android/64, MacOS/64;
• ARMbe : Linux/64;
• RISC-V : Linux/32, Linux/64;
• LoongArch : Linux/64;
• y una versión limitada de un solo hilo para x86 : Win/32.

• Flujo de datos
• Computación paralela
• Multiprocesamiento simétrico

• Sitio web oficial de BMDFM
• Sitio BMDFM en GitHub
• Manual completo de BMDFM
• Vídeo de demostración de BMDFM en YouTube
• Repositorio de GitHub de BMDFM
• Página de descarga de BMDFM en el sitio web oficial de BMDFM.
• Página de descarga de BMDFM en download3k
• Página de descarga de BMDFM en SourceForge