Université de Bordeaux U.F. Informatique Licence Informatique 2ème année Année 2017 -- 2018 ARCHITECTURE DES ORDINATEURS Devoir Surveillé 1 1 heure 20 minutes sans documents * QUESTION 1 [5 points] ============ * Question 1.1 [1 point] Ceux qui sont négatifs sont ceux dont le bit de poids le plus fort (bit de signe) est à 1, c'est-à-dire dont le premier demi-octet est compris entre 8 et F. Les nombres négatifs sont donc : N = B0B0, P = ABAF et R = 8765, qui répondent à ces critères. * Question 1.2 [1 point] Le plus petit nombre négatif est 8000 (en tant que nombre signé), le plus grand nombre négatif est FFFF, le plus petit nombre positif est 0000, et le plus grand nombre positif est 7FFF. On a donc : 8000 < FFFF < 0000 < 7FFF. On a donc : R = 8765 < P = ABAF < N = B0B0 < Q = 1789 < M = 4732, soit : R < P < N < Q < M. * Question 1.3 [1 point] N = 1011 0000 1011 0000 + Q = 0001 0111 1000 1001 = 0 1100 1000 0011 1001 = C 8 3 9 Il n'y a pas eu débordement ("overflow"), car le résultat n'est pas sorti du domaine représentable en machine. On pourrait avoir débordement en ajoutant deux nombres négatifs (cela pourrait donner un nombre négatif trop petit en valeur signée, qui apparaîtrait comme un nombre positif), ou en ajoutant deux nombres positifs (cela pourrait donner un nombre positif trop grand en valeur signée, qui apparaîtrait comme un nombre négatif). Ici, en ajoutant un nombre positif à un nombre négatif, on ne peut pas déborder. * Question 1.4 [2 points] N = 1011 0000 1011 0000 Le complément à deux de N est : /N = 0100 1111 0100 1111 +1 = 0100 1111 0101 0000 donc : -N = 4 F 5 0 qui est un nombre positif. M-N = M+(-N) M = 0100 0111 0011 0010 +-N = 0100 1111 0101 0000 = 0 1001 0110 1000 0010 = 9 6 8 2 Il y a eu débordement ("overflow") parce que l'ajout de ces deux nombres positifs a conduit à faire apparaître un 1 dans le bit de poids le plus fort, qui signifie un nombre négatif. * QUESTION 2 [6 points] ============ * Question 2.1 [1 point] On prend deux additionneurs ADD à quatre bits, l'un pour le demi-octet de poids faible, que l'on appellera "ADDl", et l'autre pour le demi-octet de poids fort, que l'on appellera "ADDh". On les câble de la façon suivante : 0 -> ADDl:c_{in} # 0 dans la retenue d'entrée c_in de ADDl X_{3..0} -> ADDl:A_{3..0} # 4 bits de poids faible de X dans ADDl Y_{3..0} -> ADDl:B_{3..0} # 4 bits de poids faible de Y dans ADDl ADDl:S_{3..0} -> Z_{3..0} # 4 bits de sortie de ADDl poids faibles de Z ADDl:c_{out} -> ADDh:c_{in} # Chaînage des retenues X_{7..4} -> ADDh:A_{3..0} # 4 bits de poids faible de X dans ADDl Y_{7..4} -> ADDh:B_{3..0} # 4 bits de poids faible de Y dans ADDl ADDh:S_{3..0} -> Z_{7..4} # 4 bits de sortie de ADDh poids forts de Z ADDh:c_{out} -> c_{out} # Retenue de sortie * Question 2.2 [1 point] Les deux résultats diffèrent de : 81_{(16)} - 7B_{(16)} = 06_{(16)}, donc de 6. Cela correspond à la différence de base entre 16 et 10. En base 10, on incrémente le chiffre des dizaines lorsque le chiffre des unités dépasse 9, alors qu'en binaire pur, exprimé en base 16, on incrémente le chiffre des "seizaines" lorsque le chiffre des unités dépasse F. Ici, le chiffre des unités aurait dû être 9 + 2 = B_{(16)}, qui est supérieur à 9, donc on a incrémenté le demi-octet de poids fort de la "seizaine", ce qui a conduit à rajouter 16 en valeur au nombre en binaire pur, tout en enlevant 10 au chiffre hexadécimal des unités, ce qui au final a conduit à rajouter 16 - 10 = 6 au résultat exprimé en nombre binaire pur. * Question 2.3 [1 point] En binaire pur : 62_{(16)} + 17_{(16)} = 79_{(16)}. En BCD : 62_{(16)} + 17_{(16)} = 79_{(16)} aussi. Cette fois, les deux résultats diffèrent de zéro. En effet, comme le chiffre des unités n'a pas dépassé 9, il n'y a pas eu besoin d'incrémenter la "seizaine" et de soustraire 10 au chiffre hexadécimal des unités. * Question 2.4 [1 point] Les valeurs qui doivent conduire à ce que la sortie r du circuit TEST valle 1 sont les valeurs a_{3}a_{2}a_{1}a_{0} égales à : 1010, 1011, 1100, 1101, 1110 et 1111. Dans tous les cas, a_{3}=1 et soit a_{2}=1, soit a_{1}=1, donc : s = AND (a_{3}, OR (a_{2}, a_{1})). * Question 2.5 [1 point] On a besoin d'un multiplexeur, commandé par p, qui choisit entre la valeur A et la valeur (A+6) calculée par un additionneur binaire ADD. La retenue n'existe que dans le cas où p = 1. On a donc le câblage suivant : A_{3..0} -> ADD:A_{3..0} {6 = 0110} -> ADD:B_{3..0} 0 -> ADD:c_{in} A_{3..0} -> MUX:A_{3..0} ADD:S_{3..0} -> MUX:B_{3..0} MUX:X{3..0} -> X_{3..0} AND (p, ADD:c{out}) -> c_{out} * Question 2.6 [1 point] Pour construire un additionneur BCD, il faut ajouter à chaque chiffre hexadécimal la valeur 6 (circuit PLUS) si la somme obtenue pour ledit chiffre est plus grande que 9 (circuit TEST). On a donc besoin d'un additionneur ADD, d'un PLUS et d'un TEST par demi-octet, ce qui donne le câblage suivant : 0 -> ADDl:c_{in} # Retenue d'entrée de poids faible nulle X_{3..0} -> ADDl:A_{3..0} # Demi-octet de poids faible Y_{3..0} -> ADDl:B_{3..0} ADDl:S_{3..0} -> TESTl:A_{3..0} ADDl:S_{3..0} -> PLUSl:A_{3..0} TESTl:r -> PLUSl:p PLUSl:X_{3..0} -> Z_{3..0} PLUSl:c_{out} -> ADDl:c_{in} # Chaînage des retenues X_{7..4} -> ADDl:A_{3..0} # Demi-octet de poids fort Y_{7..4} -> ADDl:B_{3..0} ADDl:S_{3..0} -> TESTl:A_{3..0} ADDl:S_{3..0} -> PLUSl:A_{3..0} TESTl:r -> PLUSl:p PLUSl:X_{3..0} -> Z_{7..4} PLUSl:c_{out} -> c_{out} # Retenue de sortie * QUESTION 3 [9 points] ============ * Question 3.1 [2 points] En prenant les paramètres dans l'ordre inverse de leur empilage, à partir du "call mystere" (adresses 0x006 à 0x01c), on a : - l'adresse de t, qui semble être le début d'un tableau ; - la valeur constante 4, un nombre entier, possiblement la taille du tableau t ? - l'adresse de m, qui semble être une valeur isolée, ou alors le début d'un tableau commençant à l'adresse m et comprenant m et n ? * Question 3.2 [1 point] Cette instruction permet de positionner les valeurs des bits d'état Z, S et C (celui-ci étant toujours égal à 0) en fonction de la valeur du registre %ecx, sans modifier la valeur de celui-ci. Elle est généralement utilisée pour connaître le signe de la valeur contenue dans le registre, ou bien savoir si celle-ci est nulle, ce qui semble être le cas ici, au vu de l'instruction à l'adresse 0x032. * Question 3.3 [1 point] Les registres %ebx, %esi et %edi sont des registres "callee save", c'est-à-dire que c'est à la fonction appelée d'en préserver la valeur si elle souhaite les utiliser. C'est le cas ici. De fait, ces instructions "pushl" servent à sauvegarder la valeur de ces registres dans la pile, ceux-ci étant restaurés par les "popl" situés aux adresses 0x0a1 à 0x0a5. Il faut noter que l'empilage de ces trois registres modifie les déplacements à partir desquels lire les paramètres de la fonction "mystere", vis-à-vis du sommet de pile. * Question 3.4 [4 points] La fonction "mystere" détermine les valeurs minimale et maximale contenues dans un tableau de taille donnée, et place ces deux valeurs à deux adresses consécutives en mémoire. Utilisation des registres : - %ecx : nombre d'éléments du tableau restant à parcourir, initialisé à partir de la valeur entière passée en paramètre ; - %esi : pointeur sur la cellule courante du tableau, initialisé à partir de l'adresse passée en paramètre ; - %edi : pointeur sur les deux valeurs consécutives contenant respectivement le minimum et le maximum déjà trouvés ; - %eax : valeur de la cellule courante du tableau, lue à partir de l'adresse %esi, servant aux calculs de comparaison avec les valeurs minimale et maximale courantes ; - %edx : sauvegarde de la valeur courante %eax ; - %ebx : variable temporaire servant à stocker la valeur minimale puis maximale courantes, pour comparaison avec %eax. Utilisation des étiquettes : - et1 : début du corps de boucle pour chaque cellule du tableau ; - et2 : destination permettant de sauter la modification de la valeur minimale courante ; - et3 : identifie le code situé après la sortie de la boucle, après qu'une valeur au moins a été traitée. Dans ce cas, les registres "callee-save" ont été sauvegardés, et il convient de les restaurer ; - et4 : identifie la sortie anticipée de la fonction, lorsque la taille de tableau passée en paramètre est égale à zéro. Dans ce cas, les registres "callee-save" n'avaient pas été sauvegardés. Note : on aurait pu "économiser" l'utilisation du registre temporaire %edx, de deux manières différentes. Une première façon aurait pu être de recharger directement %eax à partir de la mémoire. On sait cependant qu'en général une lecture à partir de la mémoire est plus coûteuse en temps qu'une copie entre registres, ce qui conduit les programmeurs à préférer un stockage temporaire dans un registre de travail. Une seconde façon, plus subtile, consiste à soustraire %eax à %ebx, et non l'inverse. Dans ce cas, le registre %eax n'aurait pas été modifié, et on n'aurait pas eu besoin de le sauvegarder dans %edx. On aurait alors pu faire jouer à %edx le rôle joué par %ebx, ce qui aurait évité de sauvegarder %ebx dans la pile. Il aurait fallu en tenir compte dans le calcul des déplacements pour accéder aux paramètres de la fonction "mystere". * Question 3.5 [1 point] void mystere (int * t, int s, int * m); * Question 3.6 [1 point] La valeur contenue à l'adresse 0x104 est la valeur maximale contenue dans les 4 cases du tableau débutant à l'adresse t, soit 2.