Université de Bordeaux                     Collège Sciences et Technologies

ANNÉE UNIVERSITAIRE 2024 -- 2025
SESSION 1 DE PRINTEMPS

Parcours / Étape : LSTS / L2
Code UE : 4TIN408U
Épreuve : Architecture des ordinateurs


# EXERCICE 1 [20 points]

## Question 1.1 [5 points]

L'équation logique du multiplexeur à 1 bit est la suivante :

    S = A * (/C) + B * C

Le câblage de ce circuit s'effectue de la façon suivante :

    S = OR (AND (A, NOT (C)), AND (B, C))

On appelle ce circuit « MUX1 ».

## Question 1.2 [5 points]

Pour obtenir un multiplexeur sur 4 bits, il suffit de mettre en
parallèle ce circuit pour chacun des bits des valeurs d'entrée :

    i = {0..3}
    S_{i} = MUX1 (A_{i}, B_{i}, C)

On appelle ce circuit « MUX4 ».

## Question 1.3 [10 points]

Pour obtenir un multiplexeur à 4 entrées de 4 bits, il suffit de
combiner ensemble deux multiplexeurs « MUX4 » à deux entrées sur 4 bits,
commandés par C_{0}, avec un troisième multiplexeur « MUX4 » commandé
par C_{1} :

    S = MUX4 (MUX4 (E_{00}, E_{01}, C_{0}), MUX4 (E_{10}, E_{11}, C_{0}), C_{1})


# EXERCICE 2 [80 points]

## Question 2.1 [20 points]

Le tableau demandé à la forme suivante :

    ---------------------------------------
    | N | Nbin |     a     |   b  | a - b |
    ---------------------------------------
    | 0 | 0000 | 0000 0011 | 0011 |  0000 |
    | 1 | 0001 | 0000 0100 | 0100 |  0000 |
    | 2 | 0010 | 0000 0101 | 0101 |  0000 |
    | 3 | 0011 | 0000 0110 | 0110 |  0000 |
    | 4 | 0100 | 0000 0111 | 0111 |  0000 |
    | 5 | 0101 | 0000 1000 | 1000 |  0000 |
    | 6 | 0110 | 0000 1001 | 1001 |  0000 |
    | 7 | 0111 | 0001 0000 | 1010 |  0110 |
    | 8 | 1001 | 0001 0001 | 1011 |  0110 |
    | 9 | 1001 | 0001 0010 | 1100 |  0110 |
    ---------------------------------------

## Question 2.2 [20 points]

Le codage BCD et le codage binaire pur diffèrent lorsque le codage BCD
possède une retenue, c'est-à-dire pour les valeurs de résultat
supérieures ou égales à 10_{(10)}. Dans ce cas, on a un « 1 » dans la
colonne des dizaines BCD, qui correspond à la valeur 16_{(10)} en
binaire pur, et on a soustrait 10_{(10)} de la colonne des unités
BCD. La différence binaire pure entre les deux représentations, dans
ce cas, est de 16_{(10)} - 10_{(10)} = 6_{(10)}. Cette valeur
correspond à la différence de retenue entre les bases 16 et 10.
En base 10, on incrémente le chiffre des dizaines lorsque le chiffre
des unités dépasse 9_{(10)}, 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_{(16)}.

## Question 2.3 [20 points]

De par la question précédente, on sait que l'on a une erreur de calcul
BCD lorsque le résultat _s_ de l'additionneur « FA » en binaire pur est
supérieur ou égal à 10_{(10)}, c'est-à-dire pour les configurations
suivantes :

    1010
    1011
    1100
    1101
    1110
    1111

Il faut aussi prendre en compte le cas où l'additionneur binaire pur
produit une retenue. Par exemple, 1001_{(2)} + 1001_{(2)} =
1 0010_{(2)}, qui ne rentre pas dans le cas précédent.

Une valeur binaire sur 4 bits est supérieure ou égale à 10_{(10)}
lorsque son bit de poids le plus fort s_{3} est à 1 (cela fait
8_{(10)}), plus soit s_{2} (cela fait 4_{(10)} de plus) soit s_{1}
(cela fait 2_{(10)} de plus). On peut donc écrire :

    e = s_{3} * (s_{2} + s_{1}) + c_{out}

