Algorithmes itératifs asynchrones

L’asynchronisme est en passe de devenir un sujet de recherche majeur en informatique et en microélectronique. Ce sujet recouvre les nombreuses facettes du même concept qui consiste à laisser aller les entités considérées à leur propre rythme en l’absence d’horloge globale et de synchronisation. On retrouve ce sujet dans divers domaines comme les circuits, les communications, les processus ou les algorithmes. Par exemple, on parle de circuits asynchrones lorsqu’il n’y a pas d’horloge globale et on retrouve cette notion dans les coprocesseurs asynchrones. On parle aussi de communications asynchrones dans les systèmes à passage de message lorsque les opérations de communication ne mettent pas en œuvre des mécanismes de type poignée de main ou dans le cas d’accès mémoires distants. On retrouve aussi  ce concept dans les  systèmes distribués avec les « wait free processes » ou processus sans attente. Les processus légers ou fils possèdent aussi un caractère asynchrone. En algorithmique parallèle ou distribuée, ce concept est présent dans les algorithmes itératifs asynchrones (qui sont des méthodes d’approximation successives pour lesquelles les composantes du vecteur itéré sont réactualisées sans ordre particulier ni synchronisation).

Une des caractéristiques majeures des algorithmes itératifs asynchrones est leur aptitude à fonctionner correctement avec tout type de réseau de communication et donc sur tout type de système distribué car ils sont par nature conçus dans le cadre d’un modèle général asynchrone et sont donc adaptés à des situations où les délais de communication sont a priori non bornés. Les algorithmes itératifs asynchrones pour lesquels les communications sont recouvertes par du calcul présentent généralement une très bonne efficacité. Ces performances sont particulièrement notables lorsque les tâches de calcul sont déséquilibrées. Par ailleurs, il n’est pas réaliste de synchroniser des processus sur des architectures massivement parallèles ou distribuées ainsi que sur de grandes grilles de calcul. Les algorithmes itératifs asynchrones possèdent des propriétés de tolérance aux fautes puisque ces algorithmes peuvent fonctionner correctement même lorsque certains messages sont perdus. Les algorithmes asynchrones connaissent enfin un intérêt croissant de la part des concepteurs de bibliothèques de communication comme Open MPI de  l’Université du Tennessee et du Los Alamos National Laboratory ou des utilisateurs de machines hybrides et de cartes GPUs.

L’étude du concept d’asynchronisme nous semble capitale afin de traiter les aspects liés à l’efficacité des algorithmes parallèles ou distribués et de maitriser la nature profonde du calcul distribué. On notera que ce sujet important a été étudié par de nombreux chercheurs dans des universités prestigieuses comme les équipes de D. Bertsekas et J. Tsitsiklis au MIT, D. Szyld à Temple University, M. Dubois University of Southern California, Z. Z. Bai à l’Académie des Sciences Chinoise, D. J. Evans Loughborough University of Technology, A. Frommer Wuppertal Universität et R. Bru, V. Migallon et J. Penadés à l’Université d’Alicante.

