 |
 |
|
Le but du projet était de déterminer un ensemble de paradigmes de conception pour les algorithmes parallèles: paradigmes exploitables pour la conception de programmes parallèles dans les domaines d'application de l'ingénierie. Pour parvenir à déterminer ces paradigmes, une étude des méthodes de conception des algorithmes séquentiels et parallèles a été menée en examinant le domaine de la géométrie algorithmique, la mise en oeuvre de ces méthodes dans le cadre des architectures des machines parallèles a été étudiée, les paradigmes ont été validés avec succès en testant leurs applications dans le développement de programmes de calcul des éléments finis sur machines parallèles.
Les activités de recherche du projet ont associé deux services de la Faculté des Sciences Appliquées de l’Université de Liège : le service d'Informatique (algorithmique), orienté vers l'étude et la définition des méthodes de développement des algorithmes, et le Laboratoire des Techniques Aéronautiques et Spatiales, impliqué régulièrement dans la conception et le développement de méthodes de calcul avancées en ingénierie.
Maîtriser le développement des algorithmes pour l'utilisation la plus efficace des nouveaux équipements parallèles est un défi important pour les sciences appliquées. Pour conserver la possibilité de pratiquer efficacement la conception en ingénierie, l'utilisation d'équipements parallèles s'impose de plus en plus : les réseaux de stations de travail permettent de regrouper une importante puissance de calcul, les multiprocesseurs à mémoire distribuée permettent d'envisager de s'attaquer à la résolution de problèmes de très grande taille, trop grande pour un traitement sur un monoprocesseur. La difficulté majeure provient de la conception d’algorithmes parallèles qui peuvent exploiter efficacement une architecture parallèle et justifier l’accroissement de matériel que cette architecture implique.
L’étude des paradigmes de conception des algorithmes séquentiels a mis en évidence la décomposition d’un problème en problèmes plus simples par la recherche de relations de récurrence. En général, les algorithmes séquentiels performants exploitent des structures de données élaborées qui permettent d’appliquer une relation de récurrence résolvant le problème en un nombre réduit d’étapes. Cette forme d’algorithme est plus difficile à paralléliser qu’un algorithme basé sur une récurrence dans la division des données où la solution du problème est obtenue par une phase de regroupement des résultats partiels fournis par le traitement de chaque sous-ensemble des données.
La conception d'un algorithme parallèle implique un découpage à la fois des opérations et des données, de manière à déterminer un ensemble de "sous-algorithmes" qui sont associés aux différentes unités matérielles qui composent l'ordinateur parallèle. Pour répondre au critère d'utilisation effective du matériel, il importe que la décomposition assure une répartition équitable de la charge de travail des différents sous-algorithmes. L’étude des architectures parallèles a montré l’influence profonde de l’équipement sur la structure des algorithmes développés, et la difficulté de définir des concepts transposables d’un équipement à l’autre.
L’étude comparative d’algorithmes séquentiels et d’algorithmes parallèles en géométrie algorithmique, menée en tenant compte des contraintes des équipements parallèles disponibles, a permis de rassembler un ensemble de règles de parallélisation qui sont directement exploitables dans le contexte des machines réelles : machines à mémoire partagée, disposant d'un nombre relativement modeste de processeurs, fonctionnant en mode MIMD (flots d'instructions multiples); ces règles sont également exploitables dans le contexte des équipements multiprocesseurs à mémoire distribuée. Ces règles permettent de développer une version parallèle à partir d’une version séquentielle efficace.
Les règles de parallélisation ont pu être complétées et affinées en concevant des algorithmes parallèles dans le domaine des éléments finis. Les algorithmes développés traitent de la résolution des systèmes linéaires de très grandes dimensions par les méthodes directes, itératives et semi-itératives. Des résultats importants et pratiquement applicables ont été obtenus dans ce domaine. La décomposition en sous-domaines et le problème aux valeurs propres ont été également étudiés.
Une librairie portable fournissant un ensemble minimum de fonctionnalités pour la mise en oeuvre du parallélisme a été définie. Cette librairie implémente des opérations de base de la parallélisation et permet au concepteur de ne pas devoir rentrer dans les détails d’utilisation des librairies propres à chaque constructeur. La librairie permet également de faire exécuter sur un équipement multiprocesseur à mémoire partagée un algorithme conçu pour une architecture à mémoire distribuée.
Les règles de parallélisation forment un ensemble cohérent dont la compréhension permet d'aborder efficacement le développement d'algorithmes parallèles ou la parallélisation d'algorithmes séquentiels. En appliquant ces paradigmes de parallélisation, nous avons pu mener correctement à bien des opérations de parallélisation de codes "industriels", c.-à-d. avec toutes les particularités d'un logiciel appliqué industriel, (dans le cadre d’un contrat Esprit Europort/Sammi).
|
|
|