Machine de flux de données modulaire binaire

Binary Modular Dataflow Machine ( BMDFM ) est un progiciel qui permet d'exécuter une application en parallèle sur des ordinateurs multiprocesseurs symétriques (SMP) à mémoire partagée en utilisant plusieurs processeurs pour accélérer l'exécution d'applications uniques. BMDFM identifie et exploite automatiquement le parallélisme en raison de la planification statique et principalement dynamique des séquences d'instructions de flux de données dérivées du programme autrefois séquentiel.

Le sous-système de planification dynamique BMDFM effectue une émulation multitraitement symétrique (SMP) d'une machine de flux de données à jetons étiquetés pour fournir la sémantique de flux de données transparente pour les applications. Aucune directive d'exécution parallèle n'est nécessaire.

Les SMP à mémoire partagée parallèle actuels sont des machines complexes, où un grand nombre d'aspects architecturaux doivent être traités simultanément pour atteindre des performances élevées. Les machines SMP courantes récentes pour le calcul technique peuvent avoir de nombreux cœurs étroitement couplés (de bons exemples sont les machines SMP basées sur des processeurs multicœurs d' Intel ( Core ou Xeon ) ou d'IBM ( Power )). Le nombre de cœurs par nœud SMP est prévu pour doubler tous les deux ou trois ans selon les annonces des fabricants d'ordinateurs.

Les processeurs multicœurs sont conçus pour exploiter un parallélisme au niveau des threads, identifié par logiciel. Par conséquent, la tâche la plus difficile est de trouver un moyen efficace d'exploiter la puissance des processeurs multicœurs pour traiter un programme d'application en parallèle. Le paradigme OpenMP existant de parallélisation statique avec une bibliothèque d'exécution fork-join fonctionne plutôt bien pour les calculs réguliers basés sur des tableaux à forte intensité de boucle uniquement, cependant, les méthodes de parallélisation au moment de la compilation sont faibles en général et presque inapplicables pour les applications irrégulières :

• Il existe de nombreuses opérations qui prennent un temps non déterministe, ce qui rend difficile de savoir exactement quand certaines données seront disponibles.
• Une hiérarchie de mémoire avec des caches à plusieurs niveaux présente des latences d’accès à la mémoire imprévisibles.
• En mode multi-utilisateur, les codes d'autres personnes peuvent utiliser des ressources ou ralentir une partie du calcul d'une manière que le compilateur ne peut pas prendre en compte.
• Les optimisations inter-procédurales et inter-conditionnelles au moment de la compilation sont difficiles (très souvent impossibles) car les compilateurs ne peuvent pas déterminer dans quelle direction une condition ira ou ne peuvent pas optimiser sur un appel de fonction.

La technologie BMDFM utilise principalement la planification dynamique pour exploiter le parallélisme d'un programme d'application, ainsi, BMDFM évite les inconvénients mentionnés des méthodes de compilation. BMDFM est un environnement de programmation parallèle pour SMP multi-cœur qui fournit :

• Paradigme de programmation conventionnel ne nécessitant aucune directive pour l'exécution parallèle.
• Exploitation transparente (implicite) du parallélisme de manière naturelle et équilibrée en utilisant automatiquement tous les processeurs multicœurs disponibles dans le système.

BMDFM combine les avantages des principes architecturaux connus dans une architecture hybride unique capable d'exploiter le parallélisme implicite des applications avec une surcharge de planification dynamique négligeable et aucun goulot d'étranglement. Le principe de base du flux de données est principalement utilisé. Le principe du flux de données dit : « Une instruction ou une fonction peut être exécutée dès que tous ses arguments sont prêts. Une machine de flux de données gère les balises pour chaque élément de données au moment de l'exécution. Les données sont marquées avec une balise prête lorsque les données ont été calculées. Les instructions avec des arguments prêts sont exécutées en marquant leurs données de résultat prêtes ».

