PARALLEL COMPUTING

Onesime MBULAYI
Doctorant
Machine Learning & Bioinformatics
Email: mbulayi.onesime@unikin.ac.cd

Novembre 2022
Introduction

L’objectif principal du calcul parallèle est d’effectuer des calculs plus rapidement
que ceux qui peuvent être effectués avec un seul processeur en utilisant plusieurs
processeurs simultanément. Le besoin de solutions plus rapides et de résolution
de problèmes de plus grande taille se pose dans une grande variété d’applications.
Ceux-ci incluent la dynamique des fluides, les prévisions météorologiques, la
modélisation et la simulation de grands systèmes, le traitement et l'extraction
d'informations, le traitement d'images, l'intelligence artificielle et
l'automatisation de la fabrication.
Trois facteurs principaux ont contribué à la forte tendance actuelle en faveur du
traitement parallèle.
 Premièrement, le coût du matériel a diminué régulièrement ; il est donc
désormais possible de construire des systèmes dotés de nombreux processeurs
à un coût raisonnable.
Introduction

 Deuxièmement, la technologie des circuits d’intégration à très grande échelle a

progressé au point où il est possible de concevoir des systèmes complexes
nécessitant des millions de transistors sur une seule puce.
 Troisièmement, le temps de cycle plus rapide d'un processeur de type Von-
Neumann semble se rapprocher des limites physiques fondamentales au-delà
desquelles aucune amélioration n'est possible.
Ordinateur parallèle : Un ordinateur parallèle est simplement un ensemble de
processeurs, généralement du même type, interconnectés d'une certaine manière
pour permettre la coordination de leurs activités et l'échange de données.
Calcul parallèle : le calcul parallèle ressemble à l'étude de la conception
d'algorithmes de telle sorte que la complexité temporelle soit minimale. Ainsi, le
facteur de vitesse est pris en compte.
Speed up : Soit C un problème de calcul et n soit la taille d'entrée.
Ts(n)= Complexité temporelle du meilleur algorithme séquentiel.
Tp(n)= Complexité temporelle de l'algorithme parallèle à p processeurs.
Alors speed up S(n,p)=Ts(n)/Tp(n)
Note: Ts(n)≤T1(n), putting n=1
Puisque Ts(n) est le meilleur algorithme séquentiel. T1(n) n’est peut-être pas le
meilleur.
Théorème : Si le processus est séquentiel, l'accélération ne peut pas dépasser le
nombre de processeurs, c'est-à-dire S(n,p) ≤ p, où p est le nombre de processeurs.
Preuve : Nous savons que Ts(n)≤T1(n). Supposons que ce soit faux pour p=1.
Alors S(n,1)>1
i.e., Ts(n)/T1(n)>1
i.e., Ts(n) >T1(n)
mais Ts(n) ≤T1(n)
D'où une contradiction et S(n,p) ≤ p est vrai.
Deux Motivation Parallelisme:

1. Le développement de logiciels parallèles est traditionnellement considéré

comme exigeant du temps et des efforts. Cela peut être largement attribué à la
complexité inhérente à la spécification et à la coordination des tâches
simultanées, au manque d'algorithmes portables, d'environnements
standardisés et de boîtes à outils de développement logiciel. Dans le contexte
du développement rapide des microprocesseurs, on est tenté de s'interroger
sur la nécessité de consacrer des efforts importants à l'exploitation du
parallélisme comme moyen d'accélérer les applications. Après tout, s’il faut
deux ans pour développer une application parallèle, période pendant laquelle
la plate-forme matérielle et/ou logicielle sous-jacente est devenue obsolète,
l’effort de développement est clairement vain.
Motivating Parallelism:

2. Cependant, il existe certaines tendances indubitables dans la conception

matérielle, qui indiquent que les architectures monoprocesseurs (ou
implicitement parallèles) pourraient ne pas être en mesure de maintenir le
rythme des augmentations de performances réalisables à l'avenir. Ceci est le
résultat d'un manque de parallélisme implicite ainsi que d'autres goulots
d'étranglement tels que le chemin des données et la mémoire. Dans le même
temps, les interfaces matérielles standardisées ont réduit le délai d'exécution
entre le développement d'un microprocesseur et une machine parallèle basée
sur le microprocesseur.
En outre, des progrès considérables ont été réalisés dans la standardisation des
environnements de programmation afin de garantir un cycle de vie plus long pour
les applications parallèles. Tous ces éléments présentent des arguments
convaincants en faveur des plates-formes informatiques parallèles.
La mémoire et la vitesse du disque

La vitesse globale de calcul est déterminée non seulement par la vitesse du

processeur, mais également par la capacité du système de mémoire à lui
transmettre des données. Alors que les fréquences d'horloge des processeurs haut
de gamme ont augmenté d'environ 40 % par an au cours de la dernière décennie,
les temps d'accès à la DRAM ne se sont améliorés qu'à un rythme d'environ 10 %
par an au cours de cette période. Associé à l'augmentation du nombre
d'instructions exécutées par cycle d'horloge, cet écart entre la vitesse du
processeur et la mémoire présente un énorme goulot d'étranglement en termes de
performances. Cette inadéquation croissante entre la vitesse du processeur et la
latence de la DRAM est généralement comblée par une hiérarchie de dispositifs de
mémoire successivement plus rapides, appelés caches, qui s'appuient sur la
localité de référence des données pour offrir des performances système de
mémoire plus élevées.
L’argument de la mémoire et de la vitesse du disque

En plus de la latence, la bande passante effective nette entre la DRAM et le

processeur pose d'autres problèmes pour des cadences de calcul soutenues. Les
performances globales du système de mémoire sont déterminées par la fraction
des demandes de mémoire totales qui peuvent être satisfaites à partir du cache.
Les plates-formes parallèles offrent généralement de meilleures performances du
système de mémoire car elles fournissent (i) des caches agrégés plus grands et (ii)
une bande passante globale plus élevée. au système de mémoire (tous deux
généralement linéaires en termes de nombre de processeurs). De plus, les
principes qui sont au cœur des algorithmes parallèles, à savoir la localité de
référence des données, se prêtent également aux algorithmes série respectueux du
cache. Cet argument peut être étendu aux disques sur lesquels des plates-formes
parallèles peuvent être utilisées pour obtenir une bande passante globale élevée
vers le stockage secondaire.
La communication de données :

À mesure que l'infrastructure réseau évolue, la vision d'utiliser Internet comme un

vaste environnement informatique hétérogène parallèle/distribué a commencé à
prendre forme. De nombreuses applications se prêtent naturellement à de tels
paradigmes informatiques. Certaines des applications les plus impressionnantes
du calcul massivement parallèle se situent dans le contexte de plates-formes
distribuées à grande échelle. Le projet SETI (Search for Extra Terrestrial
Intelligence) utilise la puissance d'un grand nombre d'ordinateurs domestiques
pour analyser les signaux électromagnétiques provenant de l'espace. D'autres
efforts de ce type ont tenté de factoriser des entiers extrêmement grands et de
résoudre de grands problèmes d'optimisation discrète.
Dans de nombreuses applications, il existe des contraintes quant à l'emplacement
des données et/ou des ressources sur Internet.
La communication de données :

Un exemple d’une telle application est l’extraction de grands ensembles de

données commerciales distribués sur un réseau à bande passante relativement
faible. Dans de telles applications, même si la puissance de calcul est disponible
pour accomplir la tâche requise sans recourir au calcul parallèle, il est impossible
de collecter les données à un emplacement central. Dans ces cas, la motivation en
faveur du parallélisme ne vient pas seulement du besoin de ressources
informatiques, mais également de l’infaisabilité ou du caractère indésirable
d’approches alternatives (centralisées).
1. Portée du calcul parallèle :

L'informatique parallèle a eu un impact considérable sur une variété de domaines

allant des simulations informatiques pour les applications scientifiques et
techniques aux applications commerciales dans l'exploration de données et le
traitement des transactions. Les avantages financiers du parallélisme, associés aux
exigences de performances des applications, présentent des arguments
convaincants en faveur du calcul parallèle. Nous présentons un petit échantillon
des diverses applications du calcul parallèle.
1. Applications en ingénierie et conception

L'informatique parallèle a traditionnellement été utilisée avec beaucoup de succès

dans la conception de profils aérodynamiques (optimisation de la portance, de la
traînée, de la stabilité), des moteurs à combustion interne (optimisation de la
répartition de la charge, de la combustion), des circuits à grande vitesse
(dispositions pour les retards et les effets capacitifs et inductifs) et structures
(optimisation de l’intégrité structurelle, paramètres de conception, coût, etc.), entre
autres. Plus récemment, la conception de systèmes microélectromécaniques et
nanoélectromécaniques (MEMS et NEMS) a attiré une attention considérable.
Alors que la plupart des applications en ingénierie et en conception posent des
problèmes à plusieurs échelles spatiales et temporelles et des phénomènes
physiques couplés, dans le cas de la conception MEMS/NEMS, ces problèmes
sont particulièrement aigus.
1. Applications en ingénierie et conception

Ici, nous traitons souvent d'un mélange de phénomènes quantiques, de

dynamique moléculaire et de modèles stochastiques et continus avec des
processus physiques tels que la conduction, la convection, le rayonnement et la
mécanique structurelle, le tout dans un seul système. Cela présente de formidables
défis pour la modélisation géométrique, la modélisation mathématique et le
développement d'algorithmes, le tout dans le contexte d'ordinateurs parallèles.
D'autres applications en ingénierie et en conception se concentrent sur
l'optimisation d'une variété de processus. Des ordinateurs parallèles ont été
utilisés pour résoudre divers problèmes d’optimisation discrets et continus. Des
algorithmes tels que Simplex, Interior Point Method pour l'optimisation linéaire et
Branchand-bound, et la programmation génétique pour l'optimisation discrète ont
été efficacement parallélisés et sont fréquemment utilisés.
2. Applications scientifiques

Ces dernières années ont été marquées par une révolution dans les applications du
calcul scientifique à haute performance. Le séquençage du génome humain par le
Consortium international de séquençage du génome humain et Celera, Inc. a
ouvert de nouvelles frontières passionnantes en bioinformatique. La
caractérisation fonctionnelle et structurelle des gènes et des protéines promet de
comprendre et d’influencer fondamentalement les processus biologiques.
L’analyse de séquences biologiques en vue de développer de nouveaux
médicaments et remèdes contre des maladies et des pathologies nécessite des
algorithmes innovants ainsi qu’une puissance de calcul à grande échelle. En effet,
certaines des technologies de calcul parallèle les plus récentes sont spécifiquement
destinées aux applications en bioinformatique.
2. Applications scientifiques
Les progrès en physique et en chimie computationnelles se sont concentrés sur la
compréhension de processus allant des phénomènes quantiques aux structures
macromoléculaires. Celles-ci ont abouti à la conception de nouveaux matériaux, à la
compréhension des voies chimiques et à des processus plus efficaces. Les applications en
astrophysique ont exploré l'évolution des galaxies, les processus thermonucléaires et
l’analyse d’ensembles de données extrêmement volumineux provenant de télescopes. La
modélisation météorologique, la prospection minière, la prévision des inondations, etc.,
reposent en grande partie sur des ordinateurs parallèles et ont un impact très important sur
la vie quotidienne.
La bioinformatique et l'astrophysique présentent également certains des problèmes les plus
difficiles en ce qui concerne l'analyse d'ensembles de données extrêmement volumineux. Les
bases de données sur les protéines et les gènes (telles que PDB, SwissProt, ENTREZ et NDB)
ainsi que les ensembles de données Sky Survey (tels que Sloan Digital Sky Surveys)
représentent certains des plus grands ensembles de données scientifiques. L’analyse efficace
de ces ensembles de données nécessite une puissance de calcul considérable et constitue la
clé de découvertes scientifiques significatives.
3. Applications commerciales
Avec l'utilisation généralisée du Web et du contenu statique et dynamique associé,
l'accent est de plus en plus mis sur des serveurs rentables capables de fournir des
performances évolutives. Les plates-formes parallèles allant des multiprocesseurs
aux clusters Linux sont fréquemment utilisées comme serveurs Web et de bases de
données. Par exemple, les jours de gros volume, les grandes maisons de courtage
de Wall Street gèrent des centaines de milliers de sessions utilisateur simultanées
et des millions de commandes. Plateformes telles que IBM SP
des supercalculateurs et des serveurs Sun Ultra HPC alimentent ces sites critiques
pour l'entreprise. Bien que peu visibles, certains des plus grands réseaux de calcul
intensif sont hébergés à Wall Street.
La disponibilité de données sur les transactions à grande échelle a également
suscité un intérêt considérable pour l’exploration et l’analyse des données afin
d’optimiser les décisions commerciales et marketing.
Le volume considérable et la nature géographiquement répartie de ces données
nécessitent l'utilisation d'algorithmes parallèles efficaces pour résoudre des
problèmes tels que l'exploration de règles d'association, le regroupement, la
classification et l'analyse de séries chronologiques.
4. Applications dans les systèmes informatiques
À mesure que les systèmes informatiques deviennent omniprésents et que les
calculs se propagent sur le réseau, les problèmes de traitement parallèle
s’enracinent dans diverses applications. En sécurité informatique, la détection des
intrusions constitue un défi de taille. Dans le cas de la détection d'intrusion sur le
réseau, les données sont collectées sur des sites distribués et doivent être analysées
rapidement pour signaler une intrusion. L’impossibilité de collecter ces données à
un emplacement central pour analyse nécessite des algorithmes parallèles et
distribués efficaces. Dans le domaine de la cryptographie, certaines des
applications les plus spectaculaires du calcul parallèle sur Internet se sont
concentrées sur la factorisation d’entiers extrêmement grands.
Les systèmes embarqués s'appuient de plus en plus sur des algorithmes de
contrôle distribué pour accomplir diverses tâches. Une automobile moderne se
compose de dizaines de processeurs communiquant pour effectuer des tâches
complexes visant à optimiser la maniabilité et les performances.
Dans de tels systèmes, les algorithmes traditionnels parallèles et distribués pour la
sélection des leaders, l'ensemble indépendant maximal, etc., sont fréquemment
utilisés.
Alors que l'informatique parallèle s'est traditionnellement limitée aux plates-
formes dotées d'éléments de calcul et de réseau performants dans lesquels les
pannes et les erreurs ne jouent pas un rôle significatif, il existe des enseignements
précieux qui s'étendent aux calculs sur des environnements ad hoc, mobiles ou
défectueux.
I. PLAN

Chapitre 1 : Analyse comparative des systèmes parallèles et concurrents

Chapitre 2 : Concevoir des algorithmes parallèles

Chapitre 3 : Identifier un problème parallélisable

Chapitre 4 : Utilisation des modules threading et concurrent.futures

Chapitre 5 : Utilisation de plusieurs processus et pools de processus

I. Introduction

 Le calcul parallèle est un type de calcul dans lequel de nombreux

calculs ou processus sont effectués simultanément.
 Les grands problèmes peuvent souvent être divisés en plus petits,
qui peuvent ensuite être résolus en même temps. Il existe
plusieurs formes différentes de calcul parallèle : parallélisme au
niveau des bits, au niveau des instructions, des données et des
tâches.
Chap I: Parallélisme vs concurrence

 Parallélisme: utiliser plusieurs processeurs pour accélérer un

calcul.
 Concurrence : permettre à plusieurs tâches de se poursuivre sans
attendre l'un pour l'autre.
Différents objectifs qui partagent des aspects de mise en œuvre.
L'informatique scientifique se soucie davantage du parallélisme.
La concurrence est rarement nécessaire.
Programmation parallèle

 Décomposition de la tâche complète en tâches indépendantes les

sous-tâches et le flux de données entre elles.
 Répartition des sous-tâches sur les processeurs minimiser le
temps total d’exécution.
 Pour les clusters : répartition des données sur les nœuds
minimiser le temps de communication.
 Pour les multiprocesseurs : optimisation de l'accès mémoire
modèles minimisant les temps d’attente.
 Synchronisation des processus individuels.
Des difficultés

Exactitude :
 Vérifier que les sous-tâches sont bien indépendantes.
 Rendre les modèles de synchronisation sans blocage.
 Clusters : vérification des modèles de communication.
Efficacité:
 Attribuer des charges de travail égales à tous les processeurs.
 Prise en compte du calcul et de la communication.
 Optimisation pour un ordinateur parallèle spécifique.
