Organización del Computador
Práctico 4: Circuitos Aritméticos¹

B. Gonzalez Kriegel - N. Wolovick

1. Para cada una de las siguientes representaciones binarias de 5 bits: $(10110,10111)$, $(01011,10101)$,
   $(11110,11101)$ y $(11111,01111)$:
   1. obtenga los 5 bits de la suma $s_{4}s_{3}s_{2}s_{1}s_{0}$ y los acarreos $n$ y $n-1$ $c_{5}$ y $c_{4}$.
   2. Calcule los bits de estado: ``valor a 0'', ``valor negativo'', ``acarreo'' y ``desbordamiento'' $z,n,c,v$.
   3. Interprete los resultados $zncv\ s_{4}s_{3}s_{2}s_{1}s_{0}$ para las funciones de representación $(a_{4}a_{3}a_{2}a_{1}a_{0})_{2}$ y
      $(a_{4}a_{3}a_{2}a_{1}a_{0})_{\ensuremath{\mathit{CPL2}}}$.

2. * El bit de estado $v$ que se utiliza para marcar desbordamiento en la suma $\ensuremath{\mathit{CPL2}}$ y se define como $v = c_{n}\oplus c_{n-1}$, es decir que el overflow ocurre cuando el acarreo de entrada del $\ensuremath{\mathit{MSB}}$ difiere del acarreo de salida.
   1. Dar ejemplos de pares de enteros que en la suma generen las cuatro posibilidades de $c_{n}c_{n-1}$. Verifique la regla de desbordamiento.
   2. Explique porque esta regla siempre funciona.

3. ! Se tiene una computadora que no detecta overflow en hardware. Muestre como detectar desbordamiento de una suma de enteros $\ensuremath{\mathit{CPL2}}$ en software.

4. Efectúe la suma $1011101 + 0111011$ pensando estos números como $\ensuremath{\mathit{CPL1}}$ y como $\ensuremath{\mathit{CPL2}}$.

5. * End Around Carry en suma $\ensuremath{\mathit{CPL1}}$
   1. Demuestre
      
      $$\forall n \exists a_{n-1}\ldots a_{0}, b_{n-1}\ldots b_{0} \c... ...t{CPL1}}} + (b_{n-1}\ldots b_{0})_{\ensuremath{\mathit{CPL1}}}$$
      
      

   2. Explique en términos de la definición
      
      $$(a_{n-1}\ldots a_{0})_{\ensuremath{\mathit{CPL1}}} = -a_{n-1}(2^{n}-1)+\sum_{i=0}^{n-2}a_{i} 2^{i}$$
      
      
      porque la regla End Around Carry soluciona desigualdad.

6. Un Carry Lookahead Adder puro de 4 bits $\ensuremath{\mathit{CLA}}_{4}$ es un sumador que computa más rápidamente que un Ripple Carry Adder de 4 bits $\ensuremath{\mathit{RCA}}_{4}$.
   1. Escriba las expresiones lógicas que definen un sumador completo con entradas $a_{i}$, $b_{i}$ y $c_{i}$ y salidas $s_{i}$, $p_{i}$, $g_{i}$ y $c_{i+1}$. Reescriba $c_{i+1}$ en función de $p_{i}$, $g_{i}$ y $c_{i}$.
   2. A partir de la expresión obtenida en el punto anterior desenrolle las definiciones de $c_{0}$, $c_{1}$ y $c_{2}$ a fin de obtener $\ensuremath{\mathit{SOP}}$s de $p_{i}$s, $g_{i}$s y $c_{i}$s.
   3. Obtenga la expresión para $c_{4}$ continuando con lo hecho en el punto anterior y obtenga $G_{0,2}$ y $P_{0,2}$ de tal forma que $c_{4} = G_{0,2} + P_{0,2}c_{0}$. Interpretar las expresiones $G_{i,j}$ (Group Carry Generate) y $P_{i,j}$ (Group Carry Propagate) de bloque $[i,j]$.

7. Comparación del $\ensuremath{\mathit{RCA}}$ y $\ensuremath{\mathit{CLA}}$ puro.
   1. Compare $\ensuremath{\mathit{RCA}}_{4}$ y $\ensuremath{\mathit{CLA}}_{4}$ puro en función de las medidas $\ensuremath{\mathit{GCount}}$, $\ensuremath{\mathit{Depth}}$ y $\ensuremath{\mathit{fanin}}$ donde sólo podemos construir circuitos con compuertas $\ensuremath{\mathit{AND}}$, $\ensuremath{\mathit{OR}}$ y $\ensuremath{\mathit{NOT}}$².
   2. ! Idem al punto anterior sólo que para $\ensuremath{\mathit{RCA}}_{n}$ y $\ensuremath{\mathit{CLA}}_{n}$ puro. También escriba las 3 funciones en notación ``O grande'' ( $\mathcal{O}(1)$, $\mathcal{O}(log\ n)$, $\mathcal{O}(n)$, etc.).

8. Diseñar a partir de $\ensuremath{\mathit{CLA}}_{4}$ un sumador híbrido $\ensuremath{\mathit{RCA}}$- $\ensuremath{\mathit{CLA}}$ de 16 bits donde se van a utilizar 4 bloques como el que se muestra abajo conectando sus acarreos en cascada. ¿Cuál es la profundidad máxima y mínima del circuito? ¿Sobre que entradas y salidas se producen?
   

