Université de Bordeaux Collège Sciences et Technologies ANNÉE UNIVERSITAIRE 2017 -- 2018 SESSION 1 D'AUTOMNE ́ Parcours / Étape : LSTS / L2 Code UE : 4TIN304U Épreuve : Architecture des ordinateurs * QUESTION 1 [80 points] ============ * Question 1.1 [10 points] La table de vérité du demi-additionneur est : A B | C S --------- 0 0 | 0 0 0 1 | 0 1 1 0 | 0 1 1 1 | 1 0 d'où : S = XOR (A, B) C = AND (A, B) * Question 1.2 [10 points] On veut câbler un circuit tel que : a_{2} a_{1} a_{0} + 0 0 1 --------------------- x_{2} x_{1} x_{0} Pour le bit 0, on n'a pas de retenue d'entrée. Pour les bits i={1, 2}, la valeur à calculer est a_{i} plus la retenue de l'addition dans la colonne précédente. On n'a donc besoin que d'un demi-additionneur pour traiter chaque bit. Soient c_{i} les retenues respectives de trois demi-additionneurs HAi, pour i = {0, 1, 2}. x_{0} = HA0:S (a_{0}, 1) c_{0} = HA0:C (a_{0}, 1) x_{1} = HA1:S (a_{1}, C_{0}) c_{1} = HA1:C (a_{1}, C_{0}) x_{2} = HA2:S (a_{2}, C_{1}) Il est possible d'exprimer cette solution avec les équations de la question précédente : x_{0} = XOR (a_{0}, 1) = NOT (a_{0}) c_{0} = AND (a_{0}, 1) = a_{0} x_{1} = XOR (a_{1}, c_{0}) = XOR (a_{1}, a_{0}) c_{1} = AND (a_{1}, a_{0}) x_{2} = XOR (a_{2}, c_{1}) * Question 1.3 [10 points] Il faut mémoriser trois bits à la fois. Il faut donc trois bascules D, notées Di, avec i = {0, 1, 2}. Toutes les entrées C des trois bascules sont directement connectées en parallèle à l'horloge H, pour capturer une nouvelle valeur à chaque top d'horloge. Pour mémoriser la valeur incrémentée, il faut reboucler les sorties de l'incrémenteur sur les entrées des trois bascules, les entrées de l'incrémenteur étant les sorties Q des trois bascules : Di:C = H Di:D = INC:X_{i} INC:A_{i} = Di:Q * Question 1.4 [10 points] Il s'agit de filtrer les entrées de chacune des bascules, afin que la valeur zéro soit placée sur l'entrée D de chaque bascule, au lieu du résultat de l'incrémentation. Pour cela, on a juste besoin d'une porte AND, qui rendra zéro quand "Z=1" : Di:D = AND (INC:X_{i}, NOT (Z)) Ainsi, quand Z=1, NOT (Z) = 0, et le AND renverra zéro, quelle que soit la valeur résultant de l'incrémentation. * Question 1.5 [10 points] Pour calculer l'opposé d'un nombre entier en notation "complément à deux", on prend le nombre obtenu en inversant chacun des bits du nombre initial, auquel on ajoute le nombre 1. Dans le cas présent, on veut connaître le codage de "-1", c'est-à-dire de l'opposé de "1". Sur trois bit, le nombre 1 se code 001, et l'opposé de 001 est : 001 -> 110 + 001 = 111 En fait, quel que soit le nombre de bits considéré, en notation "complément à deux", la valeur "-1" est le nombre dont tous les bits sont à 1. * Question 1.6 [20 points] Il existe deux façons d'aborder ce problème. La première, induite par la question précédente, consiste à considérer que décrémenter de 1 revient à ajouter -1 à la valeur d'entrée. On veut donc câbler un circuit tel que : a_{2} a_{1} a_{0} + 1 1 1 --------------------- x_{2} x_{1} x_{0} Le premier bit se traite exactement comme pour l'additionneur classique. Pour les deux autres, il faut ajouter 1 en plus, ce qui nécessite deux demi-additionneurs par bit : un pour traiter le "1" à ajouter à chaque fois, et un pour la retenue entrante du bit précédent. Comme on sait que l'on ajoute 1 à chaque fois, on peut simplifier le premier demi-additionneur : a'_{i} = XOR (a_{i}, 1) = NOT (a_{i}) c'_{i} = AND (a_{i}, 1) = a_{i} On aura une retenue c_{i} si c'_{i} = 1 ou par retenue du deuxième demi-additionneur, donc il faudra les grouper les retenues par un OR. On a donc : x_{0} = XOR (a_{0}, 1) = NOT (a_{0}) c_{0} = AND (a_{0}, 1) = a_{0} x_{1} = XOR (a'_{1}, c_{0}) = XOR (NOT (a_{1}), a_{0}) c_{1} = OR (c'_{1}, AND (a'_{1}, a_{0})) = OR (a_{1}, AND (NOT (a_{1}), a_{0})) # Que l'on peut simplifier en : = OR (a_{1}, a_{0}) # Car si a_{1} = 1, c_{1} = 1, et si a_{1} = 0, c_{1} = a_{0} x_{2} = XOR (a'_{2}, c_{1}) = XOR (NOT (a_{2}), c_{1}) = XOR (NOT (a_{2}), OR (a_{1}, a_{0})) La deuxième façon de voir consiste à construire un "demi-soustracteur", qui calcule le résultat (A-B), sous la forme du bit de sortie S et de la "retenue de soustraction" C, qui devra éventuellement être soustraite du bit de poids fort suivant. La table de vérité de ce demi-soustracteur est : A B | C S --------- 0 0 | 0 0 0 1 | 1 1 1 0 | 0 1 1 1 | 0 0 d'où : S = XOR (A, B) C = AND (NOT (A), B) On a donc : x_{0} = XOR (a_{0}, 1) = NOT (a_{0}) c_{0} = AND (NOT (a_{0}), 1) = x_{0} = NOT (a_{0}) x_{1} = XOR (a_{1}, c_{0}) = XOR (a_{1}, NOT (a_{0})) c_{1} = AND (NOT (a_{1}), c_{0}) = AND (NOT (a_{1}), NOT (a_{0})) # Que l'on peut simplifier par la loi de De Morgan en : = NOT (OR (a_{1}, a_{0})) x_{2} = XOR (a_{2}, c_{1}) = XOR (a_{2}, NOT (OR (a_{1}, a_{0}))) Notez les égalités (nécessaires !) entre la première et la deuxième formulation : x_{1} = XOR (NOT (a_{1}), a_{0}) x_{1} = XOR (a_{1}, NOT (a_{0})) et : x_{2} = XOR (NOT (a_{2}), OR (a_{1}, a_{0})) x_{2} = XOR (a_{2}, NOT (OR (a_{1}, a_{0}))) Les retenues n'ont en revanche pas le même sens. * Question 1.7 [10 points] On a, ici encore, besoin de trois bascules D, notées Di, avec i = {0, 1, 2}, pour mémoriser l'état du nombre courant entre chaque top d'horloge. On a également besoin de sélectionner, comme entrée des bascules, entre la sortie de l'incrémenteur ou du décrémenteur. On a donc besoin de trois multiplexeurs Mi. Le résultat du multiplexeur doit être filtré avec une porte AND pilotée par l'entrée Z, comme précédemment. On a donc le câblage suivant : INC:A_{i} = Di:Q DEC:A_{i} = Di:Q MUXi:a = INC:X_{i} MUXi:b = DEC:X_{i} MUXi:c = t Di:C = H Di:D = AND (MUXi:s, NOT (z)) * QUESTION 2 [50 points] ============ * Question 2.1 [20 points] rrmovl rA,rB ------------ Fetch : icode:ifun = M1[PC] rA:rB = M1[PC+1] valP = PC + 2 Decode : valA = R[rA] Execute : ValE = 0 + valA Memory : Write back : R[rB] = valE PC update : PC = valP IOPl rA,rB --------- Fetch : icode:ifun = M1[PC] rA:rB = M1[PC+1] valC = M4[PC+2] valP = PC + 6 Decode : valB = R[rB] Execute : valE = valB OP valC CC = SetCC () Memory : Write back : R[rB] = valE PC update : PC = valP ret --- Fetch : icode:ifun = M1[PC] valP = PC + 1 Decode : valA = R[%esp] valB = R[%esp] Execute : valE = valB + 4 Memory : ValM = M4[valA] Write back : R[%esp] = valE PC update : PC = valM * Question 2.2 [20 points] Voir plus bas. * Question 2.3 [10 points] Voir plus bas. Pour la mise à jour de new_pc par JREG, Il est possible soit d'utiliser directement valA, soit, comme pour RRMOVL, de router valA à travers l'ALU (valA + 0) pour donner valE, et d'utiliser valE dans new_pc. * QUESTION 3 [70 points] ============ Il s'agit d'écrire le code y86 correspondant aux fonctions C ci-dessous. ------ int t[10]; Cnp (int n, int p) { if ((p == 0) || (p == n)) return (1); else return (Cnp (n - 1, p) + Cnp (n - 1, p - 1)); } main () { int i; for (i = 0; i <= 9; i ++) t[i] = Cnp (9, i); } ------ * Question 3.1 [20 points] Le passage des paramètres par la pile permet de gérer les fonctions réentrantes. On empile les paramètres dans l'ordre inverse de afin de pouvoir gérer les fonctions à nombre d'arguments variables : ainsi, le premier paramètre a toujours la même place par rapport au sommet de pile, ce qui permet à la fonction appelée de toujours savoir où il se trouve. Les conventions "caller/callee save" fixent qui, de la fonction appelante ou de la fonction appelée, est responsable de la sauvegarde de certains registres : - Fonction appelante ("caller") : EAX, ECX et EDX, registres de travail dont on peut supposer que chaque fonction les modifie, d'autant que EAX (et EDX) servent à transmettre la valeur de retour de la fonction appelée ; - Fonction appelée : EBX, ESI, EDI et EBP. * Question 3.2 [30 points] Il convient en tout premier lieu de positionner la pile, qui servira dans le contexte de ce programme récursif. En ce qui concerne la boucle contenue dans la fonction "main", une solution de facilité consiste à la mettre en oeuvre au moyen de registres "callee save", afin de ne pas avoir à les sauvegarder à chaque appel de la fonction "Cnp". On prendra ici %edi comme pointeur de tableau et %ebx comme registre de borne contenant la valeur 9. .pos 0x100 # Zone de données t: .long 0 # Début de la zone tableau t .pos 0x200 # Zone de pile pile: .long 0 # Pile descendante Concernant le corps de la boucle proprement dit, la solution la plus classique consiste à effectuer l'empilage et le dépilage des paramètres de l'appel à Cnp à chaque tour. Dans la version qui suit, on ne maintient qu'un seul registre compteur, en jouant sur les constantes, et en utilisant comme compteur le registre "callee save" %esi : .pos 0 irmovl pile,%esp # Initialise la pile descendante irmovl t,%edi # %edi = p, pointeur sur le début du tableau t xorl %esi,%esi # %esi = i, compteur de boucle, à 0 irmovl 9,%ebx # %ebx = 9 boucle: subl %ebx,%esi # Test si dépasse 9 jg fin # Fin de boucle si > 9 addl %ebx,%esi # Restaure la valeur de %eax pushl %esi # Empile et sauvegarde le compteur i pushl %ebx # Empile 9 call cnp # Calcule Cnp (9, i) rmmovl %eax,(%edi) # Sauvegarde le retour de Cnp (9, i) dans t[i] iaddl 8,%esp # Dépile les deux paramètres iaddl 4,%edi # p ++ iaddl 1,%esi # i ++ jmp boucle # Reboucle fin: halt Dans le cas présent, comme l'appel est toujours le même à l'exception du deuxième paramètre, on peut empiler les paramètres une seule fois avant de rentrer dans le corps de la boucle. Dans ce cas, le corps de la boucle ne servira qu'à modifier ce deuxième paramètre. Cette astuce n'est possible que si l'on est sûr que la fonction appelée ne modifiera pas les paramètres qui lui sont passés (paramètres déclarés avec le qualificateur "const" en langage C). Comme on peut garantir que c'est le cas ici, on peut s'y risquer. C'est à la fin de la boucle que l'on dépile les paramètres empilés pour l'appel. Dans ce cas précis, ce n'est pas vraiment utile, car on fait le "halt" juste après. C'est néanmoins une bonne chose de le mettre, afin de montrer la nature de l'astuce utilisée, et que l'on a bien pensé à le faire. On peut aussi ne faire le test de sortie qu'à la fin de la boucle, car on sait qu'on fera toujours au moins un tour : .pos 0 irmovl pile,%esp # Initialise la pile descendante irmovl t,%edi # %edi = p, pointeur sur le début du tableau t xorl %eax,%eax # %eax = 0 pushl %eax # Empile i = 0, qui y restera irmovl 9,%ebx # %ebx = 9 pushl %ebx # Empile 9, qui y restera boucle: call cnp # Calcule Cnp (9, i) rmmovl %eax,(%edi) # Sauvegarde le retour de Cnp (9, i) dans t[i] iaddl 4,%edi # p ++ mrmovl 4(%esp),%eax # Récupère i dans la pile iaddl 1,%eax # i ++ rmmovl %eax,4(%esp) # Remet nouveau i dans la pile, au cas où subl %ebx,%eax # Calcule (i - 9) jle boucle # Tant que (i - 9) <= 0, on continue iaddl 8,%esp # Restaure la pile; inutile mais propre halt * Question 3.3 [20 points] cnp: irmovl 1,%eax # Valeur de retour par défaut : 1 mrmovl 8(%esp),%edx # Lecture de p andl %edx,%edx # Positionnement du bit Z je cnpfin # Si (p == 0), termine mrmovl 4(%esp),%ecx # Lecture de n subl %ecx,%edx # Test (p == n), détruit p je cnpfin # Si (p == n), termine mrmovl 8(%esp),%edx # Lecture de p à nouveau pushl %edx # Empile p subl %eax,%ecx # %ecx = (n - 1) pushl %ecx # Empile (n - 1) call cnp # Calcule Cnp (n - 1, p) popl %ecx # Dépile (n - 1) dans %ecx popl %edx # Dépile p dans %edx pushl %eax # Sauvegarde temporairement Cnp (n - 1, p) isubl 1,%edx # %edx = (p - 1) pushl %edx # Empile (p - 1) pushl %ecx # Empile (n - 1) call cnp # Calcule Cnp (n - 1, p - 1) iaddl 8,%esp # Dépile les deux paramètres d'un coup popl %edx # Dépile Cnp (n - 1, p) qui était sauvegardé addl %edx,%eax # Calcule Cnp (n - 1, p) + Cnp (n - 1, p - 1) cnpfin: ret La version ci-dessus est une version optimisée, dans laquelle on jongle avec la pile pour sauvegarder la valeur de retour de "Cnp (n - 1, p)" dans la pile, avant de remettre par dessus les paramètres d'appel de "Cnp (n - 1, p - 1)". Une autre solution consiste à sauvegarder en début de fonction un registre "callee save", tel que %ebx, pour y sauvegarder cette valeur de retour avant le deuxième appel. Cela revient somme toute au même : on a besoin que cette valeur soit stockée quelque part, donc on doit mobiliser la pile de toute façon, que ce soit pour sauvegarder la valeur elle-même ou bien l'ancienne valeur du registre "callee save" qui la contiendra. Notez le double usage de %eax, qui pré-stocke la valeur de retour par défaut, que l'on réutilise pour calculer un "-1" par la suite. On économise des octets par rapport à un "isubl 1,...". Le fait de dépiler, après le premier appel, la valeur "n - 1" déjà calculée, pour la rempiler ensuite, évite de la recalculer. Dans le cas où l'on sauvegarde à l'avance le registre %ebx, on peut aussi ne pas dépiler et rempiler, à l'image de la version optimisée présentée dans la question précédente. Il faut alors juste transformer le second paramètre "p" en "p - 1", avant de faire le second appel à "cnp". --- Ci-dessous : bloc complété --- 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 { OPL, POPL, IRMOVL, *RRMOVL, IOPL, JREG* }; # Does fetched instruction require a constant word? bool need_valC = icode in { IRMOVL, *IOPL* }; ################ Decode Stage ################################### ## What register should be used as the A source? int srcA = [ icode in { OPL, *RRMOVL, JREG* } : rA; icode in { POPL, *RET* } : RESP; 1 : RNONE; # Don't need register ]; ## What register should be used as the B source? int srcB = [ icode in { OPL, *IOPL* } : rB; icode in { POPL, *RET* } : RESP; 1 : RNONE; # Don't need register ]; ## What register should be used as the E destination? int dstE = [ icode in { IRMOVL, OPL, *RRMOVL, IOPL* } : rB; icode in { POPL, *RET* } : RESP; 1 : RNONE; # Don't need register ]; ## What register should be used as the M destination? int dstM = [ icode in { 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, *IOPL* } : valC; icode in { POPL, *RET* } : 4; # Other instructions don't need ALU ]; ## Select input B to ALU int aluB = [ icode in { OPL, POPL, *IOPL*, RET* } : valB; icode in { IRMOVL, *RRMOVL* } : 0; # Other instructions don't need ALU ]; ## Set the ALU function int alufun = [ icode in { OPL, *IOPL* } : ifun; 1 : ALUADD; ]; ## Should the condition codes be updated? bool set_cc = icode in { OPL, *IOPL* }; ################ Memory Stage ################################### ## Set read control signal bool mem_read = icode in { POPL, *RET* }; ## Set write control signal bool mem_write = icode in { }; ## Select memory address int mem_addr = [ icode in { POPL, *RET* } : valA; # Other instructions don't need address ]; ## Select memory input data int mem_data = [ # Default: Don't write anything ]; ################ Program Counter Update ############################ ## What address should instruction be fetched at int new_pc = [ *icode in { RET } : valM;* *icode in { JREG } : valA;* 1 : valP; ];