Machines à accès aléatoire parallèle

Parallel Random Access Machines (PRAM)est un modèle considéré pour la plupart des algorithmes parallèles. Ici, plusieurs processeurs sont attachés à un seul bloc de mémoire. Un modèle PRAM contient -

• Un ensemble de types de processeurs similaires.

• Tous les processeurs partagent une unité de mémoire commune. Les processeurs peuvent communiquer entre eux uniquement via la mémoire partagée.

• Une unité d'accès à la mémoire (MAU) connecte les processeurs à la mémoire partagée unique.

Ici, n nombre de processeurs peuvent effectuer des opérations indépendantes sur nnombre de données dans une unité de temps particulière. Cela peut entraîner un accès simultané au même emplacement mémoire par différents processeurs.

Pour résoudre ce problème, les contraintes suivantes ont été appliquées sur le modèle PRAM -

• Exclusive Read Exclusive Write (EREW) - Ici, deux processeurs ne sont pas autorisés à lire ou à écrire dans le même emplacement de mémoire en même temps.

• Exclusive Read Concurrent Write (ERCW) - Ici, deux processeurs ne sont pas autorisés à lire à partir du même emplacement de mémoire en même temps, mais sont autorisés à écrire dans le même emplacement de mémoire en même temps.

• Concurrent Read Exclusive Write (CREW) - Ici, tous les processeurs sont autorisés à lire à partir du même emplacement de mémoire en même temps, mais ne sont pas autorisés à écrire dans le même emplacement de mémoire en même temps.

• Concurrent Read Concurrent Write (CRCW) - Tous les processeurs sont autorisés à lire ou à écrire dans le même emplacement mémoire en même temps.

Il existe de nombreuses méthodes pour implémenter le modèle PRAM, mais les plus importantes sont -

• Modèle de mémoire partagée
• Modèle de transmission de messages
• Modèle parallèle de données

Modèle de mémoire partagée

La mémoire partagée met l'accent sur control parallelism que sur data parallelism. Dans le modèle de mémoire partagée, plusieurs processus s'exécutent sur différents processeurs indépendamment, mais ils partagent un espace mémoire commun. En raison de toute activité du processeur, s'il y a un changement dans un emplacement de mémoire, il est visible par le reste des processeurs.

Comme plusieurs processeurs accèdent au même emplacement mémoire, il peut arriver qu'à un moment donné, plusieurs processeurs accèdent au même emplacement mémoire. Supposons que l'un lit cet emplacement et que l'autre écrive à cet emplacement. Cela peut créer de la confusion. Pour éviter cela, certains mécanismes de contrôle, commelock / semaphore, est mis en œuvre pour garantir l'exclusion mutuelle.

La programmation de la mémoire partagée a été implémentée dans ce qui suit -

• Thread libraries- La bibliothèque de threads autorise plusieurs threads de contrôle qui s'exécutent simultanément dans le même emplacement mémoire. La bibliothèque de threads fournit une interface qui prend en charge le multithreading via une bibliothèque de sous-programmes. Il contient des sous-programmes pour

  • Créer et détruire des threads
  • Planification de l'exécution du thread
  • transmission de données et de messages entre les threads
  • enregistrement et restauration des contextes de thread

Des exemples de bibliothèques de threads incluent: les threads SolarisTM pour Solaris, les threads POSIX tels qu'implémentés sous Linux, les threads Win32 disponibles sous Windows NT et Windows 2000 et les threads JavaTM dans le cadre du kit de développement JavaTM standard (JDK).

• Distributed Shared Memory (DSM) Systems- Les systèmes DSM créent une abstraction de mémoire partagée sur une architecture faiblement couplée afin de mettre en œuvre une programmation de mémoire partagée sans prise en charge matérielle. Ils implémentent des bibliothèques standard et utilisent les fonctionnalités avancées de gestion de la mémoire au niveau de l'utilisateur présentes dans les systèmes d'exploitation modernes. Les exemples incluent Tread Marks System, Munin, IVY, Shasta, Brazos et Cashmere.

• Program Annotation Packages- Ceci est implémenté sur les architectures ayant des caractéristiques d'accès mémoire uniformes. L'exemple le plus notable de packages d'annotations de programmes est OpenMP. OpenMP implémente le parallélisme fonctionnel. Il se concentre principalement sur la parallélisation des boucles.

Le concept de mémoire partagée fournit un contrôle de bas niveau du système de mémoire partagée, mais il a tendance à être fastidieux et erroné. Il est plus applicable à la programmation système qu'à la programmation d'application.

Avantages de la programmation en mémoire partagée

• L'espace d'adressage global offre une approche de programmation conviviale de la mémoire.

• En raison de la proximité de la mémoire avec le processeur, le partage des données entre les processus est rapide et uniforme.

• Il n'est pas nécessaire de spécifier distinctement la communication des données entre les processus.

• La surcharge de communication de processus est négligeable.

• C'est très facile à apprendre.

Inconvénients de la programmation en mémoire partagée

• Ce n'est pas portable.
• La gestion de la localité des données est très difficile.

Modèle de transmission de messages

Le passage de messages est l'approche de programmation parallèle la plus couramment utilisée dans les systèmes de mémoire distribuée. Ici, le programmeur doit déterminer le parallélisme. Dans ce modèle, tous les processeurs ont leur propre unité de mémoire locale et ils échangent des données via un réseau de communication.

Les processeurs utilisent des bibliothèques de transmission de messages pour communiquer entre eux. Outre les données envoyées, le message contient les éléments suivants -

• L'adresse du processeur à partir duquel le message est envoyé;

