April 29, 2009

Réponses aux questions des exercices

Chapitre 1 Introduction

R1.1 Le modèle SPTR inclut du matériel distribué, un traitement concourant, des contraintes
temporelles et un fonctionnement en continu sur de longues périodes. On y différentie les
rétroactions interne et externe et les interfaces avec l’environnement sont explicites.
R1.2 Voir les notes de cours.
R1.3 besoins: agir (traitement et action) sur l’environnement d’une façon particulière (e.g. le
contrôler) en fonction de son état (données brutes de la perception et données transformées
suite au traitement).
contraintes: limites sur les mesures et actions imposées par l’environnement et objectifs ou
critères de performance (vitesse maximale, temps réel, fiabilité, ratio performance/coût,
flexibilité, etc.).
ressources: caractéristiques des interfaces avec l’environnement (capteurs et actuateurs) et des
architectures de traitement disponibles (matériel et logiciel système).
logiciel d’application: concerne principalement le traitement mais intervient aussi pour la
perception et l’action (incluant la rétroaction entre les deux).
R1.4 Pour ce système il y a 3 phases cycliques qui fonctionnent en continu. Les calculs intenses
pouvant être réalisés par des mécanismes matériels sont les traitements des images provenant
des caméras et les calculs de cinématique pour la robotique. Les événements principaux
auxquels doit réagir le système est l’arrivée d’un objet dans le champ de vision des caméras et
son déplacement selon une trajectoire inconnue. Des contraintes de temps doivent alors être
respectées. De plus, le système doit être tolérant aux fautes, en particulier si l’application est
critique, e.g. dans l’espace.
R1.5 A-d, B-c, C-g, D-a, E-h, F-e, G-f, H-b.
Lorsque plusieurs processus peuvent être actifs en même temps, on parle de traitement
concourant. Si ces processus s’exécutent sur différents processeurs, on parlera alors de
traitement parallèle. Le traitement concourant est un traitement potentiellement parallèle.
R1.6 a-D, b-A,G, c-B, d-A,B,G,H, e-A,(G), f-A,G, g-B, h-B, i-D, j-B,G, k-H, l-F, m-H, n-G, o-
C,D,E,F, p-A,G.
R1.7 Les navigateurs Internet ont des contraintes explicites (sévères) sur le temps de réponse, au
moins en ce qui concerne l’établissement d’une communication. De plus, ils ont plusieurs
contraintes implicites (indulgentes) fixées par l’utilisateur, en particulier pour les applications
multimédia véhiculant des signaux audio (voix, musique) ou vidéo, en direct ou en différé.

GIF-3003 Systèmes parallèles et temps réel 292

 Réponses aux questions des exercices Robert Bergevin (c)

Chapitre 2 Architectures et traitement parallèles

R2.1 Le couplage est serré lorsque les interactions sont nombreuses entre les processeurs. Il est
lâche lorsqu’elles sont rares.
R2.2 A: b,e,g,i,j.
B: c,d,f,j.
C: a,h.
R2.3 MIMD car temps de calcul = maximum des sommes vs. somme des maximums pour SIMD.
MIMD car les communications créent des délais de synchronisation entre les processus (ils
doivent s’attendre). Pour le SIMD, la synchronisation existe déjà pour toutes les instructions.
R2.4 SIMD: 1 programme, granularité fine, calcul à référence spatiale, processeurs moins puissants
et plus nombreux, processeurs en couplage serré, structures de données spéciales dans les
langages de programmation (e.g. plural), exécution synchrone.
MIMD: n programmes, granularité grossière, plus flexible, processeurs plus puissants,
processeurs autonomes, R/C élevé, primitives de communication dans le langage, exécution
asynchrone.

Capacité d’augmentation de performance proportionnelle à l’augmentation des ressources

(e.g. nombre de processeurs ou liens de communication) donc idéalement pas de perte
d’efficacité.
R2.5 Dans une architecture dite de Harvard, il y a 2 mémoires séparant les instructions et les
données.
R2.6 L’explication peut se faire facilement par un dessin:
N:N NxN

R2.7 MIMD avec mémoire distribuée:

NxN n:n

R2.8 Dans ce type de langage, l’ordre d’évaluation des instructions n’est pas décrit par le

GIF-3003 Systèmes parallèles et temps réel 293

 Réponses aux questions des exercices Robert Bergevin (c)

programmeur mais plutôt déterminée par les données et leurs interdépendances. L’ordre
d’évaluation est choisi par le compilateur ou l’environnement d’exécution. Ceci permet de
faciliter la programmation lorsque plusieurs threads de contrôle s’exécutent simultanément et
qu’ils sont en interaction. Ces machines sont particulières en ce qu’elles n’ont pas de IPs ni de
IMs. Les DPs doivent générer les étiquettes de leurs données eux-mêmes.
R2.9 IP: unité de contrôle, CU, CCU.
DP: unité arithmétique et logique, ALU.
R2.10 Pour IP/DP n:n.
Pour DP/DM nxn (aucun réseau DP/DP car mémoire partagée donc communiquent par la
mémoire).
R2.11 IP: processeur d’instruction. Il lit instructions en mémoire, les décode et transmet les
informations au DP (il exécute aussi les branchements e.g. jmp si nécessaire).
DP: processeur de données. Il va chercher les données en mémoire DM et exécute les
opérations arithmétiques et logiques puis transcrit les résultats en mémoire. Il comporte les
registres d’usage général.
IM: mémoire d’instruction. Elle contient le code à exécuter.
DM: mémoire de données. Elle contient les données.
commutateurs. Ils relient les unités entre elles.

Classification selon nombre d’unités de chaque type et types de commutateurs. Aussi, il y a un

diagramme d’état pour décrire le fonctionnement interne de l’architecture.

n IP; n IM; n-to-n IP-IM; n DP; n DM; n-to-n DP-DM; n-to-n IP-DP; nxn DP-DP.

IP et IM.
R2.12 C

A (ou B)

GIF-3003 Systèmes parallèles et temps réel 294

 Réponses aux questions des exercices Robert Bergevin (c)

B
R2.13 de gauche à droite: réseau nxn, DM, DP, réseau n:n, IP, réseau n:n, IM.
R2.14 boucle 5, 2, 3, 7, 1, 4, 6 avec communications 5 (IP), 2 (IP), 3 (DM), 7 (DM), 4 (IP), 6 (DM).
R2.15 niveau 1: un seul IP (une seule instruction décodée à la fois).
niveau 1: un seul DP (une seule instruction exécutée à la fois).
niveau 2: N états séquentiels et durée minimale de chaque état (e.g. vitesse d’exécution des
instructions).
niveau 2: limite sur vitesse de transfert entre les éléments aux points de synchronisation (IP/
DP, IP/IM, DP/DM).

non, car étant interne à un processeur il affecte également les ordinateurs séquentiel et
parallèle.

SIMD car synchronisation des processeurs au niveau des instructions (ou MIMD émulant le
SIMD!)

non, le temps sera le même pour les deux car structurée implique que le temps de calcul est
indépendant des données et l’application sera donc synchronisée au niveau des instructions
peu importe si elle est sur SIMD ou MIMD.
R2.16 Nombre N de données supérieur au nombre P de processeurs donc plus d’une donnée par
processeur. Il y a deux types: hiérarchique (données voisines sur un même processeur) et cut-
and-stack (données voisines distribuées sur les différents processeurs) Cette division des
données se retrouve au niveau du partitionnement dans lequel on peut aussi diviser les calculs
en plusieurs processus.

diamètre: étoile est mieux.

degré: anneau est mieux.
uniformité: anneau est mieux (maître n’importe où)
coût: identique n-1 liens.
extension: à peu près égal (mais anneau affecte deux noeuds existants)
connexité: anneau est mieux.
fiabilité: anneau mieux.
transformation vers hypercube: anneau est mieux (expansion et dilatation)
routage: étoile est mieux.

minimum de noeuds à ajouter sans changer la topologie.

nombre de noeuds existants affectés par cet ajout minimum.

extension: considère l’architecture matérielle seulement.

mise à l’échelle: la performance d’un algorithme s’exécutant sur cette architecture est
considérée.

GIF-3003 Systèmes parallèles et temps réel 295

 Réponses aux questions des exercices Robert Bergevin (c)

dilatation = n.

M: partitionnement car on décide de la décomposition du calcul en processus.

R/C et P: allocation (et mise à l’échelle pour P) car cette phase inclut le choix de
l’architecture.

