Étudiants responsables de la prise de note : Sophie Kaleba et Mehdi Noël Malamelli

Modèles de programmation distribuée

Pour rappel, dans un système distribué, deux des problèmes fondamentaux à gérer sont la gestion des délais de communication et la tolérance aux pannes.

1. Grands paradigmes de la programmation (dans un système centralisé) :

Paradigme	Abstraction manipulée
Programmation orientée-objet (Smalltalk, Java)	Objets (encapsulent un état)
	méthodes (modifient un état interne)
	Il n’existe pas de notion de classe dans tous les langages objets (cf. modèles à prototypes)
Impératif (Fortran, C)	Variables, procédures, tableaux
Fonctionnelle (Lisp)	Valeurs, fonctions, collections de valeurs
Logique (Prolog)	Prédicats

Dans un contexte fortement concurrentiel (multi-cœurs, par exemple), plusieurs unités de traitement vont en parallèle lire et écrire dans la mémoire. Dans ce contexte, on manipulera des systèmes de verrouillage (sémaphores), des fils d’exécution (threads)…

Cependant, dans ce contexte, il est difficile de ne pas rencontrer de problématiques de condition de course (le résultat du programme sera différent selon l’ordre d’arrivée des constituants du programme, tel qu’un processus par exemple), interblocage (des processus concurrent s’attendent mutuellement, bloquant le bon déroulement du programme), ou famine (un fil d’exécution n’arrive jamais à accéder à la ressource).

Dans un système distribué, on va chercher à adapter les abstractions utilisées dans les systèmes centralisés pour pallier ces problématiques :

• Pour la programmation impérative, on va faire appel à des procédures à distance (RPC). On va également reposer sur le modèle client/serveur. Les abstractions existantes (tableaux) sont adaptées, mais de nouvelles abstractions sont aussi développées : par exemple, l’envoi de messages (MPI, où on va chercher à à déterminer comment découper les messages pour obtenir un parallélisme satisfaisant), ou en utilisant un modèle reposant sur des données distribuées (HPF). L’endroit où sont stockées les données dont on a besoin pourra alors être différent de l’endroit où on va les stocker.

• Pour la programmation fonctionnelle. La parallèlisme en mathématiques est natif et on peut aisément séparer les tâches. Les collections utilisées sont par contre rendues parallèles.

• La programmation orientée-objet va utiliser les mêmes adaptations que la programmation impérative, notamment l’appel de méthodes à distance (comme Java RMI), et la communication entre objets de langages différents (Corba, .NET).

• On peut aussi mentionner la programmation orientée-agent, considérée comme une spécialisation de la programmation orientée-objet. Ce modèle s’appuie les agents comme abstraction. Il permet de mettre en place un système multi-agents (simulation d’un ensemble de comportements) ou sur un modèle d’acteurs (voir le langage Erlang, Akka (adaptation de Java), MapReduce)

2. Exemples d’abstractions distribuées

2.1 MPI (Message Passing Interface)

MPI est une API mettant à disposition un ensemble de fonctions permettant la communication entre processus par le biais de messages. C’est la norme standard utilisée par les super-calculateurs qui nécessitent un modèle efficace pour soutenir leur mode de communication parallèle.

Elle permet l’échange de données sur un ensemble de machines potentiellement hétérogènes et distantes. Plusieurs types de données peuvent être échangés à condition d’avoir été sérialisées.

Plusieurs langages supportent cette norme, notamment C, C++ et Fortran.

Références :

• https://haydn2005.u-bourgogne.fr/dsi-ccub/IMG/pdf/MPI.pdf
• http://devlog.cnrs.fr/_media/jdev2017/atelier_t8ap03_mpi_bases_jdev2017.pdf
• https://fr.wikipedia.org/wiki/Message_Passing_Interface
• https://www-master.ufr-info-p6.jussieu.fr/2012/spip.php?action=acceder_document&arg=315&cle=080a33212fb23ee11ccc351dca4863b2c7f4757d&file=pdf%2Fcours_MPI_fev_2013.pdf

2.2 Mémoire transactionnelle

La mémoire transactionnelle est une technique cherchant à simplifier la programmation concurrente en autorisant un groupe d’instructions load et store à s’exécuter de façon atomique.
Elle va donc définir des blocs d’instructions atomiques, afin de réaliser ou non des transitions après avoir vérifié leur faisabilité.
Cette solution permet de simplifier le code (suppression des verrous), et d’éviter les problèmes généralement posés par la programmation concurrente (interblocage, famine).

Elle repose donc sur 4 grands principes: Atomicité, Consistance, Isolation et Durabilité.

Références:

• http://www.i3s.unice.fr/~jplozi/prog_concurrente_2016/cours/prog_concurrente_4_9Ik28JqP.pdf
• https://en.wikipedia.org/wiki/Transactional_memory

2.3 PGAS (Partitioned Global Adress Space)

Il s’agit d’un modèle de programmation parallèle où la mémoire est partagée et distribuée. L’espace mémoire global est partitionné. Une portion peut être locale à un processus en particulier (on parle d’affinité d’un processus à la mémoire), mais chaque processus dispose aussi de son espace privé.

Cette solution permet de régler le problème de synchronisation d’accès à la mémoire et de régler le problème de condition de course. Il permet par ailleurs d’accéder directement aux données partagées, et de disposer d’un espace mémoire unifié.

UPC (Unified Parallel C) et Titanium (Java) sont des exemples concrets d’utilisation du modèle PGAS.

Références :

• https://en.wikipedia.org/wiki/Partitioned_global_address_space
• http://upc.gwu.edu/tutorials/tutorials_sc2003.pdf
• https://www.osc.edu/sites/osc.edu/files/staff_files/dhudak/pgas-tutorial.pdf
• titanium.cs.berkeley.edu

2.4 OpenMP

OpenMP est une API destinée au calcul parallèle, reposant sur le multithreading en mémoire partagée. Elle est pourvue d’une interface simple et flexible pour développer des programmes parallèles (par exemple, en C/C++. OpenMP utilise différents pragmas). Les threads s’exécutent alors de façon concurrente, le runtime allouant les threads à différents processeurs.

OpenMP peut être utilisé avec MPI. MPI exécute alors du code sur différents noeuds, alors que OpenMP le fait sur différents threads. La section de code destinée à être exécutée de façon parallèle est annotée en conséquence. Par défaut, chaque thread exécute la section de code parallélisée de façon indépendante.

Références :

• https://en.wikipedia.org/wiki/OpenMP
• https://www.openmp.org/wp-content/uploads/OpenMP-API-Specification-5.0.pdf
• https://www.lri.fr/~falcou/teaching/par/OpenMP-cours.pdf

2.5 Modèle d’acteurs

Dans ce modèle, l’acteur est une fonction primitive, utilisé pour la programmation concurrente. Dans ce modèle tout est acteur, et les acteurs communiquent par le biais de messages.

A la réception d’un message, un acteur peut :

• Réaliser un traitement localement
• Envoyer un nombre fini de messages à d’autres acteurs
• Créer un nombre fini de nouveaux acteurs
• Spécifier le comportement à avoir lors de la prochaine réception de message

Cependant, la mémoire n’est pas partagée, et l’on est pas assuré de recevoir un message. Ici, les communications sont asynchrones.

La bibliothèque Java Akka et le langage Erlang sont des exemples d’utilisation du modèle d’acteurs.

Références :

• https://en.wikipedia.org/wiki/Actor_model
• https://akka.io/
• http://www.erlang.org/