Présentation

Article

1 - APPLICATION DES ALGORITHMES PARALLÈLES ASYNCHRONES

  • 1.1 - Application à la résolution de problèmes aux limites linéaires et non linéaires
  • 1.2 - Application aux itérations chaotiques discrètes
  • 1.3 - Application des itérations chaotiques à la sécurité informatique

2 - EFFICACITÉ DES ALGORITHMES PARALLÈLES ASYNCHRONES

3 - CONCLUSION

4 - ANNEXE : COMPLÉMENTS THÉORIQUES POUR L’ANALYSE EN CONTRACTION

  • 4.1 - Notions préliminaires
  • 4.2 - Accrétivité d’une matrice par rapport à la norme uniforme
  • 4.3 - Un problème pseudo-linéaire
  • 4.4 - Un résultat de contraction de l’application de point fixe associé à la décomposition en blocs

Article de référence | Réf : AF1387 v1

Conclusion
Algorithmes parallèles asynchrones III - Application, performances

Auteur(s) : Pierre SPITERI, Jean-Claude MIELLOU

Date de publication : 10 oct. 2021

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

RÉSUMÉ

Nous nous consacrons principalement dans le présent article, d’une part, aux aspects applicatifs des méthodes itératives parallèles asynchrones pour résoudre numériquement des problèmes de grande taille issus de la résolution numérique d’équations aux dérivées partielles pseudo-linéaires, ainsi que des problèmes variés comme des problèmes d’optimisation ou d’équations algébro-différentielles mais aussi des problèmes non numériques. D’autre part des tests numériques permettront de montrer dans quelles conditions les méthodes itératives parallèles asynchrones comparées aux méthodes synchrones sont efficaces. Enfin une annexe mathématique permettra d’exposer des notions utiles pour l’analyse de ces méthodes.

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

ABSTRACT

Parallel Asynchronous Algorithms III. Application, Performances

This article is essentially devoted to the applicative aspects of the parallel asynchronous iterative methods to solve numerically large scale problems resulting from the discretization of pseudo-linear boundary value problems and also from optimisation problems or from algebro-differential equations but also from non-numerical problems. On the other hand numerical tests allow to show under which conditions the parallel iterative asynchronous methods compared to the synchronous ones are efficient.

Auteur(s)

  • Pierre SPITERI : Professeur émérite - Université de Toulouse, INP-ENSEEIHT – IRIT, Toulouse, France

  • Jean-Claude MIELLOU : Professeur honoraire - Université de Bourgogne Franche-Comté, Département de Mathématiques, Besançon, France

INTRODUCTION

Dans un premier article [AF 1 385], pour résoudre des problèmes pseudo-linéaires univoques et multivoques, ce dernier cas correspondant à la situation où la solution est soumise à des contraintes de type inégalité, nous avons présenté le modèle mathématique décrivant les méthodes itératives parallèles asynchrones. Nous avons également présenté trois méthodes distinctes permettant, sous des hypothèses convenables, d’analyser le comportement de ces méthodes itératives. L’analyse de la convergence de ces méthodes peut s’effectuer soit par des techniques de contraction, soit par des techniques d’ordre partiel liées à l’utilisation du principe du maximum discret, soit encore parce que les itérés successifs appartiennent à des ensembles emboités centrés sur la solution U* du problème à résoudre. Il est à noter que cette dernière approche reposant sur les ensembles emboités permet d’unifier les deux approches précédentes basées sur des techniques de contraction ou d’ordre partiel mais cependant ne fournit pas de critères pratiques de convergence. Une comparaison de ces trois techniques d’analyse a permis de dégager les avantages de chacune d’elle ; en particulier, sous des hypothèses convenables, les techniques de contraction permettent de donner une estimation de la vitesse asymptotique de convergence de ces méthodes itératives et d’obtenir une propriété de convergence quelle que soit la décomposition en blocs du problème à résoudre. De plus ce type d’analyse par contraction est utilisable pour la résolution de problèmes pseudo-linéaires univoques et multivoques, alors que les techniques d’ordre partiel ne peuvent être utilisables que pour la résolution de problèmes pseudo-linéaires univoques dans la mesure où l’hypothèse de continuité nécessaire dans le critère d’analyse par des techniques d’ordre partiel n’est pas satisfaite.