La durée des calculs est celle du processeur ayant le plus de processus et elle dépend de ce
nombre et de la vitesse des processeurs R.
La durée des communications correspond à une communication de durée C pour chaque paire
de processus sur des processeurs différents. Chaque processeur a donc ki (M-ki)
communications mais il faut diviser par 2 la somme de tous les processeurs sinon on compte
deux fois la communication entre deux processeurs donnés.

TC= (M/P)R + (M*M)C/2 - (M*M)C/(2P) = RM donne R/C = M/2.

terme de droite devient M’(P’-1)C/2 où P’ est le nombre de processeurs utilisés dans

l’allocation.

(M/P)R + M(P-1)C/2 = RM donc R/C = P/2.

R2.17 Ratio du nombre de noeuds du réseau physique sur le nombre de noeuds du réseau logique.

dilatation = n.
R2.18 Un nombre plus élevé de processus qu’il y a de processeurs disponibles.
R2.19 Vrai.
R2.20 Vrai.
R2.21 hiérarchique: le nombre de blocs de données est égal au nombre de processeurs disponibles.
cut-and-stack: la dimension des blocs de données est égale au nombre de processeurs
disponibles.
R2.22 hiérarchique: 48 données doivent être divisées en un nombre entier P de blocs de même
dimension.
P = 48, 24, 16, 12, 8, 6, 4, 3, 2 ou 1.
cut-and-stack: 48 données doivent être divisées en un nombre entier de blocs de même
dimension P.
mêmes valeurs de P (inversées): P = 1, 2, 3, 4, 6, 8, 12, 16, 24 ou 48.

le nombre de rangées d’un bloc doit être le même que son nombre de colonnes. Ce nombre est
donc égal à 1 ou 2.
hiérarchique: P = 48 ou P = 12.
cut-and-stack: P = 1 ou P = 4.

GIF-3003 Systèmes parallèles et temps réel 296

 Réponses aux questions des exercices Robert Bergevin (c)

R2.23 maître-esclaves.
R2.24 Une topologie ouverte a des liens libres (ex. pipeline, maille). Elle peut utiliser ces liens pour
communiquer avec l’extérieur et ainsi améliorer l’efficacité.
R2.25 Elles dépendent de la dimension du problème, du nombre de processeurs et de l’architecture
de l’ordinateur parallèle sur lequel il sera implémenté.
R2.26 C’est la proportion intrinsèquement séquentielle d’un programme.
R2.27 Vrai.
R2.28 Si les processus sont de granularité grossière, le ratio R/C est élevé.
S’ils sont de granularité fine, le ratio R/C est faible.
R2.29 Vrai.
R2.30 R: courbe ascendante car le parallélisme diminue lorsque la granularité est plus grossière
(moins de processeurs en parallèle) et donc le temps de calcul augmente.
C: courbe descendante car le nombre de communications diminue lorsque le parallélisme
diminue et le temps de communication total diminue donc.

point de rencontre des deux courbes donne T = R+C minimum. À gauche et à droite, une
courbe augmente plus vite que l’autre diminue donc le total est plus grand qu’au point de
rencontre.
R2.31 non car l’accélération S est définie en comparant le temps de l’application (algo) parallèle à
celui de l’application (algo) séquentielle. Ici, E est défini en fonction de l’application parallèle
seulement.

E = (R/C) / (1 + (R/C)) donc E maximum si R/C >> 1 ce qui veut dire granularité grossière.
R2.32 Faux, c’est le minimum.
R2.33 Vrai.
R2.34 Rapport entre T(n,1) et T(n,P) où n est la dimension du problème et P le nombre de
processeurs.

Accélération par processeur.

Amdahl: 1/s = 1/0.1 = 10.

R2.35 L’accélération est le rapport entre le débit de l’ordinateur parallèle sur le débit de l’ordinateur
séquentiel.

L’efficacité est le débit par processeur de l’ordinateur parallèle.

L’efficacité est le rapport entre R/C et (1 + R/C).

GIF-3003 Systèmes parallèles et temps réel 297

 Réponses aux questions des exercices Robert Bergevin (c)

Si R/C << 1.

Généralement faible car R et C sont comparables (R/C est d’ordre de grandeur 1 et peut même
être assez petit si le nombre de communications dépasse le nombre de calculs).

Le débit peut être élevé même si l’efficacité est faible car il y a un grand nombre de
processeurs.
R2.36 ordonnancement: moins de perte de temps par changement de contexte si la granularité est
grossière.
interdépendances: moins de blocage si la granularité est grossière.
équilibrage: plus de temps morts si la granularité est grossière.
communications: moins de traitement utile (calcul) en proportion si la granularité est fine.
calculs: plus rapides si la granularité est fine (augmentation du parallélisme).
R2.37 1/s = 20.

Loi de Amdahl avec s+p = 1.

Loi de Amdahl avec S = 19 donne P = 361.

R2.38 V

F.
R2.39 Dans les deux cas on fait le rapport du temps séquentiel sur le temps parallèle.
Amdahl: p est la proportion parallélisable du calcul séquentiel. Elle prend un temps P fois plus
court. La proportion s prend un temps identique dans la version parallèle. S = (s+p)/ ((p/P)+s)
et s+p = 1.
Gustafson: s est la proportion non-parallélisée du calcul parallèle. Elle prend un temps
identique dans la version séquentielle: S = (s+pP)/(s+p) et s+p = 1.
R2.40 E = S/P vient de S qui est basée sur les proportions s et p. Ces proportions ne tiennent pas
compte du fait qu’il existe dans la version parallèle une surcharge due aux traitements qui
n’existent pas dans la version séquentielle (e.g. communications supplémentaires,
synchronisations, etc.).

Smax = 1/s = 20.

20 (0.95) = 1/((0.95/P) + 0.05) donc P >= (20)(0.95)(0.95) / (1 - (20)(0.95)(0.05)) = 361.

n est constant.
R2.41 S’ = (s+pP)/(s+p) = s + pP = s + (1-s) P = P - s(P-1).

GIF-3003 Systèmes parallèles et temps réel 298

 Réponses aux questions des exercices Robert Bergevin (c)

R2.42 S = T1/TP et T1 = s+p =1 où p est la partie parallélisable.

hypothèses: mêmes opérations et s (et p) constante.
p = influence et P = amélioration.

La durée parallèle est normalisée. La proportion parallélisée est plus longue en séquentiel par
un facteur P.

p = (1-c) pT et S’ = s+pP / (s + pT).

E=S/P.

On vise n = n(P) tel que E = constante (iso-efficacité).

R2.43 TC= (M/P)R + (M*M)C/2 - (M*M)C/(2P) = RM donne R/C = M/2.

S=1 (TC identiques).

R2.44 L’accélération est tracée pour une dimension n du problème qui est fixe. L’algorithme 1 est
complètement parallélisable. L’algorithme 2 a une proportion non-parallélisable. L’algorithme
3 a une proportion non parallélisable et doit aussi ajouter des opérations en surcharge lors de
la parallélisation.

S = T1/TP et T1 = s+p =1 où p est la partie parallélisable.

hypothèses: mêmes opérations et s (et p) constante.
p = influence et P = amélioration.

Smax = 1/s = 1/.20 = 5.

0.9 * 5 = 4.5 = 1/ (0.2 + 0.8/P) donc P = 36.
R2.45 n (P) = 8 P logP

oui (puisque E est constant)

non (s diminue sinon S ne serait pas proportionnelle à P et E ne serait donc pas constant)

oui (car n est supérieur à P)

Après addition des nombres sur chaque processeur aux feuilles de l’arbre (lorsque n est
supérieur à P i.e. lorsqu’il y a virtualisation), le calcul de la somme des m nombres résultants
(m=n si n=P) aux feuilles de l’arbre de log(m) niveaux (+ la racine) correspond au calcul de la
somme de m/2 nombres, obtenus par les sommes des paires de nombres consécutifs, sur un
arbre de log(m)-1 niveaux. Il s’agit donc d’une série de sommes imbriquées sur des arbres de
plus en plus petits (jusqu’à 1 niveau).
R2.46 m=n=P donc hypercube de dimension i.

GIF-3003 Systèmes parallèles et temps réel 299

 Réponses aux questions des exercices Robert Bergevin (c)

Ceci correspond aux P processeurs au dernier niveau (feuilles) de l’arbre binaire du

