Réseaux et systèmes répartis Volume 13 N° 1/2001

De puissants calculateurs sont à la portée d'un grand nombre d'utilisateurs, ces ordinateurs sont en plus interconnectés par des réseaux de plus en plus rapides. Face à ces performances, les codes requis pour des applications complexes sont de plus en plus grands et lents.

La recherche en algorithmique parallèle et distribuée a pour double objectif de bénéficier de cet essor et de donner des directions futures à ce développement technologique.

La distinction entre algorithmes parallèles et distribués peut se baser sur la différence entre les deux architectures de même nom. En simplifiant et sans tenir compte de la configuration de la mémoire, on pourrait dire que les algorithmes parallèles sont conçus pour être exécutés sur un ensemble de processeurs situés à " petites distances " les uns des autres ; dans ce cas, le but principal est la performance des algorithmes ainsi parallélisés. Les algorithmes distribués sont conçus pour être implantés sur un ensemble de machines distantes reliées par un réseau de communication. Apparaissent alors des problématiques de latence de communication, de performance, de fiabilité et de coût de maintenance.

Ce numéro est consacré aux algorithmes itératifs, dont les applications en informatique sont nombreuses et variées, et qui parfois sont incontournables vu la nature de l'application traitée ; c'est le cas dans l'article sur l'extraction de racines de polynômes de R. Couturier et F. Spies : on sait, par la théorie de Galois, que dès que le degré d'un polynôme est supérieur à cinq, il est impossible de trouver ses racines par une méthode directe.

Un algorithme itératif a pour but de construire, à partir d'un vecteur initial, une suite de vecteurs dont la limite est la solution du problème considéré. C'est ce qui a été initié par Gauss il y a à peu près 180 ans. L'avènement des calculateurs parallèles a donné à ce domaine de recherche, une nouvelle vitalité dont témoignent les différents colloques périodiques et revues spécialisées. Il ne s'agit pas d'implanter naïvement, sur calculateurs parallèles, un algorithme itératif séquentiellement convergent, mais d'étudier les problèmes de convergence de l'algorithme parallèle, sa meilleure parallélisation et sa réelle efficacité. La suite d'itérés se trouvent modifiée à cause des latences de communications, ce qui pourrait avoir pour effet de détruire les propriétés de convergence. Dans l'article de P. Spitéri, J.-C. Miellou et D. El Baz, sur la méthode alternée de Schwarz asynchrone avec communications flexibles pour le problème de l'obstacle, on est assuré de la convergence de la méthode sans avoir à synchroniser les communications entre les processeurs.

Dans ce numéro, trois applications scientifiques sont présentées, l'une, de F. Magoulès et J.-C. Autrique, est consacrée aux radiations acoustiques sousmarines la deuxième, de M. Brieu, F. Devries et J. Erhel, aux simulations de propagations d'endommagement dans les milieux hyperélastiques. La troisième, de S. Contassot-Vivier et J. M. Bahi porte sur la reconnaissance deforme asynchrone ; cette dernière peut être mise en oeuvre aussi bien sur architectures parallèles ou distribuées sans se préoccuper de l'aspect indéterministe des communications interprocesseurs, ni de l'éventuel changement de topologie du réseau de communication.

Cependant, comme mentionné plus haut, les performances ne sont plus la seule priorité du calcul parallèle : permettre aux utilisateurs d'accéder facilement à des environnements parallèles et distribués sûrs, est devenu un objectif très important. Pour programmer facilement des applications complexes, diminuer les coûts de maintenance, une solution consiste à utiliser des langages à objets ; c'est dans ce cadre que s'inscrit l'article de R. Guivarch, G. Padiou et Ph. Papaïx sur la méthode alternée de Schwarz asynchrone dans un environnement distribué.

Le dernier article de ce numéro, de Z. Z. Bai et D. J. Evans, est un article de synthèse présentant les algorithmes de partitionnement de matrices " multisplitting " il s'agit de l'analogue en dimension finie des méthodes de sous-domaines.

Beaucoup de sujets très importants auraient pu être publiés dans ce numéro car ils englobent des algorithmes itératifs parallèles ou distribués, ils trouveront certainement leur place dans d'autres numéros de cette revue.

Sommaire

Editorial - Michel Tréhel

Introduction - Jacques Bahi

• Calcul parallèle et méthodes d'éléments finis et infinis pour des problèmes de radiation acoustique.
• Décomposition de domaine et acoustique
• Frédéric Magoulès, Jean-Christophe Autrique

• Asynchronous Schwarz alternating method in an observation based distributed environment
• Ronan Guivarch, Gérard Padiou, Philippe Papaïx

• Asynchronous Schwarz alternating methods with flexible communication for the obstacle problem
• Pierre Spiteri, Jean-Claude Miellou, Didier El Baz

• Extraction de racines dans des polynômes creux de degré élevé
• Raphaël Couturier, François Spies

• Algorithme parallèle non incrémental pour la simulation de l'évolution d'endommagements en milieux hyperélastiques
• Mathias Brieu, François Devries, Jocelyne Erhel

• Convergence dans les systèmes booléens asynchrones et application aux réseaux de Hopfield
• Sylvain Contassot-Vivier, Jacques Bahi

• Matrix multisplitting methods with applications to linear complementarity problems: parallel synchronous and chaotic methods
• Zhong-Zhi Bai, DJ. Evans