Bibliographies
1. Pourquoi utiliser la programmation parallèle ?
Depuis que les systèmes informatiques ont évolué, ils ont commencé à fournir des
mécanismes qui nous permettent d'exécuter des éléments indépendants d'un
programme spécifique en parallèle les uns avec les autres, améliorant ainsi la
réponse et la performance générale. De plus, nous pouvons facilement vérifier que
les machines sont équipées de plus de processeurs et ceux-ci avec beaucoup plus
de cœurs. Alors pourquoi ne pas profiter de cette architecture ?
La programmation parallèle est une réalité dans tous les contextes de
développement de systèmes, depuis les téléphones intelligents et les tablettes
jusqu'à l'informatique intensive dans les centres de recherche. Une base solide en
programmation parallèle permettra à un développeur d'optimiser les
performances d'une application. Cela se traduit par une amélioration de
l'expérience utilisateur ainsi que par une consommation de ressources
informatiques, prenant ainsi moins de temps de traitement pour
l'accomplissement de tâches complexes.
À titre d'exemple de parallélisme, imaginons un scénario dans lequel une
application qui, entre autres tâches, sélectionne des informations dans une base de
données, et cette base de données a une taille considérable. Considérez également
que l'application est séquentielle, dans laquelle les tâches doivent être exécutées
les unes après les autres dans un ordre logique. Lorsqu'un utilisateur demande
des données, le reste du système sera bloqué jusqu'à ce que le retour des données
ne soit pas terminé. Cependant, en utilisant la programmation parallèle, nous
pourrons créer un nouveau travailleur qui cherchera des informations dans cette
base de données sans bloquer d'autres fonctions de l'application, améliorant ainsi
son utilisation.
Explorer les formes courantes de parallélisation
Il existe une certaine confusion lorsque l'on tente de définir les principales formes
de mise en parallèle systèmes. Il est courant de trouver des cotations sur des
systèmes parallèles et concurrents comme si les deux signifiaient la même chose.
Il existe néanmoins de légères différences entre eux. Dans la programmation
simultanée, nous avons un scénario dans lequel un programme envoie plusieurs
travailleurs et ces travailleurs se disputent pour utiliser le processeur pour
exécuter une tâche. L'étape à laquelle survient le conflit est contrôlée par le
planificateur CPU, dont la fonction est de définir quel travailleur est apte à utiliser
la ressource à un moment précis. Dans la plupart des cas, le planificateur du
processeur exécute la tâche de ratissage des processus si rapidement que nous
pourrions avoir l'impression d'un pseudo-parallélisme. La programmation
concurrente est donc une abstraction de la programmation parallèle.
Les systèmes simultanés se disputent le même processeur pour exécuter des
tâches.
Le diagramme suivant montre un schéma de programme concurrent
La programmation parallèle peut être définie comme une approche dans laquelle
les données du programme créent des travailleurs pour exécuter des tâches
spécifiques simultanément dans un environnement multicœur sans avoir besoin
de concurrence entre eux pour accéder à un processeur.
Les systèmes parallèles exécutent des tâches simultanément.
La figure suivante montre le concept de systèmes parallèles :
La programmation distribuée vise la possibilité de partager les traitements en
échangeant des données via des messages entre machines (nœuds) de calcul,
qui sont physiquement séparés. La programmation distribuée devient de plus en
plus populaire pour de nombreuses raisons : ils sont explorés comme suit :
Tolérance aux pannes : le système étant décentralisé, nous pouvons répartir le
traitement sur différentes machines d'un réseau, et ainsi effectuer une
maintenance individuelle de machines spécifiques sans affecter le fonctionnement
du système dans son ensemble.
• Évolutivité horizontale : Nous pouvons augmenter la capacité de traitement
dans les systèmes distribués en général. Nous pouvons relier de nouveaux
équipements sans avoir besoin d’interrompre l’exécution des applications. On
peut dire que c'est moins cher et plus simple par rapport à l'évolutivité verticale.
 La programmation distribuée vise la possibilité de partager les traitements en
échangeant des données via des messages entre machines (nœuds) de calcul,
qui sont physiquement séparés. La programmation distribuée devient de plus
en plus populaire pour de nombreuses raisons : ils sont explorés comme suit :
 Tolérance aux pannes : le système étant décentralisé, nous pouvons répartir le
traitement sur différentes machines d'un réseau, et ainsi effectuer une
maintenance individuelle de machines spécifiques sans affecter le
fonctionnement du système dans son ensemble.
 Évolutivité horizontale : Nous pouvons augmenter la capacité de traitement
dans les systèmes distribués en général. Nous pouvons relier de nouveaux
équipements sans avoir besoin d’interrompre l’exécution des applications. On
peut dire que c'est moins cher et plus simple par rapport à l'évolutivité
verticale.
 Cloud computing : Avec la réduction des coûts du matériel, nous avons besoin
de la croissance de ce type d'entreprise où nous pouvons disposer d'énormes
parcs de machines agissant de manière coopérative et exécutant des
programmes de manière transparente pour leurs utilisateurs.: Avec la réduction
des coûts du matériel, nous avons besoin de la croissance de ce type
d'entreprise où nous pouvons disposer d'énormes parcs de machines agissant
de manière coopérative et exécutant des programmes de manière transparente
pour leurs utilisateurs.

Les systèmes distribués exécutent des tâches au sein de nœuds physiquement séparés.
La figure suivante montre un schéma de système distribué :
3. Communiquer en programmation parallèle
Dans la programmation parallèle, les travailleurs envoyés pour effectuer une tâche
doivent souvent établir une communication afin qu’il puisse y avoir une
coopération pour résoudre un problème.
Dans la plupart des cas, cette communication est établie de telle manière que les
données puissent être échangées entre les travailleurs. Il existe deux formes de
communication plus connues en matière de programmation parallèle : l'état
partagé et la transmission de messages. Dans les sections suivantes, une brève
description des deux sera présentée.
Etat partagé
L’État partagé est l’une des formes de communication les plus connues parmi les
travailleurs. L'état partagé semble simple à utiliser mais comporte de nombreux
pièges car une opération non valide effectuée sur la ressource partagée par l'un
des processus affectera tous les autres, produisant ainsi de mauvais résultats. Cela
rend également impossible la distribution du programme entre plusieurs
machines pour des raisons évidentes.
Pour illustrer cela, nous utiliserons un cas réel. Supposons que vous soyez client
d’une banque spécifique et que cette banque n’ait qu’un seul caissier. Lorsque
vous vous rendez à la banque, vous devez faire la queue et attendre votre chance.
Une fois dans la file d'attente, vous remarquez qu'un seul client à la fois peut
utiliser le caissier et qu'il serait impossible pour le caissier de s'occuper de deux
clients simultanément sans risquer de commettre des erreurs. L'informatique
fournit des moyens d'accéder aux données de manière contrôlée, et il existe
plusieurs techniques, telles que le mutex.
Mutex peut être compris comme une variable de processus spéciale qui indique le niveau de
disponibilité pour accéder aux données. Autrement dit, dans notre exemple réel, le client a
un numéro, et à un moment précis, ce numéro sera activé et le caissier sera disponible
exclusivement pour ce client. A la fin du processus, ceci le client libérera la caisse pour le
client suivant, et ainsi de suite.
Il existe des cas dans lesquels les données ont une valeur constante dans une variable pendant
l'exécution du programme et les données sont partagées uniquement à des fins de lecture. Ainsi, le
contrôle d’accès n’est pas nécessaire car il ne présentera jamais de problèmes d’intégrité.
Messages Passing
La transmission de messages (Message passing) est utilisée lorsque nous visons à
éviter les problèmes de contrôle d’accès aux données et de synchronisation
provenant de l’état partagé. La transmission de messages consiste en un
mécanisme d'échange de messages dans les processus en cours d'exécution. Il est
très couramment utilisé chaque fois que nous développons des programmes à
architecture distribuée, où les échanges de messages au sein du réseau dans
lesquels ils sont placés sont nécessaires. Des langages comme Erlang, par exemple,
utilisent ce modèle pour implémenter la communication dans son architecture
parallèle. Une fois les données copiées à chaque échange de messages, il est
impossible que des problèmes surviennent en termes de concurrence d'accès. Bien
que l’utilisation de la mémoire semble être plus élevée que dans l’état de mémoire
partagée, l’utilisation de ce modèle présente des avantages. Ils sont les suivants :
Avantages à l’utilisation de ce modèle. Ils sont les suivants :
 Absence de concurrence en matière d’accès aux données
 Les messages peuvent être échangés localement (processus divers) ou dans des
environnements distribués
 Cela rend moins probable l'apparition de problèmes d'évolutivité et permet
l'interopérabilité des différents systèmes.
 En général, il est facile à maintenir selon les programmeurs
Problèmes de programmation parallèle
Il existe des problèmes classiques auxquels les courageux guerriers du clavier peuvent être
confrontés lorsqu'ils se battent dans les pays où habitent les fantômes de la programmation
parallèle. Beaucoup de ces problèmes surviennent plus souvent lorsque des programmeurs
inexpérimentés utilisent des travailleurs combinés à un état partagé. Certaines de ces
questions seront décrites dans les sections suivantes.
Deadlock
Deadlock (blocage ou Impasse) est une situation dans laquelle deux travailleurs ou plus
attendent indéfiniment la libération d'une ressource, qui est bloquée par un travailleur du
même groupe pour une raison quelconque. Pour une meilleure compréhension, nous
utiliserons un autre cas réel. Imaginez la banque dont l'entrée a une porte tournante. Le client
A se dirige sur le côté, ce qui lui permettra d'entrer dans la banque, tandis que le client B
tente de sortir de la banque en utilisant le côté entrée de cette porte tournante afin que les
deux clients soient coincés en forçant la porte mais ne se dirigeant nulle part. Cette situation
serait hilarante dans la vraie vie mais tragique en programmation.
Le blocage est un phénomène dans lequel les processus attendent une condition pour libérer leurs
tâches, mais cette condition ne se produira jamais.
Starvation
Il s'agit d'un problème dont les effets secondaires sont causés par le ratissage
injuste d'un ou plusieurs processus qui prennent beaucoup plus de temps pour
exécuter une tâche. Imaginez un groupe de processus, A, qui exécute des tâches
lourdes et a la priorité sur le processeur de données. Imaginez maintenant qu'un
processus A avec une priorité élevée consomme constamment le processeur,
tandis qu'un processus B de priorité inférieure n'en a jamais l'occasion. Par
conséquent, on peut dire que le processus B manque de cycles CPU.
Starvation est causée par des politiques de classement des processus mal ajustées.
Race conditions
Lorsque le résultat d'un processus dépend d'une séquence de faits, et que cette
séquence est cassé en raison du manque de mécanismes de synchronisation, nous
sommes confrontés à des conditions de concurrence. Ils résultent de problèmes
extrêmement difficiles à filtrer dans des systèmes plus importants. Par exemple,
un couple possède un compte joint ; le solde initial avant opérations est 100 $. Le
tableau suivant montre le cas normal, dans lequel il existe des mécanismes de
protection et l’enchaînement des faits attendus, ainsi que le résultat :
Dans le tableau suivant, le scénario problématique est présenté. Supposons que le
compte ne dispose pas de mécanismes de synchronisation et que l'ordre des
opérations ne soit pas celui attendu.

Il existe une incohérence notable dans le résultat final en raison du manque inattendu de
synchronisation dans la séquence des opérations. L'une des caractéristiques de la
programmation parallèle est le non-déterminisme. Il est impossible de prévoir le moment où
deux ouvriers se présenteront, ni même lequel d'entre eux se présentera en premier. Les
mécanismes de synchronisation sont donc essentiels.
Le non-déterminisme, s'il est combiné à l'absence de mécanismes de synchronisation, peut
entraîner des problèmes de concurrence critique.
Les Outils de programmation parallèle avec Python
Le langage Python, créé par Guido Van Rossum, est un langage multi-paradigmes
et langue polyvalente. Il a été largement accepté dans le monde entier en raison de
sa puissance, de sa simplicité et de son entretien facile. On l'appelle aussi la langue
qui a des piles incluses. Il existe une large gamme de modules pour rendre son
utilisation plus fluide. Dans la programmation parallèle, Python possède des
modules intégrés et externes qui simplifient la mise en œuvre.
Le module Threading en Python
Le module de thread Python offre une couche d'abstraction au module _thread,
qui est un module de niveau inférieur. Il fournit des fonctions qui aident le
programmeur dans la tâche difficile de développer des systèmes parallèles basés
sur des threads. Les documents officiels du module de threading peuvent être
trouvés sur Search — Python 3.11.5 documentation
Le module multiprocessing Python
Le module multiprocessing vise à fournir une API simple pour l'utilisation du
parallélisme basé sur les processus. Ce module est similaire au module threading,
qui simplifie les alternances entre les processus sans difficultés majeures.
L'approche basée sur les processus est très populaire au sein de la communauté
des utilisateurs de Python car elle constitue une alternative aux réponses aux
questions sur l'utilisation des threads CPU-Bound et du GIL présents dans
Python. Les documents officiels du module multitraitement peuvent être trouvés
sur
http://docs.python.org/3/library/multiprocessing.html
Le module Python parallèle est externe et propose une API riche pour la création
de systèmes parallèles et distribués utilisant l'approche processus. Ce module
promet d'être léger et facile à installer, et s'intègre à d'autres programmes Python.
Le module Python parallèle peut être trouvé à l'adresse
The parallel Python module is external and offers a rich API for the creation of
parallel and distributed systems making use of the processes approach. This
module promises to be light and easy to install, and integrates with other Python
programs. The parallel Python module can be found at http://parallelpython.com
Parmi certaines fonctionnalités, nous pouvons souligner les suivantes :
 Détection automatique de la configuration optimale
 Le fait qu'un certain nombre de processus de travail peuvent être modifiés
pendant l'exécution
 Equilibrage de charge dynamique
 Tolérance aux pannes
 Découverte automatique des ressources informatiques
