Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

- 1 - Examen d’Architecture des Ordinateurs Majeure 1 – Polytechnique Lundi 10

- 1 - Examen d’Architecture des Ordinateurs Majeure 1 – Polytechnique Lundi 10 Décembre 2001 • L’examen dure 3 heures. • Le sujet comporte 7 pages dont 3 pages de rappels sur le LC-2 et la microprogrammation. • Tous documents autorisés. • Le barème est donné à titre indicatif, il sert surtout à évaluer le poids respectif des sections ; tel quel, l’examen est noté sur 40. • L’examen contient un problème et un exercice. Dans le problème, les questions 1 et 2 peuvent être traitées indépendamment, mais il est recommandé de bien comprendre le fonctionnement des instructions PUSH et POP avant d’aborder la question 2. • Il est impératif de commenter les programmes en assembleur et les microprogrammes ; normalement, presque chaque instruction ou microinstruction doit être suivie d’un commentaire. • Les corrections sont dans les cadres en dessous des questions. Problème. Pile et LC-2 (30 points) On considère le processeur LC-2 vu en cours et en TD ; la structure du LC-2 et le jeu d’instructions sont rappelés en Annexe. Dans ce processeur on veut rajouter des instructions destinées à faciliter l’utilisation d’une pile, que l’on utilisera pour le stockage de données temporaires quelconques (destinées au calcul, aux appels de procédures,...). Dans une telle pile, on ne peut accéder qu’au dernier élément (ici, on visualisera une pile dont le dernier élément est situé au bas de la pile). On dispose de deux nouvelles instructions pour utiliser cette pile : PUSH Rs et POP Rd : • l’effet de PUSH Rs est d’ajouter le contenu du registre Rs au bas de la pile ; le registre Rs n’est pas modifié. • l’effet de POP Rd est de placer la donnée située dans le dernier élément de la pile dans le registre Rd et d’enlever cette donnée de la pile. Le format et l’opcode des instructions PUSH et POP sont indiqués ci-dessous : Bit 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 PUSH 1011 Rs1 1 0 1 1 0 0 0 0 1 POP 1010 Rd 1 0 1 1 1 1 1 1 1 Voici un exemple de fonctionnement d’une pile à 4 éléments de 16 bits chacun (les valeurs sont données en hexadécimal): 0000 0000 0000 0000 0000 0000 0000 0A2F 0000 0000 0A2F 19C3 0000 0000 0000 0A2F Etat initial Etat après PUSH R1 (R1 contient 0A2F) Etat après PUSH R2 (R2 contient 19C3) Etat après POP R3 (R3 contient alors 19C3) Dans l’exemple ci-dessus, on déplace les données dans la pile afin de donner l’intuition du fonctionnement de la pile ; en pratique et selon les implémentations de la pile, les données sont fixes (les données sont stockées en mémoire) ou se déplacent effectivement (il existe un composant matériel sur le processeur représentant la pile); ce point est sans importance pour la question 1, il sera abordé en détail à la question 2. On suppose maintenant que le LC-2 dispose des instructions PUSH et POP et d’une implémentation de la pile. Dans la section 1 on utilise cette pile pour la programmation en assembleur, et dans la question 2 on étudie les modifications à apporter à l’architecture pour implémenter la pile. 1. Utilisation de la pile (15 points) Dans cette section, on ne se préoccupe pas de la taille de la pile que l’on suppose suffisamment grande pour tous les programmes ci-dessous. Comme la pile sert de zone de stockage, elle permet souvent de réduire le nombre de registres nécessaires dans une architecture ; dans certaines architectures, il peut n’y avoir pratiquement aucun - 2 - registre, on n’utilise alors que la pile ; c’est pourquoi, dans plusieurs questions, on restreint volontairement le nombre de registres dont on peut disposer. Dans toutes les questions, on suppose qu’initialement tous les éléments de la pile contiennent la valeur hexadécimale 0000. De manière générale, on privilégie ici la compacité (et la lisibilité) du programme sur le temps d’exécution : on préfère un programme comportant peu d’instructions à un programme plus rapide mais comportant plus d’instructions. 1.1 En utilisant un seul registre (le registre R0), les instructions de gestion de la pile décrites ci-dessus et les instructions arithmétiques et logiques du LC-2, modifier la pile pour que ses 4 derniers éléments aient les valeurs décimales suivantes : .... 28 56 8 -9 On veillera à minimiser le nombre d’instructions nécessaires au remplissage de la pile. AND R0, R0, #0 ; R0=0 ADD R0, R0, #15 ; R0=15 ADD R0, R0, #13 ; R0=28 PUSH R0 ADD R0, R0, R0 ; R0=56 PUSH R0 AND R0, R0, #15 ; R0=8 PUSH R0 NOT R0, R0 ; R0=-9 PUSH R0 1.2 On veut écrire un programme qui effectue la division entière de b par a, a et b étant deux nombres représentés sur 16 bits et tels que 0 < a, b < 215. On suppose que a et b sont respectivement stockés dans les registres R0 et R1. 1.2.1 Proposer un algorithme, et le présenter sous forme d’organigramme. Il existe un algorithme symétrique à celui vu en cours pour la multiplication, mais on conseille ici d’utiliser un algorithme plus élémentaire, dont le temps d’exécution peut éventuellement être plus long. Ecrire le programme assembleur LC-2 correspondant. En fin de programme, le quotient sera stocké dans R0 et le reste dans R1. On implémente l’algorithme de division en comptant combien de fois on peut soustraire a à b. quotient = 0 BOUCLE reste < diviseur ? OUI FIN NON reste = reste – diviseur quotient++ aller à BOUCLE .ORIG x3000 AND R2, R2, #0 ; quotient=0 BOUCLE NOT R3, R0 ; R3=-diviseur ADD R3, R3, #1 ; ADD R3, R1, R3 ; R3=reste-diviseur BRn FIN ADD R1, R3, #0 ; reste=reste-diviseur ADD R2, R2, #1 ; quotient++ JMP BOUCLE FIN ADD R0, R2, #0 ; R0=quotient .END 1.2.2 Ecrire une nouvelle version de ce programme en n’utilisant que les registres R0, R1, R2 et R3 (on n’utilise ni la mémoire, ni la pile). - 3 - Cette question concerne les programmes du 1.2.1 comportant plus de 4 registres. 1.2.3 Ecrire à nouveau le programme en n’utilisant que les registres R0, R1, R2 et la pile. En fin de programme, le quotient sera dans R0 et le reste dans R1. Une solution : .ORIG x3000 AND R2, R2, #0 ; quotient=0 PUSH R2 ; quotient sauvegardé sur la pile BOUCLE NOT R2, R0 ; R2=diviseur ADD R2, R2, #1 ; ADD R2, R1, R2 ; R2=reste-diviseur BRn FIN ADD R1, R2, #0 ; reste=reste-diviseur POP R2 ; Récupération du quotient ADD R2, R2, #1 ; quotient++ PUSH R2 ; Sauvegarde du quotient JMP BOUCLE FIN POP R0 ; R0=quotient .END 1.3 On a vu en cours que les appels de procédure, une fois codés en assembleur LC-2, utilisent une pile de contextes. Dans le LC-2, on gère normalement les contextes à l’aide d’instructions mémoire (LD, ST, LDR, STR). On veut maintenant utiliser les instructions PUSH et POP pour gérer les contextes. On suppose ici que l’on n’a pas de variables locales. Dans cette question, les seules zones de stockage dont l’on dispose sont les registres et la pile, on n’utilise pas les instructions mémoire du LC-2. 1.3.1 Par rapport au contexte décrit en cours, quelle information est-il maintenant inutile de garder dans le contexte s’il est géré à l’aide des instructions PUSH et POP ? Expliquer brièvement pourquoi. En l’absence d’instructions de gestion de la pile, la position en mémoire des contextes du LC-2 est indiquée par un pointeur stocké dans R6. Ce pointeur indique le début du contexte courant. Avec PUSH et POP, il n’est plus nécessaire d’indiquer explicitement la position en mémoire du contexte, le dernier élément de la pile va correspondre au dernier élément du contexte courant, c’est un pointeur implicite sur le contexte courant. 1.3.2 Si l’on ne dispose que des instructions PUSH et POP, peut-on utiliser la pile pour le passage de paramètres à la procédure appelée ? Expliquer brièvement pourquoi. Même question pour le passage du résultat à la procédure appelante. • Passage de paramètres : supposons que l’on place un paramètre sur la pile à l’aide d’un PUSH dans la procédure appelante ; en début de procédure appelée, on doit sauver les registres utilisés sur la pile (ils font partie du contexte de la procédure appelée) avant toute opération sur les registres ; on ne pourra donc accéder aux paramètres qui se situeront, dans la pile, au-dessus des registres sauvés. Si la procédure appelée ne modifie aucun registre, le passage de paramètres est possible. Cependant, si la sauvegarde des registres est effectuée dans la procédure appelante, il est possible d’utiliser la pile pour passer les paramètres • Passage de résultat : le raisonnement est similaire ; en fin de procédure appelée, on doit restaurer les registres modifiés avec l’instruction POP avant de retourner à la procédure appelante ; le résultat étant nécessairement dans un registre modifié, la restauration va écraser ce résultat ; inversement, si l’on sauve le uploads/s1/ corrige-01-02.pdf