Nos études passées ont porté sur des aspects théoriques (on peut citer notamment la modélisation mathématique, l’étude de la convergence, la détection de la convergence, l’étude des effets liés aux erreurs d’arrondi) ainsi que sur des aspects appliqués (on peut citer l’application de ces schémas itératifs parallèles ou distribués à divers problèmes de point fixe en simulation numérique comme des problèmes aux limites, en optimisation comme les problèmes convexes de flots dans les réseaux ou en commande optimale ainsi que la mise en œuvre effective d’algorithmes itératifs asynchrones sur diverses architectures de calcul généralistes ou dédiées). Nous avons travaillé en particulier sur des supercalculateurs à mémoire partagée ou à mémoire distribuée, des clusters et des grilles de calculs comme Grid 5000 ou diverses plateformes réseau comme PlanetLab (cf en particulier la liste des publications et le mémoire d'HDR de Didier El Baz).

Modèles et étude de convergence

Dans ce domaine, Nous avons travaillé à la conception et l’étude de performance d’une nouvelle classe générale d’algorithmes itératifs parallèles ou distribués : les itérations asynchrones avec segment d’ordre. Cette classe de méthodes itératives encore appelées itérations asynchrones flexibles est plus générale que la classe des itérations asynchrones. Elle présente l’avantage d’autoriser la prise en compte d’informations partielles issues de réactualisations en cours d’exécution, contrairement aux itérations asynchrones classiques (qui ne peuvent prendre en compte dans les calculs que les résultats de chaque phase de réactualisation et qui utilisent donc uniquement les valeurs des composantes du vecteur itéré qui sont étiquetées par un numéro d’itération). Cette nouvelle propriété est particulièrement intéressante dans le cas de la convergence sous ordre partiel pour laquelle le vecteur itéré converge de manière monotone vers la solution d’un problème de point fixe ou de l’utilisation de méthodes par blocs. Cette nouvelle classe d’algorithmes parallèles est aussi en adéquation avec des opérations de communication faisant des accès directs mémoire comme les  shmem put et les shmem get de MPI2. Un exemple simple de fonctionnement est illustré par la  Figure 1 a, où nous avons représenté le comportement de deux machines  et  au cours du temps (qui est en en abscisse). Chaque machine réactualise un sous-vecteur du vecteur itéré. Les rectangles représentent les phases de réactualisation des sous-vecteurs du vecteur itéré qui s’enchainent au cours du temps, ils sont étiquetés par un numéro de réactualisation. Les flèches en traits épais représentent les communications des valeurs d’itérés comme dans le modèle classique des itérations asynchrones donné par Baudet (cf. Figure 1 b). Les flèches en traits fins de la Figure 1 a représentent les communications des valeurs d’itérés partiels. L’innovation apportée par le modèle des algorithmes asynchrones avec segment d’ordre se situe à ce niveau. On notera que dans les modèles d’itérations asynchrones, les machines vont à leur propre rythme et n’attendent pas d’avoir reçu un message de leur voisin avant de commencer une nouvelle réactualisation du sous-vecteur qui leur est affecté.

              
Figure 1 a : itérations asynchrones avec segment d’ordre               Figure 1 b : itérations asynchrones classiques
 

Figure 1 c : méthode itérative synchrone

La Figure 1 c illustre un schéma itératif synchrone comme celui que l’on retrouve par exemple dans la méthode classique de Jacobi. Cette figure est donnée afin de pouvoir établir plus simplement une comparaison avec le cas exposé Figure 1 a. On notera que les rectangles hachurés de la Figure 1 correspondent à des temps d’attente résultants de la non réception d’un message ou bien d’un délai de transmission d’un message. Il n’y a pas de recouvrement des communications par des calculs dans le contexte synchrone.

La modélisation mathématique des itérations asynchrones avec segment d’ordre ainsi que l’étude de leur convergence sous ordre partiel pour des problèmes d’optimisation non linéaires de type flots dans les réseaux et des problèmes aux limites ont été étudiées dans deux articles présentées publiés dans Journal of Parallel and Distributed Computing en 1996 et Mathematics of Computation en 1998. Divers problèmes de simulation numérique ont été considérés :
- problèmes d’obstacle ;
- problèmes d’Hamilton-Jacobi-Bellman ;
- problèmes de convection-diffusion.
Nous avons aussi étudié la convergence des itérations asynchrones avec segment d’ordre dans un contexte de contraction dans un article publié dans Journal of Computational and Applied Mathematics en 2005 en collaboration avec le Professeur Andreas Frommer de l’Université de Wuppertal. 

Dans le contexte des modèles classiques d’itérations asynchrones on notera les travaux que nous avons effectués sur la convergence sous ordre partiel, ou convergence monotone, d’algorithmes itératifs asynchrones distribués pour des problèmes convexes de flots dans les réseaux ou pour des problèmes non linéaires faisant intervenir des M-fonctions. Ces travaux ont été publiés respectivement dans SIAM Journal on Control and Optimization en 1987 et dans SIAM Journal on Numerical Analysis en 1990. Les cinq articles mentionnés ci-dessus ont été cités plus de 230 fois dans la litérature. Pour les problèmes convexes de flot dans les réseaux, qui sont des problèmes séparables d’optimisation et qui interviennent dans les réseaux de communication ou dans la distribution de gaz ou d’eau, nous avons étudié la convergence sous ordre partiel de  divers algorithmes itératifs asynchrones de relaxation, de gradient ou de Newton multisplitting (cf. liste des publications).

Plus récemment, nous avons proposé une nouvelle classe d’algorithmes itératifs asynchrones, les algorithmes hybrides, dans un article publié à PDP 2010. Cette nouvelle classe d’algorithmes itératifs distribués est particulièrement attractive dans un contexte de calcul pair à pair ou de cluster computing pour lequel les machines peuvent être regroupées suivant leur proximité ainsi que des caractéristiques identiques. Les calculs sont effectués suivant le mode synchrone sur chaque cluster ou groupe de machine ; le fonctionnement global étant asynchrone. Ces articles ont été cités plus de 33 fois dans la littérature.

Critères d’arrêt

Dans le cas le plus général, les itérations asynchrones qui sont des méthodes d’approximations successives ne terminent pas en temps fini ; l’arrêt des itérations asynchrones est donc un problème crucial qui est de surcroît très complexe du fait de l’absence de synchronisation et du comportement chaotique des algorithmes. Par conséquent, il est de première importance de donner des critères d’arrêt pour ces méthodes  distribuées ou parallèles. Nous avons donné divers critères d’arrêt pour les itérations asynchrones dans un contexte d’erreur d’arrondi. Ces résultats  ont été présentés notamment dans un article publié dans Electronic Transactions on Numerical Analysis en 2002. En particulier, le diamètre de la boule dans laquelle convergent les itérations asynchrones perturbées par des erreurs d’arrondi a pu être précisé dans cette publication. Des extensions de ces résultats pour des erreurs de type « backward » ou « forward » ont été proposées par la suite dans un article publié dans IMA Journal on Numerical Analysis en 2005.

Des critères d’arrêt et des procédures de détection de la convergence ont été proposés dans un contexte de contraction en norme vectorielle dans la revue Parallel Algorithms and Applications en 1996 ; cet article a été cité plus de 30 fois dans la littérature. Dans le cas particulier des problèmes simple flot convexes dans les réseaux, une procédure de détection de la convergence basée sur un test local qui agrège les informations sur l’état global du système a été proposée. Dans ce contexte, la valeur absolue du résidu au sommet destination du réseau majore la somme des valeurs absolues des résidus aux autres sommets du réseau.

Il est à noter que les effets de perturbation des itérations asynchrones provenant de procédures d’arrêt ont été étudiés dans un article publié dans International Mathematical Journal en 2002. Plus récemment, un nouveau critère d’arrêt théorique en relation avec des erreurs absolues a été proposé dans le cas linéaire pour des méthodes de point fixe dans un article publié dans Journal of Computational and Applied Mathematics en 2008. Dans cet article, nous avons présenté une approche originale basée sur le concept de macro-itération et d’horizon glissant, tous les tests relatifs à l’arrêt étant effectués au sein de la même macro-itération. Ce critère d’arrêt est très utile afin de mettre en œuvre efficacement les algorithmes asynchrones sur des architectures parallèles ou distribuées.

Mise en œuvre des algorithmes itératifs asynchrones

Nous avons étudié les performances sur IBM SP4 des schémas itératifs parallèles asynchrones appliqués à des méthodes de sous-domaine pour des problèmes de convection-diffusion non linéaires  dans un article publié dans Journal of Parallel and Distributed Computing en 2007. Ces tests ont été effectués sur plus de 100 processeurs ; nous avons considéré plusieurs fréquences d’échanges de données. Nous avons obtenu les meilleurs résultats pour de hautes fréquences d’échanges de données. Les performances des algorithmes asynchrones et des  algorithmes synchrones sont illustrées Figure 2. On constate que le surcoût de synchronisation entraine une rapide chute de l’efficacité des algorithmes itératifs synchrones (l’accélération d’un algorithme parallèle correspondant au ratio temps séquentiel sur temps parallèle, l’efficacité étant le ratio accélération sur nombre de processeurs).

Figure 2 : Efficacité des algorithmes parallèles asynchrones (pointillés) et synchrones (traits pleins) en fonction du nombre de processeurs sur machine IBM SP4 pour un problème de convection-diffusion.

Ces études de performance portant sur les algorithmes itératifs asynchrones font suite à un ensemble de travaux effectués pour des applications en simulation numérique (il s’agit de problèmes d’obstacle et d’Hamilton-Jacobi-Bellman qui interviennent en mécanique, en finance ou en économie), en optimisation non linéaire (nous avons considéré des problèmes de flot dans les réseaux) et en commande optimale (il s’agit de la commande d’un four) sur divers supercalculateurs à mémoire partagé ou à mémoire distribuée tels que le Cray T3E, l’Origin 2000, l’Origin 3800, ainsi que des stations de travail de type SMP, des clusters et grilles de calculs comme GRID 5000 ou diverses plateforme réseau comme PlanetLab. Ces travaux ont été publiés notamment dans les journaux scientifiques Parallel Computing en 1993, Computational Optimization and Applications en 1996, Journal of Parallel and Distributed Computing en 1996, The Journal of Systems and Software en 2002 et Numerical Algorithms en 2003. Les articles mentionnés dans cette section ont été cités plus de 85 fois dans la littérature (cf. liste des publications).

Nous avons étudié les performances des schémas itératifs synchrones, asynchrones et hybrides appliqués à des méthodes de sous-domaine pour des problèmes d’obstacle sur architecture pair à pair. Ces résultats ont été publiés notamment à HPCC 2012. Des tests ont été effectués sur 256 machines de Grid 5000 distribuées sur cinq sites. Les performances des algorithmes synchrones, asynchrones et hybrides sont illustrées Figure 3. On constate que le surcoût de synchronisation entraine une rapide chute de l’efficacité des algorithmes itératifs synchrones  ; les itérations asynchrones présentent une très bonne efficacité même quand les calculs sont mis en œuvre sur des sites éloignés. La Figure 4 illustre l'accélération des algorithmes itératifs asynchrones pour des expérimentations effectuées sur PlanetLab avec 24 machines distribuées sur huit sites en Europe et quatre sites aux USA; ces résultats ont été publiées à PDP 2014. Des comparaisons sur clusters Infiniband et clusters Ethernet ont été publiées à PDP 2013. Plus récemment, des expérimentations on été effectuées sur Grid5000 dans un contexte multiréseau (cf. Figure 5). Des problèmes financiers évolutifs liés au prix d’options américaines ou européennes ont aussi été étudiés dans IPDPSW 2011 / PDSEC 2011.

Figure 3 : Efficacité des algorithmes itératifs synchrones, asynchrones et hybrides en fonction du nombre de pairs pour un problème d’obstacle mis en œuvre sur Grid 5000 avec 256 machines distribuées sur cinq sites en France.

 

Figure 4 : Accélération des algorithmes itératifs asynchrones en fonction du nombre de pairs pour un problème d’obstacle mis en oeuvre sur PlanetLab avec 24 machines distribuées sur douze sites (huit sites en Europe et quatre sites aux USA).

 

Figure 5 : Efficacité des algorithmes itératifs synchrones et asynchrones en fonction du nombre de pairs pour un problème d’obstacle mis en oeuvre sur Grid5000 avec 32 machines dans un contexte multi réseaux Ethernet et Infiniband.

Dans le cadre du projet ANR Smart surface (ANR-06-ROBO-0009), nous avons proposé divers algorithmes itératifs distribués synchrones et asynchrones pour l’acquisition de l’état global d’une smart surface de convoyage et de tri de micro pièces (c'est-à-dire pour la détermination de la position des pièces sur la surface) et la différentiation des pièces. Le problème a été modélisé comme un problème de point fixe. nous avons donné des preuves de convergence sous ordre partiel de ces algorithmes itératifs distribués et nous avons proposé divers critères d’arrêt. Ces résultats on été publiée dans Mechatronics en 2012 (voir aussi le Projet Smart Surface).