Mises en œuvre Mises en œuvre distribuées de distribuées de
programmes synchronesprogrammes synchrones
Pascal Aubry
Environnement de Programmation pour Applications Temps-Réel
http://perso. univ-rennes1.fr/pascal.aubryhttp://perso. univ-rennes1.fr/pascal.aubry
DistributionDistribution
• Pourquoi ?Pourquoi ?– délocalisation géographique (répartition)délocalisation géographique (répartition)– gain de performance (parallélisme)gain de performance (parallélisme)– tolérance aux fautes (redondance)tolérance aux fautes (redondance)
• Comment ?Comment ?– parallélisme intrinsèque au langageparallélisme intrinsèque au langage– programmation impérative des communicationsprogrammation impérative des communications– parallélisation automatiqueparallélisation automatique– ......
Distribution du synchroneDistribution du synchrone
• Pour garder l’approche synchronePour garder l’approche synchrone– systèmes réactifssystèmes réactifs– cadre formelcadre formel
• automatisation des transformationsautomatisation des transformations• outils de validationoutils de validation
– approche algorithmiqueapproche algorithmique• indépendance vis-à-vis de l ’architectureindépendance vis-à-vis de l ’architecture
[Girault 94] (Lustre)[Girault 94] (Lustre)
[Caillaud 94] (automates)[Caillaud 94] (automates)
SignalSignal
• [Chéron 91] :[Chéron 91] :– Transformations syntaxiques de Transformations syntaxiques de
programmes Signalprogrammes Signal
• [Maffeïs 93] :[Maffeïs 93] :– ordonnancement de flots synchronesordonnancement de flots synchrones
• [Kountouris], [Machard] :[Kountouris], [Machard] :– temps d’exécution, O.S. temps-réeltemps d’exécution, O.S. temps-réel
• [Sorel 92] : Syndex[Sorel 92] : Syndex– adéquation algorithme architectureadéquation algorithme architecture
PréambulePréambule
méthodologieméthodologie
modèlemodèlethéoriethéorie
applicationapplication
correctioncorrection
intégrationintégration
PréambulePréambule
méthodologieméthodologie
modèlemodèlethéoriethéorie
applicationapplication
correctioncorrection
intégrationintégration
PréambulePréambule
méthodologieméthodologie
applicationapplication
correctioncorrection
intégrationintégration
critères qualitatifs de la distributioncritères qualitatifs de la distribution
process JEU =
(RES,SIG) := ARBITRE(SIG_A,SIG_B) SIG_A := JOUEUR(SIG) SIG_B := JOUEUR(SIG)
end
IllustrationIllustration
A BSIG_A
Match nul
SIG SIG
signauxsignaux
répartitionrépartitioncalculcalcul
dépendancesdépendances
Répartition avec SyndexRépartition avec Syndex
compilateursourcesource
directivesdirectives
programmeprogrammedistribuédistribué
répartiteur
graphegraphe??
Plus convivial...Plus convivial...
compilateursourcesource
directivesdirectives
programmeprogrammedistribuédistribué
répartiteur
graphegraphe+
INTÉGRATION
INTÉGRATION
Le point de vue de Le point de vue de l’utilisateurl’utilisateur
machine
entréesentréesconfigurationconfiguration
programmeprogrammedistribuédistribué
environnement
tracetracesourcesource
directivesdirectives
Merci, chef.
Le point de vue de Le point de vue de l’utilisateurl’utilisateur
sourcesource
directivesdirectivestracetrace
ch’uis content
Mais au fait,comment ça marche
ton truc ?
Euh…je sais pas, chef.
SS
CORRECTION
CORRECTION
(modèle)(modèle)
– Les calculs effectués correspondent-ils aux calculs Les calculs effectués correspondent-ils aux calculs spécifiés ?spécifiés ?
Les corrections Les corrections obligatoiresobligatoires
• la correction fonctionnellela correction fonctionnelle
– la mémoire nécessaire à l’exécution est-elle bornée ?la mémoire nécessaire à l’exécution est-elle bornée ?
• la correction spatialela correction spatiale
Les corrections Les corrections obligatoiresobligatoires
• la correction fonctionnellela correction fonctionnelle
– le temps de réponse du système est-il borné ?le temps de réponse du système est-il borné ?
Les corrections Les corrections obligatoiresobligatoires
• la correction fonctionnellela correction fonctionnelle
• la correction spatialela correction spatiale
• la correction temporellela correction temporelle
Les corrections Les corrections obligatoiresobligatoires
• la correction fonctionnellela correction fonctionnelle
– une partie du programme s’exécute-t-elle infiniment une partie du programme s’exécute-t-elle infiniment plus vite qu’une autre ?plus vite qu’une autre ?
• l’équitél’équité
• la correction spatialela correction spatiale
• la correction temporellela correction temporelle
Les corrections Les corrections obligatoiresobligatoires
• la correction fonctionnellela correction fonctionnelle
• l’équitél’équité
• la correction spatialela correction spatiale
• la correction temporellela correction temporelle
Propriétés classiquesPropriétés classiques
Les corrections Les corrections facultativesfacultatives
• la correction flot-de-donnéesla correction flot-de-données
– l’ordre d’observation des signaux est-il fidèle à l ’ordre l’ordre d’observation des signaux est-il fidèle à l ’ordre spécifié ?spécifié ?
Les corrections Les corrections facultativesfacultatives
• la correction flot-de-donnéesla correction flot-de-données
– Les instants logiques peuvent-ils se chevaucher ?Les instants logiques peuvent-ils se chevaucher ?
• la correction synchronela correction synchrone
Les corrections Les corrections facultativesfacultatives
• la correction flot-de-donnéesla correction flot-de-données
– l’exécution fait-elle des suppositions sur son l’exécution fait-elle des suppositions sur son environnement d’exécution ?environnement d’exécution ?
• la correction synchronela correction synchrone
• la correction compositionnellela correction compositionnelle
spécificationimplémentationenvironnement
A
B
C
D
– l’exécution fait-elle des suppositions sur son l’exécution fait-elle des suppositions sur son environnement d’exécution ?environnement d’exécution ?
Les corrections Les corrections facultativesfacultatives
• la correction flot-de-donnéesla correction flot-de-données
• la correction synchronela correction synchrone
• la correction compositionnellela correction compositionnelle
spécificationimplémentationenvironnement
A
B
C
D
CYCLECYCLE
Les corrections Les corrections facultativesfacultatives
• la correction flot-de-donnéesla correction flot-de-données
• la correction synchronela correction synchrone
• la correction compositionnellela correction compositionnelle
Propriétés spécifiquesPropriétés spécifiques
entrées
directivesdirectives
observation
stratégiestratégie
implémentationdynamique
ordonnancementordonnancementenvironnementalenvironnemental
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
descriptioninstantanéedistribuée
spécification
descriptioninstantanée
Le point de vue Le point de vue du du
programmeurprogrammeur
Les corrections Les corrections d'une mise en œuvre ...d'une mise en œuvre ...
• sont des propriétés sur les occurrences sont des propriétés sur les occurrences des signaux du programme.des signaux du programme.
• Les analyses de propriétés statiques ne Les analyses de propriétés statiques ne suffisent pas.suffisent pas.
NÉCESSITÉ
NÉCESSITÉ
D’UN MODÈLE
D’UN MODÈLE
DYNAMIQUE
DYNAMIQUE
entrées
directivesdirectives
observation
stratégiestratégie
implémentationdynamique
ordonnancementordonnancementenvironnementalenvironnemental
descriptioninstantanéedistribuée
spécification
descriptioninstantanée comportement
inférence
directivesdirectives
stratégiestratégie
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
ordonnancementordonnancementenvironnementalenvironnemental
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
entrées
observation
spécification
descriptioninstantanée comportement
inférence
directivesdirectives
stratégiestratégie
ordonnancementordonnancementenvironnementalenvironnemental
directivesdirectives
stratégiestratégie
ordonnancementordonnancementdynamiquedynamique
implémentationdynamique
ordonnancementordonnancementenvironnementalenvironnemental
ordonnancementordonnancementstatiquestatique
descriptioninstantanéedistribuée
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
Le modèle Le modèle dynamiquedynamique
entrées
observation
spécification
descriptioninstantanée comportement
inférence
directivesdirectives
stratégiestratégie
ordonnancementordonnancementenvironnementalenvironnemental
Z := X when X>0 default Y when Y>0 default X$1
X ^= Y ^= Z
X init 1
Un exempleUn exemple
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
observation
inférence
comportement
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
entrées
observation
spécification
descriptioninstantanée comportement
inférence
directivesdirectives
stratégiestratégie
ordonnancementordonnancementenvironnementalenvironnemental
Z := X when X>0 default Y when Y>0 default X$1X ^= Y ^= ZX init 1
h1(when X>0)
X
Y
Z
h2(¬h1 when Y>0)
h3(¬h1 when ¬h2)
X
Y
Z
X$1 X
Y
Z
Un exempleUn exemple
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
Un exempleUn exemple
entrées
observation
spécification
descriptioninstantanée comportement
inférence
directivesdirectives
stratégiestratégie
ordonnancementordonnancementenvironnementalenvironnemental
Z := X when X>0 default Y when Y>0 default X$1X ^= Y ^= ZX init 1
h1(when X>0)
X
Y
Z
h2(¬h1 when Y>0)
h3(¬h1 when ¬h2)
X
Y
Z
X$1 X
Y
Z
X$1 X
Y
Zh
¬h1
h3
Un exempleUn exempleobservation
spécification
descriptioninstantanée comportement
inférence
directivesdirectives
stratégiestratégie
ordonnancementordonnancementenvironnementalenvironnemental
Z := X when X>0 default Y when Y>0 default X$1X ^= Y ^= ZX init 1
( X, Y)
(-1, 2)( 3, 7)( 0,-1)( 2, 0) ...
entrées
X$1 X
Y
Zh
¬h1
h3
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
Un exempleUn exempleobservation
spécification
descriptioninstantanée
inférence
directivesdirectives
stratégiestratégie
ordonnancementordonnancementenvironnementalenvironnemental
Z := X when X>0 default Y when Y>0 default X$1X ^= Y ^= ZX init 1
entrées
X$1 X
Y
Zh
¬h1
h3
(-1, 2)( 3, 7)( 0,-1)( 2, 0) ...
-1
2
2
3
3
7
2
2
0
0
3
-1
1
Z
X
Y
État initial :
Instants : 1 2 3 4 ...
comportement
Un exempleUn exempleobservation
spécification
descriptioninstantanée
inférence
directivesdirectives
stratégiestratégie
ordonnancementordonnancementenvironnementalenvironnemental
Z := X when X>0 default Y when Y>0 default X$1X ^= Y ^= ZX init 1
entrées
X$1 X
Y
Zh
¬h1
h3
(-1, 2)( 3, 7)( 0,-1)( 2, 0) ...
comportement
Une mise en œuvreUne mise en œuvremono-processeurmono-processeur
séquentielleséquentielle
ordonnancementordonnancementstatique / dynamiquestatique / dynamique
ordonnancementordonnancementstatique statique Une mise en œuvreUne mise en œuvre
mono-processeurmono-processeurséquentielleséquentielle
Un exempleUn exempleobservation
spécification
descriptioninstantanée
inférence
Z := X when X>0 default Y when Y>0 default X$1X ^= Y ^= ZX init 1
entrées
X$1 X
Y
Zh
¬h1
h3
(-1, 2)( 3, 7)( 0,-1)( 2, 0) ...
comportement
(-1, 2)( 3, 7)( 0,-1)( 2, 0) ...
X$1 X
Y
Zh1
h2
h3
1
Z
X
Y
État initial :
3
3
7
2
2
0
0
3
-1
-1
2
2
Instants : 1 2 3 4 ...
Une mise en œuvreUne mise en œuvremono-processeurmono-processeur
séquentielleséquentielle
Un exempleUn exempleobservation
spécification
descriptioninstantanée
inférence
Z := X when X>0 default Y when Y>0 default X$1X ^= Y ^= ZX init 1
entrées
X$1 X
Y
Zh
¬h1
h3
(-1, 2)( 3, 7)( 0,-1)( 2, 0) ...
comportement
(-1, 2)( 3, 7)( 0,-1)( 2, 0) ...
X$1 X
Y
Zh1
h2
h3
1
Z
X
Y
État initial :
3
3
7
2
2
0
0
3
-1
-1
2
2
Instants : 1 2 3 4 ...
Résultats :Résultats :
correction fonctionnelle :correction fonctionnelle :correction spatiale :correction spatiale :correction temporelle :correction temporelle :équité :équité :correction synchrone :correction synchrone :correction flots-de-données :correction flots-de-données :correction compositionnelle :correction compositionnelle :
(-1, 2)( 3, 7)( 0,-1)( 2, 0) ...
X$1 X
Y
Zh1
h2
h3
1
Z
X
Y
État initial :
3
3
7
2
2
0
0
3
-1
-1
2
2
Instants : 1 2 3 4 ...
Résultats :Résultats :
X
Y
S
X$1
X
Y
Z
h3
¬h
hS
correction fonctionnelle :correction fonctionnelle :correction spatiale :correction spatiale :correction temporelle :correction temporelle :équité :équité :correction synchrone :correction synchrone :correction flots-de-données :correction flots-de-données :correction compositionnelle :correction compositionnelle : C’est dommage...C’est dommage...
• Préservation du formalisme Signal Préservation du formalisme Signal – intégration, récupérationintégration, récupération– validation (correction fonctionnelle)validation (correction fonctionnelle)
• modularitémodularité
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
• compilationcompilation
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)
contrôlecontrôle calculcalcul
[Besnard 92][Besnard 92]
calculs du calculs du processeur 1processeur 1
calculs du calculs du processeur nprocesseur n
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)
• répartition des donnéesrépartition des données
– au niveau du sourceau niveau du source• distribution qualitativedistribution qualitative• grâce aux pragmas de Signal V4grâce aux pragmas de Signal V4
– au niveau du grapheau niveau du graphe• distribution quantitativedistribution quantitative• nombreux algorithmes possiblesnombreux algorithmes possibles
process JEU =
topology "MASTER,cheyenne.irisa.fr"topology "PL_A, guernica.irisa.fr"topology "PL_B, megalo.irisa.fr"
run_on {a} "PL_A"run_on {b} "PL_B"
m:: (RES,SIG) := ARBITRE(SIG_A,SIG_B)a:: SIG_A := JOUEUR(SIG)b:: SIG_B := JOUEUR(SIG)
end
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
nœuds de nœuds de communicationcommunicationdu processeur ndu processeur n
nœuds denœuds decommunication communication du processeur 1du processeur 1
• communication des donnéescommunication des données
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |) | (| Qle| (| Qle11 | ... | Qle | ... | Qlenn |) |)
h1
hn
X
Y1
Yn
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
nœuds de nœuds de communicationcommunicationdu processeur ndu processeur n
nœuds denœuds decommunication communication du processeur 1du processeur 1
• communication des donnéescommunication des données
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |) | (| Qle| (| Qle11 | ... | Qle | ... | Qlenn |) |)
X
Y1
Yn
Xch1
hnhc
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
contrôle descontrôle descalcul ducalcul du
processeur nprocesseur n
contrôle descontrôle descalculs ducalculs du
processeur 1processeur 1
• répartition du contrôlerépartition du contrôle
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
CC (| C (| C11 | ... | C | ... | Cnn |) |)
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) | (| Qle |) | (| Qle11 | … | Qle | … | Qlenn |) |)communication des donnéescommunication des données
[Aubry, Machard 96][Aubry, Machard 96]
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
• communication du contrôlecommunication du contrôle
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
CC (| C (| C11 | ... | C | ... | Cnn |) |) | (| Cle | (| Cle11 | ... | Cle | ... | Clenn |) |)
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) | (| Qle |) | (| Qle11 | … | Qle | … | Qlenn |) |)communication des donnéescommunication des données
CC (| C (| C11 | ... | C | ... | Cnn |) |)répartition du contrôlerépartition du contrôle
communicationcommunicationdu contrôle dudu contrôle duprocesseur nprocesseur n
communicationcommunicationdu contrôle dudu contrôle duprocesseur 1processeur 1
h, horloge produite sur et utilisée sur ;
on communique b de vers .
une horloge ne peut être communiquée de manière asynchrone.
r, une horloge plus rapide ;b := h default not r
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
• extraction des programmesextraction des programmes distribués distribués
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) | (| Qle |) | (| Qle11 | … | Qle | … | Qlenn |) |)communication des donnéescommunication des données
CC (| C (| C11 | ... | C | ... | Cnn |) |)répartition du contrôlerépartition du contrôle
CC (| C (| C11 | ... | C | ... | Cnn |) | (| Cle |) | (| Cle11 | … | Cle | … | Clenn |) |)communication du contrôlecommunication du contrôle
PP (| P (| P11 | ... | P | ... | Pnn |) |)
PPii (| Q (| Qii | Qle | Qleii | C | Cii | Cle | Cleii | | AbsAbs( P ) |)( P ) |)
Un exemple :
A
B
X
Y
A
B
X
Y
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
• extraction des programmesextraction des programmes distribués distribués
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) | (| Qle |) | (| Qle11 | … | Qle | … | Qlenn |) |)communication des donnéescommunication des données
CC (| C (| C11 | ... | C | ... | Cnn |) |)répartition du contrôlerépartition du contrôle
CC (| C (| C11 | ... | C | ... | Cnn |) | (| Cle |) | (| Cle11 | … | Cle | … | Clenn |) |)communication du contrôlecommunication du contrôle
PP (| P (| P11 | ... | P | ... | Pnn |) |)
PPii (| Q (| Qii | Qle | Qleii | C | Cii | Cle | Cleii | | AbsAbs( P ) |)( P ) |)
Un exemple :
D EC
A
B
X
Y
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
• extraction des programmesextraction des programmes distribués distribués
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) | (| Qle |) | (| Qle11 | … | Qle | … | Qlenn |) |)communication des donnéescommunication des données
CC (| C (| C11 | ... | C | ... | Cnn |) |)répartition du contrôlerépartition du contrôle
CC (| C (| C11 | ... | C | ... | Cnn |) | (| Cle |) | (| Cle11 | … | Cle | … | Clenn |) |)communication du contrôlecommunication du contrôle
PP (| P (| P11 | ... | P | ... | Pnn |) |)
PPii (| Q (| Qii | Qle | Qleii | C | Cii | Cle | Cleii | | AbsAbs( P ) |)( P ) |)
Un exemple :
B
D EC
A X
YB
CE Y
D
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
• extraction des programmesextraction des programmes distribués distribués
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) | (| Qle |) | (| Qle11 | … | Qle | … | Qlenn |) |)communication des donnéescommunication des données
CC (| C (| C11 | ... | C | ... | Cnn |) |)répartition du contrôlerépartition du contrôle
CC (| C (| C11 | ... | C | ... | Cnn |) | (| Cle |) | (| Cle11 | … | Cle | … | Clenn |) |)communication du contrôlecommunication du contrôle
PP (| P (| P11 | ... | P | ... | Pnn |) |)
PPii (| Q (| Qii | Qle | Qleii | C | Cii | Cle | Cleii | | AbsAbs( P ) |)( P ) |)
Un exemple :
B
D EC
A X
YB
CE Y
D
A C
E
X
D
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
CC (| C (| C11 | ... | C | ... | Cnn |) |)répartition du contrôlerépartition du contrôle
CC (| C (| C11 | ... | C | ... | Cnn |) | (| Cle |) | (| Cle11 | … | Cle | … | Clenn |) |)communication du contrôlecommunication du contrôle
PPii (| Q (| Qii | Qle | Qleii | C | Cii | Cle | Cleii | | AbsAbs( P ) |)( P ) |)extraction des programmes distribuésextraction des programmes distribués
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) | (| Qle |) | (| Qle11 | … | Qle | … | Qlenn |) |)communication des donnéescommunication des données
• Schéma d’exécutionSchéma d’exécution– dans chaque instantdans chaque instant– entre les instantsentre les instants
P P
Schéma d’exécution dans Schéma d’exécution dans l’instantl’instant
PP22
PP11 PP33
La mise en œuvre mono-processeur séquentielleLa mise en œuvre mono-processeur séquentielle
est impossible car non compositionnelle.est impossible car non compositionnelle.
Il faut mettre en œuvre les processus Il faut mettre en œuvre les processus PPii
sans introduire de cyclesans introduire de cycle..
Problème 1 :Problème 1 :
Schéma d’exécution dans Schéma d’exécution dans l’instantl’instant
Théorème 1Théorème 1
la mise en œuvre sur chaque processeur doit être compositionnelle.
P2
PP11 P3
La mise en œuvre mono-processeur séquentielleLa mise en œuvre mono-processeur séquentielle
est impossible car non compositionnelle.est impossible car non compositionnelle.
Problème 1 :Problème 1 :
Il faut mettre en œuvre les processus Il faut mettre en œuvre les processus PPii
sans introduire de cyclesans introduire de cycle..
Schéma d’exécution dans Schéma d’exécution dans l’instantl’instant
PP22
PP11 PP33
La mise en œuvre mono-processeur séquentielleLa mise en œuvre mono-processeur séquentielle
est impossible car non compositionnelle.est impossible car non compositionnelle.
Problème 1 :Problème 1 :
Schéma d’exécution dans Schéma d’exécution dans l’instantl’instant
Il faut mettre en œuvre les processus Il faut mettre en œuvre les processus PPii
sans introduire de cyclesans introduire de cycle..
PP22
PP11 PP33
Les mises en œuvre compositionnelles sont très Les mises en œuvre compositionnelles sont très coûteuses (ordonnancement dynamique).coûteuses (ordonnancement dynamique).
Problème 2 :Problème 2 :
Schéma d’exécution dans Schéma d’exécution dans l’instantl’instant
Il faut mettre en œuvre les processus Il faut mettre en œuvre les processus PPii
sans introduire de cyclesans introduire de cycle..
Une solution : Une solution : les lignéesles lignées..
Schéma d’exécution dans Schéma d’exécution dans l’instantl’instant
AA
BB
CC
21 nœuds, 34 arcs : 7 lignées, 12 arcs21 nœuds, 34 arcs : 7 lignées, 12 arcs
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
séquentiel
Théorème 2Théorème 2
l’ordonnancement total des lignéesn’affecte pas la compositionnalité.
PP22
PP11 PPnn
non synchronisénon synchronisé
Sur chaque processeur :
Initialiserrépéter
exécuter l’instant courant
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
PP22
PP11 PPnn
t
non synchronisénon synchronisé
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
1
1
2
2
3
3
4
4
5
5 7 8 9 10 11 12 136
6POUBELLEPOUBELLE
PP22
PP11 PPnn
fortement synchroniséfortement synchronisé
Sur chaque processeur :
Initialiserrépéter
exécuter l’instant courantsignaler la fin de l’instant courantattendre la fin de l’instant courant ailleurs
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
PP22
PP11 PPnn
t
synchronisation
fortement synchroniséfortement synchronisé
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
1
1
2
2
3
3
4
4OKOK
PP22
PP11 PPnn
faiblement synchroniséfaiblement synchronisé
Sur chaque processeur :
Initialisern = 1répéter
exécuter l’instant nsignaler la fin de l’instant nattendre la fin de l’instant n-1 ailleursn = n+1
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
PP22
PPnn
t
faiblement synchroniséfaiblement synchroniséordre 1ordre 1
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
1
1 2
2
3
3
4
4
5
5
6
6
7
7
1OKOK
PP22
PPnn
t
faiblement synchroniséfaiblement synchroniséordre 2ordre 2
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
1
1 2
2
3
3
4
4 7
1
5
5
6
6 7 8OKOKMoniteurs d’interface plus complexesMoniteurs d’interface plus complexes
PP22
PP11 PPnn
t
problème :problème :la synchronisation faible n’est valable que pour une
petite classe de programmes.
pour les autres, il faut désynchroniser.
1 1
1
2
2
2 3
3
3
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
PP22
PP11 PPnn
t
1 1
1
2
2
2 3
3
3
1-désynchronisation1-désynchronisation
Sur chaque processeur, on autorise l’exécution simultanée de 2 instants logiques.
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
PP22
PP11 PPnn
t
1 1
1
2
2
2 3
3
3
1-désynchronisation1-désynchronisation
Sur chaque processeur, on autorise l’exécution simultanée de 2 instants logiques.
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
PP22
PP11 PPnn
t
1 1
1
2
2
2 3
3
3
1-désynchronisation1-désynchronisation
Sur chaque processeur, on autorise l’exécution simultanée de 2 instants logiques.
4 4
4
2
5
5
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
OKOK
PP22
PP11 PPnn
t
1 1
1
2
2
2 3
3
3
2-désynchronisation2-désynchronisation
Sur chaque processeur, on autorise l’exécution simultanée de 3 instants logiques.
4 4
4
2
5
5
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
PP22
PP11 PPnn
t
1 1
1
2
2
2 3
3
3
2-désynchronisation2-désynchronisation
Sur chaque processeur, on autorise l’exécution simultanée de 3 instants logiques.
4 4
4
5
5
5 6
6
67
Schéma d’exécution entre Schéma d’exécution entre instantsinstants
moniteurs d’interface plus complexesmoniteurs d’interface plus complexesordonnanceurs dynamiques plus complexesordonnanceurs dynamiques plus complexes
plus de mémoire nécessaireplus de mémoire nécessaire
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) |)répartition des donnéesrépartition des données
MéthodologieMéthodologied’implémentatiod’implémentatio
nnparallèleparallèle
PP (| C | Q |) (| C | Q |)compilationcompilation
CC (| C (| C11 | ... | C | ... | Cnn |) |)répartition du contrôlerépartition du contrôle
CC (| C (| C11 | ... | C | ... | Cnn |) | (| Cle |) | (| Cle11 | … | Cle | … | Clenn |) |)communication du contrôlecommunication du contrôle
PPii (| Q (| Qii | Qle | Qleii | C | Cii | Cle | Cleii | | AbsAbs( P ) |)( P ) |)extraction des programmes distribuésextraction des programmes distribués
synchronisation, désynchronisationsynchronisation, désynchronisation
application d’un schéma d’exécutionapplication d’un schéma d’exécution
répartition des données répartition des données
répartition du contrôlerépartition du contrôle
générique générique
génériquegénérique
synchronisation, désynchronisationsynchronisation, désynchronisation
application d’un schéma d’exécutionapplication d’un schéma d’exécution
QQ (| Q (| Q11 | ... | Q | ... | Qnn |) | (| Qle |) | (| Qle11 | … | Qle | … | Qlenn |) |)communication des donnéescommunication des données
BUILD_PROG
(compilation)
LOAD_PROG
(lancement)
pour chaque processeur pour chaque processeur : :
PROG_P_comm.c
communication
PROG_P_io.c
entréessorties
PROG_P_main.c
principal
PROG_P_body.c
itération
Signal
Mise en œuvre Mise en œuvre ::
prototypeprototype
PROG.SIG
source+
directives
MODULES
MODULES
GÉNÉRATEUR
GÉNÉRATEUR
LANCEUR
LANCEUR
Mise en œuvre Mise en œuvre ::
Extracteur
extracteurextracteur
P_STATE.SIG
état
P_DF.SIG
flots-de-données
P_BOOL.SIG
contrôle
P_NUM.SIG
calculs
P_CL_n .SIG
lignée n
P_CL_n-1.SIG
lignée n-1
P_CL_.SIG
lignée ...
P_CL_2 .SIG
lignée 2
P_CL_1 .SIG
lignée 1
PROG_n .SIG
programme n
PROG_n-1.SIG
programme n-1
PROG_.SIG
programme ...
PROG_2 .SIG
programme 2
PROC_1 .SIG
programme 1
PROG.SIG
quelconque
DISTRIB
UTION
DISTRIB
UTION
PARTITIO
NNEMENT
PARTITIO
NNEMENT
AUTOMATES
AUTOMATES
VÉRIFIC
ATION
VÉRIFIC
ATION
[Aubry, Machard 96][Aubry, Machard 96]
ConclusionConclusion
• Modèle mathématiqueModèle mathématique– dynamique (dynamique ( instantané) instantané)– corrélation avec l’existantcorrélation avec l’existant
ConclusionConclusion
• Modèle mathématiqueModèle mathématique
• MéthodologieMéthodologie– complète (du source au exécutifs)complète (du source au exécutifs)– modulairemodulaire
• Modèle mathématiqueModèle mathématique
ConclusionConclusion
• Modèle mathématiqueModèle mathématique
• MéthodologieMéthodologie
• Outils nouveauxOutils nouveaux– prototype de distributionprototype de distribution– extracteur de grapheextracteur de graphe– intégrés dans l’environnement Signalintégrés dans l’environnement Signal
• Modèle mathématiqueModèle mathématique
• MéthodologieMéthodologie
• Modèle mathématiqueModèle mathématique
• MéthodologieMéthodologie
• Outils nouveauxOutils nouveaux
http://perso.univ-rennes1.fr/pascal.aubryhttp://perso.univ-rennes1.fr/pascal.aubry