La principale caractéristique de BMDFM est de fournir un paradigme de programmation conventionnel au plus haut niveau, appelé sémantique de flux de données transparent. Un utilisateur comprend BMDFM comme une machine virtuelle (VM), qui exécute toutes les instructions d'un programme d'application en parallèle, avec tous les mécanismes de parallélisation et de synchronisation entièrement transparents. Les instructions d'un programme d'application sont des opérateurs normaux, dont tout programme à thread unique peut être constitué : elles incluent les affectations de variables, le traitement conditionnel, les boucles, les appels de fonctions, etc.

Supposons que nous ayons le fragment de code ci-dessous :

( setq a ( foo0 i )) # a = foo0 ( i ); ( setq b ( foo1 ( + i 1 ))) # b = foo1 ( i + 1 ); ( setq b ( ++ b )) # b ++ ; ( outf "a = %d " a ) # printf ( "a = %d " , a ); ( outf "b = %d " b ) # printf ( "b = %d " , b );

Les deux premières instructions sont indépendantes, de sorte qu'un moteur de flux de données de BMDFM peut les exécuter sur des processeurs ou des cœurs de processeur différents. Les deux dernières instructions peuvent également être exécutées en parallèle, mais seulement après le calcul de « a » et « b ». Le moteur de flux de données reconnaît automatiquement les dépendances en raison de sa capacité à créer un graphique de flux de données de manière dynamique au moment de l'exécution. De plus, le moteur de flux de données ordonne correctement le flux de sortie pour générer les résultats de manière séquentielle. Ainsi, même après le traitement désordonné, les résultats apparaîtront de manière naturelle.

Supposons que le fragment de code ci-dessus soit désormais imbriqué dans une boucle :