redoublement récursif. Dans cet algo, un seul niveau de l’arbre est utilisé à la fois donc il n’est
pas nécessaire d’avoir des processeurs différents sur les autres niveaux. De plus, seul le noeud
racine et son fils de droite doit communiquer avec tous les autres niveaux donc avec i
processeurs voisins si on veut garder des communications directes. Le réseau hypercube de
dimension i a aussi un degré i i.e. suffisamment de voisins pour le noeud racine (celui qui
calcule la somme totale).

oui. Si les niveaux de l’arbre sont actifs simultanément, il y aura plusieurs processus (noeuds
de l’arbre) placés sur un même processeur de l’hypercube. L’expansion sera inférieure à 1
avec une perte de parallélisme potentiel (la performance des calculs sera réduite, celle des
communications augmentée). Certains noeuds voisins de l’arbre seront voisins sur
l’hypercube et d’autres seront sur le même processeur.

non. Si tous les noeuds de l’arbre sont placés sur un hypercube ayant un noeud de plus, dès
que la dimension i est supérieure ou égale à 3, il y a une dilatation supérieure à 1.

oui, les calculs et les communications sont très structurés. Un même algorithme est exécuté
par chaque processeur.
R2.47 Amélioration de l’accélération S entre P=8 et P=16. Tableau donne E=S/P donc S=EP

Avec N=64: P=8 donne S=0.57*8=4,6 et P=16 donne S=0.33*16=5,3.

Donc amélioration de l’accélération de 5,3-4,6 = 0,7.

Avec N=512: P=8 donne S=0.91*8=7,3 et P=16 donne S=0.80*16=12,8.

Donc amélioration de l’accélération de 12,8-7,3 = 5,5.

R2.48 T (n,p): (n/p)-1 = (10000/128)-1 = 77,125 et 2*log p = 2*log128 = 14.
Donc T(n,p) = 77,125 + 14 = 91,125.

L’accélération est S = T(n,1) / T(n,p) = (10 000 -1) / 81,34 = 123.

Infinie.

Oui, selon la loi de Amdahl, la limite de l’accélération donne l’avantage maximal obtenu en
augmentant le nombre de processeurs même jusqu’à l’infini. En théorie, cette limite augmente
toujours avec P même si cette augmentation se fait de plus en plus lentement.
R2.49 Par redoublement récursif, i.e. que l’on fait des sommes de paires en parallèle et de façon
hiérarchique.

GIF-3003 Systèmes parallèles et temps réel 300

 Réponses aux questions des exercices Robert Bergevin (c)

L’efficacité tend vers 0.

Parce que la proportion parallèle du traitement n’est plus limitée et qu’elle devient
prépondérante dans le calcul.
R2.50 Rapport entre la complexité temporelle du meilleur algorithme séquentiel connu pour ce
problème et la complexité temporelle de l’algorithme parallèle correspondant.

SIMD ou granularité fine car R/C << 1 et efficacité << 1.

s = 0.01; p=0.99; Amdahl donne Smax = 100 donc ici S=95. Amdahl et isole P donne P =
1881.

Parce que la proportion parallèle ou locale du traitement n’est plus fixe si le nombre de
données assignées à chaque processeur augmente. Elle peut devenir prépondérante dans le
calcul, ce qui augmentera l’efficacité des processeurs. Autrement dit, la partie globale (somme
récursive) devient négligeable si le nombre de données assignées à chaque processeur
augmente beaucoup.
R2.51 Log2(N).

1/log2(N).

Elle n’est pas parfaite car E diminue avec N (et P).

R2.52 Elle est égale à: (n/P - 1) + 11 logP.

T(n,1) = 255, S=255/((255/P - 1) + 11logP);

1:1.0, 4:3.0, 16:4.32, 64:3.7, 256:2.9

S’(n,P)= (nP-1)/((nP/P-1)+11logP)=nP-1/((n-1)+11logP)=(256P-1)/255+11logP.
1:1.0, 4:3.69, 16:13.7, 64:51.04, 256:191.06
Loi de Amdahl: n fixe et P augmente donc s, la proportion séquentielle, augmente et
l’efficacité diminue, tendant rapidement vers zero. (E= 1.0, 0.75, 0.27, 0.058, 0.011)
Loi de Gustafson: n augmente avec P donc l’accélération augmente toujours. Par contre, si
l’augmentation de n n’est pas suffisante (ici n = 256P), on est en-dessous de la fonction d’iso-
efficacité et donc l’efficacité diminue graduellement (quoique beaucoup plus lentement que
pour n fixe).
(E= 1.0, 0.92, 0.86, 0.80, 0.75))

n=n(P)=PlogP pour E constant.

R2.53 sum = 0
for i = 0 to log2(N-1)
for j = 0 to (N/(2^^(i+1)))-1)

GIF-3003 Systèmes parallèles et temps réel 301

 Réponses aux questions des exercices Robert Bergevin (c)

index = 2^^(i+1);
index2 = index + 2^^i;
A(index) = A(index) + A(index2);
endfor
endfor
(...(((A0+A1) + (A2+A3)) + ((A4 +A5) + (A6+A7))) +... + (...+ (A(N-2) + A(N-1)))...)

Sommation{i =0 to (log_2 N) -1} N / 2^^(i+1) = N/2 + N/4 + N/8 +... + 1 = 1 + 2 + 4 + 8 +...

+ N/2 = N-1 additions.

N-1 additions sont faites en partie en parallèle (à chaque “niveau” i.e. pour i constant donc
additions dans la boucle j se font en parallèle). Il faut ajouter les temps de transfert
(communication) des résultats partiels mais ils peuvent être compensés par les additions en
parallèle.
R2.54 E = R / (R + C) = Rmat (n/P - 1) / (Rmat (n/P - 1) + 1.25 Rmat logP) = 0.8
donc (n/P - 1) = 5logP et n = (5logP +1) P.

Tp = R + C et T1 = Rmat (n-1).
E = S/P = Rmat (n-1) / (Rmat (n/P - 1) + 1.25 Rmat logP) P.
Si n/P >> 1 et n >> 1, on obtient E = Rmat (n) / (Rmat (n/P) + 1.25 Rmat logP) P = 0.8
donc n = 5 P logP.
R2.55 n-1 dans les deux cas.

niveau 1 (racine): 1 addition S=1.

niveau 2: 2 additions en parallèle: S=2.
niveau 3: 4 additions en parallèle: S=4.
moyenne = (4+2+1)/3 = 7/3 = (n-1)/log n pour n = P = 8 processeurs. Même formule si n plus
élevé mais toujours une puissance de 2.

S=1/((1-p) + p/P) = (n-1)/log n.

en développant on obtient p = (1 - log n/(n-1)) (n / (n-1)).

S non changée si communications négligées.

E 2 fois meilleure.

cut-and-stack: max de L = n/P répétitions de chaque étape (niveau de l’arbre) de l’algo sans
virtualisation avec n processeurs.
S = O (n)/(n/P) log P = O (P)/ (log P)
E = O (1/logP)
hiérarchique: L = n/P additions séquentielles sur chaque processeur au début, suivi de l’algo
sans virtualisation avec P processeurs.
S = O (n / (L + logP))

GIF-3003 Systèmes parallèles et temps réel 302

 Réponses aux questions des exercices Robert Bergevin (c)

E = O (L / L + logP).

E = O (1).

L’hypothèse que l’on doit faire les mêmes additions que pour l’algorithme sans virtualisation
n’est pas nécessaire car l’ordre des additions ne change pas le résultat. Autrement dit, on
pourrait exécuter l’algorithme sur un vecteur de nombres permuté et le résultat serait le même.
Donc, dans le cas de l’addition des nombres on peut prendre l’algorithme hiérarchique même
avec la virtualisation cut-and-stack.
R2.56 8 noeuds, 16 liens, diamètre 2, degré 4.

Oui, même degré pour tous les noeuds.

4 = degré.

4 = valeur maximale. C’est un réseau régulier donc = au degré.

Non.
R2.57 Capacité d’extension: facilité d’obtenir un réseau avec plus de processeurs mais de même
topologie.
Capacité de mise à l’échelle: facilité d’obtenir une performance proportionnelle au nombre de
processeurs.
R2.58 Améliorer la robustesse et l’efficacité du réseau en anneau.
R2.59 dimension i implique degré i. Donc chaque noeud a i liens. Dans l’anneau, chaque noeud a 2
liens. Il faut ajouter i-2 liens par noeud. Le nombre total de cordes ajoutées est obtenu en
multipliant le nombre de noeuds par le nombre de liens ajoutés par noeud et en divisant par 2
(liens bidirectionnels!).
Noeuds (anneau): 2i
Cordes ajoutées: 2i*(i-2)/2 = (i-2)2(i-1). Exemple: i = 3 donne N=8 et C=4; i=2, 3,...
R2.60 Étape 1: On étiquette les noeuds de l’anneau de 0 à 7 en binaire.

Étape 2: On étiquette les noeuds de l’hypercube selon le code de Gray binaire réfléchi.

Étape 3: On fait la transposition directement.

R2.61 On a r=1, s=2, i = {0,1} et j={0,1,2,3}.

Codes obtenus par concaténation d’un élément du premier groupe G(i,r) avec un élément du
second groupe G(j,s) ci-dessous (2x4 = 8 codes pour 8 noeuds).
G(0,1) = 00
G(1,1) = 01

GIF-3003 Systèmes parallèles et temps réel 303

 Réponses aux questions des exercices Robert Bergevin (c)

G(0,2) = 00
G(1,2) = 01
G(2,2) = 11
G(3,2) = 10
R2.62 Maximum, pour toute paire de noeuds, du nombre minimum de noeuds intermédiaires, pour
tout chemin, entre les deux noeuds.

8.

Nombre de liens vers tous les autres noeuds.

Noeud central: 7; autres noeuds en périphérie: 1.

Hypercube.
R2.63 Vrai: anneau peut être transpose sur hypercube; liens supplémentaires de l’hypercube (en plus
des deux présents sur l’anneau avec les voisins de chaque côté) sont ajoutés comme cordes de
l’anneau.
R2.64 3 (4x4), 1 (6x3), 2 (8x4).
R2.65 H(A,B).

123 (010 011 001 101) 231 (010 000 100 101) 312 (010 110 111 101) ou
132 (010 011 111 101) 213 (010 000 001 101) 321 (010 110 100 101).

Oui, 2.
R2.66 8.

48.

n! 2n (choix du noeud 0 * choix de l’ordre des dimensions i.e. voisins du noeud 0)

R2.67 On a 3 pour H(A,B)=3.

d.
R2.68 H(A,B) + 2

H(A,B) + 2
R2.69 1/0.1=10

Amdahl: P = Sp/(1-sS) = 8(0.9)/(1-0.8)=7.2/0.2=36-> P = 64 (S>=8) et dimension = 6.

R2.70 16 noeuds: 2 cubes reliés noeud à noeud. Adresses selon construction hiérarchique.

GIF-3003 Systèmes parallèles et temps réel 304

 Réponses aux questions des exercices Robert Bergevin (c)

LSB -> MSB: 1011, 1001, 1101, 0101

(ou MSB -> LSB: 1011, 0011, 0111, 0101)
R2.71 4, 2, 2
Ajouter liens 1:4, 2:4, 3:6, 3:5
3, 2, (2, 3, 3, 4, 4, 3, 3, 2)

Tolérance aux fautes (plus de liens et chemins).

Moins de conflits ou contentions (plus de liens et chemins)
Plus rapide (diamètre réduit)
R2.72 Chemin possible: 00100 -> 00110 -> 01110 -> 11110.

Pour obtenir la distance, on fait un ou-exclusif entre la source et la destination, soit:

00100 XOR 11110 = 11010 et on compte le nombre de 1. Ici, la distance est donc égale à 3.
R2.73 V

F (identiques car tous les chemins sont directs).

V (pas de cycle car on change de dimension séquentiellement sans revenir à la première).

F
R2.74 réseau dynamique car il est configuré selon les chemins pris dans le réseau par chaque paquet.
Si c’était un réseau statique, on aurait une structure récursive à l’infini...

log2(64) = 6

nombre de 1 dans XOR(source, destination) = 3.

on aura le nombre maximum de chemins possibles si la longueur minimale est égale au

diamètre i.e. 6. Dans ce cas, il faut se déplacer dans chaque dimension du réseau. L’ordre
choisi pour ces déplacements correspond à un chemin possible. Pour le premier déplacement,
il y a 6 choix, pour le deuxième il en reste 5, etc. donc le nombre maximum est 6! = 720.

GIF-3003 Systèmes parallèles et temps réel 305

 Réponses aux questions des exercices Robert Bergevin (c)

SAF: chaque paquet est emmagasiné à chaque noeud au complet avant de poursuivre.
VCT: un paquet est emmagasiné ssi le noeud suivi n’est pas libre (n’a pas d’espace pour ce
paquet).
WR: le paquet n’est pas emmagasiné mais plutôt décomposé en flits et distribué le long du
chemin.
R2.75 P-1 étapes.

étoile car le diamètre est le plus petit dès que P > 4.

hypercube: k étapes
anneau: [P/2] étapes
étoile: P-1 étapes

1. nombre d’étapes minimum (à toute étape, tous les processeurs ayant les données vont les
transmettre à un processeur ne les ayant pas).
2. performance maximale de chaque étape (toute communication 1:1 est directe).
R2.76 logP étapes de durée D donc T = DlogP
R2.77 sans virtualisation, l’expansion minimum ne peut être inférieure à 1.
hypercube k-D donne 2^^k processeurs qui sont placés sur arbre binaire de 2^^(k+1) - 1
processeurs i.e. k+1 niveaux, en incluant la racine de l’arbre. Ex: hypercube 3-D a 8
processeurs qui sont placés sur arbre binaire de 4 niveaux ou 15 processeurs (8 feuilles).
L’expansion est donc (2^^(k+1) - 1) / 2^^k. Ex: 7/4, 15/8, 31/16, etc.
Pour minimiser la dilatation, on place les processeurs sur les feuilles de l’arbre et le parent est
toujours le même processeur que l’enfant de gauche. La dilatation est égale à 2k - 3 ce qui
correspond à un chemin du noeud d’extrême droite en bas de la 1ère branche de gauche vers le
noeud d’extrême droite en bas de la branche de droite..

F: hypercube: k(2^^(k-1)) liens et arbre binaire: (2^^k)-2 liens.

R2.78 minimale:
phase 1: negative hops i.e. s=1 d=0
phase 2: positive hops i.e. s=0 d=1
ordre des hops à chaque phase: arbitraire
non-minimale: ajoute “neutral-1” hops à la phase 1 i.e. s=1 et d=1 (va vers 0)

Hops MSB à LSB: negative, positive, negative, neutral-1.

2 chemins de longueur 3: (2! choix de l’ordre à la phase 1)
1011, 1001, 0001, 0101 ou 1011, 0011, 0001, 0101.

GIF-3003 Systèmes parallèles et temps réel 306

 Réponses aux questions des exercices Robert Bergevin (c)

12 chemins de plus de longueur 5 (en plus des 2 minimaux de longueur 3).

3! = 6 choix de l’ordre à la phase 1 et 2! = 2 choix de l’ordre à la phase 2 (neutral-1 a créé un
hop +)
1011, ((1010, (0010 ou 1000)) ou (1001, (1000 ou 0001)) ou (0011, (0010 ou 0001))), 0000,
(0100 ou 0001), 0101.
R2.79 exclusion mutuelle: un seul paquet occupe une partie donnée du tampon à la fois.
hold-and-wait: un paquet occupera une partie du tampon tant qu’il est bloqué sur son chemin.
aucune préemption: les tampons ne sont pas vidés automatiquement par le réseau.

cycle horaire et cycle anti-horaire sont formés chacun de 4 changements de direction

géographique.

élimine deux changements de direction par cycle.

parce qu’un changement dans le cycle horaire donne un chemin équivalent à un changement
dans le cycle anti-horaire (et vice-versa). Si on enlève le changement équivalent dans l’autre
cycle, on obtient un cycle avec croisement (un “huit”).

NW et ES.
R2.80 De l’extérieur vers l’intérieur: banyan, banyan régulier, delta, oméga.
R2.81 Permutation de type mélange parfait.
R2.82 Méthode de routage: le i ème bit le plus significatif de l’adresse de destination détermine
l’activation du i ème commutateur. Ainsi, si ce bit est à 0 le chemin passe par la sortie du haut
sur le commutateur du i ème étage, tandis que si le bit est à 1, la sortie du bas est utilisée.
R2.83 Vrai.
R2.84 On a 2 exp 7 =128 donc 7 étages (log2128).
R2.85 Plutôt que de transiter seulement à travers les commutateurs, le message peut passer par des
processeurs (noeuds) intermédiaires et ainsi passer plusieurs fois par les commutateurs afin
d’arriver à destination.
R2.86 Direct (STR: “straight”).
R2.87 2 étages de 2 commutateurs reliés shuffle-exchange.
Adresse binaire de départ = 01; adresse binaire de destination = 11.
Donc sort par le bas sur les 2 commutateurs du chemin.
1er étage: XCH ou UB; 2ième étage: STR ou LB.

Non car il y a une faute dans l’étage d’entrée (certaines sources sont inaccessibles).
R2.88 N! = 4! = 24; 2^^4 = 16 non bloquantes (2 états possibles pour 4 commutateurs) donc PC =
16/24 = 66.7%.

GIF-3003 Systèmes parallèles et temps réel 307

 Réponses aux questions des exercices Robert Bergevin (c)

R2.89 Adresse binaire de M5: 100; départ de P2; étage 1/rangée 2: sort par le bas (MSB=1); étage 2/
rangée 4: sort par le haut (2ième bit=0); étage 3/rangée 3: sort par le haut (LSB = 0).

Étage 1: XCH ou UB; étage 2: STR ou UB; étage 3: XCH ou LB.

P1: M5
P3, P5, P7: M5
P4, P8: M5 et M6
P6: M5 à M8.
R2.90

l=0 l=1 l=2 l=3

P0 M0

P1 M1

P7 M7

3 étages de 4 commutateurs. 2 processeurs consécutifs par commutateur à l’entrée du 1er

étage; 2 mémoires consécutives par commutateur à la sortie du dernier étage.
liens entre étages 1/2 et 2/3 pour permettre connexité du réseau butterfly.
donc, entre 1er et 2ième étages: liens directs et croisements haut/bas et bas/haut; entre 2ième
et 3ième étages: liens directs et croisements haut/haut et bas/bas (haut: 2 premières rangées;
bas: 2 dernières rangées).

Oui, même algorithme que pour réseau oméga avec le réseau produit en b.
R2.91 On a 2 étages de 2 commutateurs reliés shuffle-exchange.

Adresse binaire de départ = 01; adresse binaire de destination = 11.

Donc sort par le bas sur les 2 commutateurs du chemin.
1er étage: XCH ou UB; 2ième étage: STR ou LB.

3 étages de 2 commutateurs.
Même algorithme pour les 2 derniers étages. évitement du commutateur brisé au 1er
commutateur.
1er étage: UB ou STR; 2ième étage: LB ou STR; 3ième étage: XCH ou UB.
R2.92 A XOR B et si ième MSB bit = 0 alors état = DIRECT sinon (bit = 1) état = ÉCHANGE pour

GIF-3003 Systèmes parallèles et temps réel 308

 Réponses aux questions des exercices Robert Bergevin (c)

étage i.

1,2,4.

UB / LB,LB / UB,XCH,UB,UB

8! = 40320.

Non-bloquante si configurations non-conflictuelles des commutateurs i.e. chaque

commutateur est dans un état ÉCHANGE (XCH) ou DIRECT (STR); donc le nombre total est
2^^12 = 4096.

4096/40320 = 10.16%
R2.93 16

Format (sorties entrée high - sorties entrée low): h-h, h-hl, hl-h, l-l, hl-l, l-hl, hl-hl
R2.94 Commutateur matriciel, multi-étages, pipeline (maille 1-D), anneau, étoile, hypercube, arbre
élargi, etc.
R2.95
000 000
001 001

010
011
010
011
100 100
101 101

110
110
111 111

Un commutateur en faute dans l’étage d’entrée ou de sortie (ou tous les commutateurs d’une
colonne en faute, ou tous les commutateurs du réseau en faute, etc.).
entrée: 2 sources sont inutilisables; sortie: 2 destinations sont inutilisables.

Chapitre 3 Systèmes temps réel et fiabilité

R3.1 Places: donne les éléments qui définissent l’état du réseau.

GIF-3003 Systèmes parallèles et temps réel 309

 Réponses aux questions des exercices Robert Bergevin (c)

Transitions: donne les endroits où l’état du réseau peut changer.

Arcs (entrée et sortie): donne les conditions d’activation des transitions et l’effet de cette
activation sur les places avant et après.

Marquage: donne l’état du réseau par le nombre de jetons dans chaque place.
R3.2

TAMPON
génération
b lecture
a c
A
écriture utilisation

PRODUCTEUR CONSOMMATEUR

vrai. le producteur peut écrire indéfiniment même si le consommateur ne lit pas.

pour le consommateur: aucune donnée en trop, aucune donnée manquante, ordre préservé.

aucune donnée en trop: place A et transition b. ne peut lire de donnée non écrite.
aucune donnée manquante: transitions a et c. toute donnée générée pourra être utilisée.
ordre préservé: non modélisé par le réseau.
R3.3 Nombre max de mots supplémentaires = nombre de mots de 20 (prochain) à N=1 (dernier
possible) + nombre de mots de 0 (début) à 9 (dernier libre i.e. queue - 1).
Max = ((N-1) - 20 + 1) + 10 = N - 10
R3.4 Celle du centre en haut car elle indique le nombre de valeurs dans le tampon ou celle du centre
en bas car elle indique l’espace libre qui reste dans le tampon.

Impossible en tout temps car le total des deux places du centre est toujours N (une écriture
ajoute 1 au tampon et retire 1 de la place au-dessous; une lecture retire 1 au tampon et ajoute 1
à la place au-dessous) et le nombre initial de valeurs dans le tampon est 0.

1. remplace N par 1 (R/W sans accès simultané à un tampon)

2. remplace l’arc de gauche du producteur par un arc d’entrée allant de la sortie de transition
Lecture vers la place du haut du producteur (communication bloquante en R et W). (transition
Écriture devient: “demande” d’écriture).
R3.5 M/D/1 considère le temps de service déterministe (e.g. durée fixe) plutôt qu’aléatoire.

seule la variable N est aléatoire car elle dépend de la fonction aléatoire régissant l’arrivée des
clients.

GIF-3003 Systèmes parallèles et temps réel 310

 Réponses aux questions des exercices Robert Bergevin (c)

on veut que la probabilité que la file contienne 2 clients ou plus soit égale à 5%.
TSM = sqrt(0.05/1^2) = 0.22 minutes = 13.4 secondes.
R3.6 n = ρ ⁄ ( 1 – ρ ) et ρ = λ ⁄ µ on a: 1 ⁄ µ = 10 msec. 1 ⁄ λ = 13 msec.
Donc: λ ⁄ µ = 0, 77 et n = 4 clients
R3.7 Temps d’attente=T= ( 1 ⁄ µ ) ⁄ ( 1 – ρ ) = 44 msec. donc si on soustrait 1 ⁄ µ = 10 msec, on
obtient un temps moyen d’attente de 34 msec.

La borne sur le temps moyen entre deux interruptions pour 1 ⁄ µ = 10 msec:

6
( λ ⁄ µ ) ≤ 0, 05 donc:

1 ⁄ λ ≥ 1 ⁄ ( µ 6 0, 05 ) et 1 ⁄ λ = 17 msec.
27
R3.8 1 ⁄ µ = 10 msec. 1 ⁄ λ = 11 msec. donc ρ = 10 ⁄ 11 = 0, 909 . Ainsi, 0, 909 ≤ x
donne x=0,076 soit 7,6%.

Le temps de réponse moyen est T= 10 / (1-0,909) = 110 msec.

R3.9 Débordement si N >= 4. P(N>=4) = (lambda/mu)4 <= 0,05.
Donc 1/lambda >= (1/mu)/(0,05)1/4 = 42,29msec.

Débordement si N>=x. P(N>= x) = (lambda/mu)x <= 0,02.

Donc x >= (ln 0,02)/(ln (20/30)) = 9,65 et donc débordement si N=10 interruptions dans la
file. Le tampon sera donc de dimension 8 (8 en attente et 1 en traitement sans débordement).
R3.10 Wait: prendre une baguette; signal: déposer une baguette.
Chaque p(i) commence par vouloir manger; il prend la baguette de gauche (droite) dès qu’elle
est libre et ensuite il prend la baguette de droite (gauche) dès qu’elle est libre. Il mange ensuite
pour un temps fini puis redépose i.e. libère les baguettes dans le même ordre. Il pense pendant
un temps fini puis recommence le cycle.

Impasse: tous les philosophes saisissent une baguette puis sont bloqués.
Famine: tout p(i) détiendra une baguette éventuellement; si un p(i) est bloqué indéfiniment, il
finira par bloquer son voisin du côté de la baguette qu’il détient et ainsi de suite jusqu’au
dernier; donc, une famine se transformera nécessairement en impasse à plus ou moins long
terme.

Le cinquième philosophe p(4) saisit ses baguettes dans l’ordre inverse des autres i.e. wait(0)
puis wait(4); ainsi il aura éventuellement 2 baguettes et il y aura toujours quelqu’un qui
mange et tous finiront toujours par manger.
R3.11 S1=1, S2=0, R=N
MV(R)
P(S1) ;bloque l’accès au compteur

GIF-3003 Systèmes parallèles et temps réel 311

 Réponses aux questions des exercices Robert Bergevin (c)

R=R+1 ;libère une ressource

si (R <= 0) alors { ;un processus en attente d’une ressource?
;i.e. toutes les ressources étaient occupées et
V(S2)} ;on permet à un processus en attente d’utiliser
;la nouvelle ressource libre
sinon {
V(S1)} ;relâche le compteur
Il sera mis dans une file d’attente de la ressource
R3.12 Un jeton dans les deux places du haut et un autre dans la place du centre.
(aussi, un dans une place du haut et l’autre dans la place du bas opposée)

Place du centre: 3 jetons et 3 branches de sortie et 3 branches d’entrée vers la droite.

Place du haut à gauche: 3 jetons (ou répéter 3 branches de lecteurs à gauche avec un jeton en
haut chacune et 3 branches d’entrée et de sortie vers la gauche à partir de la place du centre).
R3.13 2: deux MP(S) suivis de deux MV(S)

S=nombre de ressources disponibles au total.

Oui: 2 peuvent faire un premier MP(S) avant qu’un des 2 ait fait un deuxième MP(S); ils
bloqueraient alors au 2ieme MP(S) tandis que le 3ieme bloquerait au 1er MP(S). Les 4
conditions sont respectées par les 2 premiers processus. Le troisième est simplement bloqué
par eux car l’impasse se produit avec un sous-ensemble des processus. On a: exclusion
mutuelle (ressources utilisées par 1 à la fois), hold-and-wait (2 ont fait 1 MP(S) et attendent),
attente circulaire (1->2->1), aucune préemption forcée (aucune limite dans le temps
d’attente).

Non: 2 peuvent faire les deux MP(S) à tour de rôle mais dès que le troisième atteindra son
premier MP(S) il entrera dans la file d’attente et finira par saisir une première ressource puis
une deuxième à moins qu’il y ait eu impasse.

Presque aucun changement: impasse toujours possible mais cette fois-ci les 3 processus
respectent les 4 conditions ensemble.

4: car si il y a un cycle avec les 2 premiers Pi, le troisième finira toujours par saisir une 1ère
ressource (comme dans le cas de 2 ressources) puis une deuxième car les impasses ne sont pas
possibles, le nombre de ressources étant plus grand que le nombre de processus.
prévention: aucune attente circulaire (ou hold and wait) car 1 ressource en plus.

1: réalisation matérielle du sémaphore serait différente: variable partagée accédée par bus
système donc verrouillage du bus, etc.
2: pas de changement p/r aux impasses et famines.

GIF-3003 Systèmes parallèles et temps réel 312

 Réponses aux questions des exercices Robert Bergevin (c)

R3.14 Si à un moment donné 3 processus utilisent chacun une ressource et que trois autres processus
ont effectué un MP(s) et attendent qu’une ressource se libère (ils sont suspendus), il pourra y
avoir une impasse si un autre processus effectue MP(s) avant qu’une ressource se libère. En
effet, s prendra alors la valeur -4 et ne pourra plus redevenir >=0, même si les trois ressources
se libèrent. Lorsque tous les processus actifs auront demandé l’accès à une ressource, ils
seront tous bloqués, donc impasse.

Parce que les ressources occupées sont utilisées et qu’elles seront toutes libérées à un moment
ou un autre et pourront alors être utilisées par un autre ou par le même processus (pas d’attente
circulaire ni de hold and wait).

MP(s): while (s < 1) {;}; s=s-1; MV(s): s=s+1; init(s): s=N

Lorsqu’un processus est suspendu, il sera placé dans une file d’attente et chaque fois qu’une
ressource se libérera, le premier processus de la file pourra s’exécuter à nouveau. Il faut donc
interpréter le test while comme un test vérifiant s’il y a une ressource libre ou non.
R3.15 2 processus utilisent une ressource commune. La partie de programme incluant l’accès à la
ressource est en exclusion mutuelle entre ces deux processus.

un processus qui est dans une section critique ne pourra être remplacé par un processus plus
prioritaire voulant utiliser la même ressource. Il n’y a donc pas de préemption de la ressource.

faux: l’absence de préemption est une des 4 conditions nécessaires aux impasses.
R3.16 La ressource processeur est la seule qui permet la préemption. Toutes les autres ressources ne
peuvent pas être libérées en cours d’utilisation par un processus.
R3.17 Faux. Ça dépend des critères utilisés pour définir le meilleur.

Faux. Ça concerne seulement la réalisabilité i.e. le respect des contraintes temporelles des
processus.

Faux. Les processus peuvent apparaître et disparaître dynamiquement dans la file d’attente.

Vrai. Les calculs sont identiques et simples.

Vrai. Les processus ne sont plus indépendants et il y a des blocages en plus des suspensions,
donc les temps de réponse sont plus grands et les échéances plus difficiles à respecter.
R3.18 Faux: famine plutôt. Impasse entre P2 et P4 mais P1, P3 et P5 ne sont pas bloqués.
R3.19 En se basant sur les différentes techniques d’optimisation exposées dans les notes, on devrait:
i) inclure les deux fonctions, taxe et imprime, à l’intérieur de la fonction “main” pour éviter le
passage de paramètres, la gestion de la pile et des variables locales,

GIF-3003 Systèmes parallèles et temps réel 313

 Réponses aux questions des exercices Robert Bergevin (c)

ii) éliminer la variable “temp” qui est intermédiaire et inutile,

iii) éliminer la variable morte (non-utilisée) “numéro” et
iv) effectuer le calcul 0,075+0,015 et mettre “taux” comme une constante en dehors de la
fonction “main”.
R3.20 Règle#1: TL = 2/15 + 4/15 + 2/10 + 1/5 = 4/5.
L’ordonnancement serait réalisable avec les temps d’exécution moyens.
Règle#2: TL = 5/10 + 3/10 = 11/10.
Donc, cet ordonnancement n’est pas réalisable car l’ordonnancement des processus critiques
n’est pas réalisable avec les temps d’exécution maximums.
R3.21 Voir la figure dans les notes de cours.
R3.22 vrai: en plus, il y a une limite inférieure sur le délai entre deux arrivées.

vrai: on décide d’abord où vont les processus avant de déterminer quand ils vont s’exécuter.

faux: elle n’est même pas une stratégie à base temporelle.

R3.23 PPCM de 10, 15, 20, 25 = 300 u.t.
R3.24 3 processus p1 > p2 > p3. 1 ressource R1 commune à P1 et P3.
P3 est lancé et saisit R1.
P3 est suspendu dans sa section critique et P1 est lancé.
P1 est bloqué en voulant saisir R1.
P3 est relancé.
P3 est suspendu et P2 est lancé.
P2 s’exécute et bloque donc P1 même s’ils n’ont pas de ressource commune: inversion des
priorités.

R1 a une priorité plafond égale à p1.

P3 prend la priorité de P1 lorsque ce dernier veut saisir R1.
P3 termine avec R1 puis reprend sa priorité p3.
P1 s’exécute alors avec R1 et puis termine.
P2 peut seulement s’exécuter après P1, conformément aux priorités statiques.
R3.25 Il s’agit d’écrire l’équation de contraintes sur la période PPCM et prendre la valeur maximale
pour C2 qui la vérifie; vérifier ensuite pour les autres périodes au moyen d’un diagramme
temporel. Si ça ne fonctionne pas, diminuer C2 graduellement jusqu’à ce que toutes les
contraintes soient respectées.
Sur 60 u.t: 2 C2 + 6 C3 + 3 C4 + C1 <= 60. Donc 2 C2 + 12 + 12 + 3 <= 60 et C2 <= 16.5.
On peut vérifier que C2 = 16 satisfait toutes les contraintes (voir question b).

Processus (durée):
3(2), 4(4), 2(4), 3(2), 2(8), 3(2), 4(4), 2(4), 3(2), 2(8), 3(2), 4(4), 2(4), 3(2), 2(4), 1(3), idle(1).

GIF-3003 Systèmes parallèles et temps réel 314

 Réponses aux questions des exercices Robert Bergevin (c)

Sur 60 u.t, il faut enlever 6 u.t au total (10% de 60). Donc C2 <= 13.5 = 13 u.t et encore une
fois les contraintes sont respectées.

Refaire le calcul sur 60 u.t en changeant C1. Donne C2 <= 15.5 = 15 u.t.

D’abord écrire les équations de contraintes sur 60, 20 et 10 u.t et prendre la contrainte la plus
sévère. Vérifier au moyen d’un diagramme. Diminuer les valeurs de C1 et C2 par essais et
erreurs au besoin.
Sur 60 u.t: 6 C2 + 6 C3 + 3 C4 + C1 <= 60.
Sur 20 u.t: 2 C2 + C4 + 2 C3 <= 20.
Sur 10 u.t: C2 + C3 <= 10.
Donne C2=5 et C1=6 (ou C2=6 et C1=0).
Diagramme sur 20 u.t (répété 3 fois): 2(5), 3(2), 4(3), 2(5), 3(2), 4(1), 1(2)
R3.26 PPCM = 60. Une condition suffisante est Somme (ci/Ti) <= n (21/n - 1) = 0.757 car n = 4.
Sur 60 u.t, on obtient 4C1+2C2+12C3+3C4<= 0.757(60) soit 8+20+12+3C4<= 45.42
Donc C4 <= 1.81 = 1 u.t.

TL max = 1.0 (ordonnancement non assuré) donne C4<= 6.67 = 6 u.t.

(8+20+12+18)/60 = 96.7%

Processus (durée):
3(1), 1(2), 4(2), 3(1), 4(4), 3(1), 2(4), 3(1), 1(2), 2(2), 3(1), 4(4), 3(1), 4(2), 2(2) (reste 2 u.t
d’exécution au processus 2 arrivé à u.t. 30 donc échéance non respectée)...

Comme il manque 2 u.t au processus 2 sur 30 u.t, on est certain qu’en enlevant 2 u.t au
processus 4 (à chaque 20 u.t), on pourra satisfaire toutes les échéances. Par contre, on peut
voir sur le diagramme qu’en enlevant seulement 1 u.t (C4 = 5 u.t) on réussit aussi à satisfaire
les contraintes. C’est donc cette option qu’il faut retenir.
R3.27 c1 = 2 msec, c2 = 2 msec, c3 = 6 msec.

b1 = 4 msec, b2 = 1 msec, b3 = 0 msec.

P1: aucun P2: aucun P3: 1, 4, 6 et 8 msec.

P1: aucun P2: aucun P3: 2 et 5 msec.

R3.28 processus (durée, sémaphores saisis):
4(2,A), 2(2,B), 4(1,A), 3(2), 1(1), 3(2), 4(1,A), 1(2,A), 2(2,AB), 1(1,B), 2(1), 4(1).
processus (durée, sémaphores saisis):
4(2,A), 2(2,B), 4(2,A), 2(1,AB), 1(1), 2(1,AB), 1(2,A), 1(1,B), 2(1), 3(4), 4(1).
R3.29 Le temps de réponse R4 est élevé p/r à son temps de calcul. Il est bloqué longtemps à cause de

GIF-3003 Systèmes parallèles et temps réel 315

 Réponses aux questions des exercices Robert Bergevin (c)

l’inversion des priorités. Si le temps de réponse R4 est trop grand, il risque de dépasser la
contrainte d’échéance.

Il limite à 1 le nombre de fois qu’il peut être bloqué par un processus de moindre priorité.

Voir les diagrammes dans les notes de cours.

En fait, il est bloqué une fois par le premier processus ce qui est normal car ce dernier utilise
un sémaphore de priorité plus grande (p4). La durée totale du blocage est de 3 ce qui est plus
petit que la longueur de la section critique de P1 (=4) ce qui est aussi normal. Le fait que le
blocage soit coupé en deux provient du fait que P4 est plus prioritaire et n’a donc rien a voir
avec les interdépendances et le protocole lui-même.

Non car on ne connaît pas leurs contraintes d’échéance (ou s’ils en ont une!). En fait, on ne
sait même pas si ils sont périodiques ni quelle est leur période. On ne sait pas quelle doit être
la période d’ordonnancement à considérer (ex: PPCM). On ne peut pas évaluer le chargement
temporel ni vérifier si les temps de réponse sont acceptables.
R3.30 Le 1er processus qui entre dans la section critique devra en sortir avant que le 2e puisse
s’exécuter donc accéder à son tour a la section critique (le 1er arrivé a l’accès a la ressource et
il bloque le second jusqu’a ce qu’il termine cet accès).
Non car le 2ième processus pourra s’exécuter même si le 1er est déjà en exécution et qu’ils
ont la même priorité s’ils sont sur 2 processeurs différents.
R3.31

P1

P2

P3

t
t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10

en exécution avec S1 suspendu

en exécution avec S2 en exécution

en exécution avec S3 bloqué

c1 = 2 msec, c2 = 2 msec, c3 = 6 msec

b1 = 4 msec, b2 = 1 msec, b3 = 0 msec.

P1: aucun P2: aucun P3: 1, 4, 6 et 8 msec

P1: aucun P2: aucun P3: 2 et 5 msec.

GIF-3003 Systèmes parallèles et temps réel 316

 Réponses aux questions des exercices Robert Bergevin (c)

Ti = Ri où Ri = bi + ci + temps suspendu ou bloqué (7, 9, 10 msec, respectivement).

non car TL > 1 même sans tenir compte du blocage.

non, car l’hypothèse que les durées des sections critiques correspondantes sont les mêmes
n’est pas respectée, ni pour S2 (utilisée par P1 et P3) ni pour S3 (utilisée par P2 et P3).
R3.32 TL > 1
stratégie RM: t=8 processus 3.

TL = 0.833 > Condition_Suffisante(n=2) = 0.828

simulation RM: ordonnancement réalisable (période d’ordonnancement = PPCM = 6): 1 2 1 2
121

TL = 0.93 > CS(n=3) = 0.7798

simulation RM: ordonnancement non réalisable: 1 2 2 3 3 1 3 2 2 (processus 3 rate son
échéance à t=9)

Peut-être car stratégie dynamique fonctionne parfois même si RM ne fonctionne pas.

Même chose que ci-dessus.

simulation EDF: 1 2 2 3 3 3 3 1 2 2 1 3 3 3 3 1 2 2 3 3 1 2 2 3 3: aucune échéance ratée.

Réalisable car instant critique à la première unité de temps (PPCM = 315).
R3.33 Pour chaque processus, il faut calculer à chaque instant le relâchement et donc le temps de
calcul restant. On obtient le diagramme suivant sur 60 u.t. avec processus (durée): idle(5),
1(10), 3(11), 2(2), 3(2), 2(2), 3(2), 2(6), 1(5), idle(15)

TL = 78.3% supérieur à n (2^^1/n - 1) = 77.98% donc non suffisant pour affirmer que c’est
réalisable mais nécessaire pour affirmer que c’est peut-être réalisable.

PPCM (60,50,45) = 900

Temps de calcul total = 55 u.t. Il doit être réalisé dans l’intervalle [max di, min bi] i.e. [10, 60]
soit sur une période de 50 u.t. ce qui est impossible.
R3.34 Ça dépend de: contraintes temporelles des processus, chargement temporel, vitesse du(des)
CPU, nombre de capteurs/actuateurs/périphériques, complexité des traitements, fiabilité, etc.

Ça limite les communications inter-processus (moins de perte de temps) et ça simplifie p/r à

l’utilisation des sémaphores pour partage des ressources et synchronisation.

Oui (ou non) mais c’est insuffisant car seul P2 est assuré de respecter ses contraintes

GIF-3003 Systèmes parallèles et temps réel 317

 Réponses aux questions des exercices Robert Bergevin (c)

temporelles (si elles sont cohérentes entre elles).

TL = Sommation des ci/Ti > 1

Sommation des ni*ci = 90 > PPCM = 80.

Non, TL <= 1 est une condition nécessaire mais non suffisante.

PPCM= 80
R3.35 F
V
R3.36 Fiabilité: probabilité que le système soit opérationnel au temps t, étant donné qu’il est
opérationnel au temps 0.
Disponibilité: pourcentage de temps où le système est opérationnel sur une période donnée
(tient compte du temps de réparation).
R3.37 elle est constante (fonction de probabilité uniforme). Ainsi, la probabilité de défaillance F(t)
est une rampe positive (fonction linéaire croissante) entre 0 et le temps de mission.

R(t) = 1 - F(t) est une rampe négative allant de 1.0 à t=0 à 1 - 10^-9 à t = 10 heures.

