Projet MISTRAL

Activités en Modélisation du Parallélisme

Projet MISTRAL

INRIA Sophia-Antipolis 25 Janvier 1995

Types d’activités

Un programme parallèle est vu comme un ensemble de tâches élémentaires communiquant entre elles.

• Placement Affecter les tâches aux ressources (processeurs, mémoires, communications)

• Ordonnancement Préciser l’ordre d’exécution des tâches.

• Évaluation de Performances Prédire les performances (ex: temps d’exécution, débits) des programmes résultants.

Placement et Ordonnancement

Affecter un programme à une architecture, et régler les paramètres de manière a minimiser:

– un temps d’exécution (efficacité)

– un retard (temps réel) Exemples d’études:

– Ordonnancement de graphes de tâches structurés

– Ordonnancement sous contrainte de communications

– Ordonnancement dynamique

– Algorithmes de partage de charge

– Ordonnancement cyclique temps réel sur réseau Méthodes:

– Ordonnancement stochastique

– Analyse d’algorithmes

– Heuristiques (recuit, tabou, hybrides)

Modèles d’applications parallèles

– réseaux de files d’attente synchronisés

– graphes de tâches (PERT etc.)

– réseaux de Petri temporisés

– automates stochastiques

– algèbres de processus temporisées

1  2  5 7 6^{program 1}^{program 2}^{program 3}  3 4^{6}  ^{3}^{5}^{6}  ^{5}^{3}^{1}  ^{5}^{3}^{1}^{1}  ^{2}^{4}  ^{7}^{6}  ^{2}^{4}^{2}^{4}  ^{7}^{7} Graphe de tâches  Réseau de Petri

Évaluation de Performances des SED

On décrit le système à événements discrets par des équations:

X(n + 1) = Φ(X(n), ξ(n))

On se pose d’abord des questions qualitatives:

– existe-t-il un débit limite θ? Est-il unique?

– le système est-il stable? Existe-t-il un régime stationnaire? Puis des questions calculatoires:

– calcul du débit θ

– calcul de taux d’occupation

– calcul de temps d’attente ou de réponses (distributions, moyennes, etc...)

– calcul de taux de perte

– performances spécifiques

Avancées récentes

Une étude systématique des systèmes (max, +) linéaires a permis:

– la classification des domaines de stabilité

– l’étude de monotonies en fonction de paramètres

– la définition de méthodes de calculs de performances (exacts, bornes)

– la mise au point de simulateurs parallèles efficaces.

Applications: certains réseaux de Petri, graphes de tâches périodiques. Collaboration active avec le projet META2.

Projets de Recherche

• QMIPS (Esprit BRA) Objectif: fournir une méthodologie de modélisation et d’évaluation de performances de systèmes parallèles. Partenaires: CWI, U. Erlangen, U. Paris V, U. Newcastle, Imperial College, U. Saragosse,

• PEPS (Esprit III) Objectif: développer des outils pratiques pour prédire les performances de systèmes parallèles. Partenaires: Thomson Sintra, Simulog, Intecs Systemi, U. Warwick, NPL.

• AQSI (Inter-PRC/MESR) Objectif: regrouper la recherche française dans le domaine de la modélisation des systèmes informatiques. Partenaires: LGI-IMAG, U. Paris V, CNAM, U. Versailles-St Quentin, LIX, U. Bordeaux