( pour i 1 1 N ( progn # pour ( 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 " a ) # printf ( "a = %d " , a ); ( outf "b = %d " b ) # printf ( "b = %d " , b ); )) # }

Le moteur de flux de données de BMDFM conservera les variables « a » et « b » dans des contextes uniques pour chaque itération. En fait, il s'agit de copies différentes des variables. Une variable de contexte existe jusqu'à ce qu'elle soit référencée par les consommateurs d'instructions. Les contextes ultérieurs non référencés seront récupérés lors de l'exécution. Par conséquent, le moteur de flux de données peut exploiter à la fois le parallélisme local au sein de l'itération et le parallélisme global tout en exécutant plusieurs itérations simultanément.

BMDFM est un environnement de programmation parallèle pratique et un moteur d'exécution efficace pour SMP multicœur en raison de l'unification MIMD de plusieurs paradigmes architecturaux (von-Neumann, SMP et dataflow) :

• Au départ, il s'agit d'un émulateur de flux de données hybride fonctionnant en multithread sur un SMP standard. Le SMP assure MIMD tandis que le flux de données exploite le parallélisme implicite.
• Deuxièmement, il s'agit d'un moteur d'exécution de flux de données multithread hybride contrôlé par une machine virtuelle frontale von-Neumann. Le moteur d'exécution de flux de données exécute des instructions parallèles contextuelles à jetons étiquetés (à l'opposé du paradigme de jointure à fourche restreint) tandis que la machine virtuelle frontale von-Neumann initialise les contextes et alimente le moteur d'exécution de flux de données avec des clusters d'instructions marshalés.
• Troisièmement, il s'agit d'un hybride de parallélisation statique et dynamique. La machine virtuelle frontale von-Neumann tente de diviser statiquement une application en clusters d'instructions marshalées parallèlement tandis que le moteur d'exécution du flux de données complète les méthodes de parallélisation statique de manière dynamique.

BMDFM est destiné à être utilisé dans le rôle de moteur d'exécution parallèle (au lieu de la bibliothèque d'exécution fork-join conventionnelle) capable d'exécuter automatiquement des applications irrégulières en parallèle. En raison de la sémantique de flux de données transparente, BMDFM est une technique de parallélisation simple pour les programmeurs d'applications et, en même temps, une technologie de programmation et de compilation parallèle bien meilleure pour les ordinateurs SMP multi-cœurs.

Le concept de base de BMDFM repose sur un matériel SMP de base, disponible sur le marché. En règle générale, les fournisseurs de SMP fournissent leur propre système d'exploitation (OS) SMP avec une interface UNIX SVR4/POSIX (Linux, HP-UX, SunOS/Solaris, Tru64OSF1, IRIX, AIX, BSD, MacOS, etc.). Au-dessus d'un OS SMP, le moteur d'exécution de flux de données multithread effectue une émulation logicielle de la machine de flux de données. Une telle machine virtuelle dispose d'interfaces avec le langage de la machine virtuelle et avec C, fournissant la sémantique de flux de données transparente pour la programmation conventionnelle.

BMDFM est construit comme un hybride de plusieurs principes architecturaux :

• MIMD (Multiple Instruction Streams, Multiple Data Streams), qui est soutenu par le SMP de base.
• L'exécution parallèle implicite est assurée par l'émulation du flux de données.
• Le principe de calcul de Von-Neumann est bon pour implémenter la machine virtuelle de contrôle frontal.

Un programme d'application (programme séquentiel d'entrée) est traité en trois étapes : réorganisation préliminaire du code (réorganisateur de code), ordonnancement statique des instructions (ordonnanceur statique) et compilation/chargement (compilateur, chargeur). La sortie après les étapes d'ordonnancement statique est un flux à clusters multiples qui alimente le moteur multithread via l'interface conçue de manière à éviter les goulots d'étranglement. Le flux à clusters multiples peut être considéré comme un programme d'entrée compilé divisé en clusters marshalés, dans lesquels toutes les adresses sont résolues et étendues avec des informations de contexte. La division en clusters marshalés permet de les charger de manière multithread. Les informations de contexte permettent de traiter les itérations en parallèle. Le thread d'écoute ordonne le flux de sortie après le traitement désordonné.

Le sous-système de planification dynamique BMDFM est un émulateur SMP efficace de la machine de flux de données à jetons étiquetés. Le pool de mémoire partagée est divisé en trois parties principales : port de mémoire tampon en anneau d'entrée/sortie (IORBP), tampon de données (DB) et file d'attente d'opérations (OQ). La machine virtuelle de contrôle frontale planifie un programme d'application d'entrée de manière statique et place les instructions et les données groupées du programme d'entrée dans l'IORBP. Les processus de service de mémoire tampon en anneau (IORBP PROC) déplacent les données dans la base de données et les instructions dans l'OQ. Les processus de service de file d'attente d'opérations (OQ PROC) marquent les instructions comme prêtes à être exécutées si les données des opérandes requises sont accessibles. Les processus d'exécution (CPU PROC) exécutent les instructions, qui sont marquées comme prêtes et génèrent des données calculées dans la base de données ou vers l'IORBP. De plus, IORBP PROC et OQ PROC sont responsables de la libération de la mémoire après le traitement des contextes. Le contexte est un identifiant unique spécial représentant une copie de données dans différents corps d'itération en fonction de l'architecture du flux de données à jetons étiquetés. Cela permet au planificateur dynamique de gérer plusieurs itérations en parallèle.

S'exécutant sous un système d'exploitation SMP, les processus occuperont tous les processeurs et cœurs de processeur réels disponibles. Afin de permettre à plusieurs processus d'accéder simultanément aux mêmes données, le planificateur dynamique BMDFM verrouille les objets dans le pool de mémoire partagée via des opérations de sémaphore SVR4/POSIX. La politique de verrouillage fournit plusieurs accès en lecture seule et un accès exclusif pour la modification.

Toute machine prenant en charge ANSI C et POSIX ; UNIX System V (SVR4) peut exécuter BMDFM.

BMDFM est fourni en versions multithread complètes pour :

• 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, Gagner-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 ;
• Alpha : Tru64OSF1/64, Linux/64, FreeBSD/64, OpenBSD/64 ;
• IA-64 : HP-UX/32, HP-UX/64, Linux/64, FreeBSD/64 ;
• XeonPhiMIC : Linux/64 ;
• MCST-Elbrouz : 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;
• et une version monothread limitée pour x86 : Win/32.