Estructura de una ALU de enteros.

(55 páginas)

1. Introducción

La ALU es definida por las siguientes características:

• Operaciones de enteros: Trabaja principalmente para funciones enteras, principalmente sumas y restas. Las opraciones en punto flotante van en una unidad aparte.
• Aritmética finita: Su aritmética es finita. (ej, sumar 2 números de n bits como mucho el resultado será n+1. En el caso de una multiplicación es 2n)

1.1 Representación numérica

• Maxiam precisión de los enteros: la unidad
• Rango:
  • Binario puro [0, 2ⁿ⁻¹]
  • Signo-magnitud [-(2ⁿ⁻¹-1), 2^ⁿ⁻¹-1] el primer bit indica el signo y el resto el número. Hay 2 ceros. Problema: Hay varias codificaciones para el 0/1, pueden significar el numero o pueden significar el signo.
  • Compelmento a 1 [-(2ⁿ⁻¹-1), 2^ⁿ⁻¹-1] los negativos es la inversión de bits del positivo. Hay dos ceros y sigue arrastrando el problema de signo-magnitud.
  • Complemento a 2 [-(2ⁿ⁻¹), 2^ⁿ⁻¹-1] cpl1+1. Problema: No es simétrico

1.1. Representación numérica

Entonces si
1001 en binario puero es 9
1001 en signo-magnitud es -1
1001 en cpl1 es -6
1001 en cpl2 es -7
¿Qué número es 1001?

Depende de la codificción

2. Flags

• zero: Se pone a 1 si el resultado fue 0
• carry: Es el bit que no cabe en una suma de enteros sin signo
• overflow: Lo mismo que el carry pero sirve para numeros con signo (cuando no coinciden los signos de los operandos con el bit de signo que sale)
• parity: Se pone a 1 si hay el mismo número de 1s que de 0s
• sign: Se pone a 1 si es negativo

3. Operaciones básicas

• Circuito combinacional
  • Tiene una salida y que depende de una entrada x
  • No tiene memoria y mantiene la salida mientras se mantengan las entradas
  • Tiene un retardo que es el tiempo de propagación
• Circuito secuencial
  • Tiene estados (fases/etapas)
  • Son controlados por un reloj y requieren de elementos de memoria que guarden el estado.

3.1. Elementos básicos

• Semisumador (Half-Adder)

input  a,b
output s,cout

xor(a,b; s)
and(a,b; cout)

No sirve para hacer operaciones de más de un bit porque no dispone de un cin.

• Sumadores (Full adder)

input  a,b,cin
output s,cout
middle w1,w2,w3
middle s1,co1,s2,co2

--- Con puertas básicas ---
xor(a,b; w1)
and(a,b; w2)
and(w1,cin; w3)

xor(w1,cin; s)
or(w2,w3; cout)

--- Con modulos ---
ha1(a,b; s1,co1)
ha2(cin,s1; s,co2)
or(co1,co2; cout)

Se resume en: Hay acarreo si

  (a&b) = 1
  (a|b) = 1 & cin = 1

3.2. RCA (4 bits)

El camino crítico es el peor tiempo posible. El camino más largo, el amino por el que más puertas hay que pasar. por ejemplo, en el full-adder el camino crítico sería de 3 puertas. En el caso del RCA sería 9 puertas: Las 3 primeras para llegar al cout, y a partir de ahi en el siguiente fa, son dos hasta el ultimo.

3.3. CSA

Siempre tiene 3 entradas.

¿Da un CSA directamente el resultado de la suma? ¿Cómo conseguiríamos el resultado definitivo?

No da directamente el resultado de la suma, habría que conectar a sus salidas un RCA.

¿Merece esto la pena?

3.3. CPA

A cada FA se le añade dos señales adicionales

  (propagación) pᵢ = aᵢ | bᵢ # si potencialmente puedo tener acarreo
  (generacion) gᵢ = aᵢ & bᵢ
  (acarreo) cᵢ₊₁ = gᵢ | (pᵢ & Cᵢ)

Su camino crítico es de dos niveles.

4. Multiplicación combinacional

    1010|
 x  1101|
    ————
    1010|
   0000 |
  1010  |
 1010   |
 ———————| 
10000010|

(falta pic)

Su camino critico es. Se puede mejorar poniendo en paralelo el circuito. (Árbol de Wallace)

4.1. Sin signo

4.1.1. Árbol de Wallace

(falta pic)

5. Multiplicación secuaencial

   (A)1010|
x  (B)1101|
      ————
p₀    1010|
p₁   0000 |
p₂  1010  |
p₃ 1010   |
   ———————| 
  10000010|

5.1. Lápiz y papel

• Multiplicar dos numeros de n bits en binario puro
• A, M, Q: n bits
• Sumador: n bits

bit C = 0
byte A = 000..0
byte M = Multiplicando
byte Q = Multiplicador

n = B.length
repetir i, n veces {
  if(q₀ == 1) Aᵢ = Aᵢ₋₁ + M
  desplazar(AQ)
}
Resultado {AQ}

5.2. Robertson

byte M = (X)XXX..X # Multiplicando con extensión de signo (se incrementa length de M un bit por el front propagando el bit de signo)
byte A = (0)000..0 # un bit más por la extensión de signo de M
byte Q = Multiplicador

n = B.length
repetir i (n-1) veces {
  if(q₀ == 1) Aᵢ = Aᵢ₋₁ + M 
  desplazar(AQ) # aritmético
}
if(q₀ == 1) Aᵢ = Aᵢ₋₁ - M
desplazar(AQ) # aritmético
Resultado {AQ}

5.3. Booth

byte A = (0)000..0
byte M = (X)XXX..X # Multiplicando

byte Q = XXX..X # Multiplicador
bit q₋₁ = 0 # bit adicional

n = B.length
repetir i (n) veces {
  switch(q₀q₋₁)
    01: Aᵢ = Aᵢ₋₁ + M 
    10: Aᵢ = Aᵢ₋₁ - M
}
desplazar(AQ) # aritmético
Resultado {Aₙ₋₁A₀Qₙ₋₁Q₀}

El peor caso para el algoritmo de Booth serían cadenas alternadas de 0 y 1. AUnque arregle un problema que tiene Robertson, crea otro a cambio, y puede llegar a darse el caso de ser más ineficiente que éste.

6. División

6.1. División con restauración

byte M = XXX..X # Divisor
byte A = 000..0 
byte Q = Dividendo

repetir i, n veces {
  desplazar_izq(AQ) 
  Aᵢ = Aᵢ₋₁ - M
  if(aₙ == 1) {
    Aᵢ = Aᵢ₋₁ + M   # restauración
    q₀ = 0
  } else q₀ = 1
}

Resultado {A(resto), Q(cociente)}

Lo más ineficiente del algoritmo es la restauración.

6.2. División sin restauración

byte M = XXX..X # Divisor
byte A = 000..0 
byte Q = Dividendo

repetir i, n veces {
  desplazar_izq(AQ) 
  
  if(aₙ == 0) Aᵢ = Aᵢ₋₁ - M
  else  Aᵢ = Aᵢ₋₁ + M 
  
  if(aₙ == 0) q₀ = 1
  else  q₀ = 0
}
if(aₙ == 1) Aᵢ₋₁ + M 

Resultado {A(resto), Q(cociente)}

¿Cómo hacemos divisiones con signo?

Operar con ellos en binario puro y los signos meterlos en una puerta xor.

¿Se peude hacer la división todavía más rápida

Poder ir en lugar de bit a bit, hacer predicciones basadas en tablas de resultados. de dos en dos bits, de 3 en 3 bits…