Celeri – une file d'attente de tâches distribuée
Celery est un excellent module Python utilisé pour créer des systèmes distribués et
doté d'une excellente documentation. Il utilise au moins trois types d'approches
différents pour exécuter des tâches sous forme simultanée : multiprocessing,
Eventlet et Gevent. Ce travail concentrera cependant les efforts sur l’utilisation de
l’approche multiprocessing. Aussi, le lien entre les uns et les autres est une
question de configuration, et il reste une étude pour que le lecteur puisse établir
des comparaisons avec ses propres expériences. Le module Celery peut être
obtenu sur la page officielle du projet à l'adresse http://celeryproject.org
Python GIL
GIL est un mécanisme utilisé dans l'implémentation du Python standard, connu sous le nom
de CPython, pour éviter les bytecodes exécutés simultanément par différents threads.
L’existence de GIL en Python suscite de vives discussions parmi les utilisateurs de ce
langage. GIL a été choisi pour protéger la mémoire interne utilisée par l'interpréteur
Cpython, qui n'implémente pas de mécanismes de synchronisation pour les accès
concurrents des threads. Dans tous les cas, GIL pose un problème lorsque nous décidons
d'utiliser des threads, et ceux-ci ont tendance à être liés au processeur. Les threads d'E/S, par
exemple, sortent du champ d'application de GIL. Peut-être que le mécanisme apporte plus
d’avantages à l’évolution de Python que de mal. Évidemment, on ne peut pas considérer
uniquement la vitesse comme un seul argument pour déterminer si quelque chose est bon ou
non.
Il existe des cas dans lesquels l'approche de l'utilisation de processus pour des tâches axée
sur la transmission de messages apporte de meilleures relations entre maintenabilité,
évolutivité et performances. Même ainsi, il existe des cas dans lesquels il y aura un réel
besoin de threads, qui seraient soumis à GIL.
Dans ces cas-là, il est possible d’écrire des morceaux de code sous forme
d’extensions en langage C et de les intégrer dans le programme Python. Il existe
donc des alternatives ; c'est au développeur d'analyser la réelle nécessité. Alors se
pose la question : GIL, d’une manière générale, est-il un méchant ? Il est important
de rappeler que l'équipe PyPy travaille sur une implémentation STM afin de
supprimer GIL de Python. Pour plus de détails sur le projet, visitez http://
pypy.org/tmdonate.html
Summary
Dans ce chapitre, nous avons appris quelques concepts de programmation
parallèle et découvert certains modèles, leurs avantages et leurs inconvénients.
Certains des problèmes et problèmes potentiels liés à la réflexion sur le
parallélisme ont été présentés dans de brèves explications. Nous avons également
eu une brève introduction à certains modules Python, intégrés et externes, qui
facilitent la vie du développeur lors de la construction de systèmes parallèles.
Dans le prochain chapitre, nous étudierons quelques techniques pour concevoir
des algorithmes parallèles.
Chapitre 2 : Concevoir des algorithmes
parallèles
Introduction
La conception d’algorithmes parallèles ne se réduit pas facilement à de simples
recettes. Cela nécessite plutôt le type de pensée intégrative que l'on appelle
communément « créativité ». Cependant, cela peut bénéficier d'une approche
méthodique qui maximise l'éventail des options envisagées, qui fournit des
mécanismes pour évaluer les alternatives et qui réduit les coûts. de revenir sur de
mauvais choix. Nous décrivons une telle approche et illustrons son application à
une série de problèmes. Notre objectif est de proposer un cadre dans lequel la
conception d’algorithmes parallèles peut être explorée. Ce faisant, nous espérons
que vous développerez votre intuition quant à ce qui constitue un bon algorithme
parallèle.
Après avoir étudié ce chapitre, vous devriez être capable de concevoir des
algorithmes parallèles simples de manière méthodique et de reconnaître les
défauts de conception qui compromettent l'efficacité ou l'évolutivité.
Vous devez être capable de partitionner les calculs, en utilisant à la fois des
techniques de décomposition de domaine et fonctionnelles, et savoir reconnaître et
mettre en œuvre des structures de communication locales et globales, statiques et
dynamiques, structurées et non structurées, et synchrones et asynchrones. Vous
devez également être capable d'utiliser l'agglomération comme moyen de réduire
les coûts de communication et de mise en œuvre et devez être familier avec une
gamme de stratégies d'équilibrage de charge.
2.1 Conception méthodique
La plupart des problèmes de programmation ont plusieurs solutions parallèles. La
meilleure solution peut différer de celle suggérée par les algorithmes séquentiels
existants. La méthodologie de conception que nous décrivons vise à favoriser une
approche exploratoire de la conception dans laquelle les problèmes indépendants
de la machine, tels que la concurrence, sont pris en compte dès le début et les
aspects de conception spécifiques à la machine sont retardés jusque tard dans le
processus de conception. Cette méthodologie structure le processus de conception
en quatre étapes distinctes : cloisonnement, communication, agglomération et
cartographie. (L'acronyme PCAM peut servir de rappel utile de cette structure.)
Dans les deux premières étapes, nous nous concentrons sur la concurrence et
l'évolutivité et cherchons à découvrir des algorithmes présentant ces qualités. Aux
troisième et quatrième étapes, l’attention se porte sur la localité et sur d’autres
questions liées à la performance. Les quatre étapes sont illustrées dans la figure 2.1
et peuvent être résumées comme suit :
 Partitionnement. Le calcul à effectuer et les données exploitées par ce calcul sont
décomposés en petites tâches. Les problèmes pratiques tels que le nombre de processeurs
dans l'ordinateur cible sont ignorés et l'attention se concentre sur la reconnaissance des
opportunités d'exécution parallèle.
 Communications. La communication requise pour coordonner l'exécution des tâches est
déterminée et les structures et algorithmes de communication appropriés sont définis.
 Agglomération. Les structures de tâches et de communication définies au cours des deux
premières étapes d'une conception sont évaluées en fonction des exigences de
performance et des coûts de mise en œuvre. Si nécessaire, les tâches sont combinées en
tâches plus vastes pour améliorer les performances ou réduire les coûts de
développement.
 Cartographie. Chaque tâche est attribuée à un processeur de manière à tenter de satisfaire
les objectifs concurrents consistant à maximiser l'utilisation du processeur et à minimiser
les coûts de communication. Le mappage peut être spécifié de manière statique ou
déterminé au moment de l'exécution par des algorithmes d'équilibrage de charge.
Le résultat de ce processus de conception peut être un programme qui crée et détruit des
tâches de manière dynamique, en utilisant des techniques d'équilibrage de charge pour
contrôler le mappage des tâches aux processeurs. Alternativement, il peut s'agir d'un
programme SPMD qui crée exactement une tâche par processeur. Le même processus de
découverte d'algorithmes s'applique dans les deux cas, bien que si l'objectif est de produire
un programme SPMD, les problèmes associés à la cartographie sont intégrés dans la phase
d'agglomération de la conception.
La conception d'algorithmes est présentée ici comme une activité séquentielle. En pratique,
cependant, il s’agit d’un processus très parallèle, dans lequel de nombreuses préoccupations
sont prises en compte simultanément. De plus, même si nous cherchons à éviter les retours
en arrière, l'évaluation d'une conception partielle ou complète peut nécessiter des
modifications des décisions de conception prises lors des étapes précédentes.
Dans les lignes qui suivent nous présentons un examen détaillé des quatre étapes du
processus de conception. réalistes.
2.2 Partitionnement
L'étape de partitionnement d'une conception vise à exposer les opportunités
d'exécution parallèle. Par conséquent, l’accent est mis sur la définition d’un grand
nombre de petites tâches afin d’obtenir ce que l’on appelle une décomposition fine
d’un problème. Tout comme le sable fin se coule plus facilement qu’un tas de
briques, une décomposition à grain fin offre la plus grande flexibilité en termes
d’algorithmes parallèles potentiels. Lors des étapes de conception ultérieures,
l'évaluation des exigences de communication, de l'architecture cible ou des
problèmes d'ingénierie logicielle peut nous conduire à renoncer aux opportunités
d'exécution parallèle identifiées à ce stade. Une bonne partition divise en petits
morceaux à la fois le calcul associé à un problème et les données sur lesquelles ce
calcul opère. Lors de la conception d'une partition, les programmeurs se
concentrent généralement d'abord sur les données associées à un problème, puis
déterminent une partition appropriée pour les données et enfin déterminent
comment associer le calcul aux données.
Cette technique de partitionnement est appelée décomposition de domaine. L'approche
alternative consistant à décomposer d'abord le calcul à effectuer puis à traiter les données est
appelée décomposition fonctionnelle. Ce sont des techniques complémentaires qui peuvent
être appliquées à différentes composantes d’un même problème ou même appliquées au
même problème pour obtenir des algorithmes parallèles alternatifs.
Dans cette première étape d’une conception, nous cherchons à éviter la réplication des
calculs et des données ; c'est-à-dire que nous cherchons à définir des tâches qui divisent à la
fois le calcul et les données en ensembles disjoints. Comme la granularité, c’est un aspect de
la conception sur lequel nous reviendrons peut-être plus tard. Il peut être intéressant de
répliquer les calculs ou les données si cela nous permet de réduire les besoins en
communication.
2.2.1 Décomposition du domaine
Dans l'approche de décomposition de domaine pour le partitionnement des problèmes, nous
cherchons d'abord à décomposer les données associées à un problème. Si possible, nous
divisons ces données en petits morceaux de taille à peu près égale. Ensuite, nous
partitionnons le calcul à effectuer, généralement en associant chaque opération aux données
sur lesquelles elle opère. Ce partitionnement génère un certain nombre de tâches, chacune
comprenant des données et un ensemble d'opérations sur ces données. Une opération peut
nécessiter des données provenant de plusieurs tâches. Dans ce cas, une communication est
nécessaire pour déplacer les données entre les tâches. Cette exigence est abordée dans la
phase suivante du processus de conception. Les données décomposées peuvent être l'entrée
du programme, la sortie calculée par le programme ou des valeurs intermédiaires
maintenues par le programme. Différentes partitions peuvent être possibles, basées sur
différentes structures de données. Les bonnes règles empiriques consistent à se concentrer
d’abord sur la structure de données la plus grande ou sur la structure de données la plus
fréquemment consultée.
2.2.2 Décomposition fonctionnelle
La décomposition fonctionnelle représente une manière différente et complémentaire de
penser les problèmes. Dans cette approche, l’accent est initialement mis sur le calcul à
effectuer plutôt que sur les données manipulées par le calcul. Si nous parvenons à diviser ce
calcul en tâches disjointes, nous examinons les exigences en matière de données de ces
tâches. Ces exigences en matière de données peuvent être disjointes, auquel cas la partition
est complète. Alternativement, ils peuvent se chevaucher de manière significative, auquel cas
une communication considérable sera nécessaire pour éviter la réplication des données. C’est
souvent le signe qu’une approche de décomposition de domaine devrait plutôt être
envisagée. Alors que la décomposition de domaine constitue la base de la plupart des
algorithmes parallèles, la décomposition fonctionnelle est précieuse en tant que manière
différente d’appréhender les problèmes. Pour cette seule raison, il convient d’en tenir compte
lors de l’exploration d’algorithmes parallèles possibles. Un focus sur les calculs qui doivent
être réalisées peuvent parfois révéler la structure d'un problème, et donc des opportunités
d'optimisation, qui ne seraient pas évidentes à partir d'une seule étude des données.
Exemple: Arbre de recherche à la recherche de nœuds qui correspondent à des « solutions ».
une décomposition fonctionnelle qui divise non seulement le calcul à effectuer mais
également le code qui effectue ce calcul est susceptible de réduire la complexité de la
conception globale. C'est souvent le cas dans les modèles informatiques de systèmes
complexes, qui peuvent être structurés comme des collections de modèles plus simples
connectés via des interfaces. Par exemple, une simulation du climat terrestre peut
comprendre des composants représentant l'atmosphère, l'océan, l'hydrologie, la glace, les
sources de dioxyde de carbone, etc. Bien que chaque composant puisse être plus
naturellement parallélisé en utilisant des techniques de décomposition de domaine,
l'algorithme parallèle dans son ensemble est plus simple si le système est d'abord décomposé
à l'aide de techniques de décomposition fonctionnelle, même si ce processus ne produit pas
un grand nombre de tâches .
une décomposition fonctionnelle qui divise non seulement le calcul à effectuer mais
également le code qui effectue ce calcul est susceptible de réduire la complexité de la
conception globale. C'est souvent le cas dans les modèles informatiques de systèmes
complexes, qui peuvent être structurés comme des collections de modèles plus simples
connectés via des interfaces. Par exemple, une simulation du climat terrestre peut
comprendre des composants représentant l'atmosphère, l'océan, l'hydrologie, la glace, les
sources de dioxyde de carbone, etc. Bien que chaque composant puisse être plus
naturellement parallélisé en utilisant des techniques de décomposition de domaine,
l'algorithme parallèle dans son ensemble est plus simple si le système est d'abord décomposé
à l'aide de techniques de décomposition fonctionnelle, même si ce processus ne produit pas
un grand nombre de tâches .
2.2.3 Liste de contrôle de conception de partitionnement(Partitioning Design Checklist)

La phase de partitionnement d'une conception doit produire une ou plusieurs

décompositions possibles d'un problème. Avant de procéder à l’évaluation des
exigences de communication, nous utilisons la liste de contrôle suivante pour nous
assurer que la conception ne présente aucun défaut évident. D’une manière
générale, il convient de répondre par l’affirmative à toutes ces questions.
1. Votre partition définit-elle au moins un ordre de grandeur de tâches en plus
qu'il n'y a de processeurs dans votre ordinateur cible ? Sinon, vous disposez de
peu de flexibilité dans les étapes de conception ultérieures.
2. Votre partition évite-t-elle les besoins de calcul et de stockage redondants ?
Dans le cas contraire, l’algorithme résultant risque de ne pas être évolutif pour
traiter de gros problèmes.
3. Les tâches sont-elles de taille comparable ? Dans le cas contraire, il peut être
difficile d’attribuer à chaque processeur une quantité de travail égale.
4. Le nombre de tâches évolue-t-il avec la taille du problème ? Idéalement, une
augmentation de la taille du problème devrait augmenter le nombre de tâches plutôt que
la taille des tâches individuelles. Si ce n'est pas le cas, votre algorithme parallèle risque de
ne pas être en mesure de résoudre des problèmes plus importants lorsque plus des
processeurs sont disponibles.
5. Avez-vous identifié plusieurs partitions alternatives ? Vous pouvez maximiser la
flexibilité lors des étapes de conception ultérieures en envisageant dès maintenant des
alternatives. N'oubliez pas d'étudier à la fois les décompositions de domaine et
fonctionnelles.
Les réponses à ces questions peuvent suggérer que, malgré une réflexion approfondie lors de
cette étape de conception et des suivantes, nous avons une « mauvaise » conception. Dans
cette situation, il est risqué de simplement poursuivre la mise en œuvre. Nous devons utiliser
les techniques d'évaluation des performances pour déterminer si la conception répond à nos
objectifs de performance malgré ses lacunes apparentes. Particulièrement dans les
applications scientifiques et techniques, où le problème à résoudre peut impliquer une
simulation d'un processus physique complexe, les approximations et les techniques
numériques utilisées pour développer la simulation peuvent fortement influencer la facilité
de mise en œuvre parallèle.
Summary( partionnement)
Lorsque vous êtes confronté à un problème complexe, la première chose à faire est de
décomposer le problème afin d’en identifier les parties qui peuvent être traitées
indépendamment. En général, les parties parallélisables d’une solution sont constituées de
morceaux qui peuvent être divisés et distribués pour être traités par différents opérateurs. La
technique de division et de conquête consiste à diviser le domaine de manière récursive
jusqu'à ce qu'une unité indivisible du problème complet soit trouvée et résolue. Les
algorithmes de tri, tels que le tri par fusion et le tri rapide, peuvent être résolus en utilisant
cette approche. Le diagramme suivant montre l'application d'un tri par fusion dans un
vecteur de six éléments, rendant visible la technique diviser pour mieux régner :
2.3 Communications
Les tâches générées par une partition sont destinées à s'exécuter concurremment mais ne
peuvent, en général, s'exécuter indépendamment. Le calcul à effectuer dans une tâche
nécessitera généralement des données associées à une autre tâche. Les données doivent
ensuite être transférées entre les tâches afin de permettre au calcul de se poursuivre. Ce flux
d'informations est spécifié dans la phase de communication d'une conception.
Rappelons du chapitre 1 que dans notre modèle de programmation, nous conceptualisons un
besoin de communication entre deux tâches comme un canal reliant les tâches, sur lequel une
tâche peut envoyer des messages et dont l'autre peut recevoir. Ainsi, la communication
associée à un algorithme peut être spécifiée en deux phases. Premièrement, nous définissons
une structure de canaux qui relie, directement ou indirectement, les tâches qui nécessitent
des données (consommateurs) aux tâches qui possèdent ces données (producteurs).
Deuxièmement, nous spécifions les messages qui doivent être envoyés et reçus sur ces
canaux. En fonction de notre éventuelle technologie de mise en œuvre, il se peut que nous ne
créions pas réellement ces canaux lors du codage de l'algorithme. Par exemple, dans un
langage de données parallèles, nous spécifions simplement les opérations dataparallèles et
les distributions de données
Néanmoins, penser en termes de tâches et de canaux nous aide à réfléchir quantitativement aux
problèmes locaux et aux coûts de communication. La définition d'un canal implique un coût intellectuel et
l'envoi d'un message implique un coût physique. Nous évitons ainsi d’introduire des canaux et des
opérations de communication inutiles. De plus, nous cherchons à optimiser les performances en
répartissant les opérations de communication sur de nombreuses tâches et en organisant les opérations de
communication de manière à permettre une exécution simultanée. Dans les problèmes de décomposition
de domaine, les exigences de communication peuvent être difficiles à déterminer. Rappelons que cette
stratégie produit des tâches en partitionnant d'abord les structures de données en sous-ensembles
disjoints, puis en associant à chaque donnée les opérations qui opèrent uniquement sur cette donnée.
Cette partie de la conception est généralement simple. Cependant, certaines opérations nécessitant des
données provenant de plusieurs tâches subsistent généralement. La communication est alors nécessaire
pour gérer le transfert de données nécessaire à la réalisation de ces tâches. Organiser cette communication
de manière efficace peut être un défi. Même des décompositions simples peuvent avoir des structures de
communication complexes. En revanche, les exigences de communication dans les algorithmes parallèles
obtenus par décomposition fonctionnelle sont souvent simples : elles correspondent au flux de données
entre les tâches.
Néanmoins, penser en termes de tâches et de canaux nous aide à réfléchir quantitativement aux
problèmes locaux et aux coûts de communication. La définition d'un canal implique un coût intellectuel et
l'envoi d'un message implique un coût physique. Nous évitons ainsi d’introduire des canaux et des
opérations de communication inutiles. De plus, nous cherchons à optimiser les performances en
répartissant les opérations de communication sur de nombreuses tâches et en organisant les opérations de
communication de manière à permettre une exécution simultanée. Dans les problèmes de décomposition
de domaine, les exigences de communication peuvent être difficiles à déterminer. Rappelons que cette
stratégie produit des tâches en partitionnant d'abord les structures de données en sous-ensembles
disjoints, puis en associant à chaque donnée les opérations qui opèrent uniquement sur cette donnée.
Cette partie de la conception est généralement simple. Cependant, certaines opérations nécessitant des
données provenant de plusieurs tâches subsistent généralement. La communication est alors nécessaire
pour gérer le transfert de données nécessaire à la réalisation de ces tâches. Organiser cette communication
de manière efficace peut être un défi. Même des décompositions simples peuvent avoir des structures de
communication complexes. En revanche, les exigences de communication dans les algorithmes parallèles
obtenus par décomposition fonctionnelle sont souvent simples : elles correspondent au flux de données
entre les tâches.
Dans la discussion suivante, nous utilisons une variété d'exemples pour montrer comment les exigences
de communication sont identifiées et comment les structures de canaux et les opérations de
communication sont introduites pour satisfaire ces exigences. Pour plus de clarté dans l'exposé, nous
catégorisons les modèles de communication selon quatre axes vaguement orthogonaux : local/global,
structuré/non structuré, statique/dynamique et synchrone/asynchrone.
 En communication locale, chaque tâche communique avec un petit ensemble d'autres tâches (ses «
voisines ») ; en revanche, la communication globale nécessite que chaque tâche communique avec de
nombreuses tâches.
 Dans une communication structurée, une tâche et ses voisines forment une structure régulière,
comme un arbre ou une grille ; en revanche, les réseaux de communication non structurés peuvent
être des graphiques arbitraires.
 Dans une communication statique, l'identité des partenaires de communication ne change pas dans le
temps ; en revanche, l'identité des partenaires de communication dans des structures de
communication dynamiques peut être déterminée par des données calculées au moment de
l'exécution et peut être très variable.
 Dans une communication synchrone, les producteurs et les consommateurs s'exécutent de manière