Le câblage de ce circuit s'effectue de la façon suivante :

    e = OR (AND (s_{3}, OR (s_{2}, s_{1})), c_{out})

On appelle ce circuit « E ».

## Question 2.4 [20 points]

Pour que le résultat de la tranche d'additionneur BCD soit correct, il
faut propager une retenue et soustraire 10_{(10)} dès le moment où le
résultat de l'additionneur binaire pur est supérieur ou égal à
10_{(10)}. Plutôt que de soustraire 10_{(10)}, on peut juste
additionner 6_{(10)}, puisque 6_{(10)} est le complément à deux de
10_{(10)} sur 4 bits. C'est ce que l'on voit dans le tableau de la
première question, où _a_ = _b_ + 6_{(10)} dès le moment où
_b_ >= 10_{(10)}.

Pour câbler la tranche d'additionneur BCD, on va d'abord additionner
_x_ et _y_ en binaire pur au moyen d'un additionneur complet « FA1 »,
incluant la retenue d'entrée c_{in} de la tranche, ce qui donnera une
valeur intermédiaire _t_. Si cette valeur est strictement inférieure à
10_{(10)}, alors on ne lui ajoute rien, et il n'y a pas de retenue de
sortie. Sinon, on lui ajoute 6_{(10)} au moyen d'un deuxième
additionneur « FA2 », et il y a une retenue de sortie.

On pourrait imaginer un système de multiplexeur, piloté par _e_, pour
savoir si on prend le résultat de FA2 ou bien de FA1. On peut faire
plus simple, en utilisant le résultat de FA2 dans tous les cas, et en
l'alimentant soit avec la valeur 6_{(10)}, soit 0_{(10)}. On pourrait
ici aussi utiliser un multiplexeur pour choisir entre les deux
valeurs, mais on peut être plus rusé en considérant que comme 6_{(10)}
se code 0110_{(2)} (si _e_ = 1), et 0_{(10)} se code 0000_{(2)} (si
_e_ = 0), alors la valeur à ajouter se code en fait 0 e e 0_{(2)}
(quelle que soit la valeur de _e_).

Le câblage de ce circuit s'effectue alors de la façon suivante :

    t = FA1:s (x, y, C_{in})  # Calcul de la somme binaire pure
    e = E (t)                 # Calcul si ajustement BCD à faire
    s = FA2:s (t, 0 e e 0, 0) # Ajout de 0 ou 6 selon la valeur de e
    c_{out} = e               # Retenue de sortie de la tranche


# EXERCICE 3 [100 points]

## Question 3.1 [20 points]

« call valC » effectue un appel de fonction à l'adresse de destination
donnée par _valC_. Pour cela, elle stocke dans la pile l'adresse à
laquelle retourner à la fin de la fonction appelée, c'est-à-dire
l'adresse de l'instruction suivant immédiatement l'instruction
« call », et modifie le compteur ordinal afin que la prochaine
instruction effectivement exécutée soit l'instruction située à
l'adresse _valC_. Elle se décompose de la façon suivante :

- Étage « _Fetch_ » : outre l'octet d'_opcode_ de l'instruction, on
  lit les quatre octets de l'adresse de destination _valC_, puis on
  calcule l'adresse de la prochaine instruction, à PC + 5 puisque
  l'instruction CALL fait cinq octets.

- Étage « _Decode_ » : on lit la valeur courante du registre pointeur
  de pile _esp_ depuis la banque de registres, afin de calculer la
  nouvelle adresse du sommet de pile (sur le canal B).

- Étage « _Execute_ » : on calcule dans valE la valeur de l'adresse du
  nouveau sommet de pile, à laquelle sera écrite l'adresse de
  retour. Pour cela, on injecte la valeur constante -4 sur le canal A
  de l'unité arithmétique et logique.

- Étage « _Memory_ » : on écrit à l'adresse du nouveau sommet de pile,
  _valE_, la valeur _valP_ de l'adresse de l'instruction suivant le
  « call ».

