Le concept de calcul parallèle est un schéma organisationnel général. Systèmes informatiques parallèles
Processus et systèmes informatiques parallèles (Leçon 13)
Types de parallélisme
Le traitement parallèle des données est de deux types : pipeline et parallélisme réel.
Traitement parallèle. Si un certain appareil effectue une opération par unité de temps, il effectuera alors mille opérations en mille unités. Si nous supposons qu'il existe cinq appareils indépendants identiques capables de fonctionner simultanément, alors un système de cinq appareils peut effectuer les mêmes milliers d'opérations non pas en mille, mais en deux cents unités de temps.
Traitement du convoyeur. Que faut-il pour en ajouter deux nombres réels, représenté sous forme de virgule flottante ? Tout un tas de petites opérations comme comparer les commandes, aligner les commandes, ajouter des mantisses, normaliser, etc. Les processeurs des premiers ordinateurs effectuaient toutes ces « micro-opérations » pour chaque paire d’arguments, l’une après l’autre, jusqu’à atteindre le résultat final, et ensuite seulement ils procédaient au traitement de la paire de termes suivante. L'idée du traitement par pipeline est d'isoler les étapes individuelles de l'exécution d'une opération générale, et chaque étape, après avoir terminé son travail, transmettrait le résultat à la suivante, tout en recevant simultanément une nouvelle partie des données d'entrée. Il y a un gain évident en vitesse de traitement dû à la combinaison d'opérations préalablement espacées. Supposons qu'une opération comporte cinq micro-opérations, chacune étant effectuée en une unité de temps. S'il existe un périphérique série indivisible, il traitera alors 100 paires d'arguments en 500 unités. Si chaque micro-opération est séparée en une étape distincte (ou autrement appelée étape) d'un dispositif de convoyage, alors sur la cinquième unité de temps, à différentes étapes de traitement d'un tel dispositif, les cinq premières paires d'arguments seront localisées , et l'ensemble complet de cent paires sera traité en 5 + 99 = 104 unités de temps - l'accélération par rapport à un périphérique série est presque cinq fois (en fonction du nombre d'étages du pipeline).
Il semblerait que le traitement du pipeline puisse être remplacé avec succès par le parallélisme ordinaire, pour lequel nous dupliquons le dispositif principal autant de fois que le nombre d'étages du pipeline est censé être alloué. Mais en multipliant par cinq le nombre d'appareils, nous augmentons considérablement à la fois le volume des équipements et leur coût.
Implémentation de systèmes parallèles
Les performances des ordinateurs ont augmenté de façon exponentielle depuis 1945 jusqu’à aujourd’hui (sur la base d’une moyenne tous les 10 ans). L'architecture informatique a subi des changements importants, passant du série au parallèle.
Les performances de l'ordinateur sont directement liées au temps nécessaire pour exécuter les fonctions de base et au nombre de ces opérations de base pouvant être effectuées simultanément. Le temps d'exécution d'une instruction simple est finalement limité.
Il est facile de conclure qu'on ne peut pas se limiter à augmenter la vitesse uniquement au détriment de la vitesse d'horloge du processeur. La dépendance aux processeurs conduit finalement à une impasse. Une autre stratégie dans ce domaine consiste à utiliser le parallélisme interne dans la puce du processeur. Mais une telle technologie coûte très cher. Les supercalculateurs modernes reposent en grande partie sur l’idée d’utiliser un grand nombre de processeurs relativement peu coûteux déjà disponibles.
Cela inclut également des systèmes tels que : des superordinateurs équipés de milliers de processeurs ; réseaux de postes de travail; postes de travail multiprocesseurs, etc.
Multi-ordinateur - c'est un certain montant Machines de von Neumann(nœuds) interconnectés par un réseau. Chaque ordinateur exécute son propre programme. Ces programmes peuvent accéder à la mémoire locale et envoyer et recevoir des messages sur le réseau. Les messages utilisés pour la communication entre ordinateurs sont équivalents à des opérations de lecture ou d'écriture à partir de la mémoire distante. Dans un réseau idéalisé, le délai de livraison d'un message entre machines ne dépend pas de la distance entre les nœuds ou du trafic réseau, mais dépend de la longueur de la lettre envoyée.
Le paramètre déterminant du modèle multi-ordinateurs est que l’accès à la mémoire locale (même nœud) est moins coûteux que l’accès à la mémoire distante (située dans un autre nœud). Ceux. Les opérations de lecture et d’écriture sont moins coûteuses que l’envoi ou la réception de messages. Il est donc souhaitable que les données locales soient consultées beaucoup plus fréquemment que les données distantes. Cette propriété fondamentale du logiciel s’appelle la localité. La valeur de la localité dépend du rapport entre le coût de l'accès à distance et celui de l'accès local.
Autres modèles de voitures. Examinons les architectures informatiques les plus importantes. Un multi-ordinateur est très similaire à ce que l'on appelle souvent un ordinateur à mémoire distribuée MIMD (Multiple Instruction Multiple Data). MIMD signifie que chaque processeur peut traiter un flux d'instructions distinct sur ses propres données locales. La mémoire distribuée signifie que la mémoire est répartie entre les processeurs. La différence fondamentale entre un ordinateur MIMD et un multi-ordinateur est que le coût de transmission d'un message entre deux nœuds ne dépend pas de l'emplacement du nœud et du trafic réseau. Les principaux représentants de cette classe : IBM SP, Intel Paragon, Thinking Machines CM 5, Cray T 3D, Meiko CS-2 et CUBE.
Une autre classe de supercalculateurs est l’ordinateur multiprocesseur ou à mémoire partagée MIMD. Dans un multiprocesseur, tous les processeurs partagent l'accès à une mémoire commune, généralement via un bus ou via une hiérarchie de bus. Dans un modèle idéalisé de machine à accès aléatoire parallèle (PRAM), utilisant souvent des algorithmes parallèles étudiés théoriquement, n'importe quel processeur peut accéder à n'importe quel élément de mémoire en même temps. Cette architecture implique généralement une forme spéciale de périphérique de mémoire. Le nombre d'accès à la mémoire partagée est réduit en stockant des copies des données fréquemment consultées dans un cache associé à chaque processeur.
L'accès à ce cache est beaucoup plus rapide que l'accès à la mémoire partagée, la localité est donc très importante. Les programmes conçus pour plusieurs ordinateurs peuvent fonctionner tout aussi efficacement sur des multiprocesseurs car la mémoire partagée permet une transmission efficace des messages. Les représentants de cette classe sont Silicon Graphics Challenge, Sequent Symmetry et de nombreux postes de travail multiprocesseurs.
Une classe plus spécialisée d'ordinateurs parallèles sont les ordinateurs SIMD (Single Instruction Miltiple Data). Dans les machines SIMD, tous les processeurs fonctionnent avec le même flux d'instructions sur différents éléments de données. Cette approche peut réduire la complexité des logiciels et matériel, mais cela n'a de sens que pour des problèmes spécialisés caractérisés par un haut degré de régularité, comme le traitement d'images et certains types de modélisation numérique. Les algorithmes applicables sur plusieurs ordinateurs ne peuvent, en général, pas être exécutés efficacement sur des ordinateurs SIMD.
Systèmes neuroinformatiques.
Un appareil de neuroinformatique est un système dont le fonctionnement est axé au maximum sur la mise en œuvre d'algorithmes de réseaux neuronaux. La principale différence entre les neuroordinateurs et les autres systèmes informatiques réside dans la fourniture d'un parallélisme élevé des calculs grâce à l'utilisation d'une base logique de réseau neuronal spécialisé ou de solutions architecturales spécifiques. Utiliser la capacité de représenter des algorithmes de réseau neuronal pour les mettre en œuvre sur une base logique de réseau neuronal est la principale condition préalable à une forte augmentation des performances des neuroordinateurs.
Actuellement, le développement des neuroordinateurs numériques s'effectue le plus activement dans les domaines suivants :
· émulation logicielle d'algorithmes de réseaux neuronaux basée sur l'utilisation de méthodes conventionnelles installations informatiques et logiciels de modélisation de réseaux neuronaux ;
· émulation logicielle et matérielle de réseaux neuronaux basée sur des outils informatiques standards avec une unité de réseau neuronal virtuel enfichable qui effectue des neuroopérations de base et un logiciel qui exécute des fonctions de contrôle générales ;
· implémentation matérielle des réseaux de neurones.
Malgré le fait que le plus grand effet dans la mise en œuvre des algorithmes de réseaux neuronaux ne peut être obtenu qu'avec l'utilisation de neuroordinateurs de troisième direction, leur utilisation généralisée est limitée par la haute technologie. Par exemple, le neuroordinateur Synaps1 est l'un des représentants des neuroordinateurs de la troisième direction, possède une architecture multiprocesseur, une conception originale du sous-système de mémoire et utilise des processeurs de signaux et des processeurs matriciels de signaux spéciaux MA16 pour effectuer des opérations de calcul. De ce fait, les performances du neuroordinateur s'élevaient à plusieurs milliards de multiplications et d'additions par seconde. Logiciel Ce système comprend l'OS Synaps1 avec une bibliothèque de neuroalgorithmes, ainsi que des logiciels : une bibliothèque NS de base, un compilateur pour le langage de programmation de neuroalgorithmes (nAPL) (un ensemble de fonctions de bibliothèque pour C++), etc. La recherche appliquée a montré que l'utilisation de neuroordinateurs de troisième direction permet d'augmenter les performances des systèmes informatiques conventionnels d'au moins trois ordres de grandeur et de simuler des réseaux de neurones comportant des millions de connexions. Par exemple, Synaps1 vous permet de simuler un réseau neuronal avec 64 millions de synapses en utilisant diverses fonctions d'activation.
Deux classes de systèmes informatiques parfois utilisés comme ordinateurs parallèles sont le réseau local(LAN), dans lequel les ordinateurs situés à proximité physique (par exemple, le même bâtiment) sont connectés par un réseau rapide, et réseau mondial(WAN), dans lequel géographiquement connecté ordinateurs distants. Bien que les systèmes de ce type posent des problèmes supplémentaires tels que la sécurité et la fiabilité, ils peuvent être considérés à diverses fins comme des multi-ordinateurs, bien qu'à un coût élevé. accès à distance.
Difficultés d'utilisation de systèmes parallèles
Les énormes performances des ordinateurs et supercalculateurs parallèles sont plus que compensées par les difficultés de leur utilisation.
Vous disposez d'un programme et d'un accès, disons, à un ordinateur à 256 processeurs. Qu'attendez-vous ? Oui, c'est clair : on s'attend tout à fait légitimement à ce que le programme s'exécute 256 fois plus vite que sur un seul processeur. Mais c’est précisément ce qui n’arrivera probablement pas.
La loi d'Amdahl. Supposons que dans un programme la fraction des opérations qui doivent être effectuées séquentiellement soit égale à f, où 0<=f <=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам. Тогда для того, чтобы оценить, какое ускорение S может быть получено на компьютере из "p" процессоров при данном значении f, можно воспользоваться законом Амдала: если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (10 получается только в том случае, когда время исполнения параллельной части равно 0).
Conséquence de la loi d'Amdahl. Afin d'accélérer l'exécution d'un programme de q fois, il est nécessaire d'accélérer au moins q fois pas moins que la (1-1/q)ème partie du programme. Par conséquent, si vous souhaitez accélérer un programme 100 fois par rapport à sa version séquentielle, alors vous ne devez pas obtenir moins d'accélération pour au moins 99,99 % du code !
Ainsi, faire fonctionner un système informatique parallèle avec une efficacité maximale sur un programme spécifique n'est pas une tâche facile, car il est nécessaire de coordonner soigneusement la structure des programmes et des algorithmes avec les caractéristiques architecturales des systèmes informatiques parallèles.
Programmation de systèmes parallèles
Le modèle de machine de von Neumann suppose que le processeur exécute une séquence d'instructions. Les instructions peuvent spécifier, en plus de diverses opérations arithmétiques, les adresses des données à lire/écrire en mémoire et/ou l'adresse de la prochaine instruction à exécuter. Bien qu'il ne soit possible de programmer un ordinateur qu'en fonction de ce modèle de base, cette méthode est d'une complexité prohibitive dans la plupart des cas, car nous devons suivre des millions de positions mémoire et orchestrer l'exécution de milliers d'instructions machine. Par conséquent, une technique de conception modulaire est appliquée, dans laquelle des programmes complexes sont créés à partir de composants simples, et les composants sont structurés en termes d'abstractions de niveau supérieur (telles que des structures de données, des boucles et des procédures itératives). Les abstractions (par exemple les procédures) facilitent l'exploitation de la modularité en permettant aux objets d'être manipulés sans perturber leur structure interne. C'est ainsi que sont créés les langages de haut niveau, comme Fortran, C, Ada et Java, qui permettent de développer en fonction de ces abstractions, qui sont automatiquement traduites en code exécutable. La programmation parallèle introduit des sources supplémentaires de complexité : si l’on doit programmer au niveau le plus bas, il faut non seulement augmenter le nombre d’instructions exécutées, mais aussi gérer l’exécution de milliers de processeurs et coordonner des millions de communications interprocesseurs. Par conséquent, l’abstraction et la modularité sont au moins aussi importantes que dans la programmation séquentielle. En fait, nous soulignons la modularité comme la quatrième exigence fondamentale des logiciels parallèles, en plus du parallélisme, de l’évolutivité et de la localité.
Les principales abstractions utilisées en programmation parallèle se résument aux tâches et aux canaux :
1.L'informatique parallèle consiste en une ou plusieurs tâches. Les tâches sont exécutées en parallèle. Le nombre de tâches peut changer pendant l'exécution du programme.
2.La tâche isole le programme séquentiel et la mémoire locale. De plus, un ensemble d'entrées et de sorties définit son interface dans son environnement.
3. Une tâche peut effectuer quatre actions de base en plus de la lecture et de l'écriture dans la mémoire locale : envoyer un message à ses ports de sortie, recevoir un message de ses ports d'entrée, créer de nouvelles tâches et détruire (terminer) une tâche.
4.L'opération d'envoi d'un message est asynchrone et se termine immédiatement. L'opération de réception est synchrone et provoque l'exécution d'une tâche, bloquant le processus jusqu'à ce que le message soit reçu.
5.Les paires d'E/S peuvent être liées par des messages en file d'attente appelés canaux. Des canaux peuvent être créés et supprimés, et des références aux canaux (ports) peuvent être incluses dans les messages afin que la connectivité change de manière dynamique.
6. Les tâches peuvent être mappées sur des processeurs physiques de différentes manières ; l'application d'affichage n'affecte pas la sémantique du programme. Plus précisément, plusieurs tâches peuvent être mappées sur un seul processeur (on pourrait également imaginer qu'une seule tâche puisse être mappée sur plusieurs processeurs, mais cette possibilité n'est pas prise en compte ici.)
L'abstraction des tâches nécessite la propriété de localité : les données contenues dans la mémoire locale de la tâche sont « fermées » ; les autres données sont « supprimées ». L'abstraction de canal fournit un mécanisme permettant de spécifier quelles données d'une tâche doivent être calculées avant qu'une autre tâche puisse commencer à s'exécuter. (Ceci est caractérisé par la dépendance aux données). Le modèle de tâche et de canal possède également d'autres propriétés :
Performance . Les abstractions de programmation séquentielle, telles que les procédures et les structures de données, sont efficaces car elles peuvent être mappées simplement et efficacement sur un ordinateur von Neumann. Les tâches et les canaux ont une distribution tout aussi directe dans un multi-ordinateur. Une tâche représente un morceau de code pouvant être exécuté séquentiellement sur un seul processeur. Si deux tâches partageant un canal sont mappées sur d'autres processeurs, la connexion de canal est implémentée en tant que connexion interprocesseur ; s'ils sont mappés sur le même processeur, des mécanismes plus efficaces peuvent être utilisés.
Indépendance de distribution . Puisque les tâches communiquent en utilisant le même mécanisme (canaux) quel que soit l'emplacement de la tâche, le résultat calculé par le programme ne dépend pas de l'endroit où la tâche est exécutée. Par conséquent, les algorithmes peuvent être conçus et implémentés sans se soucier du nombre de processeurs sur lesquels ils fonctionneront ; en fait, les algorithmes sont souvent conçus pour créer beaucoup plus de tâches que les processeurs. Il s’agit d’un moyen simple d’atteindre une grande échelle : à mesure que le nombre de processeurs augmente, le nombre de tâches par processeur diminue, mais l’algorithme lui-même n’a pas besoin d’être modifié. Lorsqu'il y a plus de tâches que ce que les processeurs peuvent gérer pour masquer les retards de communication, d'autres calculs sont fournis et peuvent être effectués pendant que la communication est en cours pour accéder aux données distantes.
Modularité. Dans la programmation modulaire, différents composants du programme sont développés séparément en tant que modules indépendants, puis combinés pour former un programme complet. L'interaction entre les modules est limitée à des interfaces clairement définies. Par conséquent, les implémentations modulaires peuvent être modifiées sans modifier les autres composants, et les propriétés d'un programme peuvent être déterminées à partir de la spécification de ses modules et du code qui connecte ces modules entre eux. Lorsque le développement modulaire est appliqué avec succès, la complexité du logiciel est réduite et la réutilisation du code est facilitée.
Déterminisme. Un algorithme ou un programme est déterministe si, lorsqu'il est exécuté avec une entrée spécifique, il produit toujours la même sortie. Il n’est pas déterministe si plusieurs exécutions de la même entrée peuvent produire une sortie différente. Bien que le non-déterminisme soit parfois utile et doive être pris en charge, un modèle de programmation parallèle facilitant l'écriture de programmes déterministes est hautement souhaitable. Les programmes déterministes ont tendance à être plus compréhensibles. De plus, lors de la vérification de l'exactitude, une seule séquence d'exécution d'un programme parallèle doit être calculée, et non toutes les séquences d'exécution possibles.
La version actuelle de la page n'a pas encore été vérifiée
La version actuelle de la page n'a pas encore été vérifiée par des participants expérimentés et peut différer considérablement de la version vérifiée le 5 octobre 2014 ; des contrôles sont nécessaires.
Traitement en parallèle- une méthode d'organisation de l'informatique, dans laquelle des programmes sont développés comme un ensemble de processus informatiques interactifs exécutés en parallèle (simultanément). Le terme couvre un ensemble de problèmes de parallélisme dans la programmation, ainsi que la création d'implémentations matérielles efficaces. La théorie du calcul parallèle constitue une branche de la théorie appliquée des algorithmes.
Il existe différentes manières de mettre en œuvre le calcul parallèle. Par exemple, chaque processus informatique peut être implémenté en tant que processus de système d'exploitation, ou les processus informatiques peuvent être un ensemble de threads d'exécution au sein d'un seul processus de système d'exploitation. Les programmes parallèles peuvent être exécutés physiquement soit séquentiellement sur un seul processeur - en alternant tour à tour les étapes de chaque processus de calcul, soit en parallèle - en allouant un ou plusieurs processeurs (situés à proximité ou répartis dans un réseau informatique) à chaque processus de calcul.
La principale difficulté de la conception de programmes parallèles est d’assurer la bonne séquence d’interactions entre les différents processus informatiques, ainsi que la coordination des ressources partagées entre les processus.
Dans certains systèmes de programmation parallèle, le transfert de données entre composants est caché au programmeur (par exemple, à l'aide d'un mécanisme de promesse), tandis que dans d'autres, il doit être spécifié explicitement. Les interactions explicites peuvent être divisées en deux types :
Les systèmes parallèles de transmission de messages sont souvent plus faciles à comprendre que les systèmes à mémoire partagée et sont généralement considérés comme une méthode supérieure de programmation parallèle. Il existe un large éventail de théories mathématiques pour l'étude et l'analyse des systèmes de transmission de messages, notamment le modèle de l'acteur et divers types de calcul de processus. La messagerie peut être efficacement implémentée sur des multiprocesseurs symétriques avec ou sans mémoire cohérente partagée.
Le parallélisme de la mémoire distribuée et le parallélisme de transmission de messages ont des caractéristiques de performances différentes. Généralement (mais pas toujours), la surcharge de mémoire de processus et le temps de commutation des tâches sont inférieurs pour les systèmes de transmission de messages, mais la transmission de messages est plus coûteuse que les appels de procédure. Ces différences sont souvent éclipsées par d’autres facteurs qui affectent les performances.
Plaksin M.A.
École supérieure d'économie de l'Université nationale de recherche (branche de Perm), Perm, Ph.D., professeur agrégé du Département des technologies de l'information en entreprise, mapl @ list. ru
"SUPERORDINATEURS" VS "PROGRAMMATION PARALLÈLE". « PROGRAMMATION PARALLÈLE » VS « ACTIVITÉ COLLABORATIVE ». COMMENT ÉTUDIER LE THÈME « INFORMATIQUE PARALLÈLE » AU SECONDAIRE ?
MOTS CLÉS
Informatique, programmation parallèle, calcul parallèle, algorithmes parallèles, supercalculateurs, école primaire, lycée, TRIZformashka.
ANNOTATION
L'article est consacré à la question de l'inclusion du thème « informatique parallèle » dans le cours d'informatique scolaire. Un certain nombre de problèmes qui se posent dans ce cas sont mentionnés, le but de l'étude du sujet, la sélection du matériel, certaines propositions de méthodes d'enseignement, les mécanismes de test de la méthodologie proposée et l'expérience accumulée sont pris en compte. La question de la place de ce matériel dans le curriculum n’est pas abordée.
Le stade actuel de développement de l'informatique est associé à la diffusion massive du parallélisme des calculs à tous les niveaux (clusters multi-machines, ordinateurs multiprocesseurs, processeurs multicœurs).
La diffusion massive du parallélisme a de graves conséquences qui restent encore à identifier et à analyser. Commençons par énumérer quelques problèmes théoriques.
La théorie moderne des algorithmes a été créée avec le concept d’algorithme séquentiel à l’esprit. Comment le refus d’exiger une séquence d’étapes affectera-t-il le concept d’algorithme ?
Depuis au moins 20 ans, la notion d'« algorithme » a été introduite dans les écoles, inextricablement liée à la notion d'« interprète ». C'est naturel pour un algorithme séquentiel. Que faire avec un algorithme parallèle ? Est-il interprété par un seul artiste ou un groupe d’artistes ? Pour être plus précis, prenons comme exemple le programme de formation informatique « Tank Crew ». Dans ce programme, l'étudiant doit programmer les actions d'un équipage de char composé de trois personnes : un tireur, un conducteur et un chargeur. Chacun d'eux possède son propre système de commandement. Afin d'accomplir une mission de combat (atteindre toutes les cibles), tous les membres de l'équipage doivent agir de concert. Pour un exemple du terrain de jeu du programme Tank Crew, voir la Fig. 1.
Question : ces trois acteurs doivent-ils être considérés comme des interprètes indépendants ou comme trois composants (dispositifs) d’un même interprète complexe ? Pour l'équipage du char, la deuxième option semble plus naturelle, puisqu'aucun personnage n'est capable d'accomplir la tâche par lui-même. Mais que se passe-t-il si le jeu devient plus compliqué et qu'une mission de combat est assignée à deux chars à la fois ? Pour trois réservoirs ? Trois membres d’un même équipage peuvent très bien être considérés comme trois parties d’un même artiste. Mais chaque équipage est évidemment un artiste indépendant. Cela signifie qu'un algorithme parallèle pour plusieurs chars sera exécuté par un groupe d'exécuteurs à la fois. Il s'avère que pour un algorithme parallèle, il est nécessaire de considérer les deux possibilités : l'exécution d'actions parallèles par un exécuteur et par un groupe d'exécuteurs. Dans le cas d’un équipage de char, tracer la ligne est facile. L'interprète est celui qui est capable de résoudre la tâche. Cet exécuteur peut être constitué de plusieurs composants, chacun effectuant une certaine partie de la tâche, mais ne peut pas accomplir indépendamment l'intégralité de la tâche sans l'aide d'autres composants. Mais il est impossible de dire aujourd’hui si la séparation des « interprètes entiers » et des parties d’un interprète complexe sera toujours aussi simple.
Fichier 1*ra Fenêtre À propos du programme
Vpolyet tout
Bbno.n«fTb à la ligne en surbrillance
Revenir à la page initiale**"
apparaîtrait étape par étape (après avoir exécuté la « commande .order nesykoa^ » le bouton gV ygolg « n-b next uwr » sera enfoncé)
Ё ГГВД iTHWTt. étape spéciale
Informations étape par étape
Fig. 1. Fragment du terrain de jeu du programme Tank Crew
L'identification des parties de l'interprète capables d'actions indépendantes nécessite que ces parties soient nommées d'une manière ou d'une autre. De plus, le nom doit permettre la récursivité, puisque les parties agissantes de l'interprète elles-mêmes peuvent avoir une structure complexe.
Il est nécessaire de se mettre d’accord sur un terme pour désigner un groupe d’artistes coopératifs. Le terme « commande » ne convient pas, il est associé au « système de commandes de l'exécuteur » et aux « commandes du processeur central ». « Collectif d'artistes » ? « Brigade d'artistes » ?
Algorithme Sh.
n Frapper1"; Chargeur de conducteur
1 Mesurer orun* sur « master sgkll V Stop V Charge 1
g Pci V Arrêt V Charge 2
3 Vente en gros ! V Tourner à 90 degrés dans le sens des aiguilles d'une montre V Charger 1 V
L V V premier V Charge ? V
5 Feu ! V Arrêt V Charge 1
Í P^chm V St*p V Zaryasya ? V
7 Feu ! V Arrêt V Charge 1 V
3 Pa^ V Tourner dans le sens des aiguilles d'une montre de 45 degrés V Charge 2 V
S Pause V Démarrage V Pause V
10 Pvdea V Avance V Pause ¿d
11 Plrl V Avance V Pause V
12 Paum V Tourner dans le sens des aiguilles d'une montre de 45 degrés V Pause V
13 Padm V Avancer V Pause V
14 V
Fig.2. Fragment du programme du « Tank Crew » (exemple de lignes de commande) Le concept traditionnel du « système de commandement de l'exécuteur » (SCS) et le concept de l'équipe elle-même doivent être améliorés. Si nous pensons que trois membres de l'équipage d'un char forment un seul artiste, alors quel doit être considéré comme le SKI de cet artiste ? Et qu’est-ce qu’une équipe ? Ou laisser le concept de SKI pour chaque personnage ? C'est-à-dire qu'il ne s'agit plus d'un système de commandes de l'EXECUTEUR, mais d'un système de commandes de l'un des composants de l'interprète (pour lequel il n'y a pas encore de nom) ?
Il est pratique d’étendre le concept d’équipe à une « ligne de commandement ». Pour un exemple de lignes de commande d'équipage de char, voir la Fig. 2. Cependant, le concept de « ligne de commandes » ne fonctionne bien que pour les algorithmes linéaires. Dans d’autres cas, les règles sont formées dynamiquement. Il est impossible de les représenter sous forme de tableau visuel.
Parmi les propriétés des algorithmes, une nouvelle caractéristique pratiquement significative se démarque : la capacité de parallélisme. Une question de clarification concerne le degré possible de parallélisation (dans quelle mesure est-il judicieux d'augmenter le nombre de processeurs lors de l'exécution d'un algorithme donné).
Un autre problème concerne les méthodes de parallélisation des algorithmes séquentiels existants.
Jusqu'à récemment, la programmation parallèle était l'apanage d'un petit nombre de programmeurs système hautement qualifiés. Aujourd’hui, cela fait partie des compétences professionnelles. Mais la technologie de programmation parallèle diffère considérablement de la programmation séquentielle traditionnelle. À l’appui de cette affirmation, à la suite de L.L. Bosova, nous citerons le plus grand spécialiste russe dans le domaine du calcul parallèle V.V. Voïvodine :
« ... La maîtrise de la technologie informatique à architecture parallèle... par de jeunes spécialistes s'accompagne de grandes difficultés. À notre avis, cela est dû au fait que la connaissance de l'informatique parallèle, ainsi que l'éducation dans ce domaine en général, ne commencent pas par là où il faut commencer. De plus, ce dont vous avez besoin pour commencer n’est couvert dans aucun cours. La capacité de résoudre rapidement des problèmes à l'aide de la technologie informatique à architecture parallèle oblige les utilisateurs à modifier complètement leur style habituel d'interaction avec les ordinateurs. Par rapport, par exemple, aux ordinateurs personnels et aux postes de travail, presque tout change : d'autres langages de programmation sont utilisés, la plupart des algorithmes sont modifiés, les utilisateurs doivent fournir de nombreuses caractéristiques non standard et difficiles à obtenir des tâches à résoudre, l'interface cesse d'être conviviale, etc. Un fait important est que le fait de ne pas prendre pleinement en compte les nouvelles conditions d’exploitation peut réduire considérablement l’efficacité de l’utilisation d’équipements nouveaux et, de surcroît, assez coûteux.
« Il est seulement important que l'étudiant apprenne le plus tôt possible qu'il existe d'autres façons d'organiser les processus informatiques, et pas seulement l'exécution séquentielle « opération par opération », que la technologie informatique moderne la plus puissante est construite sur ces autres méthodes, que seule une telle technologie permet de résoudre des problèmes majeurs, des tâches industrielles et scientifiques, etc. Il est important, tout d’abord, d’attirer le plus tôt possible l’attention des étudiants sur la nécessité d’adopter une attitude critique à l’égard de la philosophie du calcul séquentiel. Après tout, c’est à cette philosophie qu’ils doivent faire face tout au long de leur formation, tant à l’école qu’à l’université. Et c’est précisément cette philosophie qui empêche la compréhension des caractéristiques du travail sur des ordinateurs à architecture parallèle.
Aujourd'hui, nous avons besoin de méthodes de formation de masse à la technologie de programmation parallèle. L'auteur de cet article estime que dans le processus d'apprentissage, le moment est venu de révolutionner la relation entre programmation séquentielle et parallèle. Jusqu'à présent, nous enseignions d'abord la programmation séquentielle, puis la parallélisation des algorithmes séquentiels. Il faut maintenant se poser d’emblée la question de l’enseignement de la programmation parallèle. Un algorithme séquentiel doit être considéré comme une certaine partie d'un algorithme parallèle, qui ne nécessite pas de communication avec ses autres parties. Comment procéder est une question ouverte. Certaines idées nécessitent encore une mise en œuvre et des tests pratiques. On espère que dans un an, lors de la prochaine conférence, il sera possible de discuter des résultats obtenus.
Il y a trente ans, le début de l'informatisation massive de la production nécessitait une augmentation du niveau de culture informatique de la population. Cela a conduit à l’introduction de l’informatique dans le programme scolaire en 1985. Mais le cours d'informatique dans la version soviétique (alors russe) ne se limitait pas à « l'informatique à bouton-poussoir » - à la maîtrise de la technologie permettant de travailler avec des progiciels d'application et des jeux informatiques. Il a commencé à changer le style de pensée de la jeune génération. Tout d’abord, cela concernait l’algorithmique, l’exactitude et la rigueur. Ensuite, le cours d'informatique a intégré des éléments de logique et d'analyse des systèmes. Par la suite, tout cela a grandement simplifié la distribution de technologies indispensables au 21e siècle. approche projet. On parle désormais du fait qu’au cours de la prochaine décennie, les algorithmes parallèles devraient devenir
élément de la culture générale de la pensée. Question : comment la maîtrise du concept d'algorithme parallèle affectera-t-elle la pensée de la prochaine génération, à quoi conduira la restructuration de la conscience « de manière parallèle » ?
La diffusion massive du traitement parallèle de l'information rend urgent le déplacement des concepts pertinents dans la catégorie des concepts culturels généraux et accessibles au public. La familiarité avec les algorithmes parallèles devrait faire partie de l’alphabétisation, tout comme les concepts de base de la théorie des algorithmes l’ont été au cours du dernier quart de siècle. Cela ne peut être fait que d'une seule manière : en incluant des sujets pertinents dans le cours d'informatique de l'école. Cela signifie que nous avons besoin d'une méthodologie pour une première connaissance de la programmation parallèle au niveau secondaire.
Historiquement, la première tentative d’inclure le thème du calcul parallèle dans un cours d’informatique scolaire a eu lieu il y a vingt ans. Il y a vingt ans, dans un cours intitulé « Algorithmique », on décrivait un « directeur de construction » qui commandait les actions parallèles de plusieurs équipes construisant une structure à partir de blocs rectangulaires et triangulaires. De plus, une implémentation logicielle a été créée pour cet artiste. Hélas! Ce merveilleux développement méthodologique n'était pas demandé au milieu des années 90. Elle avait presque vingt ans d’avance sur son temps !
Aujourd'hui, la situation est telle que le thème du calcul parallèle au lycée est principalement lié au thème des supercalculateurs. C'est sur les supercalculateurs que les auteurs de divers développements méthodologiques concentrent l'attention des étudiants, même lorsque cela n'est pas nécessaire. Il suffit de dire que la section correspondante de la revue « L'informatique à l'école » s'intitule « L'éducation des superordinateurs à l'école ». Cette situation a des côtés à la fois positifs et négatifs. Parmi les aspects positifs figurent :
Le thème des supercalculateurs intéresse la société, y compris les étudiants. Cet intérêt répète au niveau moderne l’intérêt suscité il y a un demi-siècle par les grandes machines – les supercalculateurs de leur époque ;
Soutien organisationnel de la communauté du calcul intensif. Chaque été, la Faculté de mathématiques computationnelles et de cybernétique de l'Université d'État de Moscou accueille la Summer Supercomputer Academy. Et chaque été, dans le cadre de cette Académie, un parcours scolaire destiné aux professeurs d'informatique est organisé. La formation est dispensée gratuitement. Les étudiants non-résidents bénéficient d'un logement à des conditions très avantageuses. Lors de la conférence Russian Supercomputing Days en septembre 2015, une section scolaire et une master class pour les professeurs d'informatique ont été organisées. Un travail d'organisation cohérent a conduit à l'identification et à la formation d'un groupe d'enseignants intéressés par la promotion de ce sujet ;
La présence d'un leader brillant et charismatique, tel que Vladimir Valentinovitch Voevodin - Docteur en sciences physiques et mathématiques, professeur, membre correspondant de l'Académie des sciences de Russie, directeur adjoint du Centre informatique de recherche de l'Université d'État de Moscou ;
Intérêt et soutien (y compris matériel) de la part du bureau de représentation russe d'Intel et du responsable du développement stratégique d'Intel, Igor Olegovich Odintsov.
L’inconvénient de l’approche « supercalculateur » est qu’elle restreint la portée du calcul parallèle. Les supercalculateurs eux-mêmes sont, en règle générale, inaccessibles aux écoliers (à moins que dans les grandes villes on ne puisse les voir lors d'excursions). Les tâches qu'ils visent à résoudre sont trop complexes pour les écoliers et, dans la plupart des cas, n'ont pas de signification pratique immédiate et n'ont pas d'intérêt pratique.
Une extension naturelle du domaine du calcul intensif est l’étude de la programmation parallèle. Actuellement, pour exécuter des programmes parallèles, il n’est pas du tout nécessaire de disposer d’un superordinateur. Un processeur multicœur ou une carte vidéo avec un ensemble d'accélérateurs graphiques suffit. Et cela est déjà accessible à presque tout le monde. Parmi les travaux allant dans ce sens, on note le mémoire de maîtrise du candidat. Sokolovskaya sur la méthodologie d'enseignement aux futurs professeurs d'informatique des bases de la programmation parallèle et de l'expérience d'E.Yu. Kiseleva sur la maîtrise de la technologie CUDA par les écoliers.
Selon l'auteur de cet article, se concentrer sur les supercalculateurs et la programmation parallèle appauvrit et complique considérablement le sujet du calcul parallèle et détourne les étudiants de nombreuses questions importantes et accessibles. Le but du sujet « parallèle
L'informatique » au lycée n'enseigne pas la « vraie » programmation parallèle (étudier les constructions linguistiques, les langages et les technologies de programmation pertinents), mais familiariser les étudiants avec l'ensemble de concepts correspondant et comprendre les caractéristiques du travail parallèle. Le monde qui nous entoure et à l’intérieur de nous est un système parallèle complexe. Et ce système lui-même fournit de nombreux éléments pour maîtriser les concepts et les mécanismes du parallélisme. Aucune structure artificielle complexe telle que les technologies MPI et OpenMP n'est nécessaire pour cela. L’informatique scolaire devrait favoriser la réflexion « de manière parallèle ». Et laissez ensuite l’université intégrer les connaissances, compétences et capacités professionnelles dans cette réflexion. À l'école, il est logique de se concentrer non pas sur la connaissance des supercalculateurs et l'étude de la programmation parallèle, mais sur la maîtrise des mécanismes d'« activité conjointe » qui sont constamment et largement utilisés dans la vie. Le cours propose d'aborder les questions suivantes :
1) Collaboration de plusieurs exécuteurs (creuser un fossé avec plusieurs creuseurs) et parallélisation « à l'intérieur » d'un exécuteur en présence de plusieurs dispositifs de traitement (lire et manger une pomme). En informatique, il s'agira d'un complexe multi-machines et d'un processeur multicœur.
2) Types de parallélisme : vrai parallélisme et pseudo-parallélisme (un processeur exécute plusieurs programmes par parties).
3) Artistes du même type (creuseurs) et de types différents (équipage de char).
4) Œuvres du même type et de types différents.
5) Le ratio « exécuteurs - travaux » : 1 exécutant - 1 travail, 1 exécutant - N travaux (exécution pseudo-parallèle ou véritable parallélisme en présence de plusieurs dispositifs de traitement pour des travaux différents), N exécutants - 1 travail, N exécutants - N emplois.
6) Coordination des activités des artistes interprètes ou exécutants. Types d'approbation : par parties de travail, par temps, par résultats d'activités, par ressources.
7) Ressources. Les ressources sont partagées et non partagées, consommables et réutilisables. Recyclage des ressources consommées (« garbage collection » au sens large).
8) Exécution de la même œuvre par un interprète et un groupe d'interprètes. Dépendance de la vitesse de travail sur le nombre d'interprètes. Dépendance du coût des travaux sur le nombre d'interprètes. Augmentation non linéaire de la vitesse de travail avec une augmentation du nombre d'interprètes. Chemin critique. Nombre optimal d'interprètes. Chargement optimal des interprètes. Procédure optimale. L'équilibrage de charge.
9) Concurrence entre artistes pour les ressources. Blocage. Clinch (impasse).
10) Mécanismes de coordination des actions des artistes interprètes ou exécutants.
11) Exécution pseudo-parallèle de processus sur un ordinateur (division d'une ressource - le processeur) entre processus exécuteurs.
12) Adéquation des algorithmes à la parallélisation. Degré de parallélisation possible. L'existence d'algorithmes non parallélisés.
Veuillez noter que la liste ci-dessus représente l'opinion privée de l'auteur de l'article et est ouverte à la discussion, à l'ajout et à la correction. De plus, selon l’auteur, il serait très utile que la « communauté des superordinateurs » formule un « ordre social » pour l’école : quel type de connaissances et de compétences elle souhaite voir chez les diplômés de l’école. En quoi un diplômé de l’école du « monde des superordinateurs » devrait-il différer d’un diplômé d’aujourd’hui ? S'il y a une commande, il y aura un résultat. Nouvel exemple. Le premier jour des Journées russes du calcul intensif-2015, deux rapports ont exprimé l'idée que la vitesse des supercalculateurs modernes n'est pas déterminée par la puissance des processeurs (qui est au centre de l'attention du public), mais par la vitesse de la RAM. C'est cela qui devient le goulot d'étranglement dont le débit détermine la productivité de l'ensemble du système. En conséquence, le deuxième jour de la conférence, les participants à la master class du professeur ont testé un jeu inventé par l'auteur de cet article, démontrant l'interaction du processeur central, de la RAM et de la mémoire cache. L'ordre et la forme de présentation du matériel sont une question ouverte.
Le matériel doit être démontré à l'aide d'exemples non liés au fonctionnement d'un ordinateur. Les artistes doivent manipuler des objets matériels.
Autant que possible, la formation devrait prendre la forme de jeux d'entreprise (d'organisation et d'activité).
Le respect de ces exigences facilitera la compréhension de la matière étudiée. Cela sera utile aussi bien lors de l'utilisation de cette technique dans les cours d'informatique à l'école (y compris au primaire !), que dans l'enseignement aux adultes : professeurs et élèves d'informatique. Un écolier, un professeur des écoles, un élève d'une spécialité secondaire pourra s'arrêter au niveau de familiarisation et de compréhension. L'étudiant professionnel devra passer à l'étape suivante et passer de la connaissance à l'étude de ces mécanismes à un niveau professionnel. Mais cela va déjà au-delà des méthodes de familiarisation initiale avec le sujet.
L'auteur de cet article a commencé à travailler sur la préparation d'une méthodologie pour étudier le calcul parallèle en 2013 lors de la préparation du concours TRIZformashka-2013 et s'est poursuivi au cours des années suivantes.
(«TRIZformashka» est un concours Internet interrégional en informatique, analyse de systèmes et TRIZ. Organisé chaque année dans la seconde quinzaine de mars. L'âge des participants est de la première année à la quatrième année. Géographie - de Vladivostok à Riga. La moyenne le nombre de participants est de 100 équipes (300 personnes .), maximum - 202 équipes (plus de 600 personnes). Site du concours www.trizformashka.ru.) Puis, en 2013, l'objectif du travail a été formulé comme suit :
1. D'ici deux à trois ans, préparer une description des interprètes, un ensemble de jeux et de tâches liés au calcul parallèle ;
2. Les proposer (en partie, annuellement) aux participants du concours ;
3. Analyser leur réaction (évaluer le nombre de solveurs, leur âge, le succès de la solution, les erreurs typiques, les inexactitudes détectées dans la formulation des problèmes, etc.). Le concours TRIZformashka s'est avéré être un outil pratique pour résoudre les problèmes de débogage, car
a permis d'obtenir des réactions de tous âges (de la première à la quatrième année), de différentes régions, de différents établissements d'enseignement.
Au cours des dernières années, l’ensemble suivant d’outils et de plateformes méthodologiques pour leurs tests a été préparé.
1. Les tâches sur le parallélisme, à partir de 2013, ont été incluses dans le concours « TRIZformashka » (à partir de 2013, le concours porte le sous-titre « Parallel Computing »). Une liste de types de tâches est donnée ci-dessous ;
2. Un chapitre sur le parallélisme a été préparé pour la nouvelle version du manuel d'informatique pour la 4e année. Le matériau a été testé en 3e et 4e années du lycée n°10 de Perm ;
3. Le jeu informatique « Tank Crew » est développé et utilisé depuis 2014 dans le cadre du concours TRIZformashka ;
4. Un certain nombre de jeux ont été développés et testés, qui reflètent les problématiques suivantes :
Coordination des activités des artistes. Différents types d'approbation ;
Exécution de la même œuvre par un interprète et un groupe d'interprètes. Dépendance de la vitesse de travail sur le nombre d'interprètes. Augmentation non linéaire de la vitesse de travail avec une augmentation du nombre d'interprètes. Chemin critique. Nombre optimal d'interprètes. Chargement optimal des interprètes. Procédure optimale ;
Ressources. Ressources partagées et non partagées ;
Concurrence entre artistes pour les ressources. Blocage. Clinch (impasse). Les types de problèmes suivants ont été proposés et testés :
1. Tâches sur les types d'approbation. (Quels types de coordination existent à la cantine scolaire ?) ;
2. Jeu "Tank Crew". Mission de construction d'un algorithme parallèle ;
3. Interprète « Construction ». Parallèlement, les équipes de travail construisent une structure à partir de poutres horizontales et verticales. Les tâches comprennent des tâches pour l'exécution de l'algorithme spécifié, pour le développement d'un nouvel algorithme, pour la recherche d'erreurs dans un algorithme donné, pour la recherche d'algorithmes (comparaison des temps de construction à l'aide de différents algorithmes, comparaison des coûts de construction, évaluation de la possibilité d'économies en redistribuant travail, etc.);
4. Concurrence pour les ressources. Trois petits cochons préparent chacun leur propre déjeuner. Pour chaque porcelet, il est indiqué quels plats il prépare, de quelles ressources (matériel, ustensiles, etc.) il a besoin pour cela et pendant combien de temps ces ressources doivent être utilisées. Il est nécessaire d'établir un planning de travail pour chaque porcelet, s'il cuisine seul en cuisine, s'ils cuisinent à deux, si tous les trois cuisinent en même temps. Le temps de cuisson doit être minimisé ;
5. Schéma du réseau. Un schéma de réseau est donné. Il est nécessaire de représenter (schématiquement) la structure qui sera construite, de déterminer combien de jours il faudra pour la construction avec un nombre particulier d'équipes, quelle partie des travaux sera achevée dans un certain délai ;
6. Formulaires parallèles à plusieurs niveaux. Planifier les travaux selon divers critères. L'affectation du travail, la productivité des travailleurs et les règles de paiement sont indiquées. Il est nécessaire de déterminer le nombre de travailleurs nécessaires pour terminer le travail dans un temps donné, de déterminer la période de travail pour un nombre donné de travailleurs, de déterminer le nombre de travailleurs nécessaire pour minimiser le coût du travail ;
7. Diagrammes de Gantt. Le texte décrit le plan de travail pour la reconstruction de l'atelier : durée et séquence mutuelle d'actions, ouvriers requis. Il est nécessaire de déterminer le délai de réalisation de l'objet, la modification du délai en raison de certains changements d'effectif, et la liste des travailleurs impliqués à une date précise.
8. Coordination des travaux répétitifs. Supposons que la tâche soit de produire un lot d'appareils en un minimum de temps, à condition que chaque appareil doive être traité sur des équipements différents ; il existe différentes quantités d'équipements avec des productivités différentes. Il est nécessaire de planifier l'heure de démarrage et de fonctionnement de chaque équipement et de minimiser les temps d'arrêt.
Aujourd'hui, nous avons les résultats suivants :
1. Une approche a été formulée pour étudier le thème de « l'informatique parallèle » : s'éloigner non pas des problèmes de l'informatique, mais « de la vie », se concentrer sur « l'activité conjointe » ;
2. Une liste de problèmes a été formulée et il est proposé d'être reflétée dans le cours initial de calcul parallèle ;
3. Certaines classes de problèmes sont formulées. Sur la base de l'expérience accumulée, vous pouvez évaluer quels types de problèmes doivent être inventés ;
4. Un ensemble de problèmes des classes nommées a été préparé. Les problèmes ont été testés lors des concours TRIZformashka en 2013, 2014, 2015. et/ou à l'école primaire (dans des classes avec des élèves de troisième et quatrième années du lycée n°10 de Perm) ;
5. Un ensemble de jeux d'entreprise a été préparé. Les jeux ont été testés dans des écoles primaires et lors de plusieurs événements destinés aux enseignants. En particulier, ils ont été présentés lors du cursus scolaire de l'Académie d'été des supercalculateurs de l'Université d'État de Moscou en 2014, lors d'une classe de maître pour les enseignants des Journées russes du supercalculateur-2015, lors de plusieurs autres conférences (y compris lors de la conférence IT-éducation-2015 de l'association APKIT) et autres événements destinés aux professeurs d'informatique ;
6. Un ensemble de textes sur le parallélisme a été préparé pour un manuel de quatrième année. Les textes ont été testés au lycée n°10 de Perm ;
7. Le jeu informatique « Tank Crew » a été préparé. Le jeu a été testé lors des concours TRIZformashka en 2014 et 2015 ;
8. Le concours TRIZformashka s'est révélé être une plateforme de test ;
9. La tâche de « roque » dans le processus d'enseignement de l'algorithmique est formulée : enseigner immédiatement la programmation parallèle, en présentant un algorithme séquentiel dans le cadre d'un algorithme parallèle. Il y a des réflexions sur la manière dont cette idée peut être mise en œuvre. Il est possible d'essayer ces idées au cours de l'année scolaire en cours (pour les élèves de la 4e à la 5e année) ;
10. Il existe un besoin, un désir et une opportunité de continuer à travailler.
Littérature
1. Algorithmes : niveaux 5-7 : Manuel et cahier de problèmes pour l'enseignement général. établissements d'enseignement /A.K. Zvonkin, A.G. Koulakov, S.K. Lando, A.L. Semenov, A.Kh. Shen. - M. : Outarde, 1996.
2. Bosova L.L. Algorithmes parallèles dans les écoles primaires et secondaires. //L'informatique à l'école. 2015, n°2. P.24-27.
3. Voevodine V.V. Mathématiques computationnelles et structure des algorithmes : cours 10 sur les raisons pour lesquelles il est difficile de résoudre des problèmes sur des systèmes informatiques à architecture parallèle et quelles informations supplémentaires vous devez connaître. pour réussir à surmonter ces difficultés : un manuel. M. : Maison d'édition MSU 2010.
4. Gavrilova I.V. Premier voyage dans le « monde parallèle ». //L'informatique à l'école. 2015, n° 6. P.16-19.
5. Dieter M.L., Plaksin M.A. Calcul parallèle en informatique scolaire. Jeu "Construction". //L'informatique à l'école : passé, présent et futur. : matériaux de toute la Russie. méthode scientifique. conf. sur l'utilisation des TIC dans l'éducation, 6-7 février 2014 /Perm. État national recherche univ. - Perm, 2014. - P.258-261.
6. Ivanova N.G., Plaksin M.A., Rusakova O.L. TRIZformashka. //L'informatique. N05 Récupéré le 10/10/2015.
14. Plaksin M.A. Informatique : manuel pour la 4e année : 2 heures / M.A.Plaksin, N.G.Ivanova, O.L.Rusakova. - M. : BINOM. Laboratoire de connaissances, 2012.
15. Plaksin M.A. A propos de la méthode de première connaissance du calcul parallèle au lycée. //L'informatique à l'école : passé, présent et futur. : matériaux de toute la Russie. méthode scientifique. conf. sur l'utilisation des TIC dans l'éducation, 6-7 février 2014 /Perm. État national recherche univ. - Perm, 2014. - P.256-258.
16. Plaksin M.A. Un ensemble de jeux d'entreprise pour introduire le calcul parallèle à l'école primaire. //Enseigner les technologies de l'information dans la Fédération de Russie : documents de la treizième conférence panrusse ouverte « IT-0education-2015 » (Perm, 14-15 mai 2015). Université nationale de recherche de l'État de Perm, - Perm, 2015. P.60-62.
17. Plaksin M.A., Ivanova N.G., Rusakova O.L. Un ensemble de tâches pour se familiariser avec le calcul parallèle dans le cadre du concours TRIZformashka. //Enseigner les technologies de l'information dans la Fédération de Russie : documents de la treizième conférence ouverte panrusse « IT Education-2015 » (Perm, 14-15 mai 2015). Université nationale de recherche de l'État de Perm, - Perm, 2015. pp. 232-234.
18. Sokolovskaya M.A. Système méthodologique pour enseigner les bases de la programmation parallèle aux futurs professeurs d'informatique. : résumé. dis. ...et. péd. Sciences, Krasnoïarsk, 2012.
Le concept de calcul parallèle
FONDAMENTAUX DU CALCUL PARALLÈLE
Conférence n°6
Sous calculs parallèles ou simultanés vous pouvez comprendre les processus de résolution de problèmes dans lesquels plusieurs opérations de calcul peuvent être effectuées simultanément
Le calcul parallèle constitue la base des technologies de calcul intensif et du calcul haute performance
Traitement parallèle
Si un certain appareil effectue une opération par unité de temps, il effectuera alors mille opérations en mille unités. Si nous supposons qu'il existe cinq appareils indépendants identiques capables de fonctionner simultanément, alors un système de cinq appareils peut effectuer les mêmes milliers d'opérations non pas en mille, mais en deux cents unités de temps.
De même, un système de N appareils effectuera le même travail en 1 000/N unités de temps. Des analogies similaires peuvent être trouvées dans la vie : si un soldat creuse un jardin en 10 heures, alors une compagnie de cinquante soldats ayant les mêmes capacités, travaillant simultanément, accomplira le même travail en 12 minutes - le principe du parallélisme en action !
Le pionnier du traitement parallèle des flux de données fut l'académicien A.A. Samarsky, qui effectua les calculs nécessaires à la simulation d'explosions nucléaires au début des années 50. Samarsky a résolu ce problème en faisant asseoir plusieurs dizaines de jeunes femmes avec des machines à calculer à des tables. Les jeunes filles se transmettaient des données simplement en paroles et inscrivaient les nombres nécessaires sur des machines à calculer. Ainsi, en particulier, l'évolution de l'onde de souffle a été calculée.
Il y avait beaucoup de travail, les jeunes filles étaient fatiguées et Alexandre Andreïevitch marchait parmi elles et les encourageait. Ce fut, pourrait-on dire, le premier système parallèle. Bien que les calculs pour la bombe à hydrogène aient été réalisés de main de maître, leur précision était très faible, car il y avait peu de nœuds dans la grille utilisée et le temps de calcul était trop long.
Traitement du convoyeur
L'idée du traitement par pipeline est d'isoler les étapes individuelles de l'exécution d'une opération générale, et chaque étape, après avoir terminé son travail, transmettrait le résultat à la suivante, tout en recevant simultanément une nouvelle partie des données d'entrée. On obtient un gain évident en vitesse de traitement en combinant des opérations préalablement espacées.
Supposons qu'une opération comporte cinq micro-opérations, chacune étant effectuée en une unité de temps. S'il existe un périphérique série indivisible, il traitera alors 100 paires d'arguments en 500 unités. Si chaque micro-opération est séparée en une étape distincte (ou autrement appelée étape) d'un dispositif de convoyage, alors sur la cinquième unité de temps, à différentes étapes de traitement d'un tel dispositif, les cinq premières paires d'arguments seront localisées , et l'ensemble complet de cent paires sera traité en 5 + 99 = 104 unités de temps - l'accélération par rapport à un appareil en série est presque cinq fois (selon le nombre d'étages du convoyeur).
Modèles d'ordinateurs parallèles (classification Flynn)
· « Un flux de commandes - un flux de données » (SISD - « Single Instruction Single Data »)
Fait référence à l'architecture von Neumann. Les ordinateurs SISD sont des ordinateurs séquentiels ordinaires et « traditionnels », dans lesquels une seule opération est effectuée sur un élément de données (valeur numérique ou autre) à un moment donné. La plupart des ordinateurs personnels modernes entrent dans cette catégorie.
· "Un flux de commandes - plusieurs flux de données" (SIMD - "Instruction unique - Données multiples")
SIMD (instruction unique, données multiples)- un principe de calcul informatique qui permet le parallélisme au niveau des données. Les ordinateurs SIMD se composent d'un processeur de commandes (module de contrôle), appelé contrôleur, et de plusieurs modules de traitement de données, appelés éléments de traitement. Le module de contrôle reçoit, analyse et exécute les commandes.
Si des données sont rencontrées dans la commande, le contrôleur envoie une commande à tous les éléments du processeur, et cette commande est exécutée sur plusieurs ou tous les éléments du processeur. Chaque élément de traitement possède sa propre mémoire pour stocker les données. L'un des avantages de cette architecture est que dans ce cas la logique de calcul est mise en œuvre de manière plus efficace. Les processeurs SIMD sont également appelés processeurs vectoriels.
· « De nombreux flux de commandes - un flux de données » (MISD - « Instructions multiples - Données uniques »)
Il n'existe pratiquement pas d'ordinateurs de cette classe et il est difficile de donner un exemple de leur mise en œuvre réussie. L'un des rares est un réseau systolique de processeurs, dans lequel les processeurs sont situés aux nœuds d'un réseau régulier, dont le rôle de bords est joué par les connexions interprocesseurs. Tous les éléments du processeur sont contrôlés par un générateur d'horloge commun. Dans chaque cycle de fonctionnement, chaque élément de traitement reçoit des données de ses voisins, exécute une commande et transmet le résultat à ses voisins.
Les tableaux de PE avec des connexions directes entre PE proches sont appelés systolique. De tels réseaux sont extrêmement efficaces, mais chacun d’eux se concentre sur la résolution d’une classe très restreinte de problèmes. Voyons comment vous pouvez créer un tableau systolique pour résoudre un certain problème. Supposons, par exemple, que vous souhaitiez créer un dispositif pour calculer une matrice D = C + AB, Où
Ici toutes les matrices sont des matrices de bandes d'ordre n. Matrice UN a une diagonale au-dessus et deux diagonales en dessous de la diagonale principale ; matrice B- une diagonale en dessous et deux diagonales au dessus de la principale ; matrice C trois diagonales au-dessus et en dessous de la diagonale principale. Que chaque PE soit capable d'effectuer une opération scalaire c+ab et transmettre simultanément des données. Chaque PE doit donc avoir trois entrées : une, b, c et trois sorties : une, b, c. Saisir ( dans) et les week-ends ( dehors) les données sont liées par des relations
a out = a in , b out = b in , c out = c in + a in *b in ;
Si au moment de l'opération certaines données n'ont pas été reçues, alors nous supposerons qu'elles sont définies comme des zéros. Supposons en outre que tous les PE sont situés sur un plan et que chacun d’eux est connecté à six PE voisins. Si vous disposez les données comme indiqué sur la figure, le circuit calculera la matrice D.
Le réseau fonctionne par cycles d'horloge. Au cours de chaque cycle d'horloge, toutes les données sont déplacées vers les nœuds voisins dans les directions indiquées par les flèches.
La figure montre l'état du tableau systolique à un moment donné. Au cours du prochain cycle d'horloge, toutes les données seront déplacées vers un nœud et des éléments a11, b11, c11 se retrouvera dans un PE situé à l’intersection des lignes pointillées. L’expression sera donc évaluée c11+a11b11.A la même horloge, les données a12 Et b21 viendra très près du PE, situé au sommet du réseau systolique.
Au cours du prochain cycle d'horloge, toutes les données se déplaceront à nouveau d'un nœud dans le sens des flèches et apparaîtront dans le PE supérieur. a12 Et b21 et le résultat de l'opération précédente du PE situé en dessous, soit c11+a11b11. L’expression sera donc évaluée c11+a11b11+a12b21. C'est un élément d11 matrices D.
En poursuivant l'examen étape par étape du processus, nous pouvons vérifier qu'aux sorties PE correspondant à la limite supérieure du tableau systolique, des éléments matriciels sont périodiquement émis après trois étapes. D, tandis que des éléments de même diagonale apparaissent à chaque sortie. À propos 3n cycles, le calcul de la matrice entière sera terminé D. Dans ce cas, la charge sur chaque cellule systolique est asymptotiquement égale 1/3 .
"De nombreux flux de commandes - de nombreux flux de données" (MIMD - "Instruction multiple - Données multiples")
Cette catégorie d'architectures informatiques est la plus riche si gardez à l’esprit des exemples de ses mises en œuvre réussies. Il comprend symétrique systèmes informatiques parallèles, postes de travail avec plusieurs processeurs, clusters de postes de travail, etc.
Les énormes performances des ordinateurs et supercalculateurs parallèles sont plus que compensées par les difficultés de leur utilisation. Commençons par les choses les plus simples. Vous disposez d'un programme et d'un accès, disons, à un ordinateur à 256 processeurs. Qu'attendez-vous ? Oui, c'est clair : on s'attend tout à fait légitimement à ce que le programme s'exécute 256 fois plus vite que sur un seul processeur. Mais c’est précisément ce qui n’arrivera probablement pas.
L'informatique parallèle est une méthode d'organisation de l'informatique dans laquelle les programmes sont développés comme un ensemble de processus informatiques interactifs s'exécutant simultanément.
Il existe différentes manières de mettre en œuvre le calcul parallèle : chaque processus informatique peut être implémenté en tant que processus du système d'exploitation, ou les processus informatiques peuvent être un ensemble de threads d'exécution au sein d'un seul processus. Un thread (ou plus exactement un thread d'exécution) est la plus petite unité de traitement dont l'exécution peut être assignée par le noyau du système d'exploitation. Plusieurs threads d'exécution peuvent exister au sein du même processus et partager des ressources telles que la mémoire, alors que les processus ne partagent pas ces ressources. Les programmes parallèles peuvent être exécutés physiquement soit séquentiellement sur un seul processeur - en alternant tour à tour les étapes de chaque processus de calcul, soit en parallèle - en allouant un ou plusieurs processeurs (situés à proximité ou répartis dans un réseau informatique) à chaque processus de calcul.
Le principal défi de la conception de programmes parallèles est d’assurer la séquence correcte des interactions entre les différents processus informatiques, ainsi que le partage des ressources telles que la RAM ou les périphériques.
Dans certains systèmes de programmation parallèle, le transfert de données entre composants est caché au programmeur, tandis que dans d'autres, il doit être spécifié explicitement. Les interactions explicites peuvent être divisées en deux types :
1. Interaction via la mémoire partagée (par exemple, en Java ou C#). Ce type de programmation parallèle nécessite généralement une certaine forme de capture de contrôle pour coordonner les threads entre eux.
2. Interaction par transmission de messages. Les messages peuvent être échangés de manière asynchrone ou en utilisant la méthode de rendez-vous, dans laquelle l'expéditeur est bloqué jusqu'à ce que son message soit livré. La transmission asynchrone des messages peut être fiable (avec garantie de livraison) ou peu fiable. Les systèmes parallèles de transmission de messages sont souvent plus faciles à comprendre que les systèmes à mémoire partagée et sont généralement considérés comme une méthode supérieure de programmation parallèle. La messagerie peut être efficacement implémentée sur des multiprocesseurs symétriques avec ou sans mémoire cohérente partagée.
Il existe de nombreuses technologies de programmation parallèle différentes. De plus, ces technologies diffèrent moins par les langages de programmation que par les approches architecturales de la construction de systèmes parallèles. Par exemple, certaines technologies impliquent la construction de solutions parallèles basées sur plusieurs ordinateurs (de types identiques ou différents), tandis que d'autres impliquent de travailler sur une seule machine avec plusieurs cœurs de processeur. Actuellement, les principaux outils logiciels de création de programmes parallèles sont :
1. OuvrirMP utilisé dans des systèmes parallèles avec mémoire partagée (par exemple, des ordinateurs modernes équipés de processeurs multicœurs) ;
2. MPI (interface de transmission de messages) est une norme pour les systèmes de transfert de messages entre processus d'exécution parallèles, utilisée dans le développement de programmes pour superordinateurs ;
3. Discussions POSIX est un standard pour implémenter des threads d'exécution ;
4. Le système d'exploitation Windows prend en charge les applications multithread pour C++ au niveau de l'API ;
5. PVM (machine virtuelle parallèle) vous permet de combiner des ordinateurs hétérogènes connectés par un réseau en une ressource informatique commune.
Les systèmes basés sur plusieurs ordinateurs sont classés comme systèmes d'informatique distribuée. De telles solutions sont utilisées depuis un certain temps. L'exemple le plus frappant de technologie informatique distribuée est MPI (Message Passing Interface). MPI est la norme d'interface d'échange de données la plus courante pour la programmation parallèle ; il existe des implémentations pour un grand nombre de plates-formes informatiques. MPI fournit au programmeur un mécanisme unifié d'interaction des branches au sein d'une application parallèle, quelle que soit l'architecture de la machine (monoprocesseur/multiprocesseur avec mémoire partagée/séparée), l'emplacement relatif des branches (sur le même processeur ou sur des processeurs différents).
Étant donné que MPI est principalement destiné aux systèmes à mémoire partagée, son utilisation pour organiser un processus parallèle dans un système à mémoire partagée est extrêmement difficile et peu pratique. Cependant, rien ne vous empêche de réaliser des solutions MPI pour une seule machine.
Mais les systèmes de programmation parallèle permettant de travailler sur une seule machine ont commencé à se développer relativement récemment. Bien sûr, ce ne sont pas des idées fondamentalement nouvelles, mais c'est avec l'avènement des systèmes multicœurs sur le marché des ordinateurs personnels et des appareils mobiles que des technologies telles qu'OpenMP ont connu un développement significatif.
Il est très important que la technologie de programmation parallèle permette de mettre progressivement en parallèle un programme. Bien entendu, un programme parallèle idéal devrait immédiatement être écrit en parallèle, peut-être dans un langage fonctionnel où le problème de la parallélisation ne se pose pas du tout. Mais en pratique, il est nécessaire de paralléliser progressivement le séquentiel écrit afin d'augmenter les performances. Dans ce cas, la technologie OpenMP sera un très bon choix. Il permet de sélectionner les endroits de l'application qui nécessitent le plus de parallélisation, et tout d'abord de les rendre parallèles. Le processus de développement de versions parallèles peut être interrompu, les versions intermédiaires du programme publiées et reprises si nécessaire. C'est pourquoi la technologie OpenMP en particulier est devenue très populaire.
OpenMP (Open Multi-Processing) est un ensemble de directives de compilateur, de procédures de bibliothèque et de variables d'environnement conçues pour programmer des applications multithread sur des systèmes multiprocesseurs à mémoire partagée.
La spécification OpenMP est développée par plusieurs grands fabricants de matériel et de logiciels, dont le travail est réglementé par une organisation à but non lucratif appelée OpenMP Architecture Review Board (ARB).
La première version est apparue en 1997, destinée au langage Fortran. La version C/C++ a été développée en 1998. En 2008, OpenMP 3.0 est sorti. L'interface OpenMP est devenue l'une des technologies de programmation parallèle les plus populaires. OpenMP est utilisé avec succès à la fois dans la programmation de systèmes de supercalculateurs dotés d'un grand nombre de processeurs et dans les systèmes d'utilisateurs de bureau ou, par exemple, dans la Xbox 360.
OpenMP implémente le calcul parallèle en utilisant le multithreading, dans lequel un thread « maître » crée un ensemble de threads esclaves et la tâche est répartie entre eux. Les threads sont supposés être exécutés en parallèle sur une machine dotée de plusieurs processeurs (le nombre de processeurs ne doit pas nécessairement être supérieur ou égal au nombre de threads).
Les tâches exécutées par les threads en parallèle, ainsi que les données nécessaires pour effectuer ces tâches, sont décrites à l'aide de directives de préprocesseur spéciales du langage correspondant - les pragmas. Par exemple, une section de code Fortran qui doit être exécutée par plusieurs threads, chacun possédant sa propre copie de la variable N, est précédée de la directive suivante : !$OMP PARALLEL PRIVATE(N)
Le nombre de threads créés peut être régulé à la fois par le programme lui-même en appelant des procédures de bibliothèque et en externe, à l'aide de variables d'environnement.
Les éléments clés d'OpenMP sont
1. constructions pour créer des threads (directive parallèle) ;
2. constructions pour répartir le travail entre les threads (directives DO/for et section) ;
3. constructions pour gérer le travail avec les données (expressions partagées et privées pour définir la classe mémoire des variables) ;
4. constructions pour synchroniser les threads (directives critiques, atomiques et barrières) ;
5. procédures de bibliothèque de support d'exécution (par exemple, omp_get_thread_num) ;
6. variables d'environnement (par exemple, OMP_NUM_THREADS).
OpenMP utilise un modèle d'exécution parallèle par fusion de branches. Un programme OpenMP commence comme un seul thread d'exécution, appelé thread initial. Lorsqu'un thread rencontre une construction parallèle, il crée un nouveau groupe de threads composé de lui-même et d'un certain nombre de threads supplémentaires, et devient le maître du nouveau groupe. Tous les membres du nouveau groupe (y compris le groupe principal) exécutent du code à l'intérieur de la construction parallèle. Il existe une barrière implicite à la fin de la structure parallèle. Après la construction parallèle, seul le thread principal continue d'exécuter le code utilisateur. Une région parallèle peut être imbriquée avec d'autres régions parallèles, dans lesquelles chaque thread de la région d'origine devient le thread principal de son groupe de threads. Les régions imbriquées peuvent à leur tour inclure des régions situées à un niveau d’imbrication plus profond.
Le nombre de threads dans un groupe exécuté en parallèle peut être contrôlé de plusieurs manières. L'un d'eux utilise la variable d'environnement OMP_NUM_THREADS. Une autre façon consiste à appeler la procédure omp_set_num_threads(). Une autre façon consiste à utiliser l'expression num_threads en combinaison avec la directive parallèle.
Dans ce programme, deux tableaux (a et b) sont ajoutés en parallèle par dix threads.
#inclure
#inclure
int principal (int argc, char *argv)
flotter a[N], b[N], c[N] ;
omp_set_dynamic(0); // empêche la bibliothèque openmp de modifier le nombre de threads pendant l'exécution
omp_set_num_threads(10); // définit le nombre de threads à 10
// initialise les tableaux
pour (je = 0; je< N; i++)
// calcule la somme des tableaux
#pragma omp parallèle partagé (a, b, c) privé (i)
pour (je = 0; je< N; i++)
c[i] = a[i] + b[i];
printf("%f\n", c);
Ce programme peut être compilé en utilisant gcc-4.4 et versions ultérieures avec l'indicateur –fopenmp. Évidemment, si vous supprimez l'inclusion du fichier d'en-tête omp.h, ainsi que les appels à la fonction de configuration OpenMP, le programme peut être compilé sur n'importe quel compilateur C en tant que programme séquentiel normal.
OpenMP est pris en charge par de nombreux compilateurs modernes :
1. Les compilateurs Sun Studio prennent en charge la spécification officielle - OpenMP 2.5 - avec des performances améliorées sous le système d'exploitation Solaris ; Le support de Linux est prévu pour la prochaine version.
2. Visual C++ 2005 et versions ultérieures prennent en charge OpenMP dans les éditions Professional et Team System.
3. GCC 4.2 prend en charge OpenMP et certaines distributions (telles que Fedora Core 5 gcc) ont inclus la prise en charge dans leurs versions de GCC 4.1.
4. Compilateur Intel C++, comprenant une version d'Intel Cluster OpenMP pour la programmation dans les systèmes à mémoire distribuée.
Interface de transmission de messages (MPI interface de transmission de messages) est une interface de programmation de transfert d'informations (API) qui permet l'échange de messages entre des processus effectuant la même tâche. Développé par William Group, Evin Lusk et d'autres.
MPI est la norme d'interface d'échange de données la plus courante pour la programmation parallèle et il existe des implémentations pour un grand nombre de plates-formes informatiques. Utilisé dans le développement de programmes pour les clusters et les supercalculateurs. Le principal moyen de communication entre les processus dans MPI consiste à se transmettre des messages. La normalisation MPI est réalisée par le MPI Forum. La norme MPI décrit une interface de transmission de messages qui doit être prise en charge à la fois sur la plateforme et dans les applications utilisateur. Il existe actuellement un grand nombre d'implémentations gratuites et commerciales de MPI. Il existe des implémentations pour les langages Fortran 77/90, C et C++.
MPI se concentre principalement sur les systèmes à mémoire distribuée, c'est-à-dire lorsque les coûts de transfert de données sont élevés, tandis qu'OpenMP se concentre sur les systèmes à mémoire partagée (multicœurs avec ESH partagé). Les deux technologies peuvent être utilisées ensemble pour utiliser de manière optimale les systèmes multicœurs dans un cluster.
La première version de MPI a été développée en 1993-1994 et MPI 1 a été lancée en 1994.
La plupart des implémentations MPI modernes prennent en charge la version 1.1. La version 2.0 de la norme MPI est prise en charge par la plupart des implémentations modernes, mais certaines fonctionnalités peuvent ne pas être entièrement implémentées.
envoyer et recevoir des messages entre des processus distincts ;
interactions collectives des processus ;
interactions dans les groupes de processus ;
mise en œuvre de topologies de processus ;
génération de processus dynamiques et gestion de processus ;
communications unidirectionnelles (Get/Put) ;
entrée et sortie parallèles ;
opérations collectives étendues (les processus peuvent effectuer des opérations collectives non seulement au sein d'un communicateur, mais également au sein de plusieurs communicateurs).
La version MPI 2.1 est sortie début septembre 2008.
Le mécanisme de base de communication entre les processus MPI est la transmission et la réception de messages. Le message contient des données et des informations transmises qui permettent au destinataire de les recevoir de manière sélective :
1. expéditeur - rang (numéro dans le groupe) de l'expéditeur du message ;
2. destinataire - rang du destinataire ;
3. signe - peut être utilisé pour séparer différents types de messages ;
4. communicateur - code de groupe de processus.
Les opérations de réception et d'émission peuvent être bloquantes ou non bloquantes. Pour les opérations non bloquantes, des fonctions sont définies pour vérifier l'état de préparation et attendre la fin de l'opération.
Une autre méthode de communication est l'accès à la mémoire à distance (RMA), qui permet de lire et de modifier la région mémoire d'un processus distant. Un processus local peut transférer la zone mémoire d'un processus distant (dans une fenêtre spécifiée par les processus) dans sa mémoire et inversement, et également combiner les données transférées au processus distant avec les données disponibles dans sa mémoire (par exemple, en additionnant ). Toutes les opérations d'accès à la mémoire distante sont non bloquantes ; cependant, les fonctions de synchronisation bloquantes doivent être appelées avant et après leur exécution.
Vous trouverez ci-dessous un exemple de programme pour calculer π en C à l'aide de MPI :
// Connexion des en-têtes nécessaires
#inclure
#inclure
// Inclut le fichier d'en-tête MPI
#include "mpi.h"
// Fonction pour les calculs intermédiaires
double f(double a)
retourner (4,0 / (1,0+ a*a));
// Fonction principale du programme
int principal (int argc, char **argv)
// Déclaration des variables
int done = 0, n, monid, numprocs, I ;
double PI25DT = 3,141592653589793238462643 ;
double mypi, pi, h, somme, x ;
double heure de début = 0,0, heure de fin ;
char nom_processeur ;
// Initialise le sous-système MPI
MPI_Init(&argc, &argv);
// Récupère la taille du communicateur MPI_COMM_WORLD
// (nombre total de processus dans la tâche)
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
// Récupère le numéro du processus en cours dans
// communicateur MPI_COMM_WORLD
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
MPI_Get_processor_name(processor_name,&namelen);
// Afficher le numéro de thread dans le pool partagé
fprintf(stdout, "Le processus %d de %d est sur %s\n", myid,numprocs,processor_name);
// nombre d'intervalles
fprintf(stdout, "Entrez le nombre d'intervalles : (0 quitte) ");
si(scanf("%d",&n) != 1)
fprintf(stdout, "Aucun numéro saisi ; quitter\n");
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
h = 1,0 / (double)n ;
// Calculer le point attribué au processus
pour(I = monid + 1 ; (I<= n) ; I += numprocs)
x = h * ((double)I – 0,5);
// Réinitialise les résultats de tous les processus et ajoute
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
// S'il s'agit du processus principal, affiche le résultat
printf("PI est d'environ %.16f, l'erreur est %.16f\n", pi, fabs(pi – PI25DT));
endwtime = MPI_Wtime();
printf("heure de l'horloge murale = %f\n", endwtime-startwtime);
// Libère le sous-système MPI
Les implémentations MPI les plus courantes aujourd'hui sont :
MPICH est l'implémentation gratuite la plus courante, fonctionne sur les systèmes UNIX et Windows NT
LAM/MPI est une autre implémentation gratuite de MPI. Prend en charge les configurations hétérogènes, LAM (http://www.lam-mpi.org) prend en charge les configurations hétérogènes, le package Globus et satisfait à IMPI (Interoperable MPI).
Divers systèmes de communication sont pris en charge (dont Myrinet).
WMPI - Implémentation MPI pour Windows
MPI/PRO pour Windows NT - implémentation commerciale pour Windows NT
Intel MPI - implémentation commerciale pour Windows/Linux
Microsoft MPI est inclus dans le SDK Compute Cluster Pack. Basé sur MPICH2, mais inclut des fonctionnalités supplémentaires de gestion des tâches. La spécification MPI-2 est prise en charge.
HP-MPI - implémentation commerciale de HP
SGI MPT - bibliothèque MPI payante de SGI
Mvapich - implémentation MPI gratuite pour Infiniband
Open MPI - implémentation gratuite de MPI, successeur de LAM/MPI
Oracle HPC ClusterTools - implémentation gratuite pour Solaris SPARC/x86 et Linux basée sur Open MPI
MPJ-MPI pour Java
Discussions POSIX- Standard POSIX pour implémenter les threads d'exécution, définissant une API pour les créer et les gérer.
Les bibliothèques qui implémentent ce standard (et les fonctions de ce standard) sont généralement appelées Pthreads (les fonctions sont préfixées par "pthread_"). Bien que les options les plus connues concernent les systèmes d'exploitation de type Unix tels que Linux ou Solaris, il existe également une implémentation pour Microsoft Windows (Pthreads-w32).
Pthreads définit un ensemble de types et de fonctions dans le langage de programmation C. Le fichier d'en-tête est pthread.h.
Types de données:
1. pthread_t – descripteur de thread ;
2. pthread_attr_t – liste des attributs du thread.
Fonctions de contrôle des fils :
1. pthread_create() – création d'un fil de discussion ;
2. pthread_exit() – terminaison du thread (doit être appelée par la fonction thread à la fin) ;
3. pthread_cancel() – annule le fil ;
4. pthread_join() – bloque l'exécution d'un thread jusqu'à ce qu'un autre thread spécifié dans l'appel de fonction se termine ;
5. pthread_detach() – libère les ressources occupées par le thread (si le thread est en cours d'exécution, les ressources seront libérées une fois terminé) ;
6. pthread_attr_init() – initialise la structure des attributs du thread ;
7. pthread_attr_setdetachstate() – indique au système qu'une fois le thread terminé, il peut automatiquement libérer les ressources occupées par le thread ;
8. pthread_attr_destroy() – libère de la mémoire de la structure d'attribut du thread (détruit le descripteur).
Fonctions de synchronisation des threads :
2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();
3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().
Exemple d'utilisation de threads en C :
#inclure
#inclure
#inclure
#inclure
statique vide wait_thread (void)
time_t start_time = heure (NULL);
while (time(NULL) == start_time)
/* ne fait rien d'autre que mâcher des tranches de CPU pendant une seconde maximum. */
vide statique *thread_func(void *vptr_args)
pour (je = 0; je< 20; i++)
fputs("b\n", stderr);
fil pthread_t ;
if (pthread_create(&thread, NULL, thread_func, NULL) != 0)
renvoyer EXIT_FAILURE ;
pour (je = 0; je< 20; i++)
si (pthread_join(thread, NULL) != 0)
renvoyer EXIT_FAILURE ;
renvoyer EXIT_SUCCESS ;
Le programme présenté utilise deux threads qui impriment les messages sur la console, l'un qui imprime "a", le second - "b". La sortie du message est mixte en raison du basculement d'exécution entre les threads ou de l'exécution simultanée sur les systèmes multiprocesseurs.
Le programme C crée un nouveau thread pour imprimer "b" et le thread principal imprime "a". Le thread principal (après avoir imprimé "aaaaa….") attend la fin du thread enfant.
Questions de contrôle
- Qu'est-ce qu'un programme parallèle ?
- Quelle est la différence entre un processus et un thread d’exécution ?
- Un programme peut-il créer 5 threads lorsqu’il est exécuté sur un processeur quad core ?
- Quelles sont les fonctionnalités des programmes parallèles à mémoire partagée ?
- Quels outils logiciels existent pour développer des programmes parallèles ?
- Pourquoi OpenMP s'est-il généralisé lors de la création de programmes pour PC, et non, par exemple, MPI ?