coordonnée, les couples producteurs/consommateurs coopérant dans les opérations de transfert de
données ; en revanche, la communication asynchrone peut nécessiter qu'un consommateur obtienne
des données sans la coopération du producteur.
2.4 Agglomération
Au cours des deux premières étapes du processus de conception, nous avons divisé le calcul à effectuer en
un ensemble de tâches et introduit la communication pour fournir les données requises par ces tâches.
L’algorithme résultant est encore abstrait dans le sens où il n’est pas spécialisé pour une exécution efficace
sur un ordinateur parallèle particulier. En fait, il peut s'avérer très inefficace si, par exemple, il crée
beaucoup plus de tâches qu'il n'y a de processeurs sur l'ordinateur cible et que cet ordinateur n'est pas
conçu pour une exécution efficace de petites tâches.
Dans la troisième étape, l'agglomération, on passe de l'abstrait au concret. Nous revisitons les décisions
prises lors des phases de partitionnement et de communication en vue d'obtenir un algorithme qui
s'exécutera efficacement sur une classe d'ordinateurs parallèles. En particulier, nous examinons s'il est
utile de combiner, ou d'agglomérer, les tâches identifiées par la phase de partitionnement, de manière à
fournir un plus petit nombre de tâches, chacune de plus grande taille.
Le nombre de tâches générées par la phase d'agglomération, bien que réduit, peut néanmoins être
supérieur au nombre de processeurs. Dans ce cas, notre conception reste quelque peu abstraite, puisque
les problèmes liés au mappage des tâches sur les processeurs restent non résolus. Alternativement, on
peut choisir lors de la phase d'agglomération de réduire le nombre de tâches à exactement une par
processeur. Nous pourrions le faire, par exemple, parce que notre ordinateur parallèle cible ou notre
environnement de développement de programmes nécessite un programme SPMD. Dans ce cas, notre
conception est déjà en grande partie terminée, puisqu’en définissant P tâches qui s’exécuteront sur P
processeurs, nous avons également abordé le problème de mappage. Dans cette section, nous nous
concentrons sur les problèmes généraux qui surviennent lors de l’augmentation de la granularité des
tâches.
Les problèmes spécifiques liés à la génération de programmes SPMD sont abordés dans la section 2.5.
Trois objectifs parfois contradictoires guident les décisions concernant l'agglomération et la réplication :
réduire les coûts de communication en augmentant la granularité du calcul et de la communication,
conserver la flexibilité en ce qui concerne les décisions d'évolutivité et de mappage, et réduire les coûts
d'ingénierie logicielle. Ces objectifs sont discutés dans les trois sous-sections suivantes.
Le nombre de tâches générées par la phase d'agglomération, bien que réduit, peut néanmoins être
supérieur au nombre de processeurs. Dans ce cas, notre conception reste quelque peu abstraite, puisque
les problèmes liés au mappage des tâches sur les processeurs restent non résolus. Alternativement, on
peut choisir lors de la phase d'agglomération de réduire le nombre de tâches à exactement une par
processeur. Nous pourrions le faire, par exemple, parce que notre ordinateur parallèle cible ou notre
environnement de développement de programmes nécessite un programme SPMD. Dans ce cas, notre
conception est déjà en grande partie terminée, puisqu’en définissant P tâches qui s’exécuteront sur P
processeurs, nous avons également abordé le problème de mappage. Dans cette section, nous nous
concentrons sur les problèmes généraux qui surviennent lors de l’augmentation de la granularité des
tâches.
Les problèmes spécifiques liés à la génération de programmes SPMD sont abordés dans la section 2.5.
Trois objectifs parfois contradictoires guident les décisions concernant l'agglomération et la réplication :
réduire les coûts de communication en augmentant la granularité du calcul et de la communication,
conserver la flexibilité en ce qui concerne les décisions d'évolutivité et de mappage, et réduire les coûts
d'ingénierie logicielle. Ces objectifs sont discutés dans les trois sous-sections suivantes.
2.4.1 Augmentation de la granularité
Dans la phase de partitionnement du processus de conception, nos efforts se concentrent sur la définition
du plus grand nombre de tâches possible. Il s’agit d’une discipline utile car elle nous oblige à considérer
un large éventail de possibilités d’exécution parallèle. Nous notons cependant que définir un grand
nombre de tâches à granularité fine ne produit pas nécessairement un algorithme parallèle efficace.
L’un des problèmes critiques qui influencent les performances parallèles est celui des coûts de
communication. Sur la plupart des ordinateurs parallèles, nous devons arrêter de calculer pour envoyer et
recevoir des messages. Parce que nous préférons généralement utiliser l'informatique, nous pouvons
améliorer les performances en réduisant le temps passé à communiquer. De toute évidence, cette
amélioration des performances peut être obtenue en envoyant moins de données. De manière peut-être
moins évidente, cela peut également être réalisé en utilisant moins de messages, même si nous envoyons
la même quantité de données. En effet, chaque communication entraîne non seulement un coût
proportionnel à la quantité de données transférées mais également un coût de démarrage fixe.
En plus des coûts de communication, nous devrons peut-être nous préoccuper des coûts de création de
tâches.
2.5 Cartographie
Dans la quatrième et dernière étape du processus de conception d’algorithmes parallèles, nous spécifions
où chaque tâche doit être exécutée. Ce problème de mappage ne se pose pas sur les monoprocesseurs ou
sur les ordinateurs à mémoire partagée qui assurent la planification automatique des tâches. Dans ces
ordinateurs, un ensemble de tâches et les exigences de communication associées constituent une
spécification suffisante pour un algorithme parallèle ; on peut compter sur les mécanismes du système
d'exploitation ou du matériel pour planifier des tâches exécutables sur les processeurs disponibles.
Malheureusement, les mécanismes de cartographie à usage général doivent encore être développés pour
les ordinateurs parallèles évolutifs. En général, la cartographie reste un problème difficile qui doit être
explicitement abordé lors de la conception d’algorithmes parallèles.
Notre objectif dans le développement d’algorithmes de mappage est normalement de minimiser le temps
d’exécution total. Nous utilisons deux stratégies pour atteindre cet objectif :
1. Nous plaçons des tâches capables de s'exécuter simultanément sur différents processeurs, afin
d'améliorer la concurrence.
2. Nous plaçons les tâches qui communiquent fréquemment sur le même processeur, afin d'augmenter la
localité.
De toute évidence, ces deux stratégies entreront parfois en conflit, auquel cas notre conception impliquera
des compromis. De plus, les limitations de ressources peuvent restreindre le nombre de tâches pouvant
être confiées à un seul processeur.
Décomposition des données
L'un des moyens de paralléliser un problème consiste à décomposer les données.
Imaginer une situation dans laquelle la tâche consiste à multiplier une matrice 2 x
2, que nous appellerons Matrice A, par une valeur scalaire de 4. Dans un système
séquentiel, on effectuera chaque opération de multiplication l'une après l'autre,
générant le résultat final à la fin de toutes les instructions. Selon la taille de la
matrice A, la solution séquentielle du problème peut prendre du temps.
Cependant, lorsque la décomposition des données est appliquée, nous pouvons
imaginer un scénario dans lequel la matrice A est divisée en morceaux, et ces
morceaux sont associés aux travailleurs qui traitent les données reçues de manière
parallèle. Le schéma suivant illustre le concept de décomposition de données
appliqué à l'exemple d'une matrice 2 x 2 multipliée par une valeur scalaire :
Traitement et cartographie
Le nombre de Processeurs n’est pas toujours suffisant pour résoudre un problème
spécifique en une seule étape. Les techniques de décomposition sont donc
nécessaires. Cependant, les techniques de décomposition ne doivent pas être
appliquées arbitrairement ; il existe des facteurs qui peuvent influencer les
performances de la solution.
Après avoir décomposé des données ou des tâches, la question que nous devons
nous poser est : « Comment répartir la charge de traitement entre les travailleurs pour
obtenir de bonnes performances ? » Il n’est pas facile de répondre à cette question, car
tout dépend du problème étudié.
Fondamentalement, nous pourrions mentionner deux étapes importantes lors de
la définition de la cartographie des processus :
 Identifier les tâches indépendantes
 Identifier les tâches qui nécessitent un échange de données
Identifier les tâches indépendantes
L'identification de tâches indépendantes dans un système nous permet de répartir
les tâches entre différents processeurs, car ces tâches ne nécessitent pas une
communication constante. Comme il n'est pas nécessaire de localiser les données,
les tâches peuvent être exécutées sur différents processeur sans affecter l'exécution
des autres tâches.
Identifier les tâches qui nécessitent un échange de données
Regrouper les tâches qui établissent une communication constante chez un seul
processeur peut améliorer les performances. Cela est vrai lorsqu'il y a une charge
importante de communication de données, car cela peut aider à réduire la
surcharge liée à l'échange d'informations au sein des tâches.
Équilibre de charge
Une caractéristique pertinente dans une solution parallèle est la manière dont les
unités de travail sont réparties sur différentes ressources informatiques. Plus nous
répartissons les tâches entre les différents processeurs, plus nous augmentons la
granularité de la communication. En revanche, plus nous regroupons de tâches dans un
seul processeur, plus nous réduisons les frais généraux associés à la communication.
Nous pouvons néanmoins augmenter l’inactivité, c’est-à-dire la puissance de
calcul inutilisée. L'oisiveté n'est pas agréable en programmation parallèle. De plus,
l'augmentation de l'emplacement réduit la flexibilité de la solution concernant la
capacité d'augmenter la puissance de calcul en ajoutant simplement plus
d'équipements. Dans une architecture basée sur les messages (low data location),
il est simple d'ajouter plus de machines au cluster ou à la grille, ce qui augmente
sa puissance de traitement sans même interrompre le fonctionnement du système.
Chapitre 2 : Concevoir des algorithmes
parallèles
Chap 3: Identifying a Parallelizable Problem
The previous chapter presented some of the different ways in which we can think
about a problem in terms of parallelism. Now we will analyze some specific
problems that will be useful in guiding us throughout the implementation.
This chapter covers the following topics:
 Obtaining the highest Fibonacci value for multiple inputs
 Crawling the Web
v
I.1 Facteurs de limite
I.1 Facteurs de limite

Cette relation s’appelle AMDAHL’S LAW

I.1 Facteurs de limite

En programmation informatique, la loi d'Amdahl est que, dans un

programme avec traitement parallèle, un nombre relativement faible
d'instructions devant être exécutées en séquence aura un facteur limitant
sur l'accélération du programme, de sorte que l'ajout de processeurs
supplémentaires peut ne pas accélérer l'exécution du programme.
D'autres soutiennent que les types d'applications pour lesquelles le
traitement parallèle est le mieux adapté ont tendance à être des problèmes
plus importants dans lesquels l'augmentation du nombre de processeurs
apporte en effet une amélioration correspondante du débit et des
performances.
I.1 Facteurs de limite

la loi d'Amdahl nous dit quelle vitesse nous allons obtenir en

augmentant le nombre de ressources de traitement,
Si les parties parallèles de notre programme sont importantes, si la
majeure partie de notre programme est réalisée en parallèle, nous
obtiendrons le plus d'accélération.
I.1 L'évolution de la plate-forme
I.1 Loi de Gustafson

Dans l'architecture informatique, la loi de Gustafson (ou la loi de

Gustafson-Barsis) donne l'accélération du temps d'exécution d'une tâche
qui bénéficie théoriquement du calcul parallèle, en utilisant une exécution
hypothétique de la tâche sur une machine monocœur comme ligne de
base. Autrement dit, il s'agit du "ralentissement" théorique d'une tâche
déjà parallélisée si elle s'exécute sur une machine série. Il porte le nom de
l'informaticien John L. Gustafson et de son collègue Edwin H. Barsis, et a
été présenté dans l'article Reevaluating Amdahl's Law en 1988.
I.1 Loi de Gustafson
I.1 Loi de Gustafson
2. Différence Entre Un « Cœur » Et Un « Thread » CPU

C’est quoi la différence entre un cœur et un thread ? La différence entre

un cœur et un thread, est qu’un cœur est physiquement présent sur le
processeur alors qu’un thread correspond à une séquence d’instructions
qu’un cœur va exécuter. Grâce aux technologies de multithreading, un
cœur peut exécuter 2 threads à la fois.
2. Qu’est-ce qu’un processeur ?

Le processeur ou CPU (Central Processing Unit) est le composant de

votre ordinateur qui exécute les instructions qui lui sont données par votre
système d’exploitation (Windows). Quand vous exécutez un logiciel,
décompressez une archive ZIP ou regardez une vidéo en haute définition,
vous faites travailler en priorité le processeur ! Pour répondre à vos
demandes les plus exigeantes, le processeur peut être doté des
plusieurs cœurs.
I.Qu’est-ce qu’un cœur ?

Un processeur standard possède un cœur (on dit qu’il est single-core).

Un processeur avec un seul cœur ne peut traiter qu’une seule instruction
à la fois, une instruction étant une tâche que l’on demande au processeur
d’exécuter : convertir une vidéo, compresser des fichiers volumineux,
exécuter un logiciel, etc.
Plusieurs instructions peuvent être traitées par le cœur d’un processeur
mais ce sera toujours en série, c’est-à-dire une instruction à la fois. Avant
l’apparition des processeurs multi-cœurs, on avait l’impression que
les processeurs avec un seul cœur étaient multi-tâches tellement ils
passaient d’une instruction à une autre rapidement mais il n’en était rien.
I.Qu’est-ce qu’un processeur multi-cœurs ?

Un processeur multi-cœur est composé de deux ou plusieurs cœurs

indépendants, chacun étant capable de traiter des instructions
individuellement. Un processeur dual-core contient deux cœurs, un
processeur quad-core quatre cœurs, un processeur hexa-core six cœurs…
Bref, je crois que vous avez compris.
I.Qu’est-ce qu’un processeur multi-cœurs ?

Un processeur multi-cœur permet à l’utilisateur d’exécuter plusieurs tâches

en même temps sans subir de ralentissements ! Autrement dit, les cœurs sont
utiles si vous utilisez plusieurs logiciels à la fois. Quand un programme (un
logiciel de retouche photo par exemple) est en cours d’exécution et traité par un
cœur, vous pouvez solliciter un autre cœur pour utiliser votre navigateur Web ou
écrire un document, sans subir de ralentissements.
Avoir plusieurs cœurs est aussi utile lorsque vous utilisez un logiciel qui peut
utiliser plus d’un cœur. En effet, la majorité des programmes est conçue pour
n’utiliser qu’un seul et unique cœur. Un logiciel qui est compatible avec le
multi-cœur fonctionne lui beaucoup plus rapidement puisqu’il peut exécuter
plusieurs instructions en même temps.
I.Différence Entre Un « Cœur » Et Un « Thread » CPU

c’est quoi la différence entre un cœur et un thread ? La différence entre un

cœur et un thread, est qu’un cœur est physiquement présent sur le
processeur alors qu’un thread correspond à une séquence d’instructions
qu’un cœur va exécuter. Grâce aux technologies de multithreading, un cœur
peut exécuter 2 threads à la fois.
Mais ce n’est pas équivalent à l’exécution de deux threads sur deux cœurs
différents. Le multi-threading permet d’optimiser l’exécution de 2 threads par un
même coeur, mais n’est pas aussi performant que l’utilisation de plusieurs cœurs
physiques.
I.La principale différence entre un Core et un Thread

La différence numéro entre un core et un thread est qu’un core est physiquement
présent sur la puce électronique qui constitue le processeur. C’est-à-dire que
vous pouvez distinguer physiquement chaque core de processeur sur le circuit
électronique du processeur.
I.La principale différence entre un Core et un Thread

Les Threads sont uniquement logiques. C’est une séquence d’instruction que doit
exécuter le processeur. Avec le multi-threading le processeur prend en charge 2
threads à la fois. Cela dit les CPUs core doivent être conçus pour supporter
plusieurs threads aussi appelé le Multi-threading.
Un core qui n’est pas conçu et fabriqué pour supporter le multi-threading ne peut
pas les activer avec une mise à jour logiciel. Cela dit certains processeurs
peuvent supporter plusieurs threads, c’est juste que le fabricant à décider de
désactiver cette fonctionnalité pour segmenter sa gamme de produit. Aujourd’hui
avec la technologie du multi-threading un processeur gérer 2 threads à fois. On
les appelle alors des « cœurs logiques » par opposition au « cœurs physiques ».
Cœur avec Multithreading et Cœur sans Multi-threading

Avant l’arrivée des technologies de multi-threading (Hyperthreading pour Intel et

SMT pour AMD), un cœur était attaché à un thread.
Concrètement cela veut dire qu’un core ne peut s’occuper que d’une « tâche » à
la fois. Le multi-threading est une forme de parallélisation qui permet à un core
de s’occuper de 2 « tâches » en même temps. C’est une technologie
d’optimisation du travail de chaque core ce qui lui permet de gérer ces 2 « tâches
» à la fois. Cette optimisation du travail génère dans la grande majorité des cas
un gain en performance, le core « travail » plus efficacement pour gérer deux
tâches à la fois. Et donc le cœur de votre CPU n’est pas divisé en deux pour créer
deux cœurs logiques, ce n’est pas comme ça qu’il faut le voir..
Il faut voir le multi-threading comme étant un assistant qui aide le travail
du processeur à gérer plus efficacement 2 tâches en même temps. Un cœur
sans multi-threading est un donc dépourvu de cet assistant, il n’est pas capable
de gérer deux tâches aussi efficacement. Cela se traduit, en général, par une
perte de performance par rapport à un cœur avec le multi-threading.
Cœur physique vs Cœur logique