Toujours dans ce premier article [AF 1 385], il a été indiqué diverses méthodes de décomposition en blocs du problème à résoudre. Il s’agit des méthodes de sous-domaines ou plus généralement des méthodes de multi-décomposition. Grâce aux résultats établis précédemment l’analyse du comportement de ces méthodes a pu être étudiée. Enfin dans cet article divers exemples de problèmes classiques, où les critères d’analyse ont été appliqués pratiquement, ont été présentés.

L’article suivant [AF 1 386], consacré à l’implémentation des méthodes itératives parallèles asynchrones comporte deux parties distinctes nécessaires à la mise en oeuvre de ces méthodes. La première partie est consacrée à la terminaison de ces algorithmes itératifs parallèles asynchrones ; c’est un problème très difficile qui nécessite l’utilisation combinée de techniques informatiques diverses et variées ainsi que la mise en œuvre de tests numériques reposant soit sur les techniques de contraction, soit sur les techniques d’ordre partiel, soit sur les propriétés induites par l’analyse utilisant les ensembles emboités. Divers critères pratiques de terminaison ont été exposés. La seconde partie du deuxième article [AF 1 386] était consacrée à la mise en œuvre des algorithmes itératifs parallèles asynchrones sur des machines multiprocesseurs. Cette implémentation nécessite un rappel des concepts de programmation des algorithmes numériques ainsi que l’exposé d’une classification des architectures des machines multiprocesseurs et des diverses méthodes de parallélisation. Après avoir rappelé les concepts de base des fonctions MPI (Message Passing Interface), en particulier des mécanismes de communications synchrones et asynchrones, le principe d’implémentation des méthodes itératives parallèles asynchrones a été présenté. Divers aspects d’équilibrage des charges en algorithmique asynchrone ont également été décrits ainsi que l’utilisation des architectures GPU (Graphics Processing Unit).

Le présent article a pour vocation de compléter les deux précédents articles. Dans une première partie nous verrons diverses applications des algorithmes itératifs parallèles asynchrones pour, d’une part, résoudre numériquement des problèmes de grande dimension et, d’autre part, des problèmes non numériques en relation avec du calcul booléen ou des problèmes de sécurité informatique. Enfin, pour terminer nous analysons sur des exemples de problèmes réels et en fonction des architectures des machines, l’efficacité des algorithmes itératifs parallèles asynchrones comparée aux méthodes synchrones. On termine cette série d’articles par une annexe mathématique explicitant le plus simplement possible les concepts théoriques sous-jacents pour l’analyse de la convergence par contraction.

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

KEYWORDS

high performance computing   |   discretized pseudo-linear problems   |   efficiency of algorithms   |   large scale problems

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af1387


Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

3. Conclusion

Dans cette série d’articles, nous avons présenté de manière synthétique et aussi complète que possible, les méthodes itératives parallèles asynchrones, en essayant de mettre en évidence les points essentiels. Les références à de nombreux travaux permettront au lecteur d’approfondir ce vaste sujet en pleine évolution. Cependant, cette liste de travaux n’est pas exhaustive dans la mesure où il est difficile de citer tous les travaux réalisés dans au moins 50 laboratoires dans le monde entier. Néanmoins, une recherche bibliographique sur Internet permet d’enrichir la liste des références mentionnées dans cette étude.

HAUT DE PAGE

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Conclusion
Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - ARNAL (J.), MIGALLÓN (V.), PENADÉS (J.) -   Non-stationary parallel multisplitting algorithms for almost linear systems.  -  In: Numer. Linear Algebra Appl. 6, p. 79–92 (1999).

  • (2) - BAHI (J.), MIELLOU (J.-C.), RHOFIR (K.) -   Asynchronous Multisplitting Methods for Nonlinear Fixed Point Problems.  -  In: Numerical Algorithms 15, p. 315–345 (1997).

  • (3) - BAHI (J.), GRIEPENTROG (E.), MIELLOU (J.-C.) -   Parallel treatment of a class of differential algebraic systems.  -  In: SIAM J. Numer. Anal. 23, p. 1969–1980 (1996).

  • (4) - BAHI (J.), MIELLOU (J.-C.) -   Asynchronous multisplitting algorithms for differential-algebraic systems discretized by Runge-Kutta methods.  -  In: Proceedings of the 8th Colloquium on Differential Equations. Sous la dir. de D. Bainov editor. VSP International Science Publishers Utrecht, p. 315–323 (1998).

  • (5) - RHOFIR (K.), EL KYAL (M.), BAHI (J.), MIELLOU (J.-C.) -   Résolution d’un système différentiel algébrique raide par une méthode...

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS