Liste des événements uniques du groupe Groupe de travail ScAlApplix-RUNTIME


2006-12-05Méthodes d'ordre élevées et adaptation de maillage pour les lois de conservation
13:00-14:15
Salle 075
Cette présentation expose le concept de l'adaptation de maillage et décrit les techniques développées à l'INRIA au sein du projet Gamma. Chaque étape du schéma d'adaptation de maillage sera décrite, ainsi que les différents algorithmes permettant entre autre de traiter de manière adaptative des problèmes instationnaires. Etant donné que les schémas d'adaptation de maillage impliquent plusieurs codes, il est donc nécessaire lors d'un calcul à un certain ordre que toute la boucle d'adaptation soit à cet ordre, i.e., chaque étape doit être d'ordre élevée. De plus, certaines étapes doivent préserver (prendre en compte) les propriétés physiques du problème étudié. Par ailleurs, on montrera que les techniques d'adaptation de maillage sont nécessaires pour préserver l'ordre de convergence global des méthodes numériques lorsque les solutions sont non régulières (par exemple des écoulements avec chocs). En effet dans le cas des discontinuités, seulement un ordre de convergence en maillage de 1/p est atteint en norme Lp avec des méthodes standards. Dans notre approche, un ordre deux de convergence global théorique est prédit pour des modèles simplifiés. L'analyse théorique est basée sur le concept de métrique continue. Elle utilise la notion de classe d'équivalence de maillages. La métrique est alors vue comme un représentant continue de la classe de tous les maillages qui ont un certain niveau d'erreur d'interpolation locale donnée. A partir d'un modèle d'erreur continu, on exhibe alors la métrique optimale qui minimise l'erreur d'interpolation en norme Lp à l'aide d'un calcul global de variation. Plusieurs exemples viendront illustrer l'efficacité de la méthode sur des applications concrètes en stationnaire et instationnaire. Une analyse de l'ordre de convergence numérique sera présentée.
 Plus d'infos  


2006-11-28RICAr: un solveur hybride direct-itératif basé sur une approche de type factorisation incomplète par blocs
13:00-14:00
Salle 075
Les solveurs directs sont maintenant capables de résoudre efficacement des problèmes 3D comportant des millions d'équations, mais ils
nécessitent beaucoup de mémoire. Pour leur part, les solveurs itératifs nécessitent beaucoup moins de mémoire mais sont moins efficaces (voir inefficaces) pour résoudre des problèmes très mal conditionnés. Nous proposons une approche hybride directe/itérative, différente de celle présentée dans le GT précédent, qui est également un compromis entre ces deux classes de méthodes.
Le but de ce travail est d'utiliser au mieux la technologie algorithmique parallèle par bloc qui est utilisée pour les solveurs directs haute performance pour développer des préconditionneurs parallèles de type Cholesky incomplet de manière adaptative et paramétrée, et qui soient robustes numériquement, suffisamment économes en mémoire et très performants en temps CPU.
Ces préconditionneurs sont alors intégrés dans des implémentations par blocs d'algorithmes du type gradient conjugué ou GMRES.
Nous conservons les techniques de renumérotation et de distribution/ordonnancement pour avoir une implémentation parallèle efficace
du calcul par bloc du préconditionneur et des itérés.
 Plus d'infos  


2006-11-21HIPS: un solveur hybride direct-itératif basé sur une approche complément de Schur
13:00-14:00
Les solveurs directs sont maintenant capables de résoudre efficacement des problèmes 3D comportant des millions d'équations, mais ils nécessitent beaucoup de mémoire. Pour leur part, les solveurs itératifs nécessitent beaucoup moins de mémoire mais sont moins efficaces (voir inefficaces) pour résoudre des problèmes très mal conditionnés. Nous proposons une approche hybride directe/itérative qui est un compromis entre ces deux classes de méthodes. Le principe de la méthode est de définir un ordonnancement et un partitionnement des inconnues qui repose sur une numérotation de type dissection emboîtée (ex: Scotch ou Metis) mais où les séparateurs sont décomposés de manière hierarchique (ex face, arete et coin dans le cas simple d'un cube). Les sous-graphes produits dans la phase de dissection emboîtée sont éliminés en utilisant une méthode directe et le complément de Schur sur le reste des inconnues (qui correspondent aux interfaces entre les sous-domaines) est résolu en utilisant une méthode itérative. L'ordonnancement et le partitionnement hiérarchique de l'interface permet l'utilisation d'algorithmes par blocs denses pour le traitement du complément de Schur et procure un très grand degré de parallélisme à ces algorithmes. Nous comparerons plusieurs variantes de cette méthode offrant des compromis temps/mémoire différents.
 Plus d'infos  