Avoir plus de cœurs physiques est largement supérieur en termes de

performance que d’avoir des cœurs logiques. En effet alors que le
multithreading permet à un cœur de mieux gérer 2 taches à la fois
par rapport à un cœur qui n’est pas multi-threadé, avoir 2 cœurs
séparé permet de réellement traiter deux tâches en parallèle. Le
gain de performance est alors beaucoup plus important en ajoutant
des cœurs physiques qu’avec des cœurs logiques (à supposer que
les tâches sont parallélisables, mais c’est un problème pour les
développeurs). De manière générale, il est donc bien plus
intéressant d’avoir plus de cœurs physiques.
Cœur physique vs Cœur logique

Avoir des cœurs logiques en plus par exemple un CPU qui 4 cœurs
et 8 Threads, sera plus performant qu’un CPU avec 4 cœurs et 4
threads. En effet un processeur 6 cœurs sera en général plus
performant que notre i7 à 8 threads (à supposer qu’il s’agit de la
même architecture CPU)
Processus et Threads
Plateformes de programmation parallèle :
La vision logique traditionnelle d'un ordinateur séquentiel consiste en une
mémoire connectée à un processeur via un chemin de données. Ces trois
composants - processeur, mémoire et chemin de données - constituent des
goulots d'étranglement pour le taux de traitement global d'un système
informatique. Au fil des ans, un certain nombre d'innovations architecturales ont
permis de remédier à ces goulets d'étranglement. L'une des innovations les plus
importantes est la multiplicité - dans les unités de traitement, les chemins de
données et les unités de mémoire. Cette multiplicité est soit entièrement cachée
au programmeur, comme dans le cas du parallélisme implicite, soit exposée au
programmeur sous différentes formes. D
Pipelining
Les processeurs s'appuient depuis longtemps sur les pipelines pour améliorer les
taux d'exécution. En superposant différentes étapes de l'exécution des
instructions (récupération, ordonnancement, décodage, récupération des
opérandes, exécution, stockage, entre autres), le pipelining permet une exécution
plus rapide. Le pipelining est une technique qui consiste à diviser une tâche en
plusieurs sous-tâches et à exécuter ces sous-tâches en parallèle avec plusieurs
unités matérielles. Dans un processeur de pipelining, plusieurs instructions sont
exécutées simultanément à différents stades du cycle d'instruction dans
différentes sections du processeur. L'objectif du traitement en pipeline est
d'augmenter le débit grâce au chevauchement entre l'exécution des tâches
consécutives. Il existe deux types de pipelines : Pipeline d'instructions et
Pipeline arithmétique.
Pipelining
Un pipeline d'instructions divise les actions d'un cycle d'instructions en
plusieurs étapes qui sont exécutées une par une dans différentes sections du
processeur. Le nombre de sections dans le pipeline est conçu par l'architecte
informatique.
Considérons que le cycle d'instruction est divisé en quatre étapes :
 Récupération des instructions (IR)
 Décodage des instructions (ID)
 Exécution (EX)
 Résultat d'écriture (WR)
Supposons qu'il y ait m instructions et que ces instructions soient exécutées dans
n sections du processeur pipeline.
Processeurs à mots d'instruction très longs
Le temps pris pour la première instruction = ntc , où tc est la durée du cycle
d'horloge.
 Temps pris pour les (m-1) instructions restantes = (m-1)tc
 Temps total pris pour m instructions = ntc + (m-1)tc = (n+m-1)tc
 Si le processeur n'est pas pipellé, alors le temps total pris pour m instructions
est mntc .
 Par conséquent, le gain de performance dû au pipeline = mntc /(m+n-1)tc
Un moyen évident d'améliorer le taux d'exécution des instructions au-delà de ce
niveau est d'utiliser des pipelines multiples. Au cours de chaque cycle d'horloge,
plusieurs instructions sont introduites dans le processeur en parallèle. Ces
instructions sont exécutées sur plusieurs unités fonctionnelles.
Processeurs à mots d'instruction très longs (VLIW) :
Le parallélisme extrait par les processeurs superscalaires est souvent limité par le
look- ahead des instructions. La logique matérielle pour l'analyse de dépendance
dynamique est typiquement de l'ordre de 5-10% de la logique totale sur les
microprocesseurs conventionnels (environ 5% sur le superscalaire à quatre voies
Sun UltraSPARC). Cette complexité croît à peu près quadratiquement avec le
nombre de problèmes et peut devenir un goulot d'étranglement.
Un autre concept d'exploitation du parallélisme au niveau des instructions utilisé
dans les processeurs VLIW (very long instruction word) s'appuie sur le
compilateur pour résoudre les dépendances et la disponibilité des ressources au
moment de la compilation. Les instructions qui peuvent être exécutées
simultanément sont regroupées et transmises au processeur sous la forme d'un
seul long mot d'instruction (d'où son nom) pour être exécutées sur plusieurs
unités fonctionnelles en même temps.
Processeurs à mots d'instruction très longs (VLIW) :
Le concept VLIW présente à la fois des avantages et des inconvénients par
rapport aux processeurs superscalaires. L'ordonnancement étant effectué par
logiciel, les mécanismes de décodage et d'émission des instructions sont plus
simples dans les processeurs VLIW. Le compilateur dispose d'un contexte plus
large pour sélectionner les instructions et peut utiliser une variété de
transformations pour optimiser le parallélisme par rapport à une unité d'émission
matérielle. Des instructions parallèles supplémentaires sont généralement mises à
la disposition du compilateur pour contrôler l'exécution parallèle. les
performances des processeurs VLIW sont très sensibles à la capacité des
compilateurs à détecter les dépendances de données et de ressources ainsi que les
risques de lecture et d'écriture, et à programmer les instructions pour un
parallélisme maximal.
Le déroulement des boucles, la prédiction des branchements et l'exécution
spéculative jouent tous un rôle important dans les performances des processeurs
VLIW. Si les processeurs superscalaires et VLIW ont réussi à exploiter le
parallélisme implicite, ils sont généralement limités à des échelles de
concurrence plus petites, de l'ordre du parallélisme à quatre ou huit voies.
Limites de la performance du système de mémoire
L'exécution effective d'un programme sur un ordinateur ne dépend pas seulement
de la vitesse du processeur, mais aussi de la capacité du système de mémoire à
fournir des données au processeur. Au niveau logique, un système de mémoire,
éventuellement constitué de plusieurs niveaux d'antémémoire, reçoit une requête
pour un mot de mémoire et renvoie un bloc de données de taille b contenant le
mot demandé après l nanosecondes. Ici, l est appelé la latence de la mémoire. La
vitesse à laquelle les données peuvent être pompées de la mémoire vers le
processeur détermine la bande passante du système de mémoire.
Dichotomie des plates-formes de calcul parallèle
Nous explorons d'abord une dichotomie basée sur l'organisation logique et
physique des plates-formes parallèles. L'organisation logique fait référence à la
vision de la plate-forme par le programmeur, tandis que l'organisation physique
fait référence à l'organisation matérielle réelle de la plate-forme. Du point de vue
du programmeur, les deux composantes essentielles du calcul parallèle sont les
moyens d'exprimer les tâches parallèles et les mécanismes permettant de
spécifier
l'interaction entre ces tâches. Le premier élément est parfois appelé structure de
contrôle et le second, modèle de communication.
Dichotomie des plates-formes de calcul parallèle
1. Structure de contrôle des plates-formes parallèles
Les tâches parallèles peuvent être spécifiées à différents niveaux de granularité.
À un extrême, chaque programme d'un ensemble de programmes peut être
considéré comme une tâche parallèle. À l'autre extrême, les instructions
individuelles dans un programme peuvent être considérés comme des tâches
parallèles. Entre ces deux extrêmes se trouve une gamme de modèles permettant
de spécifier la structure de contrôle des programmes et le support architectural
correspondant. Exemple : Parallélisme à partir d'une seule instruction sur
plusieurs processeurs Considérons le segment de code suivant qui additionne
deux vecteurs :
for (i = 0 ; i < 1000 ; i++)
c[i] = a[i] + b[i] ;
Dans cet exemple, les différentes itérations de la boucle sont indépendantes les
unes des autres ; c'està-dire que c[0] = a[0] + b[0] ; c[1] = a[1] + b[1] ; , etc.
peuvent toutes être exécutées indépendamment les unes des autres. Par
conséquent, s'il existe un mécanisme permettant d'exécuter la même instruction,
dans ce cas ajouter sur tous les processeurs avec les données appropriées, nous
pourrions exécuter cette boucle beaucoup plus rapidement.
Les unités de traitement des ordinateurs parallèles fonctionnent soit sous le
contrôle centralisé d'une seule unité de commande, soit de manière indépendante.
Dans les architectures appelées SIMD (single instruction stream, multiple data
stream), une seule unité de commande envoie des instructions à chaque unité de
traitement. Dans un ordinateur parallèle SIMD, la même instruction est exécutée
de manière synchrone par toutes les unités de traitement.
Nota: Si le concept SIMD fonctionne bien pour les calculs structurés sur des
structures de données parallèles telles que les tableaux, il est souvent nécessaire
de désactiver sélectivement les opérations sur certains éléments de données. Pour
cette raison, la plupart des paradigmes de programmation SIMD prévoient un
"masque d'activité". Il s'agit d'un masque binaire associé à chaque élément de
données et opération qui spécifie s'il doit participer à l'opération ou non. Des
primitives telles que where (condition) then <stmnt> <elsewhere stmnt> sont
utilisées pour prendre en charge l'exécution sélective. L'exécution conditionnelle
peut être préjudiciable aux performances des processeurs SIMD et doit donc être
utilisée avec précaution.
Contrairement aux architectures SIMD, les ordinateurs dans lesquels chaque
élément de traitement est capable d'exécuter un programme différent
indépendamment des autres éléments de traitement sont appelés ordinateurs
MIMD (multiple instruction stream, multiple data stream). Une variante simple
de ce modèle, appelée modèle SPMD (single program multiple data), repose sur
l'exécution de plusieurs instances du même programme sur des données
différentes. Il est facile de voir que le modèle SPMD a la même expressivité que
le modèle MIMD puisque chacun des multiples programmes peut être inséré
dans un grand bloc if-else dont les conditions sont spécifiées par les
identificateurs de tâches.
Modèle de communication des plates-formes parallèles
Il existe deux formes principales d'échange de données entre les tâches parallèles
: l'accès à un espace de données partagé et l'échange de messages.
Plateformes d'espace d'adressage partagé
La vision "espace d'adressage partagé" d'une plate-forme parallèle prend en
charge un espace de données commun accessible à tous les processeurs. Les
processeurs interagissent en modifiant les objets de données stockés dans cet
espace d'adressage partagé. Les plates-formes à espace d'adressage partagé
prenant en charge la programmation SPMD sont également appelées
multiprocesseurs. La mémoire des plates-formes à espace d'adressage partagé
peut être locale (exclusive à un processeur) ou globale (commune à tous les
processeurs).
Modèle de communication des plates-formes parallèles
Si le temps mis par un processeur pour accéder à n'importe quel mot de mémoire
du système (global ou local) est identique, la plate-forme est classée comme un
multi-ordinateur à accès mémoire uniforme (UMA). En revanche, si le temps
d'accès à certains mots de mémoire est plus long que d'autres, la plate-forme est
qualifiée de multi-ordinateur à accès mémoire non uniforme (NUMA). Par
conséquent, même un uniprocesseur ne serait pas qualifié d'UMA si les temps
d'accès au cache sont pris en compte. Pour cette raison, nous définissons les
architectures NUMA et UMA uniquement en termes de temps d'accès à la
mémoire et non de temps d'accès au cache. La distinction entre les plateformes
UMA et NUMA est importante. Si l'accès à la mémoire locale est moins cher que
l'accès à la mémoire globale, les algorithmes doivent tenir compte de la localité
et structurer les données et les calculs en conséquence.
Plateformes de transmission de messages
La vue logique de la machine d'une plate-forme à passage de messages se
compose de p nœuds de traitement, chacun ayant son propre espace d'adressage
exclusif. Chacun de ces nœuds de traitement peut être soit un processeur unique,
soit un multiprocesseur à espace d'adressage partagé - une tendance qui gagne
rapidement du terrain dans les ordinateurs parallèles modernes à passage de
messages. Les exemples d'une telle vue proviennent naturellement des stations
de travail en grappe et des multi-ordinateurs à espace d'adressage non partagé.
Sur ces plates-formes, les interactions entre les processus s'exécutant sur
différents nœuds doivent être accomplies à l'aide de messages, d'où le nom de
passage de messages. Cet échange de messages est utilisé pour transférer des
données, du travail et pour synchroniser les actions entre les processus. Dans sa
forme la plus générale, les paradigmes de passage de messages permettent
l'exécution d'un programme différent sur chacun des p nœuds.
Plateformes de transmission de messages
La vue logique de la machine d'une plate-forme à passage de messages se
compose de p nœuds de traitement, chacun ayant son propre espace d'adressage
exclusif. Chacun de ces nœuds de traitement peut être soit un processeur unique,
soit un multiprocesseur à espace d'adressage partagé - une tendance qui gagne
rapidement du terrain dans les ordinateurs parallèles modernes à passage de
messages. Les exemples d'une telle vue proviennent naturellement des stations
de travail en grappe et des multi-ordinateurs à espace d'adressage non partagé.
Sur ces plates-formes, les interactions entre les processus s'exécutant sur
différents nœuds doivent être accomplies à l'aide de messages, d'où le nom de
passage de messages. Cet échange de messages est utilisé pour transférer des
données, du travail et pour synchroniser les actions entre les processus. Dans sa
forme la plus générale, les paradigmes de passage de messages permettent
l'exécution d'un programme différent sur chacun des p nœuds.
Les interactions étant réalisées par l'envoi et la réception de messages, les
opérations de base de ce paradigme de programmation sont l'envoi et la réception
(les appels correspondants peuvent différer d'une API à l'autre, mais la
sémantique est largement identique). En outre, comme les opérations d'envoi et
de réception doivent spécifier des adresses cibles, il doit exister un mécanisme
permettant d'attribuer une identification unique ou ID à chacun des multiples
processus exécutant un programme parallèle. Cet ID est généralement mis à la
disposition du programme à l'aide d'une fonction telle que whoami, qui renvoie
au processus appelant son ID. Une autre fonction est généralement nécessaire
pour compléter l'ensemble de base des opérations de passage de messages -
numprocs, qui spécifie le nombre de processus participant à l'ensemble. Avec ces
quatre opérations de base, il est possible d'écrire n'importe quel programme de
passage de messages.
Différentes API de passage de messages, telles que l'interface MPI (Message
Passing Interface) et la PVM (Parallel Virtual Machine), prennent en charge ces
opérations de base et une variété de fonctionnalités de plus haut niveau sous
différents noms de fonctions.
Organisation physique des plates-formes parallèles
Architecture d'un ordinateur parallèle idéal
Une extension naturelle du modèle de calcul en série (la machine à accès
aléatoire, ou RAM) consiste en p processeurs et une mémoire globale de taille
non limitée, accessible uniformément à tous les processeurs. Tous les processeurs
accèdent au même espace d'adressage. Les processeurs partagent une horloge
commune mais peuvent exécuter des instructions différentes dans chaque cycle.
Ce modèle idéal est également appelé machine parallèle à accès aléatoire
(PRAM). Étant donné que les PRAM permettent l'accès simultané à divers
emplacements de mémoire, selon la façon dont les accès simultanés à la mémoire
sont traités, les PRAM peuvent être divisées en quatre sous-classes.
Organisation physique des plates-formes parallèles
 PRAM à lecture exclusive et écriture exclusive (EREW). Dans cette classe,
l'accès à un emplacement mémoire est exclusif. Aucune opération
concurrente de lecture ou d'écriture n'est autorisée. Il s'agit du modèle de
PRAM le plus faible, offrant une concurrence minimale dans l'accès à la
mémoire.
 PRAM à lecture simultanée et écriture exclusive (CREW). Dans cette classe,
les accès multiples en lecture à un emplacement mémoire sont autorisés.
Cependant, les accès multiples en écriture à un emplacement de mémoire sont
sérialisés.
 PRAM à lecture exclusive et écriture simultanée (ERCW). Les accès
multiples en écriture sont autorisés sur un emplacement mémoire, mais les
accès multiples en lecture sont sérialisés.
Organisation physique des plates-formes parallèles
 PRAM à lecture et écriture simultanées (CRCW). Cette classe permet des
accès multiples en lecture et en écriture à un emplacement mémoire commun.
Il s'agit du modèle de PRAM le plus puissant.
Python Parallel Programming
Organisation physique des plates-formes parallèles
Ce dont vous avez besoin pour la pratique. Tous les exemples sera et peuvent
être testés sur une machine Windows ou Linux avec l version de python 3.3.
Les modules suivants (tous téléchargeables gratuitement) sont requis :
 mpich
 Pyro
 pip
 PyCSP
 mpi4py
 DISCO
 asyncio
 NumbaPro compiler
 Celery
 PyOpenCL
 Numpy
 Flower
 SCOOP
Organisation physique des plates-formes parallèles
L'architecture de la mémoire de calcul parallèle en fonction du nombre
d'instructions et de données pouvant être traitées simultanément, les systèmes
informatiques sont classés en quatre catégories :
 Instruction unique, données uniques (SISD)
 Instruction unique, données multiples (SIMD)
 Instruction multiple, données uniques (MISD)
 Instruction multiple, données multiples (MIMD)
Cette classification est connue sous le nom de taxonomie de Flynn
Organisation physique des plates-formes parallèles
L'architecture de la mémoire de calcul parallèle en fonction du nombre
d'instructions et de données pouvant être traitées simultanément, les systèmes
informatiques sont classés en quatre catégories :
 Instruction unique, données uniques (SISD)
 Instruction unique, données multiples (SIMD)
 Instruction multiple, données uniques (MISD)
 Instruction multiple, données multiples (MIMD)
Cette classification est connue sous le nom de taxonomie de Flynn
SISD
L'architecture de la mémoire de calcul parallèle en fonction du nombre
d'instructions. Le système informatique SISD est une machine monoprocesseur.
Il exécute une seule instruction qui fonctionne sur un seul flux de données. Dans
SISD, les instructions machine sont traitées séquentiellement. Dans un cycle
d'horloge, la CPU exécute les opérations suivantes :
 Fetch : le CPU récupère les données et les instructions d'une zone mémoire,
appelée registre.
 Decode : Le CPU décode les instructions.
 Executer : L'instruction est exécutée sur les données. Le résultat de
l'opération est stocké dans un autre registre.
Une fois l'étape d'exécution terminée, le CPU se prépare à commencer un autre
cycle CPU.
Les algorithmes qui s'exécutent sur ces types d'ordinateurs sont séquentiels (ou
série), car ils ne contiennent aucun parallélisme. Des exemples d'ordinateurs
SISD sont des systèmes matériels avec un seul processeur. Les principaux
éléments de ces architectures (architectures Von Neumann) sont :
 Unité de mémoire centrale : elle est utilisée pour stocker à la fois les
instructions et les données de programme.
 CPU : il est utilisé pour obtenir l'instruction et/ou les données de l'unité
de mémoire, qui décode les instructions et les implémente
séquentiellement
 Le système d'E/S : Il s'agit des données d'entrée et des données de sortie