Vrai. Une bonne disponibilité n’assure pas que le nombre de pannes est pratiquement nul. En
effet, s’il y a des pannes et que le temps de réparation est très court, on pourra avoir une bonne
disponibilité instantanée, ce qui n’est pas suffisant pour un STR sévère et critique.
R3.38 La probabilité que le système tombe en panne augmente avec le temps.

MTBF = 1 ⁄ λ et λ = 0, 2 donc MTBF = 5h.

1 - probabilité qu’il y ait une panne entre 0 et 7 heures (intégrale de la fonction de défaillance).
–7 ⁄ 5
On obtient e = 0, 247 soit 24,5%.

DS = MTBF/ (MTBF+MTTR) soit 5/(5+2)=0.714 donc 71,4%.

1/5 = 0,2 défaillances par heure

La probabilité de défaillance s’obtient en calculant l’intégrale de la fonction de défaillance du

système.
ax ax
∫e dx = e ⁄a

2
à t=2 on a: – ( 0, 2t ) donc 33,0%
– 1e = 0, 330
0

GIF-3003 Systèmes parallèles et temps réel 318

 Réponses aux questions des exercices Robert Bergevin (c)

10
– ( 0, 2t )
à t=10 on a: – 1e = 0, 865 donc 86,5%
0
∞
– ( 0, 2t )
à t = infini, on a: – 1e = 1 donc 100%
0

La disponibilité du système avant la première panne est égale à la fiabilité du système. Cette
donc une fonction du temps t. Si on veut un résultat moyen, on utilise t=5h et on obtient alors
0.368 soit 36.8%.

La fonction doit être une fonction de probabilité, donc son intégrale doit être égale à 1.
R3.39 La fiabilité est égale à 1 - F(t) où F(t) est la probabilité de défaillance au temps t soit
l’intégrale entre 0 et t de la fonction de probabilité du temps de défaillance.
MTBF = Ef(t=infini) où Ef est l’espérance mathématique de cette fonction de probabilité du
temps de défaillance.
R3.40 Minimum au point de rencontre commun des 2 fonctions: f(t0) = B.

Deux fonctions égales à f(t0) donc extrait t de la première expression ce qui donne
t0= ln (A/B)/alpha.

Baignoire

Calcul de t0 pour ces valeurs donne: 6.9315, donc t=7 secondes tombe dans la 2ieme portion.
La probabilité de défaillance F(t) à t=7 se calcule donc en faisant l’intégrale de la portion à
gauche du minimum et en additionnant l’intégrale de la portion à droite du minimum jusqu’à
t=7.
La fiabilité R(t) = 1 = F(t).
L’intégrale de la portion gauche donne (-A/alpha)e-alpha t évalué de 0 à t0 donc 0.4999.
L’intégrale de la portion droite donne (B/beta ebeta t0)ebeta t évalué de t0 à 7 donc 0.00351.
F(7) est donc égal à 0.503 et R(7) = 1 - F(t) = 0.497.

On veut que l’intégrale donne 1 entre tmin et tmax i.e. que la probabilité de défaillance soit
égale à 1 à la fin de l’intervalle.
Comme le temps ne peut être négatif, on choisit tmin = 0.
tmax est obtenu en calculant l’intégrale en 2 portions comme ci-dessus pour avoir
F(tmax)=1.0.
On garde le même temps minimum entre les deux portions.
En résolvant, on obtient tmax = 13.8629.
R3.41 Faux: la probabilité de défaillance est l’intégrale de la fonction (positive) qui augmente avec t.
R3.42 1ère expression: plus disponible (SA->1.0) si dénominateur petit i.e. MTTR faible et/ou

GIF-3003 Systèmes parallèles et temps réel 319

 Réponses aux questions des exercices Robert Bergevin (c)

MTBF élevé.
R3.43 1. complexité du système et de l’application (matériel et logiciel, capteurs, traitement,
actuateurs) peut nuire à la fiabilité
2. coût élevé du système et de l’application (vol interplanétaire)
3. difficulté de réparation à distance et importance de la durée de vie

Les conditions d’opération ne sont pas déterministes (imprévus possibles dans le déroulement
de l’application). De plus, la complexité du système le rend difficile à tester de façon
exhaustive en essayant d’éviter i.e. éliminer toutes les fautes possibles.

Action. Vu de l’extérieur l’utilité du système est définie par ses actions.

La fonction de défaillance permet de calculer F(t) la probabilité de défaillance au temps t

(intégrale sous la courbe de t=0 à t=t). La fiabilité instantanée R(t) = 1 - F(t).

Programmation N exemplaires (NVP) et blocs de reprise (RB).

NVP est plus approprié parce que parallèle (statique) et ne cause donc pas de délais
supplémentaires.

1. acquisition des images, traitement (compression etc.) et transmission au taux vidéo (sévère
car chaque image doit être compréhensible mais interruptions possibles dans le déroulement)
2. réception des fichiers de tracé (sévère car on ne peut manquer de données)
3. contrôle (asservissement) du déplacement du véhicule (sévère si veut suivre le tracé avec
précision).
R3.44 Plus faible car il faut multiplier les deux fiabilités (les deux modules doivent être
fonctionnels).
R3.45 Tolérance car ces tests sont typiquement faits dans le système en opération (“on-line”) et non
avant de le lancer (“off-line”). L’évitement des fautes consiste à trouver les fautes avant de
lancer le système e.g. par un design rigoureux, le choix de modules fiables, les essais
exhaustifs, etc.
R3.46 Blocs de reprise: méthode séquentielle; programmation N-exemplaires: méthode parallèle.

Exécution du bloc; vérification de la validité du résultat; retour au début du bloc pour

réexécution si non valide; après n essais, essai d’un nouveau bloc pour même traitement mais
réalisé différemment.
R3.47 R(t) = 1 - F(t) =
1 - intégrale(lambda*exp(-lambda*t)) entre 0 et t = 1-(1-exp(-lambda*t) = exp(-lambda*t)

Allure d’une fonction de rodage: logiciel d’abord si matériel a été bien testé sinon les deux.

R(t) = P(OP(t)/OP(t=0)) donc R(0)=1 par définition i.e. que la probabilité que le système soit

GIF-3003 Systèmes parallèles et temps réel 320

 Réponses aux questions des exercices Robert Bergevin (c)

opérationnel au temps 0 est égale à 1.0. Par contre, si lambda est très élevé alors R tend vers
zéro très rapidement ce qui peut indiquer des problèmes existants à la mise en marche. Il faut
cependant additionner à la fonction de défaillance une fonction de vieillissement
(exponentielle positive bornée à droite) pour tenir compte de la correction de ces erreurs
initiales. Ceci donne une fonction de type “baignoire” qui est plus réaliste.

R12 = R1 + R2 - R1R2 = 2exp(-lambda*t) - exp(-2*lambda*t)

La redondance se fait par un mécanisme séquentiel, donc on risque de rater des échéances. Il
faut changer pour un mécanisme de redondance parallèle.
De plus, l’utilisation d’un système identique n’est pas idéale du point de vue des fautes
logicielles. Il faudrait un système de fonctionnalité identique mais avec deux logiciels
différents pour que la redondance soit vraiment efficace.
R3.48 plusieurs versions du logiciel obtenues par une diversité de la conception (outils, personnes,
etc.) à partir des mêmes spécifications.

Programmation N exemplaires (NVP) et blocs de reprise (RB).

NVP est plus approprié parce que parallèle (statique) et ne cause donc pas de délais
supplémentaires.

Faux. Dans ces situations, un processeur est en faute mais il ne peut pas être identifié. Il
produit des données qui sont arbitraires plutôt que de devenir silencieux (inaccessible,
déconnecté). On ne peut donc pas reprendre le calcul avec le même processeur ou avec un
autre processeur (mécanisme séquentiel RB) ni utiliser un autre résultat déjà calculé à la place
de celui du processeur en faute (mécanisme parallèle NVP). Le mécanisme parallèle pourrait
parfois être utile car la décision se base seulement sur une comparaison des résultats qui peut
être plus complexe que la simple majorité. Il faudrait alors que les modules soient dans une
structure hiérarchique et que ce soit les esclaves qui contiennent des éléments redondants et
possiblement en faute.
R3.49 une faute dans le système ne se traduit pas par une mise hors service mais par un
comportement imprévisible de certains éléments. L’objectif est que le reste des éléments
restent prévisibles.

GIF-3003 Systèmes parallèles et temps réel 321