Universit de Nice Sophia Antipolis Licence 1 Sciences Fondamentales 2013-2014
Inormati!"e #nrale
$% n& 11
'(ercice 1 ) *erormance
Un processeur 1,8 GHz excute un programme de benchmark qui utilise un mlange de 4 tpes
d!instruction"
$+pe instr"ction Nom,re d-instr"ction
e(c"tes
Nom,re de c+cle .
instr"ction
#pration enti$re 1%&&&& 1
'rans(ert mmoire 4%&&& )
#pration (lottante %%&&& )
*ontr+le ,sauts- )&&&& )
.((ichage %&& 1%
1/ *ombien de ccles se programme prendra0t0il pour s1excuter 2
1%&&&& 3 1 4 ) 3 ,4%&&& 4 %%&&& 4 )&&&&- 4 1% 3 %&& 5 678%&&
)/ 9uelle sera la dure d1excution 2 678%&& : ,1,8 3 1&
07
-, en;iron ))& <s
6/ *alculez le *=> ,ccle per instruction- de ce programme, d(ini comme le rapport entre
le nombre de ccles requis pour son excution et le nombre d1instructions/
>l a )8&%&& instructions excutes en tout, donc *=> 5 678%&& : )8&%&& 5 1,48
'(ercice 2 ) *erormance encore
#n consid$re le m?me processeur que prcdemment, et le programme sui;ant,
p <- 0 1+2 cycles
tant que b > 0 faire 1+2+1 cycles (+2 si saut)
p <- p + a 1+3*2+1
b <- b 1 1+2*2+1
fin tant que 1+2 (saut en dbut de boucle)
afficher p 1+2+15
1/ 9ue calcule ce programme 2 @ssaer de la (aire (onctionner pour le de;iner, en prenant
par exemple a 5 6 et b 5 %/ A;idemment a 3 b
)/ *haque opration ou comparaison demande que ses oprandes ,sau( les constantes-
soient en registre/ =our chaque ligne, indiquez le nombre de ccles ncessaires
,comptez 1 ccle pour aller chercher l!instruction en mmoire-
6/ Be quelle ;ariable dpend son temps d!xecution 2 bien sCr b
4/ *ombien de ccles au total se programme prendra0t0il pour s1excuter en (onction de
cette ;ariable 2 6 4 b 3 ,4 4 8 4 D 4 6- 4 ) 4 18 5 )6 4 )1b
Eormellement, il (aut compter que le test du tantque se (ait 1 (ois de plus que la boucle
et saute, mais Fa ne change pas (ondamentalement les rsultats " )6 4 D G )7
%/ 9uelle sera la dure d1excution pour b 5 1&)6 2 ,)7 4 1&)6 3 )1- : 1,8 5 en;iron 1,)<s
'(ercice 3 ) *erormance encore et encore
H?mes questions que prcdemment, mais a;ec le programme sui;ant
p <- 0 1 + 2 cycles
tant que b > 0 faire 1 + 2 + 1 cycles (+ 2 si saut)
si b % 2 = 1 alors 1 + 2 + 1+1 cycles (+ 2 si saut)
p <- p + a 1 + 3*2 + 1 (que si b impair)
fin si
b <- b / 2 1 + 2*2 + 1
a <- a * 2 1 + 2*2 + 1
fin tant que 1 + 2
afficher p 1 + 2 + 15
*omparer les per(ormances des ) programmes pour un b de la (orme )
n
01 et )
n
/
Ie programme calcule aussi a 3 b, mais J l!gptienne K/
Lombre total de ccles, si U est le nombre de 1 dans la reprsentation binaire de b et M le nombre
de &, et b N )
n
,n5U4M-
6 4 n 3 ,4 4 % 4 D 4 D 4 6- 4 8 3 U 4 D 4 18 5 )8 4 )4n 4 8U
Oi on multiplie par 1&)6, n5U51& donc )84)4&48&5648 ccles, comparer aux plus de )&&&& de
l!autre programme/ Oi on multiplie par )&48, le premier aura en;iron le double de ccles ,on double
le nombre de boucles-, l!autre uniquement les ccles pour 1 boucle de plus, soit pr$s de 4&&&&
contre moins de D&&/ I!un est linaire, l!autre logarithmique/
@n multipliant par )
n
, on a seulement )4,n41- 4 )8 4 8 ccles, soit )77 pour n 5 1&/
'(ercice 4 ) *ipeline
Bans cet exercice nous allons considrer processeur aant un pipeline % tages, chacun prenant un
ccle/
1/ Une instruction entre dans le pipeline au ccle i, quel ccle aura0t0elle (ini son
excution 2
elle s!excute en i4&, i41, i4), i46, i44 et sera donc compl$tement termine en i4%
)/ #n consid$re un programme de n instructions/ @n ignorant les stall dans le pipeline,
calculez le nombre de ccles ncessaires pour son excution/
n 4 ,p P 1- si p est le pro(ondeur du pipeline, donc ici n 4 4
6/ 9uel est le *=> de ce programme sur ce processeur 2
n44 : n, tend donc ;ers 1 quand n tend ;ers 4
4/ 9uel serait le *=> sur un processeur n1aant pas de pipeline 2
%n:n 5 %
'(ercice / ) Data Hazard
Un processeur poss$de un pipeline 4 tages tel que dcrit dans le cours ,Eetch0Becode0@xecute0
Qrite-/ Ia lecture des donnes est (aite lors de l!tape @xecute/ Un programme est compos des
instructions sui;antes
ADD R4, R1, R2
SUB R1, R2, R4
MUL R6, R1, R5
DIV R3, R2, R5
MUL R2, R3, R4
*e programme n1utilise que des registres et ne (ait donc pas d1acc$s mmoire/
1/ @n ignorant les data hazard, reprsentez l1excution de ces instructions dans le pipeline
en ;ous basant sur le cours/
ADD R4, R1, R2 E B @ Q ,R4-
SUB R1, R2, R4 E B @ ,R4- Q ,R1-
MUL R6, R1, R5 E B @ ,R1- Q,RD-
DIV R3, R2, R5 E B @ Q,R6-
MUL R2, R3, R4 E B @,R6- Q,R)-
)/ Re(aites le m?me schma en raSoutant des stall lorsque c1est ncessaire
ADD R4, R1, R2 E B @ Q ,R4-
SUB R1, R2, R4 E B stall @ ,R4- Q ,R1-
MUL R6, R1, R5 E stall B stall @ ,R1- Q,RD-
DIV R3, R2, R5 stall E B @ stall Q,R6-
MUL R2, R3, R4 stall E B @ stall @,R6- Q,R)-
le stall en rouge " car on ne peut pas a;oir ) critures registre en m?me temps
6/ =roposez un r0ordonnancement des instructions minimisant le temps total
d1excution/
.ttention ce que les registres gardent les m?mes ;aleurs quand on dplace les
instructions " donc
ADD R4, R1, R2
DIV R3, R2, R5
SUB R1, R2, R4
MUL R2, R3, R4
MUL R6, R1, R5
ADD R4, R1, R2 E B @ Q,R4-
DIV R3, R2, R5 E B @ Q ,R6-
SUB R1, R2, R4 E B @ ,R4- Q ,R1-
MUL R2, R3, R4 E B @,R6,R4- Q,R)-
MUL R6, R1, R5 E B @ ,R1- Q,RD-
'(ercice 0 ) Control Hazard
1/ 9uel est le coCt d1une erreur de prdiction de branchement 2
>l (aut ;ider le pipeline, donc c!est un coCt proportionnel la pro(ondeur/
)/ Un programme est compos de 64&&& instructions dont 1&T sont des sauts/ #n
dispose d1un processeur qui a un taux de succ$s de 7&T aux prdictions de
branchement/ *alculez le nombre de ccles ncessaires l1excution de ce
programme sur un processeur dont le pipeline a % tages/
Ie programme aant 64&&& instructions, il prendra en;iron 64&&& ccles pour
s!excuter/ 64&& instructions sont des branches/ Bans 1&T des cas ,64& instructions-,
il (audra (lusher le pipeline, ce qui aura un coCt de %/ Bonc au (inal Fa coCtera
66DD& 4 64&3%
6/ H?me question concernant un pipeline )& tages
Bans le cas oU le pipeline est de )& tages, c!est 66DD& 4 64&3)&
4/ V a0t0il un taux de succ$s minimum qui rendrait le processeur % tages plus e((icace
que celui )& 2 *ommentez/
Ooit x le taux de succ$s en T
Lb ccles 5 61D&& 4 64&&3x 4 64&&,10x-3p a;ec p pro(ondeur du pipeline
>l (aut tracer les ) courbes pour p5% et p5)&
=our x5&/%T
p5% " 418&& ccles
p 5)& " 61D&& 4 18&& 4 64&&& 5 D86&&
Oi on (ait le calcul pour plusieurs ;aleurs on s!aperFoit que c!est touSours celui a;ec
le pipeline le plus court qui gagne/ Bonc pourquoi (aire des pipeline long2 c!est parce
que cet exercice (ait un hpoth$se (ausse/ #n augmente la longueur du pipeline, sans
changer la (rquence/ .utrement dit, une instruction prend plus de temps pour
s!excuter sur la machine long pipeline, ce qui est le contraire de ce qu!on ;oudrait
en allongeant le pipeline/ >l (audrait donc, pour ?tre plus raliste, augmenter la
(rquence/