du programme. Les ordinateurs conventionnels à processeur unique sont
classés comme systèmes SISD.
La figure suivante montre spécifiquement quelles zones d'un processeur sont
utilisées dans les étapes d'extraction, de décodage et d'exécution :
MISD
Dans ce modèle, n processeurs, chacun avec sa propre unité de contrôle,
partagent une seule unité de mémoire. A chaque cycle d'horloge, les données
reçues de la mémoire sont traitées simultanément par tous les processeurs,
chacun selon les instructions reçues de son unité de contrôle. Dans ce cas, le
parallélisme (parallélisme au niveau des instructions) est obtenu en effectuant
plusieurs opérations sur la même donnée. Les types de problèmes qui peuvent
être résolus efficacement dans ces architectures sont assez particuliers, comme
ceux concernant le chiffrement des données ; pour cette raison, l'ordinateur
MISD n'a pas trouvé de place dans le secteur commercial. Les ordinateurs MISD
sont plus un exercice intellectuel qu'une configuration pratique.
SIMD
Un ordinateur SIMD est constitué de n processeurs identiques, chacun avec sa
propre mémoire locale, où il est possible de stocker des données. Tous les
processeurs fonctionnent sous le contrôle d'un seul flux d'instructions ; en plus
de cela, il y a n flux de données, un pour chaque processeur. Les processeurs
travaillent simultanément sur chaque étape et exécutent la même instruction,
mais sur des éléments de données différents. Ceci est un exemple de parallélisme
au niveau des données. Les architectures SIMD sont beaucoup plus polyvalentes
que les architectures MISD. De nombreux problèmes couvrant un large éventail
d'applications peuvent être résolus par des algorithmes parallèles sur des
ordinateurs SIMD. Une autre caractéristique intéressante est que les algorithmes
de ces ordinateurs sont relativement faciles à concevoir, analyser et mettre en
œuvre.
La limite est que seuls les problèmes décomposables en plusieurs sous-
problèmes (qui sont tous identiques, dont chacun sera alors résolu
simultanément, par le même jeu d'instructions) peuvent être traités avec le
calculateur SIMD. Au supercalculateur développé selon ce paradigme, il faut
citer Connection Machine (1985 Thinking Machine) et MPP (NASA - 1983).
Comme nous le verrons au chapitre 6, Programmation GPU avec Python,
l'avènement du processeur graphique (GPU) moderne, construit avec de
nombreuses unités embarquées SIMD, a conduit à une utilisation plus répandue
de ce paradigme informatique.
MIMD
Cette classe d'ordinateurs parallèles est la classe la plus générale et la plus
puissante selon la classification de Flynn. Il y a n processeurs, n flux
d'instructions et n flux de données. Chaque processeur possède sa propre unité de
contrôle et sa propre mémoire locale, ce qui rend les architectures MIMD plus
puissantes en termes de calcul que celles utilisées dans SIMD. Chaque
processeur fonctionne sous le contrôle d'un flux d'instructions émises par sa
propre unité de contrôle ; par conséquent, les processeurs peuvent
potentiellement exécuter différents programmes sur différentes données,
résolvant des sous-problèmes différents et pouvant faire partie d'un seul
problème plus vaste. Dans MIMD, l'architecture est réalisée à l'aide du niveau de
parallélisme avec des threads et/ou des processus. Cela signifie également que
les processeurs fonctionnent généralement de manière asynchrone.
MIMD
Les ordinateurs de cette classe sont utilisés pour résoudre les problèmes qui n'ont
pas une structure régulière requise par le modèle SIMD. De nos jours, cette
architecture est appliquée à de nombreux PC, supercalculateurs et réseaux
informatiques. Cependant, il y a un compteur que vous devez considérer : les
algorithmes asynchrones sont difficiles à concevoir, analyser et mettre en œuvre.
Memory organization
Un autre aspect que nous devons considérer pour évaluer une architecture
parallèle est l'organisation de la mémoire ou plutôt la manière dont les données
sont accédées. Quelle que soit la vitesse de l'unité de traitement, si la mémoire ne
peut pas maintenir et fournir des instructions et des données à une vitesse
suffisante, il n'y aura aucune amélioration des performances. Le principal
problème qu'il faut surmonter pour rendre le temps de réponse de la mémoire
compatible avec la vitesse du processeur est le temps de cycle mémoire, qui est
défini comme le temps qui s'est écoulé entre deux opérations successives. Le
temps de cycle du processeur est généralement beaucoup plus court que le temps
de cycle de la mémoire.
Memory organization
Lorsque le processeur commence à transférer des données (vers ou depuis la
mémoire), la mémoire restera occupée pendant toute la durée du cycle mémoire :
pendant cette période, aucun autre périphérique (contrôleur d'E/S, processeur ou
même le processeur lui-même qui la requête) peut utiliser la mémoire car elle
sera engagée pour répondre à la requête.
Memory organization
Les solutions au problème d'accès à la mémoire ont abouti à une dichotomie des
architectures MIMD. Dans le premier type de système, connu sous le nom de
système à mémoire partagée, la mémoire virtuelle est élevée et tous les
processeurs ont un accès égal aux données et aux instructions de cette mémoire.
L'autre type de système est le modèle à mémoire distribuée, dans lequel chaque
processeur possède une mémoire locale qui n'est pas accessible aux autres
processeurs. La différence entre la mémoire partagée et la mémoire distribuée
réside dans la structure de la mémoire virtuelle ou de la mémoire du point de vue
du processeur. Physiquement, presque chaque mémoire système est divisée en
composants distincts accessibles indépendamment. Ce qui distingue une
mémoire partagée d'une mémoire distribuée est la gestion des accès mémoire par
l'unité de traitement.
Memory organization
Si un processeur devait exécuter l'instruction load R0, i, c'est-à-dire charger dans
le registre R0 le contenu de l'emplacement mémoire i, la question est maintenant
que devrait-il se passer ? Dans un système à mémoire partagée, l'index i est une
adresse globale et l'emplacement mémoire i est le même pour chaque processeur.
Si deux processeurs exécutaient cette instruction en même temps, ils chargeraient
les mêmes informations dans leurs registres R0. Dans un système de mémoire
distribuée, i est une adresse locale. Si deux processeurs devaient charger
l'instruction R0 en même temps, des valeurs différentes pourraient se retrouver
dans le R0 du registre respectif, puisque, dans ce cas, les cellules de mémoire
sont attribuées une pour chaque mémoire locale.
Memory organization
La distinction entre mémoire partagée et mémoire distribuée est très importante
pour les programmeurs car elle détermine la manière dont les différentes parties
d'un programme parallèle doivent communiquer. Dans un système, la mémoire
partagée est suffisante pour construire une structure de données en mémoire et
passer au sous-programme parallèle, qui sont les variables de référence de cette
structure de données. De plus, une machine à mémoire distribuée doit faire des
copies des données partagées dans chaque mémoire locale. Ces copies sont
créées par l'envoi d'un message contenant les données à partager d'un processeur
à l'autre. Un inconvénient de cette organisation mémoire est que parfois, ces
messages peuvent être très volumineux et prendre un temps de transfert
relativement long.
Memoire partagée
Le schéma d'un système multiprocesseur à mémoire partagée est présenté dans la
figure suivante. Les connexions physiques ici sont assez simples. La structure du
bus autorise un nombre arbitraire de périphériques partageant le même canal. Les
protocoles de bus ont été conçus à l'origine pour permettre à un seul processeur
et à un ou plusieurs disques ou contrôleurs de bande de communiquer via la
mémoire partagée ici. A noter que chaque processeur a été associé à une
mémoire cache, car on suppose que la probabilité qu'un processeur ait besoin de
données ou d'instructions présentes dans la mémoire locale est très élevée. Le
problème se produit lorsqu'un processeur modifie des données stockées dans le
système de mémoire qui sont simultanément utilisées par d'autres processeurs.
La nouvelle valeur passera du cache du processeur qui a été modifié à la
mémoire partagée ; plus tard, cependant, il doit également être transmis à tous les
autres processeurs, afin qu'ils ne fonctionnent pas avec la valeur obsolète.
Memoire partagée
Ce problème est connu sous le nom de problème de cohérence du cache, un cas
particulier du problème de cohérence de la mémoire, qui nécessite des
implémentations matérielles capables de gérer les problèmes de concurrence et
de synchronisation similaires à ceux ayant une programmation par thread.
Les principales caractéristiques des systèmes de mémoire partagée sont :
 La mémoire est la même pour tous les processeurs, par exemple, tous les
processeurs associés à la même structure de données travailleront avec les
mêmes adresses mémoire logiques, accédant ainsi aux mêmes emplacements
mémoire.
 La synchronisation est rendue possible en contrôlant l'accès des processeurs à
la mémoire partagée. En effet, un seul processeur à la fois peut avoir accès
aux ressources mémoire.
 Un emplacement de mémoire partagée ne doit pas être modifié à partir d'une
tâche pendant qu'une autre tâche y accède.
 Le partage de données est rapide ; le temps nécessaire à la communication
entre deux tâches est égal au temps de lecture d'un seul emplacement
mémoire (il dépend de la vitesse d'accès mémoire).
Les accès à la mémoire dans les systèmes de mémoire partagée sont les suivants :
 Uniform memory access (UMA) : La caractéristique fondamentale de ce
système est le temps d'accès à la mémoire qui est constant pour chaque
processeur et pour n'importe quelle zone de la mémoire. Pour cette raison, ces
systèmes sont également appelés multiprocesseurs symétriques (SMP). Ils
sont relativement simples à mettre en œuvre, mais peu évolutifs ; le
programmeur est responsable de la gestion de la synchronisation en insérant
les contrôles, sémaphores, verrous, etc. appropriés dans le programme qui
gère les ressources.
 Accès mémoire non uniforme (NUMA) : Ces architectures divisent la zone
mémoire en une zone d'accès rapide qui est affectée à chaque processeur et
une zone commune pour l'échange de données, avec un accès plus lent. Ces
systèmes sont également appelés systèmes de mémoire partagée distribués
(DSM). Ils sont très évolutifs, mais complexes à développer.
 Pas d'accès mémoire distant (NORMA) : La mémoire est physiquement répartie
entre les processeurs (mémoire locale). Toutes les mémoires locales sont privées et
ne peuvent accéder qu'au processeur local. La communication entre les processeurs
se fait à travers un protocole de communication utilisé pour l'échange de messages,
le protocole de passage de messages.
 Accès à la mémoire cache uniquement (COMA) : ces systèmes sont équipés
uniquement de mémoires cache. Lors de l'analyse des architectures NUMA, il a été
remarqué que ces architectures conservaient les copies locales des données dans le
cache et que ces données étaient stockées en double dans la mémoire principale.
Cette architecture supprime les doublons et ne conserve que les mémoires caches,
la mémoire est physiquement répartie entre les processeurs (mémoire locale).
Toutes les mémoires locales sont privées et ne peuvent accéder qu'au processeur
local. La communication entre les processeurs se fait à travers un protocole de
communication pour l'échange de messages, le protocole de passage de messages.
Mémoire distribuée
Dans un système à mémoire distribuée, la mémoire est associée à chaque
processeur et un processeur ne peut adresser que sa propre mémoire. Certains
auteurs qualifient ce type de système de "multi-ordinateur", reflétant le fait que
les éléments du système sont eux-mêmes de petits systèmes complets d'un
processeur et d'une mémoire, comme vous pouvez le voir sur la figure suivante :
Ce type d'organisation présente plusieurs avantages. Dans un premier temps, il
n'y a pas de conflits au niveau du bus de communication ou du switch. Chaque
processeur peut utiliser toute la bande passante de sa propre mémoire locale sans
aucune interférence des autres processeurs. Deuxièmement, l'absence de bus
commun signifie qu'il n'y a pas de limite intrinsèque au nombre de processeurs,
la taille du système n'est limitée que par le réseau utilisé pour connecter les
processeurs. Troisièmement, il n'y a pas de problèmes de cohérence du cache.
Chaque processeur est responsable de ses propres données et n'a pas à se soucier
de la mise à niveau des copies. Le principal inconvénient est que la
communication entre processeurs est plus difficile à mettre en œuvre. Si un
processeur a besoin de données dans la mémoire d'un autre processeur, les deux
processeurs doivent nécessairement échanger des messages via le protocole de
passage de messages.
Cela introduit deux sources de ralentissement ; construire et envoyer un message
d'un processeur à un autre prend du temps, et aussi, tout processeur doit être
arrêté afin de gérer les messages reçus des autres processeurs. Un programme
conçu pour fonctionner sur une machine à mémoire distribuée doit être organisé
comme un ensemble de tâches indépendantes qui communiquent via des
messages.
Les principales caractéristiques des systèmes de mémoire distribuée sont les
suivantes :
 La mémoire est physiquement répartie entre les processeurs ; chaque
mémoire locale n'est directement accessible que par son processeur.
 La synchronisation est obtenue en déplaçant les données (même s'il ne s'agit
que du message lui-même) entre les processeurs (communication).
 La subdivision des données dans les mémoires locales affecte les
performances de la machine, il est essentiel de faire une subdivision précise,
afin de minimiser la communication entre les CPU. De plus, le processeur qui
coordonne ces opérations de décomposition et de composition doivent
communiquer efficacement avec les processeurs qui opèrent sur les parties
individuelles des structures de données.
 Le protocole de transmission de messages est utilisé pour que les CPU
puissent communiquer entre elles via l'échange de paquets de données. Les
messages sont des unités d'information discrètes ; dans le sens où ils ont une
identité bien définie, il est donc toujours possible de les distinguer les uns des
autres.
Traitement massivement parallèle
Les machines MPP sont composées de centaines de processeurs (qui peuvent
atteindre des centaines de milliers dans certaines machines) qui sont connectés
par un réseau de communication. Les ordinateurs les plus rapides au monde sont
basés sur ces architectures ; quelques exemples de systèmes de ces architectures
sont : Earth Simulator, Blue Gene, ASCI White, ASCI Red et ASCI Purple and
Red Storm.
Un cluster de postes de travail
Ces systèmes de traitement sont basés sur des calculateurs classiques reliés par
des réseaux de communication. Les grappes de calcul entrent dans cette
classification.
Dans une architecture en cluster, nous définissons un nœud comme une unité de
calcul unique qui participe au cluster. Pour l'utilisateur, le cluster est totalement
transparent : toute la complexité matérielle et logicielle est masquée et les
données et applications sont rendues accessibles comme si elles provenaient
toutes d'un seul nœud. Ici, nous avons identifié trois types de clusters :
 Le cluster de basculement : dans celui-ci, l'activité du nœud est surveillée en
permanence, et lorsqu'une machine cesse de fonctionner, une autre machine
prend en charge ces activités. L'objectif est d'assurer un service continu grâce
à la redondance de l'architecture.
 Le cluster d'équilibrage de charge : dans ce système, une demande de tâche
est envoyée au nœud qui a le moins d'activité. Cela garantit que moins de
temps est nécessaire pour terminer le processus.
 Le cluster de calcul haute performance : Dans celui-ci, chaque nœud est
configuré pour fournir des performances extrêmement élevées. Le processus
est également divisé en plusieurs tâches sur plusieurs nœuds. Les travaux sont
parallélisés et seront distribués sur différentes machines.
L'architecture hétérogène
L'introduction des accélérateurs GPU dans le monde homogène du supercalcul a
changé la nature de la façon dont les supercalculateurs étaient à la fois utilisés et
programmés auparavant. Malgré les hautes performances offertes par les GPU,
ils ne peuvent pas être considérés comme une unité de traitement autonome car
ils doivent toujours être accompagnés d'une combinaison de CPU. Le paradigme
de programmation est donc très simple ; le CPU prend le contrôle et calcule en
série, affectant à l'accélérateur graphique les tâches qui sont très coûteuses en
calcul et qui ont un haut degré de parallélisme.
La communication entre un CPU et un GPU peut s'effectuer non seulement
grâce à l'utilisation d'un bus à haut débit, mais aussi grâce au partage d'une
seule zone de mémoire à la fois physique ou virtuelle. En effet, dans le cas
où les deux appareils ne sont pas équipés de leurs propres zones mémoire, il
est possible de se référer à une zone mémoire commune en utilisant les
bibliothèques logicielles fournies par les différents modèles de
programmation, tels que CUDA et OpenCL. Ces architectures sont appelées
architectures hétérogènes, dans lesquelles les applications peuvent créer des
structures de données dans un seul espace d'adressage et envoyer une tâche
au matériel de l'appareil approprié pour la résolution de la tâche. Plusieurs
tâches de traitement peuvent s'opérer en toute sécurité sur les mêmes régions
pour éviter les problèmes de cohérence des données, grâce aux opérations
atomiques.
Ainsi, malgré le fait que le CPU et le GPU ne semblent pas fonctionner
efficacement ensemble, avec l'utilisation de cette nouvelle architecture, nous
pouvons optimiser leur interaction avec et les performances des applications
parallèles.
Modèles de programmation parallèle

Les modèles de programmation parallèle existent en tant qu'abstraction des

architectures matérielles et mémoire. En fait, ces modèles ne sont pas spécifiques
et ne font pas référence à des types particuliers de machines ou d'architectures
mémoire. Ils peuvent être implémentés (au moins théoriquement) sur n'importe
quel type de machines. Par rapport aux subdivisions précédentes, ces modèles de
programmation sont réalisés à un niveau supérieur et représentent la manière
dont le logiciel doit être implémenté pour effectuer un calcul parallèle. Chaque
modèle a sa propre façon de partager des informations avec d'autres processeurs
afin d'accéder à la mémoire et de diviser le travail.
Il n'y a pas de meilleur modèle de programmation en termes absolus ; le meilleur
à appliquer dépendra beaucoup du problème qu'un programmeur doit traiter et
résoudre.
Les modèles les plus largement utilisés pour la programmation parallèle sont :
 Le modèle de mémoire partagée
 Le modèle multithread
 Le modèle de mémoire distribuée/passage de messages
 Le modèle parallèle de données
Dans cette recette, nous allons vous donner un aperçu de ces modèles. Une
description plus précise sera dans les prochains chapitres qui vous présenteront
le module Python approprié qui
met en œuvre celles-ci.
Modèle de la mémoire partagée

Dans ce modèle, les tâches partagent une seule zone de mémoire partagée, où
l'accès (lecture et écriture de données) aux ressources partagées est asynchrone.
Il existe des mécanismes qui permettent au programmeur de contrôler l'accès à la
mémoire partagée, par exemple, des verrous ou des sémaphores. Ce modèle offre
l'avantage que le programmeur n'a pas à clarifier la communication entre les
tâches. Un inconvénient important en termes de performances est qu'il devient
plus difficile de comprendre et de gérer la localité des données ; conserver les
données locales au processeur qui y travaille conserve les accès à la mémoire, les
actualisations du cache et le trafic de bus qui se produisent lorsque plusieurs
processeurs utilisent les mêmes données.
Modèle multithread
Dans ce modèle, un processus peut avoir plusieurs flux d'exécution, par exemple,
une partie séquentielle est créée et par la suite, une série de tâches sont créées qui
peuvent être exécutées en parallèle. Habituellement, ce type de modèle est utilisé
sur des architectures à mémoire partagée. Ainsi, il sera très important pour nous de
gérer la synchronisation entre les threads, car ils fonctionnent sur de la mémoire
partagée, et le programmeur doit empêcher plusieurs threads de mettre à jour les
mêmes emplacements en même temps. Les processeurs de la génération actuelle
sont multithreads dans le logiciel et le matériel. Les threads Posix sont l'exemple
classique de l'implémentation du multithreading sur un logiciel. La technologie
Intel Hyper-threading implémente le multithreading sur le matériel en basculant
entre deux threads lorsque l'un est bloqué ou en attente d'E/S. Le parallélisme peut
être obtenu à partir de ce modèle même si l'alignement des données n'est pas
linéaire.
Modèle de transmission de messages
Le modèle de transmission de messages est généralement appliqué dans le cas où
chaque processeur possède sa propre mémoire (systèmes à mémoire distribuée).
Plusieurs tâches peuvent résider sur la même machine physique ou sur un nombre
arbitraire de machines. Le programmeur est chargé de déterminer le parallélisme
et l'échange de données qui se produit à travers les messages. La mise en œuvre de
ce modèle de programmation parallèle nécessite l'utilisation de bibliothèques
logicielles (ad hoc) à utiliser dans le code. De nombreuses implémentations du
modèle de transmission de messages ont été créées : certains des exemples sont
disponibles depuis les années 1980, mais seulement à partir du milieu des années
90, ont été créés pour un modèle standardisé, aboutissant à une norme de facto
appelée MPI (l'interface de transmission de messages).
Modèle de transmission de messages
Le modèle MPI est clairement conçu avec de la mémoire distribuée, mais étant
des modèles de programmation parallèle, la multiplateforme peut également être
utilisée avec une machine à mémoire partagée.
Modèle parallèle de données
Dans ce modèle, nous avons plus de tâches qui fonctionnent sur la même structure
de données, mais chaque tâche fonctionne sur une partie différente des données.
Dans l'architecture de mémoire partagée, toutes les tâches ont accès aux données
via des architectures de mémoire partagée et de mémoire distribuée, où la
structure de données est divisée et réside dans la mémoire locale de chaque tâche.
Pour mettre en œuvre ce modèle, un programmeur doit développer un programme
qui spécifie la distribution et l'alignement des données. Les GPU de la génération
actuelle fonctionnent parfaitement avec les données alignées.
Comment concevoir un programme parallèle

La conception des algorithmes qui exploitent le parallélisme repose sur une

série d'opérations, qui doivent nécessairement être effectuées pour que le
programme effectue correctement le travail sans produire de résultats partiels
ou erronés. Les macro-opérations à effectuer pour une parallélisation
correcte d'un algorithme sont :
 Décomposition des tâches
 Affectation des tâches
 Agglomération
 Cartographie
Décomposition des tâches

Dans cette première phase, le programme logiciel est découpé en tâches ou en un

ensemble d'instructions qui peuvent ensuite être exécutées sur différents
processeurs pour mettre en œuvre le parallélisme. Pour faire cette subdivision, il
y a deux méthodes qui sont utilisées :
 Décomposition de domaine : Ici, les données des problèmes sont
décomposées ; l'application est commune à tous les processeurs qui
travaillent sur une portion de données différente. Cette méthodologie est
utilisée lorsque nous avons une grande quantité de données à traiter.
 Décomposition fonctionnelle : Dans ce cas, le problème est découpé en
tâches, où chaque tâche effectuera une opération particulière sur toutes les
données disponibles.
Attribution de tâche

Dans cette étape, le mécanisme par lequel la tâche sera répartie entre les
différents processus est spécifié. Cette phase est très importante car elle
établit la répartition de la charge de travail entre les différents processeurs.
L'équilibre de charge est ici crucial ; en fait, tous les processeurs doivent
fonctionner avec continuité, en évitant un état d'inactivité pendant une
longue période. Pour ce faire, le programmeur prend en compte l'éventuelle
hétérogénéité du système qui tente d'attribuer plus de tâches à des
processeurs plus performants. Enfin, pour une plus grande efficacité de la
parallélisation, il faut limiter au maximum les communications entre
processeurs, car elles sont souvent à l'origine de ralentissements et de
consommation de ressources.
Une agglomération

L'agglomération est le processus consistant à combiner des tâches plus

petites avec des tâches plus grandes afin d'améliorer les performances. Si les
deux étapes précédentes du processus de conception ont divisé le problème
en un nombre de tâches dépassant largement le nombre de processeurs
disponibles, et si l'ordinateur n'est pas spécifiquement conçu pour gérer un
grand nombre de petites tâches (certaines architectures, telles que les GPU,
gérer cette amende et bénéficier en effet de l'exécution de millions, voire de
milliards de tâches), la conception peut s'avérer très inefficace.
Généralement, cela est dû au fait que les tâches doivent être communiquées
au processeur ou au thread afin qu'il calcule ladite tâche.
Une agglomération

La plupart des communications ont des coûts qui sont non seulement
proportionnels à la quantité de données transférées, mais entraînent
également un coût fixe pour chaque opération de communication (comme la
latence inhérente à l'établissement d'une connexion TCP). Si les tâches sont
trop petites, ce coût fixe peut facilement rendre la conception inefficace.
Mapping (Cartographie)
Dans l'étape de mappage du processus de conception de l'algorithme
parallèle, nous spécifions où chaque tâche doit être exécutée. L'objectif est
de minimiser le temps d'exécution total. Ici, vous devez souvent faire des
compromis, car les deux principales stratégies entrent souvent en conflit :
 Les tâches qui communiquent fréquemment doivent être placées dans le
même processeur pour augmenter la localité.
 Les tâches qui peuvent être exécutées simultanément doivent être placées
dans des processeurs différents pour améliorer la simultanéité.
C'est ce qu'on appelle le problème de mappage, et il est connu pour être
NP-complet. En tant que tel, il n'existe pas de solutions en temps
polynomial au problème dans le cas général. Pour des tâches de taille
égale et des tâches avec des modèles de communication facilement
identifiables, le mappage est simple (nous pouvons également effectuer
une agglomération ici pour combiner des tâches qui correspondent au
même processeur.)Cependant, si les tâches ont des modèles de
communication difficiles à prévoir ou si la quantité de travail varie d'une
tâche à l'autre, il est difficile de concevoir un schéma de cartographie et
d'agglomération efficace. Pour ces types de problèmes, des algorithmes
d'équilibrage de charge peuvent être utilisés pour identifier les stratégies
d'agglomération et de mappage pendant l'exécution.
Les problèmes les plus difficiles sont ceux dans lesquels la quantité de
communication ou le nombre de tâches change pendant l'exécution du
programme. Pour ce type de problèmes, des algorithmes d'équilibrage de
charge dynamique peuvent être utilisés, qui s'exécutent périodiquement
pendant l'exécution.
Dynamic mapping (Cartographie dynamique)
Il existe de nombreux algorithmes d'équilibrage de charge pour divers
problèmes, à la fois globaux et locaux. Les algorithmes globaux nécessitent
une connaissance globale du calcul effectué, ce qui ajoute souvent beaucoup
de surcharge. Les algorithmes locaux reposent uniquement sur des
informations locales à la tâche en question, ce qui réduit les frais généraux
par rapport aux algorithmes globaux, mais sont généralement moins
performants pour trouver une agglomération et une cartographie optimales.
Cependant, la surcharge réduite peut réduire le temps d'exécution même si le
mappage est moins bon en soi. Si les tâches communiquent rarement
autrement qu'au début et à la fin de l'exécution, un algorithme de
planification des tâches est souvent utilisé qui mappe simplement les tâches
aux processeurs lorsqu'ils deviennent inactifs. Dans un algorithme de
planification de tâches, un pool de tâches est maintenu. Les tâches sont
placées dans ce pool et en sont extraites par les travailleurs. Il existe trois
approches courantes dans ce modèle, qui sont expliquées ci-après.
Gestionnaire/travailleur
Il s'agit du schéma de mappage dynamique de base dans lequel tous les
travailleurs se connectent à un gestionnaire centralisé. Le responsable envoie
à plusieurs reprises des tâches aux travailleurs et collecte les résultats. Cette
stratégie est probablement la meilleure pour un nombre relativement
restreint de processeurs. La stratégie de base peut être améliorée en
récupérant les tâches à l'avance afin que la communication et le calcul se
chevauchent.
Responsable hiérarchique/travailleur
Il s'agit de la variante d'un gestionnaire/travailleur qui a une disposition
semi-distribuée ; les travailleurs sont divisés en groupes, chacun avec son
propre responsable. Ces responsables de groupe communiquent avec le
responsable central (et éventuellement entre eux également), tandis que les
Cela répartit la charge entre plusieurs gestionnaires et peut ainsi gérer un
plus grand nombre de processeurs si tous les travailleurs demandent des
tâches au même gestionnaire.
Décentraliser
Dans ce schéma, tout est décentralisé. Chaque processeur maintient son
propre pool de tâches et communique avec les autres processeurs afin de
demander des tâches. La manière dont les processeurs choisissent d'autres
processeurs pour demander des tâches varie et est déterminée en fonction du
problème.
Comment évaluer les performances d'un programme parallèle
Le développement de la programmation parallèle a créé le besoin de
métriques de performance et d'un outil logiciel pour évaluer les
performances d'un algorithme parallèle afin de décider si son utilisation est
pratique ou non. En effet, l'objectif du calcul parallèle est de résoudre de
gros problèmes en un temps relativement court. Les facteurs qui contribuent
à la réalisation de cet objectif sont, par exemple, le type de matériel utilisé,
le degré de parallélisme du problème et le modèle de programmation
parallèle adopté. Pour faciliter cela, une analyse des concepts de base a été
introduite, qui compare l'algorithme parallèle obtenu à partir de la séquence
d'origine.
La performance est obtenue en analysant et en quantifiant le nombre de
threads et/ou le nombre de processus utilisés. Pour analyser cela, quelques
indices de performance sont introduits : accélération, efficacité et mise à
l'échelle. Les limitations d'un calcul parallèle sont introduites par la loi
d'Ahmdal pour évaluer le degré d'efficacité de la parallélisation d'un
algorithme séquentiel on a la loi de Gustafson.
Speedup (Accélérer)
L'accélération est la mesure qui affiche l'avantage de résoudre un problème
en parallèle. Il est défini comme le rapport du temps mis pour résoudre un
problème sur un seul élément de traitement, , au temps nécessaire pour
résoudre le même problème sur éléments de traitement identiques, . On note
accélération par
Nous avons une accélération linéaire, où si , cela signifie que la vitesse
d'exécution augmente avec le nombre de processeurs. Bien sûr, c'est un cas
idéal. Alors que l'accélération est absolue lorsque est le temps d'exécution
du meilleur algorithme séquentiel, l'accélération est relative lorsque est le
temps d'exécution de l'algorithme parallèle pour un seul processeur.
Récapitulons ces conditions :
 S = p est une accélération linéaire ou idéale
 S < p est l'accélération réelle
 S > p est une accélération superlinéaire
Efficacité
Dans un monde idéal, un système parallèle avec éléments de traitement peut
nous donner une accélération égale à . Cependant, cela est très rarement
atteint. Habituellement, un certain temps est gaspillé à ne rien faire ou à
communiquer. L'efficacité est une mesure de performance évaluant le niveau
d'utilisation des processeurs dans la résolution d'une tâche, par rapport à la
quantité d'efforts gaspillés dans la communication et la synchronisation. On
le note et on peut le définir comme.

Les algorithmes avec accélération linéaire ont la valeur de ; dans les autres
cas, la valeur de est inférieure à .
Efficacité
Les trois cas sont identifiés comme suit :
 Quand E = 1, c'est un cas linéaire
 Quand E < 1, c'est un cas réel
 Lorsque E<< 1, c'est un problème parallélisable à faible efficacité
Mise à l'échelle (Scaling)
La mise à l'échelle est définie comme la capacité à être efficace sur une
machine parallèle. Il identifie la puissance de calcul (vitesse d'exécution)
proportionnellement au nombre de processeurs. En augmentant la taille du
problème et en même temps le nombre de processeurs, il n'y aura aucune
perte en termes de performances. Le système évolutif, en fonction des
incréments des différents facteurs, peut conserver la même efficacité ou
l'améliorer.
La loi d'Amdahl
La loi d'Amdahl est une loi largement utilisée pour concevoir des
processeurs et des algorithmes parallèles. Il indique que l'accélération
maximale pouvant être atteinte est limitée par le composant série du
programme :

où désigne la composante série (non parallélisée) d'un programme. Cela

signifie que pour, par exemple, un programme dans lequel 90 % du code
peut être mis en parallèle, mais 10 % doivent rester en série, l'accélération
maximale réalisable est de 9, même pour un nombre infini de processeurs.
loi de Gustafson
La loi de Gustafson est basée sur les considérations suivantes :
 Tout en augmentant la dimension d'un problème, ses parties séquentielles
restent constantes.
 Tout en augmentant le nombre de processeurs, le travail requis sur chacun
d'eux reste toujours le même.
Cela indique que , où est le nombre de processeurs, est l'accélération et est
la fraction non parallélisable de tout processus parallèle. Ceci est en
contraste avec la loi d’Amdahl, qui prend le temps d'exécution d'un
processus unique comme étant la quantité fixe et le compare à une réduction
du temps d'exécution parallèle par processus.
Ainsi, la loi d'Amdahl est basée sur l'hypothèse d'une taille de problème
fixe ; il suppose que la charge de travail globale d'un programme ne change
pas en fonction de la taille de la machine (c'est-à-dire du nombre de
processeurs). La loi de Gustafson comble la lacune de la loi d'Amdahl, qui
ne prend pas en compte le nombre total de ressources informatiques
impliquées dans la résolution d'une tâche. Il suggère que la meilleure façon
de fixer le temps imparti pour la résolution d'un problème parallèle est de
considérer toutes les ressources informatiques et sur la base de ces
informations, il résout le problème.
Python dans un monde parallèle
Pour être un langage interprété, Python est rapide, et si la vitesse est critique,
il s'interface facilement avec des extensions écrites dans des langages plus
rapides, tels que C ou C++. Une manière courante d'utiliser Python consiste
à l'utiliser pour la logique de haut niveau d'un programme ; l'interpréteur
Python est écrit en C et est connu sous le nom de CPython. L'interpréteur
traduit le code Python dans un langage intermédiaire appelé bytecode
Python, qui est analogue à un langage d'assemblage, mais contient un haut
niveau d'instruction. Pendant l'exécution d'un programme Python, la soi-
disant boucle d'évaluation traduit le bytecode Python en opérations
spécifiques à la machine. L'utilisation de l'interpréteur présente des
avantages dans la programmation de code et le débogage, mais la vitesse
d'un programme peut être un problème.
Une première solution est fournie par des packages tiers, où un programmeur
écrit un module C puis l'importe depuis Python. Une autre solution est
l'utilisation d'un compilateur Python Just-in-Time, qui est une alternative à
CPython, par exemple, l'implémentation PyPy optimise la génération de
code et la vitesse d'un programme Python. Dans ce cours, nous examinerons
une troisième approche du problème ; en fait, Python fournit des modules ad
hoc qui pourraient bénéficier du parallélisme. La description de plusieurs de
ces modules, dans lesquels s'inscrit le paradigme de la programmation
parallèle, sera abordée dans les slides suivants.
Cependant, dans ce cours, nous présenterons les deux concepts
fondamentaux de threads et de processus et comment ils sont traités dans le
langage de programmation Python.
Présentation des processus et des threads
Un processus est une instance d'exécution d'une application, par exemple,
un double-clic sur l'icône du navigateur Internet sur le bureau démarrera un
processus qui exécute le navigateur.
Un thread est un flux de contrôle actif qui peut être activé en parallèle avec
d'autres threads au sein du même processus. Le terme "contrôle de flux"
désigne une exécution séquentielle d'instructions machine.
De plus, un processus peut contenir plusieurs threads, donc en démarrant le
navigateur, le système d'exploitation crée un processus et commence à
exécuter les threads principaux de ce processus. Chaque thread peut exécuter
un ensemble d'instructions (généralement, une fonction) indépendamment et
en parallèle avec d'autres processus ou threads.
Cependant, étant les différents threads actifs au sein d'un même processus,
ils partagent l'adressage de l'espace, puis les structures de données.
Un thread est parfois appelé un processus léger car il partage de
nombreuses caractéristiques d'un processus, en particulier les
caractéristiques d'être un flux de contrôle séquentiel exécuté en parallèle
avec d'autres flux de contrôle séquentiels.
Résumons:
 Un processus peut être constitué de plusieurs threads parallèles.
 Normalement, la création et la gestion d'un thread par le système
d'exploitation est moins coûteuse en ressources CPU que la création et la
gestion d'un processus. Les threads sont utilisés pour de petites tâches,
tandis que les processus sont utilisés pour des tâches plus lourdes,
essentiellement l'exécution d'applications.
 Les threads d'un même processus partagent l'espace d'adressage et
d'autres ressources, tandis que les processus sont indépendants les uns des
autres.
Avant d'examiner en détail les caractéristiques et fonctionnalités des
modules Python pour la gestion du parallélisme via les threads et les
processus, regardons d'abord comment le langage de programmation Python
fonctionne avec ces deux entités.
Commencer à travailler avec des processus en Python
Sur les systèmes d'exploitation courants, chaque programme s'exécute dans
son propre processus. Habituellement, nous démarrons un programme en
double-cliquant sur le programme de l'icône ou en le sélectionnant dans un
menu. Dans cette logique, nous montrons simplement comment démarrer un
nouveau programme unique à partir d'un programme Python.
Un processus a sa propre adresse d'espace, sa pile de données et d'autres
données auxiliaires pour suivre l'exécution ; le système d'exploitation gère
l'exécution de tous les processus, gérant l'accès aux ressources de calcul du
système via une procédure d'ordonnancement.
Parallélisme basé sur les threads
(Jupyter Notebook)
Parallélisme basé sur les threads
Dans ce chapitre, nous aborderons les recettes suivantes :

 Comment utiliser le module de thread Python

 Comment définir un thread

 Comment déterminer le thread actuel

 Comment utiliser un thread dans une sous-classe

 Synchronisation des threads avec Lock et Rlock

 Synchronisation des threads avec les sémaphores

 Synchronisation des threads avec une condition

 Synchronisation des threads avec un événement

 Comment utiliser l'instruction with

 Communication de thread à l'aide d'une file d'attente

 Évaluation des performances des applications multithread

 La criticité de la programmation multithread

Introduction
Actuellement, le paradigme de programmation le plus largement utilisé

pour la gestion de la concurrence dans les applications logicielles est

basé sur le multithreading. En règle générale, une application est créée

par un processus unique divisé en plusieurs threads indépendants, qui

représentent des activités de différents types qui s'exécutent en parallèle

et se font concurrence. Bien qu'un tel style de programmation puisse

entraîner des inconvénients d'utilisation et des problèmes à résoudre, les

applications modernes avec le mécanisme de multithreading sont encore

largement utilisées.
Pratiquement, tous les systèmes d'exploitation existants prennent en charge

le multithreading, et dans presque tous les langages de programmation, il

existe des mécanismes que vous pouvez utiliser pour implémenter des

applications simultanées grâce à l'utilisation de threads. Par conséquent, la

programmation multithread est définitivement un bon choix pour réaliser

des applications concurrentes. Cependant, ce n'est pas le seul choix

disponible - il existe plusieurs autres alternatives, dont certaines, entre

autres, fonctionnent mieux sur la définition de thread. Un thread est un flux

d'exécution indépendant qui peut être exécuté parallèlement et

simultanément avec d'autres threads du système.

Plusieurs threads peuvent partager des données et des ressources, tirant parti

de ce que l'on appelle l'espace d'informations partagées. L'implémentation

spécifique des threads et des processus dépend du système d'exploitation sur

lequel vous envisagez d'exécuter l'application, mais, en général, on peut dire

qu'un thread est contenu à l'intérieur d'un processus et que différents threads

dans les mêmes conditions de processus partagent certaines ressources .

Contrairement à cela, différents processus ne partagent pas leurs propres

ressources avec d'autres processus.

Chaque thread semble être principalement composé de trois éléments :

compteur de programme, registres et pile. Les ressources partagées avec

d'autres threads du même processus incluent essentiellement les données et

les ressources du système d'exploitation. Semblable à ce qui arrive aux

processus, même les threads ont leur propre état d'exécution et peuvent se

synchroniser les uns avec les autres. Les états d'exécution d'un thread sont

généralement appelés prêt, en cours d'exécution et bloqué.

Une application typique d'un thread est certainement la parallélisation d'un

logiciel d'application, en particulier pour tirer parti des processeurs multicœurs

modernes, où chaque cœur peut exécuter un seul thread. L'avantage des threads

sur l'utilisation de processus réside dans les performances, car le changement

de contexte entre processus s'avère beaucoup plus lourd que le changement de

contexte entre threads appartenant au même processus. La programmation

multithread privilégie une méthode de communication entre threads utilisant

l'espace d'informations partagées. Ce choix nécessite que le problème majeur à

résoudre par la programmation avec les threads soit lié à la gestion de cet

espace.
Utilisation du module de thread Python
Python gère un thread via le package de threading fourni par la bibliothèque
standard Python. Ce module fournit des fonctionnalités très intéressantes qui
facilitent grandement l'approche basée sur les threads. en fait, le module de
threading fournit plusieurs des mécanismes de synchronisation très simples à
mettre en oeuvre. Les principaux composants du module de threading sont :
 The thread object
 The Lock object
 The RLock object
 The semaphore object
 The condition object
 The event object
Comment définir un thread
La façon la plus simple d'utiliser un thread est de l'instancier avec une
fonction cible, puis d'appeler la méthode start() pour lui permettre de
commencer son travail. Le threading du module Python a la méthode
Thread() qui est utilisée pour exécuter des processus et des fonctions dans un
thread différent :
class threading.Thread(group=None,
target=None,
name=None,
args=(),
kwargs={})
Comment définir un thread
Dans le code précédent :
Il est utile de générer un thread et de lui transmettre des arguments qui lui
indiquent ce qu'il doit faire. Cet exemple passe un nombre, qui est le numéro de
thread, puis imprime le résultat.
 group : il s'agit de la valeur du groupe qui doit être 0
 Target : il s'agit de la fonction qui doit être exécutée lorsque vous démarrez
une activité de thread
 name : C'est le nom du thread ; par défaut, un nom unique de la forme
Thread-N lui est attribué
 args : il s'agit du tuple d'arguments à transmettre à une cible.
 kwargs : il s'agit du dictionnaire des arguments de mots clés à utiliser pour
la fonction cible
Il est utile de générer un thread et de lui transmettre des arguments qui lui
indiquent ce qu'il doit faire. Cet exemple passe un nombre, qui est le numéro de
thread, puis imprime le résultat.
Comment faire…
Voyons comment définir un thread avec le module threading, pour cela,
quelques lignes de code sont nécessaires :
Comment faire…
Pour importer le module de threading, nous utilisons simplement la
commande Python :
Import thread
Dans le programme principal, nous instancions un thread, en utilisant l'objet
Thread avec une fonction cible appelée fonction. De plus, nous passons un
argument à la fonction qui sera incluse dans le message de sortie :
t = threading.Thread(target=fonction , args=(i,))
Le thread ne commence pas à s'exécuter tant que la méthode start() n'est pas
appelée, et que join() fait attendre le thread appelant jusqu'à ce que le thread
ait terminé l'exécution :
t.start()
t.join()
Comment déterminer le thread en cours
L'utilisation d'arguments pour identifier ou nommer le thread est fastidieuse
et inutile. Chaque instance de Thread a un nom avec une valeur par défaut
qui peut être modifiée lors de la création du thread. Nommer les threads est
utile dans les processus serveur avec plusieurs threads de service qui gèrent
différentes opérations.
Comment faire…
Pour déterminer quel thread est en cours d'exécution, nous créons trois
fonctions cibles et importons le module de temps pour introduire une
suspension d'exécution de deux secondes :
Comment utiliser un thread dans une sous-classe

Pour implémenter un nouveau thread à l'aide du module de threading, vous

devez procéder comme suit :
 Définir une nouvelle sous-classe de la classe Thread
 Remplacez la méthode _init__(self [,args]) pour ajouter des arguments
supplémentaires
 Ensuite, vous devez remplacer la méthode run(self [,args]) pour
implémenter ce que le thread doit faire lorsqu'il est démarré
Une fois que vous avez créé la nouvelle sous-classe Thread, vous pouvez en
créer une instance, puis démarrer un nouveau thread en appelant la méthode
start(), qui, à son tour, appellera la méthode run().
Comment faire…
Le module de threading est la forme préférée pour créer et gérer les threads.
Chaque thread est représenté par une classe qui étend la classe Thread et
remplace sa méthode run(). Ensuite, cette méthode devient le point de départ
du fil. Dans le programme principal, nous créons plusieurs objets de type
myThread ; l'exécution du thread commence lorsque la méthode start()
est appelé. L'appel du constructeur de la classe Thread est obligatoire - en
l'utilisant, nous pouvons redéfinir certaines propriétés du thread en tant que
nom ou groupe du thread. Le thread est placé dans l'état actif de l'appel à
start() et y reste jusqu'à ce qu'il termine la méthode run() ou que vous lui
lanciez une exception non gérée. Le programme se termine lorsque tous les
threads sont terminés. La commande join() gère uniquement la terminaison
des threads.
Synchronisation des threads avec Lock et RLock
Lorsque deux opérations ou plus appartenant à des threads concurrents
tentent d'accéder à la mémoire partagée et qu'au moins l'une d'entre elles a le
pouvoir de modifier l'état des données sans mécanisme de synchronisation
approprié, une condition de concurrence peut se produire et produire une
exécution de code invalide et des bogues. et un comportement inattendu. Le
moyen le plus simple de contourner les conditions de course est l'utilisation
d'un cadenas. Le fonctionnement d'une serrure est simple ; quand un fil veut
accéder à une partie de la mémoire partagée, il doit nécessairement acquérir
un verrou sur cette partie avant de l'utiliser. De plus, après avoir terminé son
opération, le thread doit libérer le verrou obtenu précédemment afin qu'une
partie de la mémoire partagée soit disponible pour tout autre thread qui
souhaite l'utiliser.
De cette manière, il est évident que l'impossibilité d'encourir des courses est
critique car le besoin du verrou pour le thread nécessite qu'à un instant
donné, seul un thread donné puisse utiliser cette partie de la mémoire
partagée. Malgré leur simplicité, l'utilisation d'une serrure fonctionne.
Cependant, en pratique, nous pouvons voir comment cette approche peut
souvent conduire l'exécution à une mauvaise situation de blocage. Un
blocage se produit en raison de l'acquisition d'un verrou à partir de différents
threads ; il est impossible de procéder à l'exécution des opérations puisque
les différents verrous entre eux bloquent l'accès aux ressources.
Synchronisation des threads avec Lock et RLock
Par souci de simplicité, imaginons une situation dans laquelle il y a deux
threads simultanés (Thread A et Thread B) qui ont à leur disposition les
ressources 1 et 2. Supposons que le Thread A nécessite la ressource 1 et que
le Thread B nécessite la ressource 2. Dans ce cas , les deux threads
nécessitent leur propre verrou et jusqu'à présent, tout se déroule sans
problème. Imaginez, cependant, que par la suite, avant de libérer le verrou,
le thread A nécessite un verrou sur la ressource 2 et le thread B nécessite un
verrou sur la ressource 1, qui est maintenant nécessaire pour les deux
processus. Puisque les deux ressources sont verrouillées, les deux threads
sont bloqués et attendent l'un l'autre jusqu'à ce que la ressource occupée soit
libérée. Cette situation est l'exemple le plus emblématique de la survenance
d'une situation de blocage.
Comme dit, donc, montrer l'utilisation de verrous pour assurer la
synchronisation afin que vous puissiez accéder à la mémoire partagée d'une
part est une solution de travail, mais, d'autre part, elle est potentiellement
destructrice dans certains cas. Dans cette recette, nous décrivons le
mécanisme de synchronisation des threads Python appelé lock(). Cela nous
permet de restreindre l'accès d'une ressource partagée à un seul thread ou à
un seul type de thread à la fois. Avant d'accéder à la ressource partagée du
programme, le thread doit acquérir le verrou et doit ensuite autoriser tout
autre thread à accéder à la même ressource.
Comment faire…
L'exemple suivant montre comment vous pouvez gérer un thread via le
mécanisme de lock(). Dans ce code, nous avons deux fonctions : incrément()
et décrément(), respectivement. La première fonction incrémente la valeur de
la ressource partagée, tandis que la seconde fonction décrémente la valeur,
où chaque fonction est insérée dans un thread approprié. En plus de cela,
chaque fonction a une boucle dans laquelle l'augmentation ou la diminution
est répétée. Nous voulons nous assurer, grâce à la bonne gestion des
ressources partagées, que le résultat de l'exécution est égal à la valeur de la
variable partagée qui est initialisée à zéro. L'exemple de code est illustré ci-
dessous, où chaque fonctionnalité dans le l'exemple de code est correctement
commenté :
How to do it…
The following example demonstrates how you can manage a thread through
the mechanism of lock().

Voir le lien GitHub

Processus vs Thread n python
Processus vs Thread n python
Processus vs Thread n python

Le Python Global Interpreter Lock ou GIL, en termes simples, est un

mutex (ou un verrou) qui permet à un seul thread de détenir le contrôle
de l'interpréteur Python. Cela signifie qu'un seul thread peut être en état
d'exécution à tout moment. L'impact du GIL n'est pas visible pour les
développeurs qui exécutent des programmes à un seul thread, mais il
peut constituer un goulot d'étranglement des performances dans le code
lié au processeur et multithread. Étant donné que le GIL ne permet qu'à
un seul thread de s'exécuter à la fois, même dans une architecture
multithread avec plus d'un cœur de processeur, le GIL a acquis la
réputation d'être une fonctionnalité "infâme" de Python.
Processus vs Thread n python
Bibliographies

Pratique en Python