Université de Bordeaux Collège Sciences et Technologies ANNÉE UNIVERSITAIRE 2018 -- 2019 SESSION 1 D'AUTOMNE ́ Parcours / Étape : LSTS / L2 Code UE : 4TIN304U Épreuve : Architecture des ordinateurs * QUESTION 1 [50 points] ============ * Question 1.1 [10 points] On notera Di les trois bascules D, avec i = {0, 1, 2}. Toutes les entrées C des trois bascules sont directement connectées en parallèle à l'horloge H, pour modifier leurs valeurs à chaque top d'horloge. La valeur binaire "1" doit circuler de D2 à D1, puis de D1 à D0, puis revenir à D2. Il faut donc câbler les trois bascules de façon circulaire, l'entrée D de D1 recevant la sortie Q de D2, etc. On allumera chaque lampe avec la sortie de la bascule qui lui correspond. i = { 0, 1, 2 } Di:C = H D1:D = D2:Q D0:D = D1:Q D2:D = D0:Q s_i = Di:Q * Question 1.2 [10 points] Avec le chenillard "zig-zag", le "1" doit allumer à nouveau la lampe du milieu pendant qu'il "remonte" vers la bascule D2. On va donc créer un cycle de quatre bascules D3 à D0, la bascule D3 correspondant alors à la phase de "remontée" du "1" de D0 vers D2. La lampe du milieu sera allumée soit lorsque le "1" "descend" de D2 vers D0 à travers D1, soit lorsqu'il "remonte" de D0 vers D2 à travers D3, au moyen d'une porte "OR". i = { 0, 1, 2, 3 } Di:C = H D1:D = D2:Q D0:D = D1:Q D3:D = D0:Q D2:D = D3:Q s_2 = D2:Q s_1 = OR (D1:Q, D3:Q) s_0 = D0:Q * Question 1.3 [20 points] Le circuit CPT sera construit au moyen de deux bascules D1 (poids fort) et D0 (poids faible). Il doit parcourir les quatre états suivants : 00, 01, 10, 11. On voit que : - la bascule D0 doit changer d'état à chaque cycle d'horloge. Il suffit donc de fournir comme entrée l'opposé de sa sortie, au moyen d'un inverseur ; - la bascule D1 ne doit changer d'état que quand la bascule D0 était à "1" au cycle précédent. On veut donc une fonction qui renvoie D1:Q lorsque D0:Q vaut 0, et NOT (D1:Q) quand D0:Q vaut 1 : x = OR (AND (D1:Q, NOT (D0:Q)), AND (NOT (D1:Q), D0:Q)) = XOR (D0:Q, D1:Q) . D0:C = H D1:C = H D0:D = NOT (D0:Q) D1:D = XOR (D0:Q, D1:Q) * Question 1.4 [10 points] Il s'agit de faire correspondre chacun des quatre états d'allumage des trois lampes s_2, s_1 et s_0 aux quatre configurations possibles. On peut prendre par exemple : 00 -> 1 0 0 01 -> 0 1 0 10 -> 0 0 1 11 -> 0 1 0 Les configurations conduisant à l'allumage de chaque lampe sont alors : s_2 = AND (NOT (D1:Q), NOT (D0:Q)) s_1 = D0:Q s_0 = AND (D1:Q, NOT (D0:Q)) * QUESTION 2 [110 points] ============ * Question 2.1 [20 points] Pour calculer le modulo, on initialise une variable à la valeur "a", et on lui soustrait la valeur "b" tant que le reste de cette soustraction est positif ou nul. modit: mrmovl 4(%esp),%eax # %eax contient "a" puis les restes successifs mrmovl 8(%esp),%edx # %edx contient "b" à soustraire au reste modit2: rrmovl %eax,%ecx # %ecx sauvegarde la valeur courante du reste subl %edx,%ecx # Soustrait "b" au reste courant jl modit3 # Fin si négatif, avec %eax contenant le modulo rrmovl %ecx,%eax # Met à jour le reste après soustraction jmp modit2 # Reboucle sur la soustraction modit3: ret Comme on n'utilise que les trois registres "caller save", on n'a pas besoin d'effectuer de sauvegardes d'autres registres. On peut aussi soustraire tant que l'on n'a pas atteint une valeur strictement négative, puis restaurer une valeur positive. Cela réduit considérablement le nombre d'instructions au coeur de la boucle. modit: mrmovl 4(%esp),%eax # %eax contient "a" puis les restes successifs mrmovl 8(%esp),%edx # %edx contient "b" à soustraire au reste modit2: subl %edx,%eax # Soustrait "b" au reste courant jge modit2 # Tant qu'on n'a pas atteint une valeur négative addl %edx,%eax # Restaure une valeur positive ou nulle ret * Question 2.2 [10 points] .pos 0 irmovl 0x200,%esp # Initialise la pile mrmovl pb,%eax # Passage du deuxième paramètre : b pushl %eax mrmovl pa,%eax # Passage du premier paramètre : a pushl %eax call modit iaddl 8,%esp # Restauration de la pile (2 paramètres) rmmovl %eax,pm # Sauvegarde du résultat dans la zone pm halt .align 4 pa: .long 15 pb: .long 4 pm: .long 0 * Question 2.3 [20 points] modre: mrmovl 4(%esp),%eax # Place a dans %eax mrmovl 8(%esp),%edx # Place b dans %edx rrmovl %eax,%ecx # Sauvegarde a pour le test subl %edx,%ecx # Compare b à a : a -= b jl modre2 # Fin si (b > a), avec %eax contenant a addl %edx,%edx # Calcule (2 * b) pushl %edx # Empile (2 * b) en deuxième paramètre pushl %eax # Empile a en premier paramètre call modre # Appel récursif à "modre (a, 2 * b)" iaddl 8,%esp # Restaure la pile (2 paramètres) mrmovl 8(%esp),%edx # Place à nouveau b dans %edx subl %edx,%eax # Compare b à i : i -= b jge modre2 # Fin si (i >= b), avec %eax contenant (i - b) addl %edx,%eax # Restaure i sinon, pour le retourner modre2: ret Ici encore, comme on n'utilise que les trois registres "caller save", on n'a pas besoin de sauvegarder d'autres registres. Au lieu de relire "b" après l'appel récursif (qui aura détruit le registre "caller save" %edx), on aurait pu empiler %edx avant l'empilage du premier paramètre, puis le dépiler après le dépilage de l'espace des deux paramètres : cela aurait pris 4 octets de code ("pushl %edx" et "popl %edx") au lieu de 6, mais au prix de l'occupation de 4 octets supplémentaires dans la pile par niveau de récursion, alors que la valeur s'y trouve déjà. * Question 2.4 [20 points] Le calcul itératif du quotient est similaire à celui du modulo, à la différence que l'on a besoin d'un registre supplémentaire pour compter le nombre de fois que l'on effectue la soustraction. À l'opposé, on n'a pas besoin de conserver telle quelle l'ancienne valeur du reste, ce qui nous fait gagner un registre. On peut donc encore une fois coder la fonction avec les seuls trois registres "caller save". quotit: xorl %eax,%eax # %eax contient le quotient, initialisé à 0 mrmovl 4(%esp),%ecx # %ecx contient a puis les restes successifs mrmovl 8(%esp),%edx # %edx contient b à soustraire au reste quotit2: subl %edx,%ecx # Soustrait b au reste courant jl quotit3 # Fin si négatif, avec %eax contenant le quotient iaddl 1,%eax # Met à jour le quotient jmp quotit2 # Reboucle sur la soustraction quotit3: ret * Question 2.5 [20 points] On va coder la fonction avec un langage C mâtiné de Python, pour renvoyer des 2-uplets au lieu de simples valeurs. La fonction "modre" renvoyait un reste, par soustraction récursive de multiples. Il faut la modifier afin d'ajouter au quotient chaque fois que l'on soustrait un multiple. La récursion à un multiple doublé doit donc s'accompagner du passage à un quotient doublé aussi. int /* Renvoie le quotient */ quotre (int a, int b) { int q, r; (q, r) = quotre2 (a, b, 1); /* Reste: a, soustrait: b, quotient: 1 */ return (q); /* On ne retourne que le quotient */ } (int, int) /* Renvoie le quotient et le reste */ quotre2 (int a, int b, int q) { int iq, ir; if (a < b) /* Si on ne peut pas soustraire */ return (0, a); /* Aucune contribution au quotient */ (iq, ir) = modre (a, 2 * b, 2 * q); /* Essaie de soustraire le double */ if (ir >= b) /* Si on peut encore soustraire au reste */ return (iq + q, ir - b); /* Soustrait au reste et ajoute au quotient */ return (iq, ir); /* Sinon on renvoie ce qu'on a déjà */ } * Question 2.6 [20 points] La fonction quotre2 renvoie le quotient et le reste. Pour simplifier l'écriture de la fonction quotre, on va renvoyer le quotient dans %eax et le reste dans %edx, comme cela le quotient sera déjà en place dans la fonction quotre. quotre: mrmovl 4(%esp),%ecx # %ecx contient le premier paramètre : a mrmovl 8(%esp),%edx # %edx contient le premier paramètre : b irmovl 1,%eax pushl %eax # Empile le troisième paramètre : 1 pushl %edx # Ré-empile le deuxième paramètre : b pushl %ecx # Ré-empile le premier paramètre : a call quotre2 # Calcule récursivement quotient et modulo iaddl 12,%esp # Restaure la pile (3 paramètres) ret # %eax contient déjà le quotient quotre2: mrmovl 4(%esp),%edx # %edx contient a, le reste mrmovl 8(%esp),%eax # %eax contient b, à soustraire rrmovl %edx,%ecx # Sauvegarde a pour le test subl %eax,%ecx # Compare b à a jge quotre3 # Si (a >= b), continue la fonction xorl %eax,%eax # Le quotient vaut 0 ret # %edx contient déjà le reste a quotre3: mrmovl 12(%esp),%ecx # %ecx contient q addl %ecx,%ecx # Calcule 2 * q pushl %ecx # Empile le troisième paramètre : 2 * q addl %eax,%eax # Calcule 2 * b pushl %eax # Empile le deuxième paramètre : 2 * b pushl %edx # Empile le premier paramètre : a call quotre2 # Appel récursif à "quotre2 (a, 2 * b, 2 * q)" iaddl 12,%esp # Restaure la pile (3 paramètres) mrmovl 8(%esp),%ecx # %ecx contient b, à soustraire subl %ecx,%edx # Calcule (ir - b) jge quotre4 # Si (ir >= b), calcule avant de retourner addl %ecx,%edx # Restaure la valeur de ir dans %edx ret # %eax contient déjà iq, le quotient quotre4: mrmovl 12(%esp),%ecx # %ecx contient q, à ajouter addl %ecx,%eax # %eax contient (iq + q) ret # %edx contenait déjà (ir - b) * QUESTION 3 [40 points] ============ * Question 3.1 [20 points] mrmovl D(rB),rA --------------- Fetch : icode:ifun = M1[PC] rA:rB = M1[PC+1] valC = M4[PC+2] valP = PC + 6 Decode : valB = R[rB] Execute : valE = valB + valC Memory : valM = M4[valE] Write back : R[rA] = valM PC update : PC = valP popl rA ------- Fetch : icode:ifun = M1[PC] rA:rB = M1[PC+1] valP = PC + 2 Decode : valA = R[%esp] valB = R[%esp] Execute : valE = valB + 4 Memory : ValM = M4[valA] Write back : R[%esp] = valE R[rA] = valM PC update : PC = valP call D ------ Fetch : icode:ifun = M1[PC] valC = M4[PC+1] valP = PC + 5 Decode : valB = R[%esp] Execute : valE = valB + (-4) Memory : M4[valE] = valP Write back : R[%esp] = valE PC update : PC = valC * Question 3.2 [20 points] Le code qui a été rajouté est entouré d'astérisques '*' pour le mettre en valeur. Ces astérisques doivent être enlevés pour que le code HCL compile effectivement. ################ Fetch Stage ################################### # Does fetched instruction require a regid byte? bool need_regids = icode in { RRMOVL, OPL, PUSHL, IRMOVL, RMMOVL *, POPL, MRMOVL* }; # Does fetched instruction require a constant word? bool need_valC = icode in { OPL, IRMOVL, RMMOVL, JXX *, MRMOVL, CALL* }; # List of all valid instructions bool instr_valid = icode in { NOP, HALT, RRMOVL, IRMOVL, RMMOVL, MRMOVL, OPL, JXX, CALL, RET, PUSHL, POPL }; ################ Decode Stage ################################### ## What register should be used as the A source? int srcA = [ icode in { OPL, RRMOVL, RMMOVL, PUSHL } : rA; icode in { RET *, POPL* } : RESP; 1 : RNONE; # Don't need register ]; ## What register should be used as the B source? int srcB = [ (icode == IRMOVL) && (ifun == 1) : rB; icode in { OPL, RMMOVL *, MRMOVL* } : rB; icode in { PUSHL, RET *, POPL, CALL* } : RESP; 1 : RNONE; # Don't need register ]; ## What register should be used as the E destination? int dstE = [ (icode == IRMOVL) && (ifun == 1) : rA; icode in { IRMOVL, RRMOVL, OPL } : rB; icode in { PUSHL, RET *, POPL, CALL* } : RESP; 1 : RNONE; # Don't need register ]; ## What register should be used as the M destination? int dstM = [ icode in { *MRMOVL, POPL* } : rA; 1 : RNONE; # Don't need register ]; ################ Execute Stage ################################### ## Select input A to ALU int aluA = [ icode in { OPL, RRMOVL } : valA; icode in { IRMOVL, RMMOVL *, MRMOVL* } : valC; icode in { PUSHL *, CALL* } : -4; icode in { RET *, POPL* } : 4; # Other instructions don't need ALU ]; ## Select input B to ALU int aluB = [ icode in { RMMOVL, OPL, PUSHL, RET *, MRMOVL, CALL, POPL* } : valB; (icode == IRMOVL) && (ifun == 1) : valB; icode in { RRMOVL, IRMOVL } : 0; # Other instructions don't need ALU ]; ## Set the ALU function int alufun = [ icode in { OPL } : ifun; 1 : ALUADD; ]; ## Should the condition codes be updated? bool set_cc = (icode == OPL); ################ Memory Stage ################################### ## Set read control signal bool mem_read = icode in { RET *, MRMOVL, POPL* }; ## Set write control signal bool mem_write = icode in { RMMOVL, PUSHL *, CALL* }; ## Select memory address int mem_addr = [ icode in { RMMOVL, PUSHL *, CALL, MRMOVL* } : valE; icode in { RET *, POPL* } : valA; # Other instructions don't need address ]; ## Select memory input data int mem_data = [ icode in { RMMOVL, PUSHL } : valA; icode in { *CALL* } : valP; # Default: Don't write anything ]; ################ Program Counter Update ############################ ## What address should instruction be fetched at int new_pc = [ *icode == CALL : valC;* icode == JXX && Bch : valC; icode == RET : valM; 1 : valP; ];