- Étage « _Write back_ » : la valeur _valE_ de l'adresse du nouveau
  sommet de pile est réécrite dans le registre _esp_ au sein de la
  banque de registres.

- Étage « _PC update_ » : le compteur ordinal est mis à jour avec
  l'adresse de destination de l'appel, _valC_, afin que la prochaine
  instruction effectivement exécutée soit la première instruction de
  la fonction appelée.

## Question 3.2 [20 points]

L'instruction « ret », sur un octet, sert à retourner d'une
fonction. Elle lit l'adresse de retour depuis le sommet courant de la
pile, incrémente ce dernier de 4 octets et le met à jour dans la
banque de registres, puis effectue un branchement à l'adresse lue
depuis la mémoire de la pile.

En regardant, dans le code HCL, toutes les occurrences de RET servant
à contrôler le chemin de données, on arrive au tableau suivant :

    -------------------------------------
    | Fetch      | icode:ifun = M_1[PC] |
    |            | valP = PC + 1        |
    -------------------------------------
    | Decode     | valA = R[esp]        |
    |            | valB = R[esp]        |
    -------------------------------------
    | Execute    | valE = valB + 4      |
    -------------------------------------
    | Memory     | valM = M_4[valA]     |
    -------------------------------------
    | Write back | R[esp] = valE        |
    -------------------------------------
    | PC update  | PC = valM            |
    -------------------------------------

## Question 3.3 [20 points]

L'instruction « creg rA » est sur deux octets : un premier pour
l'_opcode_, et un second pour stocker le numéro de registre _rA_.
De façon analogue à l'instruction « call », il faudra effectuer le
stockage dans la pile de l'adresse de retour _valP_. Cependant,
l'adresse de destination du branchement ne sera pas une valeur
immédiate, mais devra être lue à partir de la banque de registres,
à partir de son canal A. On adapte donc le tableau de l'instruction
« call valC » de la façon suivante :

    -------------------------------------
    | Fetch      | icode:ifun = M_1[PC] |
    |            | rA:rB = M_1[PC + 1]  |
    |            | valP = PC + 2        |
    -------------------------------------
    | Decode     | valA = R[rA]         |
    |            | valB = R[esp]        |
    -------------------------------------
    | Execute    | valE = valB + (-4)   |
    -------------------------------------
    | Memory     | M_4[valE] = valP     |
    -------------------------------------
    | Write back | R[esp] = valE        |
    -------------------------------------
    | PC update  | PC = valA            |
    -------------------------------------

## Question 3.4 [20 points]