2006-06-15Runtime Reorderings to Improve Irregular Array Accesses
14:15-15:30
075
Processor speeds are increasing must faster than the speed of making random accesses to a large memory. But often algorithms that have low operation counts have poor locality in their memory reference patterns. This makes it possible to improve performance by determining (at run time) improved data layouts or iteration orderings.
We will survey several techniques that can be used to achieve such performance improvements. Then we will present a framework (developed by Kelly and Pugh, and extended by our student Michelle Strout), that might allow a compiler to express and select an appropriate composition of reordering techniques automatically.
 Plus d'infos  


2006-04-25MPICH2 : Nemesis, une implémentation hautes performances de MPI2
14:15-15:15
salle 075
Jusqu'a très récemment, les implémentations du standard MPI2 n'étaient pas très courante, quelques constructeurs seulement les proposaient avec leur matériel. Depuis quelques mois, l'univers MPI a bouge avec l'apparition de nouvelles implémentations libres : MPICH2, Open MPI ou encore YAMPII. Dans cet expose, je détaillerai un sous-système de communication qui a été crée et développé pour permettre a MPICH2 d'obtenir de hautes performances. Je montrerai également les premiers résultats obtenus (certains publies, d'autres non) et établierai des comparaisons entre les précédents sous-systèmes de communication existants pour MPICH2, mais aussi avec les implémentations concurrentes.

 Plus d'infos  


2006-03-28Équilibrage de charge et redistribution de données sur plates-formes hétérogènes
14:15-15:15
salle 075
Nous nous sommes intéressée à la mise en oeuvre d'algorithmes itératifs sur des grappes hétérogènes. Ces algorithmes fonctionnent avec un volume important de données (calcul de matrices, traitement d'images, etc.), qui sera réparti sur l'ensemble des processeurs. À chaque itération, des calculs indépendants sont effectués en parallèle et certaines communications ont lieu. Prenons l'exemple d'une matrice rectangulaire de données : l'algorithme itératif fonctionne répétitivement sur cette matrice, divisée en tranches verticales (ou horizontales) allouées aux processeurs. À chaque étape de l'algorithme, les tranches sont mises à jour localement et les informations frontières sont échangées entre tranches consécutives. Cette contrainte géométrique implique que les processeurs soient organisés en anneau virtuel. Chaque processeur communique seulement deux fois, une fois avec son prédécesseur (virtuel) dans l'anneau et une fois avec son successeur. Il n'existe pas de raison a priori de réduire le partitionnement des données à une unique dimension et de ne l'appliquer que sur un anneau de processeurs unidimensionnel. Cependant, un tel partitionnement est très naturel et nous montrerons que trouver l'optimal est déjà très difficile.
Après cette étude sur le placement et l'équilibrage de charge pour plates-formes hétérogènes, nous nous sommes intéressée à la redistribution de données sur ces mêmes plates-formes, lorsque que les caractéristiques de ces dernières changent. En ce qui concerne les anneaux de processeurs homogènes, nous avons totalement résolu le problème : nous avons obtenu des algorithmes optimaux et prouvé leur exactitude dans le cas homogène et dans le cas hétérogène. En ce qui concerne les anneaux hétérogènes, le cas unidirectionnel a été totalement résolu, alors que le cas bidirectionnel reste ouvert. Cependant, sous l'hypothèse de redistribution légère, nous sommes capable de résoudre le problème de manière optimale.
 Plus d'infos  


2006-03-21Redistribution de données à travers un réseau à haut débit
14:15-15:15
Salle 075
Le calcul distribué sur internet (appelé aussi méta-computing) est un domaine de l'informatique qui regroupe à la fois le réseau et le calcul haute performance. Pour utiliser au mieux les ressources distribuées (calculateurs parallèles, grappes d'ordinateurs, serveurs de calcul ou de données, ordinateur personnel, dispositifs de visualisation, etc.) et plus généralement l'infrastructure numérique il est nécessaire de mettre au point des environnements et des algorithmes qui gèrent celle-ci de manière optimisée. Nous présenterons le problème qui survient lorsque des données doivent être rapidement transférées d'un calculateur parallèle à un autre calculateur. C'est le cas lorsque le traitement fait intervenir du couplage de code ou lorsque l'on veut visualiser des données calculées par une machine parallèle. Ce problème appelé la redistribution de données est un problème très important quand les critères de performances sont au premier plan. Pour être résolu, il nécessite surtout d'optimiser l'ordre dans lequel les données sont transférées.

 Plus d'infos  




Liste des événements répétitifs du groupe Groupe de travail ScAlApplix-RUNTIME




Retour
Retour à l'index