• Adresse de départ de l'emplacement mémoire des données dans le processeur émetteur;

• Type de données des données d'envoi;

• Taille des données des données d'envoi;

• L'adresse du processeur auquel le message est envoyé;

• Adresse de départ de l'emplacement de mémoire pour les données dans le processeur récepteur.

Les processeurs peuvent communiquer entre eux par l'une des méthodes suivantes:

• Communication point à point
• Communication collective
• Interface de transmission de messages

Communication point à point

La communication point à point est la forme la plus simple de transmission de messages. Ici, un message peut être envoyé du processeur d'envoi à un processeur de réception par l'un des modes de transfert suivants:

• Synchronous mode - Le message suivant n'est envoyé qu'après la réception d'une confirmation que son message précédent a été remis, pour maintenir la séquence du message.

• Asynchronous mode - Pour envoyer le message suivant, la réception de la confirmation de la remise du message précédent n'est pas requise.

Communication collective

La communication collective implique plus de deux processeurs pour la transmission des messages. Les modes suivants permettent des communications collectives -

• Barrier - Le mode barrière est possible si tous les processeurs inclus dans les communications exécutent un bock particulier (appelé barrier block) pour la transmission du message.

• Broadcast - La diffusion est de deux types -

  • One-to-all - Ici, un processeur avec une seule opération envoie le même message à tous les autres processeurs.

  • All-to-all - Ici, tous les processeurs envoient un message à tous les autres processeurs.

Les messages diffusés peuvent être de trois types -

• Personalized - Des messages uniques sont envoyés à tous les autres processeurs de destination.

• Non-personalized - Tous les processeurs de destination reçoivent le même message.

• Reduction - En diffusion de réduction, un processeur du groupe collecte tous les messages de tous les autres processeurs du groupe et les combine en un seul message auquel tous les autres processeurs du groupe peuvent accéder.

Mérites de la transmission de messages

• Fournit un contrôle de bas niveau du parallélisme;
• Il est portable;
• Moins sujet aux erreurs;
• Moins de frais généraux dans la synchronisation parallèle et la distribution des données.

Inconvénients de la transmission de messages

• Par rapport au code à mémoire partagée parallèle, le code de transmission de messages nécessite généralement plus de temps système.

Bibliothèques de transmission de messages

Il existe de nombreuses bibliothèques de transmission de messages. Ici, nous allons discuter de deux des bibliothèques de transmission de messages les plus utilisées -

• Interface de transmission de messages (MPI)
• Machine virtuelle parallèle (PVM)

Interface de transmission de messages (MPI)

Il s'agit d'une norme universelle pour assurer la communication entre tous les processus simultanés dans un système de mémoire distribuée. La plupart des plates-formes informatiques parallèles couramment utilisées fournissent au moins une implémentation d'interface de transmission de messages. Il a été implémenté en tant que collection de fonctions prédéfinies appeléeslibrary et peuvent être appelés à partir de langages tels que C, C ++, Fortran, etc. Les MPI sont à la fois rapides et portables par rapport aux autres bibliothèques de transmission de messages.

Merits of Message Passing Interface

• Fonctionne uniquement sur des architectures de mémoire partagée ou des architectures de mémoire distribuée;

• Chaque processeur a ses propres variables locales;

• Par rapport aux grands ordinateurs à mémoire partagée, les ordinateurs à mémoire distribuée sont moins chers.

Demerits of Message Passing Interface

• D'autres changements de programmation sont nécessaires pour l'algorithme parallèle;
• Parfois difficile à déboguer; et
• Ne fonctionne pas bien dans le réseau de communication entre les nœuds.

Machine virtuelle parallèle (PVM)

PVM est un système de transmission de messages portable, conçu pour connecter des machines hôtes hétérogènes séparées pour former une seule machine virtuelle. Il s'agit d'une seule ressource informatique parallèle gérable. Les grands problèmes de calcul tels que les études de supraconductivité, les simulations de dynamique moléculaire et les algorithmes matriciels peuvent être résolus de manière plus rentable en utilisant la mémoire et la puissance globale de nombreux ordinateurs. Il gère tout le routage des messages, la conversion des données, la planification des tâches dans le réseau des architectures informatiques incompatibles.

Features of PVM

• Très facile à installer et à configurer;
• Plusieurs utilisateurs peuvent utiliser PVM en même temps;
• Un utilisateur peut exécuter plusieurs applications;
• C'est un petit paquet;
• Prend en charge C, C ++, Fortran;
• Pour une exécution donnée d'un programme PVM, les utilisateurs peuvent sélectionner le groupe de machines;
• C'est un modèle de transmission de messages,
• Calcul basé sur les processus;
• Prend en charge l'architecture hétérogène.

Programmation parallèle de données

L'objectif principal du modèle de programmation parallèle de données est d'effectuer simultanément des opérations sur un ensemble de données. L'ensemble de données est organisé en une structure telle qu'un tableau, un hypercube, etc. Les processeurs effectuent des opérations collectivement sur la même structure de données. Chaque tâche est effectuée sur une partition différente de la même structure de données.

Il est restrictif, car tous les algorithmes ne peuvent pas être spécifiés en termes de parallélisme des données. C'est la raison pour laquelle le parallélisme des données n'est pas universel.

Les langages parallèles de données aident à spécifier la décomposition des données et le mappage vers les processeurs. Il comprend également des instructions de distribution de données qui permettent au programmeur d'avoir le contrôle sur les données - par exemple, quelles données iront sur quel processeur - pour réduire la quantité de communication au sein des processeurs.