9. Un Carry Select Adder ( $\ensuremath{\mathit{CSeA}}$) se basa en el principio de efectuar 2 sumas en paralelo, una suponiendo $c_{in}=0$ y la otra $c_{in}=1$. Cuando el acarreo de entrada se conoce, un multiplexor selecciona la suma apropiada. El siguiente es un diagrama básico para un $\ensuremath{\mathit{CSeA}}$ de 8 bits dividido en 2 grupos de 4 bits, donde cada grupo está siendo operado con $\ensuremath{\mathit{CLA}}_{4}$.
   
   Obtenga las medidas del circuito $\ensuremath{\mathit{GCount}}$, $\ensuremath{\mathit{Depth}}$ y $\ensuremath{\mathit{fanin}}$, y comparelas con un $\ensuremath{\mathit{RCA}}_{8}$ y $\ensuremath{\mathit{CLA}}_{8}$ puro, todas sobre la base $\{\ensuremath{\mathit{AND}}_{n},\ensuremath{\mathit{OR}}_{n},\ensuremath{\mathit{NOT}}\}$.

10. Dado $a = a_{n-1}\ldots a_{0}$, demuestre que $a+a= a<<1$, donde $a_{n-1}\ldots a_{0}<<1=a_{n-2}\ldots a_{0}0$. Esta operación se la conoce como $\ensuremath{\mathit{sll}}$ (shift left logical).

11. Muestre el proceso de la multiplicación serial sin signo entre el multiplicando $1010$ y el multiplicador $0101$. Utilice el esquema propuesto por el libro ``Principles of Computer Architecture''.

12. Muestre el proceso de división serial sin signo entre el dividendo $1010$ y el divisor $0100$. Aquí también siga el esquema propuesto por el libro citado en el punto anterior.

13. Multiplique $010011$ (multiplicando) por $011011$ (multiplicador) utilizando el algoritmo de Booth ( $\ensuremath{\mathit{Booth}}-2$) y el algoritmo de Booth modificado ( $\ensuremath{\mathit{Booth}}-4$).

14. El algoritmo de Booth maneja de manera directa enteros en representación $\ensuremath{\mathit{CPL2}}$. Efectúe la multiplicación $-8 \times -8$ utilizando este método.

15. ! El algoritmo de Booth-4 examina conjuntos de 3 bits superpuestos $a_{i+1}a_{i}a_{i-1}$ con $i\in \{0,2,4,\ldots\}$ y determina el factor que le corresponde a cada par de bits. Explique porque no resulta conveniente extender este sistema a 4 o más bits (Booth-8, Booth-16, etc.).

16. * Para el algoritmo de Booth ordinario (Booth radix-2), el Booth recorded multiplier i-ésimo está dado por $f_{2}(a_{i}, a_{i-1})=a_{i-1} - a_{i}$ (¡Compruébelo!). Encuentre la función $f_{4}(a_{i+1}, a_{i}, a_{i-1})$ para los bit pair recorded multiplier del algoritmo del algoritmo Booth modificado (Booth radix-4).

17. Diseñe una $\ensuremath{\mathit{ALU}}$ de 4 bits con 2 puertos de entrada $A$ y $B$ y una salida $C$ que efectúa las siguientes operaciones según los bits de control $F=f_{1}f_{0}$. La $\ensuremath{\mathit{ALU}}$ no dispone de entradas o salidas adicionales.

    $f_{1}f_{0}$	Función
    00	$\ensuremath{\mathit{NAND}}(A,B)$
    01	$\ensuremath{\mathit{SLL}}(A,1)$
    10	$\ensuremath{\mathit{ADD}}(A,B)$
    11	$\ensuremath{\mathit{SUB}}(A,B)$

18. ! Diseñe una $\ensuremath{\mathit{ALU}}$ genérica de 2 puertos de entrada $A$ y $B$ y uno de salida $C$, todos de $n$ bits, que efectúa las siguientes operaciones según los bits de control $F=f_{1}f_{0}$

    $f_{1}f_{0}$	Función
    00	$\ensuremath{\mathit{AND}}(A,B)$
    01	$\ensuremath{\mathit{NOT}}(A)$
    10	$\ensuremath{\mathit{INC}}(A)$
    11	$\ensuremath{\mathit{ADD}}(A,B)$

    La $\ensuremath{\mathit{ALU}}$ posee además la entrada $c_{in}$ y las salidas $c_{out}zcnv$. Utilice sumadores completos para las operaciones aritméticas, compuertas para las operaciones lógicas y cualquier tipo de bloque constructivo ( $\ensuremath{\mathit{MUX}}$es, $\ensuremath{\mathit{DECODER}}$s, etc.) o conjunto de compuertas para la lógica de selección.

19. Muestre la manera más sencilla de multiplicar por 2 un número $\ensuremath{\mathit{IEEE754}}$ de precisión simple. No considere casos denormalizados o número especiales.

20. ! Escriba en pseudocódigo imperativo algoritmos para comparar y sumar dos números de punto flotante $\ensuremath{\mathit{IEEE754}}$ $f_{1} = m_{1}\cdot 2^{e_{1}}$ y $f_{2} = m_{2}\cdot 2^{e_{2}}$, sin tener en cuenta casos denormalizados ni números especiales (el 0 si se incluye).

21. ! ¿Podría suceder en $\ensuremath{\mathit{IEEE754}}$ que $-x\neq 0-x$?