Scribd Logo
Importer

Bienvenue sur Scribd !

  • 3 vues

    td03-suj

    Transféré par

    Baha Abdslam

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    td03-suj

    Transféré par

    Baha Abdslam
    3 vues2 pages

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    3 vues2 pages

    td03-suj

    Transféré par

    Baha Abdslam

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 2

    ENSIIE – 2e année – 2024-2025 Christophe Mouilleron

    Architecture matérielle [email protected]

    TD 3 : Unité arithmétique et logique


    Exercice 1 - Une histoire de drapeaux

    Dans cet exercice, on considère que les entiers sont codés sur 8 bits avec complément à deux.
    Pour chacune des opérations suivantes, donner :
    — le résultat de l’opération en binaire et en décimal,
    — la valeur des drapeaux S(ign), Z(ero), C(arry) et O(verflow).

    1.1 100 + 52 1.3 (-56) + (-100)


    1.2 52 + (-56) 1.4 (-128) + (-128)

    Exercice 2 - Additionneur carry-select (exam. 2021)

    Le but de cet exercice est de concevoir un additionneur binaire sur n bits efficace.
    Soit k un diviseur de n. On va réaliser l’addition de la manière suivante :
    n
    1. découper les entrées en k paquets de k bits ;
    2. pour chaque poids (sauf le plus faible), faire en parallèle deux additions (séquentielles) sur
    k bits, la première avec une retenue de 0 et la deuxième avec une retenue de 1 ;
    3. pour chaque poids, choisir le résultat final en fonction de la retenue issue de poids précédent.
    Dans la suite, on appellera additionneur carry-select le circuit ainsi obtenu.

    2.1 Dessiner l’additionneur carry-select quand n = 6 et k = 2.


    2.2 Rappeler la profondeur et le nombre de portes logiques pour faire un additionneur séquentiel
    sur k bits.
    2.3 Rappeler la profondeur et le nombre de portes logiques pour faire un multiplexeur 2N → N .
    2.4 Calculer le nombre de portes de l’additionneur carry-select en fonction de n et de k.
    Vérifier que le résultat est bien linéaire par rapport à n.
    2.5 Calculer la profondeur de l’additionneur carry-select en fonction de n et de k.
    2.6 Trouver la valeur de k qui minimise cette profondeur (à n fixé).
    Quelle profondeur obtient-on alors ?

    Exercice 3 - Diviser pour regner (exam. 2019)

    L’additionneur carry-select vu en cours utilise en interne trois additionneurs séquentiels.


    Afin de diminuer la profondeur, on se propose de remplacer ces additionneurs séquentiels par des
    additionneurs carry-select, et ce récursivement jusqu’à arriver une taille 1. L’addition de taille 1
    est alors effectuée à l’aide d’un full-adder.
    Dans la suite, on notera t(n) la profondeur du circuit ainsi obtenu pour faire une addition sur n
    bits, et a(n) le nombre de portes logiques nécessaires à la réalisation de ce circuit.

    3.1 Dessiner le circuit correspondant lorsque n = 2, puis lorsque n = 4.


    3.2 Donner les valeurs de t(1) et a(1).
    3.3 Justifier les équations suivantes : t(n) = t(n/2) + 3,
    a(n) = 3 a(n/2) + 2 n + 4.
    3.4 Exprimer t(n) et a(n) en fonction de n uniquement. Commenter.

    1
    ENSIIE – 2e année – 2024-2025 Christophe Mouilleron
    Architecture matérielle [email protected]

    Exercice 4 - Additionneur de Brent et Kung (exam. 2023)

    L’additionneur de Brent et Kung est un circuit permettant de faire une addition d’entiers
    non signés sur n bits. Il repose sur le principe de retenues anticipées vu en cours. On rappelle
    que le but est de calculer efficacement, à chaque position i, le bit Ci correspondant à la retenue
    entrante à cette position.
    Pour ce faire, on utilise les valeurs suivantes :
    — Pi = Ai ⊕ Bi , indiquant qu’une retenue sera propagée à la position i ;
    — Gi = Ai · Bi , indiquant qu’une retenue sera générée à la position i
    où Ai et Bi désignent les bits des deux opérandes de l’addition à la position i.
    L’idée de Brent et Kung est de généraliser ces valeurs en introduisant pour i ≤ j :
    — Pi,j = Pi Pi+1 . . . Pj ,
    — Gi,j = Gj + Gj−1 Pj,j + · · · + Gi Pi+1,j .
    On remarque en particulier que, lorsque i = j, on a bien Pi,i = Pi et Gi,i = Gi .
    4.1 Rappeler la formule liant Ci , Ci+1 , Gi et Pi vue en cours.
    4.2 En vous inspirant de la formule précédente, donnez une formule pour calculer Cj à partir
    de C0 , G0,j−1 et P0,j−1 .
    Expliquez pourquoi votre formule est correcte.
    4.3 Proposez un circuit pour calculer efficacement P0,2ℓ −1 à partir des valeurs P0 , P1 , . . ., P2ℓ −1 .
    Précisez, en fonction de ℓ, la profondeur et le nombre de portes logiques de votre circuit.
    4.4 Afin de calculer Gi,j efficacement, on introduit l’opérateur • défini par
    (x1 , y1 ) • (x2 , y2 ) = (x1 x2 , y1 x2 + y2 ).
    Un calcul rapide montre que • est associatif, donc que (a • b) • c = a • (b • c) pour tout a, b et c.
    Montrer que, si i ≤ j < k, on a (Pi,k , Gi,k ) = (Pi,j , Gi,j ) • (Pj+1,k , Gj+1,k ).
    4.5 Expliquez comment on peut obtenir P0,2ℓ −1 et G0,2ℓ −1 efficacement en utilisant la formule
    de la question précédente.
    Illustrez votre méthode en dessinant le circuit correspondant pour ℓ = 3.
    note : On considère ici que les entrées sont P0 , G0 , P1 , G1 , . . ., P2ℓ −1 , G2ℓ −1 . Et on utilisera
    une boîte • en guise de circuit pour l’opérateur •.
    4.6 On note T (ℓ) la profondeur du circuit permettant de calculer P0,2ℓ −1 et G0,2ℓ −1 .
    (
    T (0) = 0
    Justifiez que , puis exprimez T (ℓ) en fonction de ℓ uniquement.
    T (ℓ) = T (ℓ − 1) + 2 si ℓ > 0
    4.7 On note maintenant A(ℓ) le nombre de portes logiques de ce circuit.
    (
    A(0) = 0
    Justifiez que , puis exprimez A(ℓ) en fonction de ℓ uniquement.
    A(ℓ) = 2 A(ℓ − 1) + 3 si ℓ > 0
    4.8 [⋆] Expliquez comment étendre le circuit précédent pour calculer toutes les valeurs de la
    forme P0,j et G0,j , où 0 ≤ j < n.
    Illustrez votre méthode dans le cas où n = 2ℓ = 8.
    indication : On pourra s’appuyer sur l’écriture binaire de j + 1.
    4.9 Utilisez ce qui précède pour évaluer (en ordre de grandeur par rapport à n) la profondeur
    et le nombre de portes logiques pour l’additionneur de Brent et Kung.
    Comparez à ce qui a été vu en cours/TD et commentez.

    Vous aimerez peut-être aussi