Dans le cas où l'_opcode_ de CREG est distinct de celui de CALL, on
ajoute les instructions relatives à CREG sans modifier aucunement
celles relatives à CALL. La mise à jour du code HCL découle du tableau
de la question précédente :

    ################ Fetch Stage     ###################################
    
    # Does fetched instruction require a regid byte?
    bool need_regids =
            icode in { RRMOVL, OPL, PUSHL, POPL, IRMOVL, RMMOVL, MRMOVL, CREG };
    
    # Does fetched instruction require a constant word?
    bool need_valC =
            icode in { IRMOVL, RMMOVL, MRMOVL, JXX, CALL };
    
    # List of all valid instructions
    bool instr_valid =
            icode in { NOP, HALT, RRMOVL, IRMOVL, RMMOVL, MRMOVL,
                       OPL, JXX, CALL, RET, PUSHL, POPL, CREG };
    
    ################ Decode Stage    ###################################
    
    ## What register should be used as the A source?
    int srcA = [
            icode in { RRMOVL, RMMOVL, OPL, PUSHL, CREG } : 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 { RMMOVL, MRMOVL, OPL } : rB;
            icode in { PUSHL, POPL, CALL, RET, CREG } : RESP;
            1 : RNONE;  # Don't need register
    ];
    
    ## What register should be used as the E destination?
    int dstE = [
            icode in { RRMOVL, IRMOVL, OPL } : rB;
            icode in { PUSHL, POPL, CALL, RET, CREG } : 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 { RRMOVL, OPL } : valA;
            icode in { IRMOVL, RMMOVL, MRMOVL } : valC;
            icode in { CALL, PUSHL, CREG } : -4;
            icode in { RET, POPL } : 4;
            # Other instructions don't need ALU
    ];
    
    ## Select input B to ALU
    int aluB = [
            icode in { RMMOVL, MRMOVL, OPL, CALL, PUSHL, RET, POPL, CREG } : 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 { MRMOVL, POPL, RET };
    
    ## Set write control signal
    bool mem_write = icode in { RMMOVL, PUSHL, CALL, CREG };
    
    ## Select memory address
    int mem_addr = [
            icode in { RMMOVL, MRMOVL, PUSHL, CALL, CREG } : valE;
            icode in { POPL, RET } : valA;
            # Other instructions don't need address
    ];
    
    ## Select memory input data
    int mem_data = [
            icode in { RMMOVL, PUSHL } : valA;
            icode in { CALL, CREG } : valP;
            # Default: Don't write anything
    ];
    
    ################ Program Counter Update ############################
    
    ## What address should instruction be fetched at
    int new_pc = [
            icode == CALL : valC;
            icode == CREG : valA;
            icode == JXX && Bch : valC;
            icode == RET : valM;
            1 : valP;
    ];

## Question 3.5 [20 points]

Dans le cas où l'_opcode_ de CREG est celui de CALL, mais avec un
_ifun_ égal à 1, on peut factoriser tous les cas où, dans la question
précédente, on avait CALL et CREG sur la même ligne. Le symbole « ⊗ »
indique la factorisation. En revanche, il faut spécialiser les lignes
où seulement l'un des deux apparaissait.  On a donc le code suivant :

################ Fetch Stage     ###################################
    
    # Does fetched instruction require a regid byte?
    bool need_regids =
            icode in { RRMOVL, OPL, PUSHL, POPL, IRMOVL, RMMOVL, MRMOVL } ||
            ((icode == CALL) && (ifun == 1));
    
    # Does fetched instruction require a constant word?
    bool need_valC =
            icode in { IRMOVL, RMMOVL, MRMOVL, JXX } ||
            ((icode == CALL) && (ifun == 0));
    
    # 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 { RRMOVL, RMMOVL, OPL, PUSHL } ||
            ((icode == CALL) && (ifun == 1)) : 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 { RMMOVL, MRMOVL, OPL } : rB;
            icode in { PUSHL, POPL, CALL, RET } : RESP; ⊗
            1 : RNONE;  # Don't need register
    ];
    
    ## What register should be used as the E destination?
    int dstE = [
            icode in { RRMOVL, IRMOVL, OPL } : rB;
            icode in { PUSHL, POPL, CALL, RET } : 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 { RRMOVL, OPL } : valA;
            icode in { IRMOVL, RMMOVL, MRMOVL } : valC;
            icode in { CALL, PUSHL } : -4; ⊗
            icode in { RET, POPL } : 4;
            # Other instructions don't need ALU
    ];
    
    ## Select input B to ALU
    int aluB = [
            icode in { RMMOVL, MRMOVL, OPL, CALL, PUSHL, RET, POPL } : 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 { MRMOVL, POPL, RET };
    
    ## Set write control signal
    bool mem_write = icode in { RMMOVL, PUSHL, CALL }; ⊗
    
    ## Select memory address
    int mem_addr = [
            icode in { RMMOVL, MRMOVL, PUSHL, CALL } : valE; ⊗
            icode in { POPL, RET } : valA;
            # Other instructions don't need address
    ];
    
    ## Select memory input data
    int mem_data = [
            icode in { RMMOVL, PUSHL } : valA;
            (icode == CALL) : valP; ⊗
            # Default: Don't write anything
    ];
    
    ################ Program Counter Update ############################
    
    ## What address should instruction be fetched at
    int new_pc = [
            ((icode == CALL) && (ifun == 0)) : valC;
            ((icode == CALL) && (ifun == 1)) : valA;
            icode == JXX && Bch : valC;
            icode == RET : valM;
            1 : valP;
    ];
