unidad 3 aritmetica de las computadoras
TRANSCRIPT
1
UNIDAD 3: Aritmética de las computadoras.
3.1. Introducción
Hasta el momento se han revisado algunas métricas para la obtención del rendimiento
(segundos, ciclos, instrucciones). También el concepto de abstracción y en particular se
hizo énfasis en la abstracción que vincula al hardware con el software de más bajo nivel, a
esta abstracción se le denomina: Arquitectura del repertorio de instrucciones o
simplemente Arquitectura de Computadoras.
Se revisó el repertorio de instrucciones MIPS, con el cual es posible implementar cualquier
programa.
Esta sección inicia con la implementación del hardware, en particular en esta unidad se
revisa la aritmética de las computadoras, para obtener una Unidad Aritmético Lógica
enfocada al repertorio de instrucciones previamente estudiando. Además, se describe el
mecanismo para realizar multiplicaciones y divisiones con base en esta ALU.
Finalmente, se muestra la representación de los números en punto flotante y se revisan las
operaciones de suma y producto. Se esboza el hardware que realiza estas operaciones, sin
entrar en detalles de la implementación completa.
3.2. Números con signo y sin signo
Los humanos preferimos representar a los números en base 10, sin embargo para las
computadoras lo más adecuado es utilizar el sistema binario (base 2).
Si para una secuencia de dígitos en cualquier base numérica, se quiere obtener su valor en
base 10, debe multiplicarse cada dígito por la base elevada a la posición del dígito dentro
del número, de manera que su valor sería
d x basei
donde i corresponde a la posición de un dígito dentro del número. La posición 0 es la que
está más a la izquierda (menos significativa). Por ejemplo, si tenemos el número 1011dos, en
base 10 nos representa a:
(1 x 23) + (0 x 2
2) + (1 x 2
1) + (1 x 2
0) diez
= (1 x 8) + (0 x 4) + (1 x 2) + (1 x 1) diez
= 8 + 0 + 2 + 1 diez = 11diez
Sin embargo los números en MIPS utilizan 32 bits, por lo que el número 1011dos, quedaría
representado como:
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
(32 bits de ancho)
2
Los números se representan colocando al dígito menos significativo a la derecha (posición
0) y al más significativo a la izquierda (posición 31).
Con 32 bits se pueden representar 232
números diferentes, desde el número 0 hasta el 232
– 1
(4, 294, 967, 295diez) :
0000 0000 0000 0000 0000 0000 0000 0000dos = 0diez
0000 0000 0000 0000 0000 0000 0000 0001dos = 1diez
0000 0000 0000 0000 0000 0000 0000 0010dos = 2diez
. . . . . . . . . . . . . . . . . .
1111 1111 1111 1111 1111 1111 1111 1101 dos = 4, 294, 967, 293diez
1111 1111 1111 1111 1111 1111 1111 1110 dos = 4, 294, 967, 294diez
1111 1111 1111 1111 1111 1111 1111 1111 dos = 4, 294, 967, 295diez
Los patrones de bits contienen una representación de los números, en realidad el conjunto
de números es infinito; solo que es necesario tener una representación para poder operarlos
aritméticamente a través de sumas, restas, productos, etc. Puede ocurrir que el resultado de
una operación no alcance en los 32 bits dedicados a cada número, cuando eso ocurre, se
generará una señal de sobreflujo (overflow), y el sistema operativo o el programa
determinarán lo que deben hacer.
Los programas de computadora realizan cálculos sobre números positivos y negativos, de
manera que es necesaria una representación que distinga los positivos de los negativos.
Una solución obvia consiste en dedicar uno de los bits para que determine el signo, dejando
31 bits para la magnitud. A esta representación se le conoce como magnitud y signo, tiene
diferentes inconvenientes. En principio, para la ubicación del signo existen dos
posibilidades, derecha o izquierda de la magnitud. Luego, el hardware requerirá de un paso
extra para la evaluación del signo y la determinación anticipada del signo del resultado.
Finalmente, se contaría con dos representaciones para el cero, lo cual se refleja en la
programación, por ejemplo, si un ciclo repetitivo terminará cuando una variable alcance el
valor de cero, será necesaria una doble comparación. Debido a estos inconvenientes, la idea
de representar a los números usando magnitud y signo no es utilizada.
Otra alternativa es el complemento de los números positivos para obtener el negativo que le
corresponde (complemento 1), esta representación tiene la ventaja de que la clasificación de
los números es bastante simple, un número positivo tendrá un cero en su bit mas
significativo y un número negativo tendrá un uno. Además, al sumar un número con su
correspondiente negativo, se tendrá una cadena de 1’s que corresponderá al 0 (0 negativo).
Pero se mantiene la desventaja de contar con dos representaciones para el cero.
La solución para obtener una representación coherente consiste en sumar 1 a la
representación de complemento a 1 (complemento 2), de manera que solo se tendrá una
representación para el cero, el bit más significativo nos indicará el signo del número y la
simple operación de sumar un número con su correspondiente negativo nos producirá el
número 0.
3
Esta representación es la que actualmente usa la mayoría de computadoras, y funciona
correctamente, aunque no está balanceada, porque existe un número negativo más debido a
la presencia del cero. Con los 32 bits dedicados a la representación de cada número, la
representación en complemento a dos es:
0000 0000 0000 0000 0000 0000 0000 0000dos = 0diez
0000 0000 0000 0000 0000 0000 0000 0001dos = 1diez
0000 0000 0000 0000 0000 0000 0000 0010dos = 2diez
. . . . . . . . . . . . . . . . . .
0111 1111 1111 1111 1111 1111 1111 1101dos = 2, 147, 483, 645diez
0111 1111 1111 1111 1111 1111 1111 11110dos = 2, 147, 483, 646diez
0111 1111 1111 1111 1111 1111 1111 1111dos = 2, 147, 483, 647diez
1000 0000 0000 0000 0000 0000 0000 0000dos = - 2, 147, 483, 648diez
10000 0000 0000 0000 0000 0000 0000 0001dos = - 2, 147, 483, 647diez
10000 0000 0000 0000 0000 0000 0000 0010dos = - 2, 147, 483, 646diez
. . . . . . . . . . . . . . . . . .
1111 1111 1111 1111 1111 1111 1111 1101 dos = - 3diez
1111 1111 1111 1111 1111 1111 1111 1110 dos = - 2diez
1111 1111 1111 1111 1111 1111 1111 1111 dos = - 1diez
La mitad de los números, del 0 al 2, 147, 483, 645diez (231
– 1), usa la representación
mostrada anteriormente (cuando no se había considerado el signo). El siguiente patrón
(1000. . .000dos) representa al número mas negativo (- 2, 147, 483, 648diez) y es seguido por
un conjunto decreciente de números negativos: - 2, 147, 483, 647diez (1000. . .0001 dos) hasta
el –1 (1111. . .1111 dos).
Esta representación no está balanceada por que el número - 2, 147, 483, 648diez no tiene un
número positivo correspondiente. Este hecho podría preocupar a los desarrolladores de
software, en contraparte con la representación de magnitud y signo que también
preocuparía a los desarrolladores de hardware.
El hecho de que el bit más significativo indique el signo del número, hace que este bit se
comporte como un auténtico bit de signo, de manera que si se quiere obtener el valor en
base 10 de cualquier número representado en complemento a 2, el bit de la posición 31 se
deberá multiplicar por –231
y los restantes 31 bits seguirán el mismo tratamiento que los
números sin signo (su valor lo obtendrán de acuerdo con su posición).
Ejemplo: Conversión de Binario a Decimal
¿Cuál es el valor decimal del siguiente número en complemento a 2?
1111 1111 1111 1111 1111 1111 1111 1100dos
4
Respuesta:
Considerando la posición de cada bit tenemos:
(1 x -231
) + (1 x 230
) + (1 x 229
) + . . . + (1 x 22) + (0 x 2
1) + (0 x 2
0) diez
= -231
+ 230
+ 229
+ . . . + 22 + 0 + 0diez
= - 2,147,483,648 + 2,147,483,644diez = - 4diez
Cuando se manejan números en complemento a dos, puede generarse una señal de
sobreflujo (o desbordamiento) si el signo del resultado de una operación no corresponde
con el signo esperado, por ejemplo, al sumar dos números positivos, si el resultado no se
puede representar en el conjunto de números positivos, éste tomará una representación que
corresponda a un número negativo.
En algunos casos, como en el manejo de direcciones de memoria, no es posible usar
números negativos, las direcciones de memoria inician en 0 y crecen hacia una dirección
mayor. Entonces, los programas en ocasiones manejan variables que pueden tomar valores
positivos y negativos, o bien, variables que sólo tomarán valores positivos. Para hacer esa
distinción, los lenguajes de programación incorporan modificadores a los tipos de datos,
para que puedan ser tratadas adecuadamente; por ejemplo en el lenguaje C, el modificador
unsigned indica que un número debe ser tratado sin considerar el signo.
Las comparaciones tratan con esta dicotomía, si un número tiene un 1 en su bit más
significativo y es tratado en complemento a 2, será un número negativo y por lo tanto será
menor que todos aquellos que tengan 0 en su bit más significativo. Pero si el mismo
número es interpretado como entero sin signo, será mayor que todos aquellos que tengan 0
en su bit más significativo. Esta situación debe resolverse a nivel de hardware.
En el caso de MIPS se consideran diferentes variantes de la instrucción slt (set on less
than), tanto slt como slti trabajan con enteros sin signo, pero sltu (set on less than unsigned)
y sltiu (set on less than immediate unsigned) trabajan con enteros sin signo.
Ejemplo: Comparación con signo y sin signo
Supongamos que el registro $s0 tiene el número binario
1111 1111 1111 1111 1111 1111 1111 1111dos
y que el registro $s1 tiene el número binario
0000 0000 0000 0000 0000 0000 0000 0001dos
¿Cuáles son los valores de los registros $t0 y $t1 después de las instrucciones?
slt $t0, $s0, $s1
sltu $t1, $s0, $s1
5
Respuesta:
Para la instrucciones slt los números se consideran en complemento 2, de manera que $s0
tiene un número negativo (-1), que es menor al número 1 contenido en $s1, por lo que $t0
tendrá 1.
Pero para la instrucciones sltu los números son tratados sin signo, entonces $s0 tiene al
número positivo 4, 294, 967, 295diez, que definitivamente es mayor que 1, entonces $t1
tendrá 0.
Cuando se trabaja en complemento a 2, para obtener la versión negativa (o positiva) a partir
de un número positivo (o negativo), la forma más simple para hacerlo consiste en
complementar cada uno de los bits (cambiar 1’s por 0’s y 0’s por 1’s) y luego sumar 1. Esta
idea se justifica por el hecho de que cuando sumamos un número con su complemento
obtenemos una cadena de 32 unos (que representa al –1).
De manera que x + x’ = -1 que es equivalente a x + x’ + 1 = 0, de donde obtenemos
- x = x’ + 1
que nos indica que el negado de un número es igual al complemento del mismo mas 1.
Ejemplo: Negación.
Negar el 2diez y verificar el resultado negando –2diez
Respuesta:
2diez = 0000 0000 0000 0000 0000 0000 0000 0010dos
Para negarlo lo complementamos y luego le agregamos 1:
1111 1111 1111 1111 1111 1111 1111 1101 dos
+ 1 dos
= 1111 1111 1111 1111 1111 1111 1111 1110 dos
= - 2diez
En la otra dirección:
- 2diez = 1111 1111 1111 1111 1111 1111 1111 1110 dos
Primero lo complementamos y luego de agregamos 1:
0000 0000 0000 0000 0000 0000 0000 0001 dos
+ 1 dos
= 0000 0000 0000 0000 0000 0000 0000 0010 dos
= 2diez
6
Otro aspecto a considerar es el tamaño de las constantes. El repertorio MIPS incluye
instrucciones que manejan constantes de 16 bits, cuando estas constantes son operadas en
una ALU de 32 bits, deben completarse con otros 16 bits. Si se trabajan números en
complemento a 2, su valor dependerá del bit más significativo de la constante (el bit 15).
Si este bit es 0 se completa con 0’s y la magnitud se conserva (los 0’s a la derecha no tienen
valor). Si se trata de un 1, para conservar la magnitud habrá que completar con 1’s.
Finalmente, aunque las computadoras trabajan en binario, resulta más fácil utilizar al
sistema octal o al hexadecimal para la representación y manipulación de los números, esto
porque la cantidad de símbolos existentes en estas bases corresponde a una cantidad exacta
de combinaciones de 3 y 4 bits respectivamente. Las bases octal y hexadecimal pueden
considerarse como una forma abreviada de representar a los números en binario, un dígito
en octal corresponde con 3 bits y un dígito en hexadecimal con 4. Y viceversa, por cada 3
bits puede obtenerse un dígito octal y por cada 4 uno hexadecimal.
3.3.Suma y resta
Las sumas en binario se realizan de la misma manera que en base 10, es decir, de derecha a
izquierda se va sumando dígito a dígito y si el resultado es mayor al dígito más grande (9 en
base 10 y 1 en base 2), se produce un acarreo que debe sumarse en el dígito siguiente.
Entonces, al sumar dos bits debe tomarse en cuenta un posible acarreo en la entrada o bien
la generación de un acarreo en la salida. En la tabla 3.1 se muestran todas las posibles
combinaciones que pueden ocurrir al sumar un dígito a con un dígito b, el resultado de la
suma se coloca en el dígito s, también se considera la presencia de un acarreo en la entrada
y la generación de un acarreo de salida.
a b cin s cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1 Tabla 3.1 Comportamiento de la suma
Al sumar dos palabras de 32 bits, solo se va aplicando la tabla de derecha a izquierda, y los
acarreos generados se suman al siguiente bit más significativo:
7
La resta también podría realizarse de derecha a izquierda, bit a bit, considerando que
algunas veces será necesario “tomar prestado un 1 del dígito más significativo”, cuando el
minuendo es menor que el sustraendo. Sin embargo, a nivel de hardware esto es complejo,
lo más simple es obtener la versión negativa del número a restar, y después realizar una
suma.
Ejemplo: Suma y resta binaria.
Sumar 37diez + 45diez en binario y después restar 37diez de 45diez.
Respuesta:
0000 0000 0000 0000 0000 0000 0010 0101dos = 37diez
+ 0000 0000 0000 0000 0000 0000 0010 1101dos = 45diez
= 0000 0000 0000 0000 0000 0000 0101 0010 dos = 82diez
Para la resta, emplearemos el complemento 2 de 37diez (para obtener – 37diez) y luego lo
sumaremos al 45diez:
1111 1111 1111 1111 1111 1111 1101 1010dos
+ 1dos
1111 1111 1111 1111 1111 1111 1101 1011dos = - 37diez
0000 0000 0000 0000 0000 0000 0010 1101dos = 45diez
+ 1111 1111 1111 1111 1111 1111 1101 1011dos = - 37diez
1 0000 0000 0000 0000 0000 0000 0000 1000dos = 8diez
El 1 que aparece más a la izquierda se ignora, por que el resultado debe quedar en 32 bits,
no es un sobreflujo o desbordamiento.
Cuando se realizan sumas o restas, cuando se trabaja en complemento a 2 tiene sentido
hablar de sobreflujo. Si sumamos dos números positivos grandes, esperamos que el
resultado sea positivo, pero si la cantidad de bits no es suficiente para la representación del
resultado, entonces se desbordará hacia un número negativo. En la tabla 3.2 se muestra un
resumen de los casos en los que si se considera la existencia de un sobreflujo.
Operación Operando A Operando B Resultado
(Indicación de sobreflujo)
A + B 0 0 < 0
A + B < 0 < 0 0
A – B 0 < 0 < 0
A – B < 0 0 0 Tabla 3.2 Situaciones de sobreflujo
8
Debe contemplarse el hecho de ignorar el sobreflujo en algunos casos y reconocerlo en
otros. La solución para MIPS es contar con dos clases de instrucciones aritméticas para
reconocer estas dos posibilidades:
La suma (add), la suma inmediata (addi) y la resta (sub) producen una excepción si
ocurre un sobreflujo.
La suma sin signo (addu) , la suma inmediata sin signo (addiu) y la resta sin signo
(subu) no producen excepciones debidas a los sobreflujos.
Puesto que en el lenguaje C se ignoran los desbordamientos, los compiladores para MIPS
siempre generarán las versiones sin signo de las instrucciones aritméticas addu, addiu y
subu no importa el tipo de las variables. Los compiladores MIPS de Fortran, sin embargo,
seleccionan las instrucciones aritméticas apropiadas, dependiendo del tipo de operando.
Un sobreflujo en MIPS producirá una excepción, algunas veces también conocida como
interrupción. Una excepción o interrupción es esencialmente una llamada no proyectada a
un procedimiento. La dirección de la instrucción en la que ocurrió el sobreflujo es
almacenada en un registro, y se produce un salto a una dirección predefinida para invocar al
procedimiento encargado de manejar la excepción. La dirección en la que ocurrió la
excepción se salva de manera que sea posible continuar con la ejecución del programa
después de ejecutar algún código correctivo.
En MIPS se incluye a un registro llamado contador del programa para las excepciones
(EPC) el cual contendrá la dirección de la instrucción que ocasionó la excepción. También
se cuenta con la instrucción mover desde el control del sistema (mfc0) que sirve para copiar
el contenido del registro EPC en un registro de propósito general de manera que el software
tiene la opción de regresar a la instrucción infractora a través de un salto a registro.
3.4. Operaciones lógicas
Aunque las primeras computadoras se centralizaron sobre palabras completas, pronto llego
a ser claro que es útil operar sobre campos de bits dentro de una palabra o aún sobre los bits
individuales. Un ejemplo lo encontramos al manipular caracteres dentro de una palabra,
debido a que cada carácter utiliza ocho bits, se observa que se requiere de instrucciones por
medio de las cuales sea posible empaquetar y desempaquetar los bits dentro de las palabras.
Una clase de estas operaciones son los desplazamientos (shifts). Con ellos se mueven todos
los bits de una palabra a la izquierda o derecha, llenando los bits vacíos con 0s. Por
ejemplo, si el registro $s0 contiene
0000 0000 0000 0000 0000 0000 0000 1101dos
y una instrucción de un desplazamiento a la izquierda por ocho es ejecutada, el nuevo valor
que tomará esta palabra será
0000 0000 0000 0000 0000 1101 0000 0000dos
9
El dual de un desplazamiento a la izquierda es un desplazamiento hacia la derecha. En
MIPS las instrucciones para los desplazamientos son sll – desplazamiento lógico a la
izquierda (shift left logical ) y srl – desplazamiento lógico a la derecha (shift right logical).
La instrucción para realizar la operación anterior, suponiendo que el resultado se
almacenará en el registro $t0, es
sll $t0, $s0, 8 # reg $t0 = reg $s0 << 8 bits
En la sección 2.3 (Representación de instrucciones), para las instrucciones Tipo – R se
mencionó la existencia del campo shamt (shift amount), este campo solo es utilizado por las
instrucciones de desplazamientos e indica la cantidad de desplazamiento. Para estas
instrucciones el registro rs es ignorado y se llena con 0s, rt es el registro que será
desplazado y rd es el registro destino. La representación de la instrucción anterior es:
0 0 16 8 8 0
op rs rt rd shamt funct
El campo de funct debe tener 0 para sll y 2 para srl.
Otras operaciones útiles son la AND y la OR, estas operaciones se aplican bit a bit.
La AND es comúnmente utilizada para aplicar una máscara a un registro, puesto que la
AND va a colocar un 1 en el bit resultante si los dos bits sobre los que se aplica tienen 1s.
La máscara se realiza colocando 1s en aquellas posiciones que se quiera dejar pasar, y 0s en
los bits que se van a eliminar (contendrán 0s).
Por ejemplo, si el registro $t0 contiene: 1010 0011 0011 1001 1100 1100 1110 1101dos
y si el registro $t1 contiene: 0000 0000 1111 1111 1111 1111 0000 0000dos
Al realizar la operación: and $t2, $t1, $t0
El registro $t1 está funcionando como una máscara que deja pasar los 16 bits intermedios y
oculta al resto.
El resultado en $t2 será: 0000 0000 0011 1001 1100 1100 0000 0000dos
En el caso de la OR, en el resultado se obtendrá un 1 si alguno de los bits sobre los que se
aplica tiene 1.
La operación: or $t2, $t1, $t0
dejará en $t2: 1010 0011 1111 1111 1111 1111 1110 1101dos
10
En la tabla 3.3 se muestran las operaciones lógicas y su correspondiente instrucción MIPS.
Debido a que las constantes también son utilizadas en operaciones lógicas, se incluyen
versiones inmediatas para la AND y la OR.
Operación Lógica Operador en C Instrucción MIPS
Desplazamiento a la izquierda << sll
Desplazamiento a la derecha >> srl
AND bit a bit & and, andi
OR bit a bit | or, ori Tabla 3.3 Las operaciones lógicas y sus correspondientes operaciones en C y MIPS
El lenguaje C permite definir campos de bits dentro de palabras, permitiendo empaquetar
diversos objetos dentro de una palabra para que exista compatibilidad con algunos
dispositivos I/O. Los campos pueden tener la longitud de un bit, y el compilador debe
colocarlos dentro palabras utilizando las operaciones lógicas: and, or, sll y srl.
Ejemplo: Campos de Bits.
El siguiente código C ubica tres campos dentro de una palabra etiquetada receiver: Un
campo de 1 bit denominado ready, un campo de un bit denominado enable, y un campo de
8 bits denominado receivedByte. Se copia receivedByte dentro de data, se ajusta ready a 0,
y se ajusta enable a 1.
int data;
struct {
unsigned int ready: 1;
unsigned int enable: 1;
unsigned int receivedByte: 8;
} receiver;
. . .
data = receiver.receivedByte;
receiver.ready = 0;
receiver.enable = 1;
¿Cuál es el correspondiente código MIPS? Suponga que data y receiver están ubicados en
$s0 y $s1.
Respuesta:
C alinea los campos a la derecha:
31 . . . . . 10 9 2 1 0
receivedByte enable ready
11
Copia el campo de 8 bits (receivedByte) a data y lo aísla:
slr $s0, $s1, 2 # Se desplaza y copia en data
andi $s0, $s0, 0x00ff # Se usa una máscara que elimina la información
# no deseada
Luego se realizan los ajustes:
andi $s1, $s1,0xfffe # Bit 0 ajustado a 0
ori $s1, $s1,0x0002 # Bit 1 ajustado a 1
Las instrucciones addi y ori trabajan con números con signos, de manera que para poder
operar en una ALU de 32 bits, las constantes se extienden a 32 bits extendiendo el bit de
signo.
3.5. Construcción de una Unidad Aritmético-Lógica
La Unidad Aritmético-Lógica (ALU) es la fuerza física de la computadora, el dispositivo
que realiza las operaciones aritméticas como suma y resta; y operaciones lógicas como
AND y OR. En esta sección se construirá una ALU basada en los 4 componentes mostrados
en la figura 3.1, los componentes enumerados con 1, 2 y 4 tienen dos entradas, en ocasiones
tal vez sea necesario ampliar el número de entradas.
Fig. 3.1 Los cuatro componentes en los que se fundamentará la construcción de la ALU
12
Debido a que MIPS trabaja con palabras de 32 bits, la ALU a construir deberá contar con
operandos de 32 bits. Para ello, primero se realizará el diseño de una ALU de 1 bit, para
después utilizar 32 bloques basados en esa ALU de 1 bit.
ALU de 1 Bit
Una unidad lógica con las operaciones AND y OR se muestra en la figura 3.2, para las
entradas a y b es posible seleccionar una operación lógica por medio de la entrada de
operación en el multiplexor, si operación es igual a 0, en la salida tendremos a AND b, pero
si operación es igual con 1, la salida tendrá a OR b.
Fig. 3.2 Unidad lógica con AND y OR
La siguiente función a incluir es la suma. En la tabla 3.1 se mostró el comportamiento de un
sumador completo, el sumador es un bloque con 3 entradas y dos salidas, como se muestra
en la figura 3.3.
Fig. 3.3 Bloque sumador de 1 Bit.
En el sumador, tanto la salida sum como la salida CarryOut se producen por dos circuitos
combinacionales. Como ejemplo se revisará al circuito correspondiente a CarryOut. La
señal CarryOut es verdadera en 4 ocasiones, que tomaremos de la tabla 3.1, para mostrarlas
en la tabla 3.4:
a b CarryIn CarryOut
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1 Tabla 3.4 Comportamiento de CarryOut
Utilizando el símbolo + para la operación lógica OR y el para la AND, se tienen que:
13
CarryOut = (bCarryIn) + (aCarryIn) + (ab) + (abCarryIn)
Si (abCarryIn) es verdadero los demás términos serán verdaderos, de manera que es
posible anular este término, que corresponde a la cuarta línea de la tabla 3.4, para obtener:
CarryOut = (bCarryIn) + (aCarryIn) + (ab)
Esta expresión requiere de una compuerta OR de tres entradas y 3 compuertas AND de dos
entradas, su implementación es:
Fig. 3.4 Hardware para la señal CarryOut del sumador de 1 bit
La expresión para la suma se puede obtener de la tabla 3.1 y es:
Sum = (ab’CarryIn’) + (a’bCarryIn’) + (a’b’CarryIn) + (abCarryIn)
Que puede simplificarse a: Sum = a XOR b XOR CarryIn
Manejando al sumador como un bloque, se implementa a la ALU de 1 Bit, como se muestra
en la figura 3.5, la cual realiza las operaciones de AND, OR y ADD.
Fig. 3.5 ALU de 1 bit, capaz de realizar las operaciones AND, OR y ADD.
14
ALU de 32 Bits
El bloque mostrado en la figura 3.5 puede repetirse 32 veces para la construcción de una
ALU de 32 bits, la señal de acarreo generada en el bloque i va a corresponder al acarreo de
entrada en el bloque i + 1. Esta forma de conectar las señales de acarreo nos produce un
sumador poco eficiente conocido como Sumador de acarreo extendido (ripple carry
adder). Más adelante se muestra otra técnica en la que se buscará generar al acarreo de
manera más rápida. Todos los bloques comparten las señales de operación.
Fig. 3.6 ALU de 32 bits, capaz de realizar las operaciones AND, OR y ADD.
La resta equivale a la suma con el negado del segundo operando, así es como el hardware
realiza las restas. De manera que para realizar una resta se sumará el complemento a 2 del
segundo operando. Para eso es necesario un inversor con el que se obtenga el complemento
y un multiplexor para seleccionar entre el operando o su complemento. En la figura 3.7 se
muestra al inversor que se agrega para obtener el complemento de b. Pero además es
15
necesario sumar 1, esto simplemente se hace colocando 1 al acarreo de entrada del bit
menos significativo.
Fig. 3.7 ALU de 1 bit, con la entrada Binvert se selecciona entre b y su complemento.
Otra instrucción importante que se incorpora en MIPS es slt (set on less than), esta
instrucción requiere de tres argumentos (slt reg1, reg2, reg3) y coloca un 1 en reg1 si
resulta que reg2 es menor que reg3. Reg1 = 1 si reg2 < reg3, que es equivalente a reg2 -
reg3 < 0. Lo que indica que una buena opción para la comparación consiste en realizar la
resta reg2 – reg3 y luego evaluar el resultado; en el resultado no importa la magnitud, lo
que importa es saber si es o no menor que 0, lo cual queda directamente determinado por el
bit más significativo. Si el bit más significativo tiene 1, el resultado de la operación slt
deberá ser 1, y si es 0 el resultado deberá ser 0.
La instrucción slt es otra operación para la ALU, de manera que el multiplexor de la salida
deberá incrementarse con una entrada más. Estas ideas se muestran en la figura 3.8, en
donde el multiplexor se ha incrementado y la nueva entrada se incorpora desde fuera del
bloque de la ALU (la entrada etiquetada como less) (fig. 3.8 a). Sin embargo para el bit 31
(el más significativo) se genera una salida (etiquetada como set) que corresponde al bit de
signo del resultado (fig. 3.8 b). Esta salida se retroalimentará a la entrada less del bit 0,
mientras que para los otros bits (del 1 al 31), la entrada less estará conectada directamente a
tierra, para que mantenga un cero en forma permanente. En la figura 3.9 se muestra la
retroalimentación de set a la entrada less del bit menos significativo, así como los 0’s en las
demás entradas less.
Otra idea interesante que se presenta en la figura 3.8 (b) es la presencia de la unidad de
detección de sobreflujo, el objetivo de este bloque es generar una bandera (señal de 1 bit)
que indique la existencia de un sobreflujo, para ello es necesario conocer los signos de los
operandos ( a31 y b31 ), el tipo de operación (Binvert), el signo del resultado y tal vez la
existencia de un acarreo en el bit más significativo. El comportamiento de este circuito
puede basarse en el comportamiento de la suma descrito en la tabla 3.2.
16
Fig. 3.8 El valor del bit más significativo se usará para la instrucción slt,
en a) se muestra la estructura de los 31 bits menos significativos y
en b) la estructura del bit más significativo
En la figura 3.9 se muestra la conexión de las 32 ALUs de 1 bits, las primeras 31 tienen la
misma construcción, la última difiere un poco por la presencia de la unidad de detección de
sobreflujo y porque de ahí se toma la salida set que se retroalimenta al bit 0.
0
3
Result
Operation
a
1
CarryIn
CarryOut
0
1
Binvert
b 2
Less
0
3
Result
Operation
a
1
CarryIn
0
1
Binvert
b 2
Less
Set
Overflow
detectionOverflow
a.
b.
17
Fig. 3.9 ALU de 32 Bits, capaz de realizar sumas, restas, AND, OR y slt.
También puede indicar la existencia de un sobreflujo.
El acarreo de entrada sólo se ocupa para las restas, y su comportamiento es el mismo que el
de la entrada Binvert, si la entrada Binvert tiene 1, indica que se realizará una resta, y para
la obtención correcta del complemento 2, debe sumarse 1 con la entrada CarriIn del
sumador de los bits menos significativos. Si la entrada de Binvert es 0, se trata de una suma
y la entrada CarryIn deberá tener 0. Por lo tanto, las entradas Binvert y CarryIn pueden
conectarse en una sola, a la cual se llamará Bnegado como se muestra en la figura 3.10.
En la figura 3.10 también se muestra la generación de la bandera de zero, la cual será
verdadera (contendrá 1) si el resultado de cualquier operación es igual a 0. La idea de la
generación de esta bandera es bastante simple, cuando las 32 salidas de las ALUs de 1 bit
tengan 0, la OR que las une producirá un 0 y por lo tanto el inversor que le sigue lo
transformará a 1. Pero si alguna de las salidas tiene un valor 1, la OR generará un 1 y el
inversor lo transformará a 0.
Set
a31
0
ALU0 Result0
CarryIn
a0
Result1
a1
0
Result2
a2
0
Operation
b31
b0
b1
b2
Result31
Overflow
Binvert
CarryIn
Less
CarryIn
CarryOut
ALU1
Less
CarryIn
CarryOut
ALU2
Less
CarryIn
CarryOut
ALU31
Less
CarryIn
18
Fig. 3.10 ALU de 32 Bits, capaz de realizar sumas, restas, AND, OR y slt.
Con banderas de zero y de sobreflujo.
La ALU de la figura 3.10 tiene 3 líneas de control, concatenando la entrada Bnegado con
las entradas de operación, el comportamiento de la ALU se resume en la tabla 3.5.
Líneas de Control de la ALU Función
000 And
001 Or
010 Suma
110 Resta
111 Slt Tabla 3.5 Comportamiento de la ALU
La ALU se representa con su símbolo tradicional en la figura 3.11, las entradas a y b son de
32 bits, la entrada ALU Operación es de 3 bits, la salida Result es de 32 bits, y las salidas
Zero, Overflow y CarryOut son todas de 1 bit.
19
Fig. 3.10 ALU de 32 Bits, cuyo comportamiento se describe en la tabla 3.5
Anticipación del acarreo.
El sumador que se incorporó a la ALU de 32 bits (Sumador de acarreo extendido) es poco
eficiente debido a que la generación del último acarreo no se podrá hacer, mientras no se
hayan generado los 31 acarreos menos significativos. Porque el acarreo de cada bit se va
propagando en forma secuencial hasta alcanzar al último bit.
Existe una variedad de esquemas que permiten la generación anticipada del acarreo, estos
esquemas son más rápidos que el acarreo extendido por que viajan por menos compuertas.
Algunos resultados aceptables producen el acarreo en un orden log2 del número de bits a
sumar.
La anticipación de acarreo es posible, porque a diferencia del software, el hardware puede
trabajar en paralelo, muchas compuertas pueden compartir entradas y todas trabajarán
cuando existan cambios en tales entradas.
Acarreo rápido usando “Hardware Infinito”
De acuerdo con los principios del álgebra Booleana, cualquier función se puede expresar
como una suma de productos, o como un producto de sumas, por lo que para su
implementación en ambos casos, requeriría de dos niveles de compuertas.
Por ejemplo, para el acarreo de entrada en el sumador 2, el cual es exactamente el acarreo
de salida del bit 1, se tendría:
CarryIn2 = (b1CarryIn1) + (a1CarryIn1) + (a1b1)
Similarmente, CarryIn1 está definido como:
CarryIn1 = (b0CarryIn0) + (a0CarryIn0) + (a0b0)
Usando solo c en lugar de CarryIn, podemos rescribir las dos expresiones anteriores como:
20
c2 = (b1c1) + (a1c1) + (a1b1)
c1 = (b0c0) + (a0c0) + (a0b0)
Sustituyendo el resultado encontrado para c1 en la expresión de c2 se tiene:
c2 = (b1( (b0c0) + (a0c0) + (a0b0)) ) + (a1(b0c0) + (a0c0) + (a0b0) ) +
(a1b1)
c2 = (a1a0b0) + (a1a0c0) + (a1b0c0) + (ba0b0) + (b1a0c0) + (b1b0c0)
+ (a1b1)
Esta expresión es sólo para el 2º bit, pero la ecuación crece exponencialmente con el
número de bits, de manera que si se pretende usar este esquema, el costo de la
implementación de la unidad de anticipación de acarreo, debido a su gran número de
compuertas, será mayor que el costo del resto de la ALU.
Generación y Propagación para la obtención del acarreo.
En este esquema se reorganizan las ecuaciones con la finalidad de simplificar al Hardware.
Para el acarreo 2 se obtuvo la expresión:
c2 = (a1b1) + (a1 + b1)c1
y para acarreo 1:
c1 = (a0b0) + (a0 + b0)c0
En general el acarreo i + 1 depende del acarreo i de acuerdo a la expresión:
ci+1 = (aibi) + (ai + bi)ci
El primer término indica la generación de un acarreo en el bloque i, se denominará como
gi; el segundo término indica que el acarreo ci se va a propagar si su coeficiente de
propagación es verdadero, este coeficiente se denominará pi. De manera que:
gi = aibi
pi = ai + bi
Con estas definiciones se tiene que:
ci+1 = gi + pici
Esta expresión indica que habrá un acarreo a la salida del bloque i, si éste fue generado
dentro del bloque o si este ya existía (en ci) y se dieron las condiciones para su
propagación. Con estas definiciones de generación y propagación, es posible obtener de
manera simplificada los 4 primeros acarreos:
c1 = g0 + (p0c0)
c2 = g1 + (p1 g0) + (p1p0c0)
c3 = g2 + (p2g1) + (p2p1g0) + (p2p1p0c0)
c4 = g3 + (p3g2) + (p3p2g1) + (p3p2p1g0) + (p3p2p1p0c0)
21
Estas ecuaciones representan el sentido común: Existe acarreo si algún sumador cercano lo
generó y todos los sumadores intermedios lo propagaron. Una analogía con una tubería de
agua se muestra en la figura 3.11 para dar claridad a estas ideas.
Fig. 3.11 Una tubería como analogía para mostrar la anticipación del acarreo para 1 bit, 2 bits y 4 bits.
El acarreo va a existir (existirá agua en la salida) si fue generado (se abrió alguna de las llaves g), o si existía
un acarreo inicial y se dieron las condiciones para su propagación (todas las llaves p se abrieron).
Otro nivel de abstracción para Acarreos rápidos.
Con las ecuaciones anteriores se demuestra que con un poco más de Hardware es posible
generar acarreos rápidos para sumadores de 4 bits. Al conectar 4 sumadores como bloques
de un Sumador de acarreo extendido, se tendrá un sumador de 16 bits más rápido que si el
acarreo se arrastrase por los 16 bits.
Para mejorarlo aún más, es posible usar este esquema en un nivel más alto. Para obtener el
acarreo anticipado en sumadores de 4 bits, es necesario generar y propagar señales en este
nivel más alto. La propagación para bloques con sumadores de 4 bits será posible si todos
los bits dentro de un bloque la hacen posible, esto es:
22
P0 = p3p2p1p0
P1 = p7p6p5p4
P2 = p11p10p9p8
P3 = p15p14p13p12
Cada Pi representa una “súper” propagación en un sumador de 4 bits.
Para la generación debe considerarse que será verdadera si se generó en el bit más
significativo, o si se generó en uno de los bits inferiores al más significativo, y durante las
etapas intermedias se realizó su propagación.
G0 = g3 + (p3g2) + (p3p2g1) + (p3p2p1g0)
G1 = g7 + (p7g6) + (p7p6g5) + (p7p6p5g4)
G2 = g11 + (p11g10) + (p11p10g9) + (p11p10p9g8)
G3 = g15 + (p15g14) + (p15p14g13) + (p15p14p13g12)
Cada Gi representa una “súper” generación en un sumador de 4 bits. Una analogía con una
tubería, para estas nuevas versiones de generación y propagación, se muestra en la figura
3.12 para dar claridad a estas ideas.
Fig. 3.12 La tubería como analogía para mostrar la anticipación del acarreo, en otro nivel de abstracción. P0
estará abierto sólo si todas las pi ( i = 0 .. 3) están abiertas; además, fluirá agua en G0 si al menos una gi esta
abierta y las pi permiten su propagación.
Entonces, en un nivel de abstracción más alto, es posible escribir las ecuaciones de los
acarreos de salida de cada bloque de 4 bits.
C1 = G0 + (P0c0)
C2 = G1 + (P1 G0) + (P1P0c0)
C3 = G2 + (P2G1) + (P2P1G0) + (P2P1P0c0)
C4 = G3 + (P3G2) + (P3P2G1) + (P3P2P1G0) + (P3P2P1P0c0)
23
Estas ecuaciones son iguales a las versiones en minúsculas mostradas anteriormente,
excepto que cada Ci corresponde al acarreo de un bloque de 4 bits. En la figura 3.13 se
muestra un sumador de 16 bits (a bloques), resaltando el bloque por medio del cual se
procesan los acarreos de cada sumador de 4 bits, para generar el acarreo de los 16 bits.
Fig. 3.13 Se utilizan ALUs de 4 bits para anticipar el acarreo de un sumador de 16 bits.
Tarea 5
1. Convertir 512diez, -1023diez y – 4 000 000diez en números binarios en complemento 2.
2. Qué números en decimal representan los números en complemento 2 siguientes:
1111 1111 1111 1111 1111 1110 0000 1100dos
1111 1111 1111 1111 1111 1111 1111 1111dos
0111 1111 1111 1111 1111 1111 1111 1111dos
3. ¿Por que MIPS no tiene una instrucción de resta inmediata?
24
4. Encontrar la secuencia más corta de instrucciones MIPS para determinar si existió
acarreo de salida después de la suma de dos registros, supongamos que $t3 se sumó con
$t4 y el resultado se almacenó en $t5. Colocar 0 o 1 en $t2 el acarreo de salida es 0 o 1,
respectivamente (Sugerencia: Esto puede hacerse en dos instrucciones).
5. Dos amigos, Enrique y Beto están en desacuerdo. Enrique dice “Todos los enteros
mayores que cero y exactamente divisibles por 6 tienen exactamente dos 1s en su
representación binaria”. Beto no está de acuerdo, él dice “No, pero tales números tienen
un número par de 1s en su representación”. ¿Estás de acuerdo con Enrique, con Beto o
con ninguno de los dos?
6. Esquema de Anticipación de acarreo. Se quiere sumar:
a: 0001 1010 0011 0011dos
b: 1110 0101 1110 1011dos
Determinar los valores de gi, pi, Pi y Gi con los dos números y encuentre CarryOut14
(C4).
Práctica de laboratorio 2:
1. Desarrollar y simular en VHDL las ALU’s de 1 bit que se muestran en la figura 3.8 (a)
y (b).
2. Construir y simular en VHDL una ALU de 16 bits, con base en la figura 3.10.
3.6 Multiplicación
La multiplicación es una operación más complicada que la suma y que la resta. Para
entender cómo el hardware realiza esta operación, con base en la ALU desarrollada,
primero se revisa cómo se realiza esta operación de manera manual, recordando así los
nombres de los diferentes elementos que intervienen en la operación. Por ejemplo:
Multiplicando 1000
Multiplicador x 1001
1000
0000
0000
1000
Producto 1001000
El primer operando se llama multiplicando y el segundo multiplicador. Al resultado final se
le llama producto. El algoritmo básico realiza la multiplicación entre el multiplicando y un
dígito del multiplicador, para obtener un resultado parcial, cada resultado parcial se
desplaza un lugar a la derecha. Al final se suman todos los productos parciales desplazados
para obtener el producto final.
25
Cuando se trata de números binarios, la obtención de cada producto parcial es inmediata, si
el dígito del multiplicador que se está evaluando es 1, el producto parcial es igual al valor
del multiplicando; y si es un 0, el resultado parcial es 0.
Otra observación importante es que, sin importar la base numérica en la que se obtenga el
producto, al multiplicar un número de n-dígitos con otro de m-dígitos, el resultado puede
llegar a requerir, a lo mas, de n + m dígitos. En el caso de MIPS se multiplicarán dos
registros de 32 bits, de manera que el resultado puede requerir hasta de 64 bits para su
representación.
Primera versión del Algoritmo y Hardware de la Multiplicación.
La primera versión de la implementación corresponde con el algoritmo básico, el hardware
se muestra en la figura 3.14, el multiplicando debe ubicarse en la mitad izquierda de un
registro de 64 bits, para que se vaya desplazando a la izquierda como ocurría con cada
producto parcial. El multiplicando se va a sumar con el registro del producto (de 64 bits) y
el resultado se va a escribir en este último registro. A diferencia del algoritmo básico, la
suma se va a realizar cada vez que el multiplicando se recorra a la izquierda, y no al final de
la obtención de todos los productos parciales.
El multiplicador estará en un registro de desplazamiento de 32 bits, este registro se
desplazará a la derecha de manera que sólo se evalúe al bit menos significativo. El bloque
encargado de sincronizar a los demás elementos es el Control, este bloque evalúa al bit
menos significativo del multiplicador y en función de ello determina si se sumará al
multiplicando con el producto parcial o si solamente se desplazará a la izquierda; también
determina cuando la operación debe terminar. La actividad de este bloque se describe en el
algoritmo de la figura 3.15, donde se muestra que, debido a que los operandos son de 32
bits, se requiere de 32 iteraciones.
Fig. 3.14 Hardware de la multiplicación (primera versión)
26
Fig. 3.15 Algoritmo para la multiplicación (primera versión)
Ejemplo: Primer algoritmo de la multiplicación
Usando números de 4 bits, para reducir espacio, multiplicar 6diez x 3diez. (0110dos x 0011dos).
Respuesta:
Debido a que los números son de 4 bits, el algoritmo requerirá de 4 iteraciones, se
construye una tabla mostrando los diferentes pasos en cada iteración:
Iteración Paso Multiplicador Multiplicando Producto
0 Valores iniciales 0011 0000 0110 0000 0000
1
1: 1 => prod = prod + mcando 0011 0000 0110 0000 0110
2: Desp. Mcando. a la izq. 0011 0000 1100 0000 0110
3: Desp. Mdor. a la der. 0001 0000 1100 0000 0110
2
1: 1 => prod = prod + mcando 0001 0000 1100 0001 0010
2: Desp. Mcando. a la izq. 0011 0001 1000 0001 0010
3: Desp. Mdor. a la der. 0000 0001 1000 0001 0010
27
3
1: 0 => No operación 0000 0001 1000 0001 0010
2: Desp. Mcando. a la izq. 0000 0011 0000 0001 0010
3: Desp. Mdor. a la der. 0000 0011 0000 0001 0010
4
1: 0 => No operación 0000 0011 0000 0001 0010
2: Desp. Mcando. a la izq. 0000 0110 0000 0001 0010
3: Desp. Mdor. a la der. 0000 0110 0000 0001 0010
En cada iteración se subraya al bit a evaluar (multiplicador[0]).
Segunda versión del Algoritmo y Hardware de la Multiplicación.
Una observación al hardware de la primera versión es la siguiente: Aunque se suman
registros de 64 bits, en realidad la parte significativa de la suma es de 32 bits, ya que en los
otros 32 se están sumando 0’s. Entonces, es posible reducir la ALU a 32 bits, para ello se
mantendrá al multiplicando fijo (en un registro de 32 bits) y por lo tanto, será necesario
desplazar a la derecha al producto. El producto se mantiene en un registro de 64 bits, por lo
que la suma con el multiplicando, se hará con sus 32 bits más significativos.
La nueva versión para el hardware se muestra en la figura 3.16, mientras que en la figura
3.17 se muestra la nueva versión para el algoritmo. Se conservan las 32 iteraciones y los 3
pasos en cada iteración.
Fig. 3.16 Hardware de la multiplicación (segunda versión)
28
Fig. 3.17 Algoritmo para la multiplicación (segunda versión)
Ejemplo: Segundo algoritmo de la multiplicación
Con este nuevo algoritmo, repetir la multiplicación de 0110dos x 0011dos.
Respuesta:
Nuevamente construiremos una tabla con los resultados de cada iteración:
Iteración Paso Multiplicador Multiplicando Producto
0 Valores iniciales 0011 0110 0000 0000
1
1: 1 => prod = prod + mcando 0011 0110 0110 0000
2: Desp. Producto a la der. 0011 0110 0011 0000
3: Desp. Mdor. a la der. 0001 0110 0011 0000
29
2
1: 1 => prod = prod + mcando 0001 0110 1001 0000
2: Desp. Producto a la der. 0011 0110 0100 1000
3: Desp. Mdor. a la der. 0000 0110 0100 1000
3
1: 0 => No operación 0000 0110 0100 1000
2: Desp. Producto a la der. 0000 0110 0010 0100
3: Desp. Mdor. a la der. 0000 0110 0010 0100
4
1: 0 => No operación 0000 0110 0010 0100
2: Desp. Producto a la der. 0000 0110 0001 0010
3: Desp. Mdor. a la der. 0000 0110 0001 0010
La segunda versión requiere de una menor cantidad de Hardware. Aunque se tiene la
misma cantidad de pasos, es una versión más rápida debido a que la suma de datos de 32
bits es más rápida que la suma de datos de 64 bits.
Versión final del Algoritmo y Hardware de la Multiplicación.
En el hardware mostrado en la figura 3.16 pueden notarse que, el registro del multiplicador
y el registro del producto se desplazan a la derecha, y que cuando el algoritmo comienza no
importa lo que haya en la mitad derecha del registro del producto, por que se va a perder. Y
cuando el algoritmo termina, el registro del multiplicador queda con 0’s, es decir, su valor
se va perdiendo durante el desarrollo del algoritmo.
De manera que puede obtenerse una versión mejorada del hardware, si al comienzo del
algoritmo se coloca al multiplicador a la mitad derecha del producto. Con ello, además de
reducir los recursos, da pie a un algoritmo más rápido, por que en lugar de 2
desplazamientos sólo se realizará 1. En la figura 3.18 se muestra la versión final del
hardware para la multiplicación y en la figura 3.19 se muestra al algoritmo que desarrollará
el control en esta versión final. Puede notarse que en cada iteración se ha reducido a 2 el
número de pasos.
Fig. 3.18 Hardware de la multiplicación (versión final)
30
Fig. 3.19 Algoritmo para la multiplicación (versión final)
Ejemplo: Versión final del algoritmo de la multiplicación
Repetir la multiplicación de 0110dos x 0011dos, con el algoritmo de la figura 3.19.
Respuesta:
En este caso la tabla sólo cuenta con una columna para el multiplicando y otra para el
producto:
Iteración Paso Multiplicando Producto
0 Valores iniciales 0110 0000 0011
1 1: 1 => prod = prod + mcando 0110 0110 0011
2: Desp. Producto a la der. 0110 0011 0001
2 1: 1 => prod = prod + mcando 0110 1001 0001
2: Desp. Producto a la der. 0110 0100 1000
3 1: 0 => No operación 0110 0100 1000
2: Desp. Producto a la der. 0110 0010 0100
31
4 1: 0 => No operación 0110 0010 0100
2: Desp. Producto a la der. 0110 0001 0010
Solo el registro del producto se modifica a lo largo del algoritmo, el multiplicando
permanece sin cambios durante todas las iteraciones.
En estas versiones de la multiplicación no se hace la distinción entre números con signo o
sin signo. Una opción para hacer estas distinciones podría consistir en evaluar los signos de
los operandos y con ello determinar el signo del resultado (basándose en las leyes de los
signos para la multiplicación). Luego, realizar la multiplicación con números positivos y
colocar el signo correspondiente al resultado. Este esquema es muy fácil de entender,
aunque algo complicado y lento para implementar.
Existen otros algoritmos que desde un principio consideran los signos de los operandos,
uno de ellos es el algoritmo de Booth.
3.7 División
La división es la operación complementaria a la multiplicación, nuevamente se realizarán
aproximaciones al hardware y al algoritmo de control, basadas en el algoritmo básico,
luego se realizarán mejoras para alcanzar una versión final más eficiente.
Se ilustra al algoritmo básico dividiendo 101011 entre 100:
1010 Cociente
Divisor 100 101011 Dividendo
- 100
101
- 100
11 Residuo
Los diferentes componentes de la división están relacionados por:
Dividendo = Divisor x Cociente + Residuo
En una división entera el resultado quedará en dos registros, en uno de ellos se tendrá al
cociente y en el otro se tendrá al residuo o resto.
Nuevamente, sólo se considerarán números positivos para simplificar la estructura y
comprensión del algoritmo y hardware de la división.
Primera versión del Algoritmo y Hardware de la División.
La división se fundamenta en restas, en el algoritmo básico se escogen algunos dígitos de la
derecha del dividendo “hasta que alcance” el divisor en los dígitos escogidos. Si la
32
operación es manual, es posible determinar por inspección cuantos dígitos son necesarios
para que “alcance” el divisor en una parte del dividendo. Con hardware, la única manera
para determinar si alcanza un número en otro es por medio de una resta. Si después de
hacer la resta el resultado es mayor o igual que cero, efectivamente, alcanzó el divisor en
una parte del dividendo. Pero si el resultado es menor que cero, significa que no alcanzó el
divisor y habrá que restablecer el valor que el dividendo tenía antes de la resta.
El divisor se colocará a la izquierda de un registro de 64 bits y en cada iteración se
desplazará a la derecha, para obtener el mismo resultado que el algoritmo de la primaria. El
dividendo deberá estar colocado a la derecha de otro registro de 64 bits para que los
operandos sean del mismo tamaño y la resta pueda realizarse, en este mismo registro
quedará el residuo.
El cociente se generará a lo largo del algoritmo, en un registro de desplazamiento a la
izquierda se introducirá un dígito en cada iteración. Si el divisor “alcanzó” en el residuo, se
introducirá por la izquierda un 1 al cociente y si no, se introducirá un 0. Al final del
algoritmo, en este registro estará el cociente.
En la figura 3.20 se muestra el hardware para la división y en la figura 3.21 el algoritmo
que sigue el bloque de control. El algoritmo inicia con una resta y dependiendo del
resultado se determina el valor del bit que se introducirá al cociente. Se requiere de 33
iteraciones por que la primera no tiene efecto, puesto que aún no se ha desplazado al divisor
a la derecha.
Fig. 3.20 Hardware para la división (primera versión)
33
Fig. 3.21 Algoritmo para la división (primera versión)
Ejemplo: Primer algoritmo de la división
Usando números de 4 bits, para reducir espacio, dividir 7diez 2diez. (0111dos x 0010dos).
Respuesta:
Debido a que los números son de 4 bits, el algoritmo requerirá de 5 iteraciones, en la tabla
siguiente se muestran los pasos en cada iteración:
Iteración Paso Cociente Divisor Residuo
0 Valores iniciales 0000 0010 0000 0000 0111
1
1: Res. = Res. – Div. 0000 0010 0000 1110 0111
2b: Res < 0 => +Div, Sll C, C0 = 0 0000 0010 0000 0000 0111
3: Desp. Div. a la der. 0000 0001 0000 0000 0111
34
2
1: Res. = Res. – Div. 0000 0001 0000 1111 0111
2b: Res < 0 => +Div, Sll C, C0 = 0 0000 0001 0000 0000 0111
3: Desp. Div. a la der. 0000 0000 1000 0000 0111
3
1: Res. = Res. – Div. 0000 0000 1000 1111 1111
2b: Res < 0 => +Div, Sll C, C0 = 0 0000 0000 1000 0000 0111
3: Desp. Div. a la der. 0000 0000 0100 0000 0111
4
1: Res. = Res. – Div. 0000 0000 0100 0000 0011
2a: Res > 0 => Sll C, C0 = 1 0001 0000 0100 0000 0011
3: Desp. Div. a la der. 0001 0000 0010 0000 0011
5
1: Res. = Res. – Div. 0001 0000 0010 0000 0001
2a: Res > 0 => Sll C, C0 = 1 0011 0000 0010 0000 0001
3: Desp. Div. a la der. 0011 0000 0001 0000 0001
En cada iteración se subraya en el residuo al bit más significativo, porque este bit determina
si se continuará con el paso 2a o con el paso 2b (indica si el resultado de la resta es mayor o
menor que cero).
Segunda versión del Hardware de la División.
Observando a la figura 3.20 y analizando con detalle el desarrollo del algoritmo, puede
notarse que la parte significativa de la resta es de 32 bits, por que en los otros 32 se están
restando 0’s, por lo que la ALU que realiza las restas puede reducirse a 32 bits. Además, se
consigue el mismo resultado si en lugar de desplazar el divisor a la derecha, éste se
mantiene fijo y se desplaza al registro del residuo a la izquierda.
Debe recordarse que al comienzo del algoritmo, el registro del residuo deberá contener al
dividendo en sus 32 bits más a la derecha.
En la figura 3.22 se muestra la segunda versión del hardware de la división; la resta se
realiza entre los 32 bits más significativos del residuo y el divisor. No se muestra al
algoritmo que sigue el control, porque prácticamente sería el mismo al mostrado en la
figura 3.21, con la única diferencia que en el paso 3, en lugar de desplazar a la derecha al
divisor, se desplazará a la izquierda al residuo.
35
Fig. 3.22 Hardware para la división (segunda versión)
Versión final del Algoritmo y Hardware de la División.
El hardware de la figura 3.22 puede mejorarse si se observa que tanto el registro del
cociente y el del residuo se desplazan a la izquierda; además, en cada desplazamiento que
realiza el registro del residuo, se introduce un 0 en el bit menos significativo, de manera
que cuando el algoritmo termina, el residuo queda en los 32 bits más significativos,
mientras que los 32 bits menos significativos quedan llenos de 0’s.
Entonces, el hardware puede modificarse de manera que los bits que se introduzcan sean
los que correspondan al cociente, con ello, además de reducir un poco los recursos de
hardware, produce un algoritmo más rápido, puesto que en lugar de realizar dos
desplazamientos, sólo se realizará 1. Al final del algoritmo, en un registro de 64 bits se
tendrá al residuo (en los 32 bits más significativos) y al cociente (en los 32 bits menos
significativos).
Otra observación importante es que en la primera iteración siempre el divisor se resta de 0,
esta resta no tiene sentido porque siempre será menor que 0. Es posible mejorar al
algoritmo si antes de la primera resta se desplaza a la izquierda el residuo, con ello el
número de iteraciones se reduce a 32, sin embargo, para compensar este desplazamiento
inicial, al concluir las 32 iteraciones, los 32 bits más significativos deben desplazarse una
posición a la derecha, para obtener el resultado correcto.
En las figuras 3.23 y 3.24 se muestran la versión final del hardware y del algoritmo de la
división, respectivamente.
36
Fig. 3.23 Hardware para la división (versión final)
Fig. 3.24 Algoritmo para la división (versión final)
37
Ejemplo: Versión final del algoritmo de la división
Con la versión final del algoritmo, dividir 7diez 2diez. (0111dos x 0010dos).
Respuesta:
Con esta nueva versión sólo se requerirá de 4 iteraciones y en cada iteración se realizarán
dos pasos:
Iteración Paso Divisor Residuo
0 Valores iniciales 0010 0000 0111
Desp. Res. a la izq. 1 0010 0000 1110
1 2: Res. = Res. – Div. 0010 1110 1110
3b: Res < 0 => +Div, Sll R, R0 = 0 0010 0001 1100
2 2: Res. = Res. – Div. 0010 1111 1100
3b: Res < 0 => +Div, Sll R, R0 = 0 0010 0011 1000
3 2: Res. = Res. – Div. 0010 0001 1000
3a: Res > 0 => Sll R, R0 = 1 0010 0011 0001
4 2: Res. = Res. – Div. 0010 0001 0001
3a: Res > 0 => Sll R, R0 = 1 0010 0010 0011
Desp. Mitad izq. de Rem. a la der. 0010 0001 0011
Después de las 4 iteraciones se desplaza a la izquierda la mitad izquierda del registro del
residuo. En los 4 bits menos significativos se tiene al cociente.
El hardware para la multiplicación es prácticamente el mismo que el hardware para la
división, la diferencia estriba en el algoritmo de control.
Los registros en los que se ubicará el resultado (en ambos casos) son conocidos como HI y
LO. Al realizar una multiplicación, HI contendrá la parte alta del producto y LO la parte
baja. En el caso de una división, HI quedará con el residuo, mientras que LO contendrá al
cociente.
3.8 Números y operaciones Punto Flotante
Otros tipos de datos importantes son los números de punto flotante, los cuales son una
aproximación a los números reales. La mayoría de computadoras utilizan al estándar IEEE
754 el cual establece una representación de 32 bits para números en punto flotante en
simple precisión y 64 bits para números en punto flotante en doble precisión (MIPS no es la
excepción, también emplea ese formato).
El estándar IEEE 754 representa a los números en notación científica normalizada (en base
2). La versión normalizada deja un dígito a la izquierda del punto decimal y los dígitos
restantes se sitúan a la derecha; por ejemplo, el número: 0.000111, una vez normalizado es
38
1.11 x 2-4
y el número 11000000 al normalizarse queda como: 1.1 x 27, de manera que
cualquier número puede ser aproximado con una expresión de la forma:
1.xxxxxxdos x 2yyyyyy
A la cadena xxxxxx se le conoce como mantisa y a la cadena yyyyyy se le conoce como
exponente.
Pero además, los números en punto flotante pueden ser positivos o negativos, de manera
que en la representación de un número debe considerarse un campo para el signo, un campo
para el exponente y otro para la mantisa. De los 32 bits que se disponen en simple
precisión, la distribución de los campos es:
31 30 29 28 . . . 24 23 22 21 20 19 . . . 3 2 1 0
signo Exponente Mantisa
1 bit 8 bits 23 bits
Se han dedicado 8 bits para el exponente, lo que significa que se tienen 256 combinaciones,
de las cuales deben considerarse algunas mayores y otras menores que cero, para
representar números muy pequeños y números muy grandes. Sin embargo y debido a que es
más fácil manipular números sin signo, las combinaciones se conservarán desde el valor 0
hasta el 255, y para obtener el valor representado, al valor del exponente se le restará un
número conocido como desplazamiento.
La mantisa corresponde a los dígitos que quedan a la derecha del punto decimal, después de
la normalización. La representación contiene un 1 que no se escribe por que todos los
números normalizados lo incluirán.
Entonces, a partir de los 32 bits (conteniendo 1’s y 0’s), el valor representado
corresponderá a:
(-1)signo
x 1.mantisa x 2exponente - desplazamiento
El valor del desplazamiento es de 127 para simple precisión, por lo que el número más
cercano al cero se obtiene con una cadena de 32 ceros (correspondería a 1 x 2-127
), y está en
el orden de 10-39
. Por convención, esta combinación es interpretada como 0.0, puesto que
en simple precisión no es posible encontrar un número más cercano al 0.
El número más alejado del 0 se obtiene con una cadena de 1s (a excepción del bit de signo,
que puede tener 0). Esta combinación está en el orden de 1038
, que aunque es un número
grande, difiere de lo que consideramos como infinito.
Las operaciones en punto flotante pueden producir resultados más pequeños (bajo flujo) o
resultados más grandes (sobre flujo) de los que se pueden representar, por lo que en
ocasiones será necesario contar con mas bits para la representación.
39
El estándar IEEE 754 incluye una representación de doble precisión, la cual utiliza 64 bits,
por lo que los tamaños de los campos crecen significativamente:
31 30 29 28 . . . 21 20 19 18 17 . . . 3 2 1 0
signo Exponente Mantisa
1 bit 8 bits 23 bits
31 30 29 28 . . . 3 2 1 0
Mantisa
32 bits
Para el campo del exponente se dispone de 11 bits, mientras que para la mantisa se tienen
52; con ello, el número más cercano al 0 está en el orden de 10-308
y el más alejado del 0
está en el orden de 10308
.
Para obtener el valor que se está representando, se emplea la misma expresión utilizada en
simple precisión, con la diferencia de que el valor del desplazamiento será de 1023.
Ejemplo: Conversión de binario a decimal.
¿Qué número decimal representa la palabra?
1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 . . . .
signo exponente mantisa
Respuesta:
Aplicando directamente la expresión:
(-1)signo
x 1.mantisa x 2exponente – desplazamiento
= (-1)1x1.0100dos x 2
129 – 127
= - 1.01dos x 22 = - 101dos = - 5.0 diez
Ejemplo: Representación en Punto-Flotante
¿Cuál sería la representación del –0.75diez en simple precisión?
Respuesta:
El número –0.75diez = -3/4 diez = -3/22 diez = -11dos / 2
2 diez = - 0.11dos
En notación científica normalizada se tendría: - 1.1 x 2-1
Comparando con la expresión: (-1)signo
x 1.mantisa x 2exponente – 127
se tiene que:
40
exponente – 127 = -1, de manera que exponente = 127 – 1 = 126
Por lo tanto, la representación del –0.75diez es:
1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0. . . .
signo exponente mantisa
3.9 Suma en punto flotante.
Para entender cómo sería el algoritmo y hardware para sumar números en punto flotante, se
revisa como se realiza la operación con números en decimal. Se sumarán los números
9.999diez x 101 con 1.610diez x 10
-1, suponiendo que sólo es posible conservar cuatro dígitos
decimales en la mantisa (uno a la izquierda del punto decimal) y dos en el exponente.
a) Para que la suma sea correcta, primero se deben alinear los números adecuadamente, es
decir, se debe buscar que el exponente sea el mismo para los dos números. Para ello, se
desplaza al número con el exponente más pequeño, para que coincida con el del
exponente más grande:
1.610diez x 10-1
= 0.1610diez x 100 = 0.01610diez x 10
1
Pero como sólo se han considerado 4 dígitos, el número anterior se redondeará a:
0.016diez x 101
b) Ahora es posible sumar las mantisas:
9.999 diez
+ 0.016 diez
10.015 diez
La suma es 10.015 x 101.
c) Este resultado no está normalizado, por lo que el siguiente paso consistirá en
normalizarlo, para obtener: 1.0015 x 102.
d) Finalmente, puesto que solo se pueden almacenar 4 dígitos para la mantisa, el resultado
debe redondearse a 4 dígitos, el redondeo consiste en aproximar al número inmediato
superior el penúltimo dígito, si el dígito menos significativo es mayor o igual a 5.
Obteniéndose como resultado final:
1.002 x 102
En el inciso (c) al normalizar la suma puede ocurrir un error de sobre flujo si el valor del
exponente es mayor al que se puede representar o bajo flujo en caso de que sea menor. El
algoritmo para la suma en punto flotante se muestra en la figura 3.25, en donde se muestra
que después de un redondeo, puede ser necesaria otra normalización. La detección del
41
sobre flujo o bajo flujo depende de la precisión que se esté utilizando para la representación
de los números.
Fig. 3.25 Algoritmo para la suma en punto flotante
Ejemplo: Suma en punto flotante.
Sumar los números 0.5diez y –0.4375 diez en binario, usando el algoritmo de la figura 3.25
Respuesta:
Primero obtendremos la versión binaria normalizada, suponiendo 4 bits de precisión:
0.5diez = 1/2 diez = 1/21
diez = 0.1dos = 0.1dos x 20 = 1.000dos x 2
-1
- 0.4375diez = - 7/16 diez = - 7/24
diez = - 0.0111dos = 0.0111dos x 20 = - 1.110dos x 2
-2
Ahora siguiendo el algoritmo:
1) Se desplaza al número con exponente más pequeño (a la derecha), hasta alinearlo con el
exponente mayor:
- 1.110dos x 2-2
= - 0.111dos x 2-1
42
2) Se suman las mantisas: 1.000dos x 2-1
+ (- 0.111dos x 2-1
) = 0.001dos x 2-1
3) Se normaliza la suma, verificando si existe sobre flujo o bajo flujo:
0.001dos x 2-1
= 0.010dos x 2-2
= 0.100dos x 2-3
= 1.000dos x 2-4
Puesto que 127 > - 4 > - 126, no hay sobre flujo ni bajo flujo (El exponente desplazado
sería – 4 + 127 = 123, y está entre 1 y 254).
4) Redondeo de la suma: 1.000dos x 2-4
Ya está redondeada, por lo que el resultado es:
1.000dos x 2-4
= 0.0001000dos = 1/24
diez = 1/16diez = 0.0625diez
Muchas máquinas dedican hardware para ejecutar operaciones de punto flotante tan rápido
como sea posible. En la figura 3.26 se esboza la organización básica del hardware para la
suma en punto flotante.
Fig. 3.26 Hardware requerido para la suma en punto flotante
43
3.10 Multiplicación en punto flotante
Para entender cómo se realiza la multiplicación en punto flotante, se inicia con números
decimales en notación científica, multiplicando 1.110diez x 1010
con 9.200diez x 10-5
.
Suponiendo que sólo es posible conservar cuatro dígitos decimales en la mantisa (uno a la
izquierda del punto decimal) y dos en el exponente.
a) A diferencia de la suma, el exponente del producto se calcula sumando los exponentes
de los factores.
Nuevo exponente = 10 + (-5) = 5
Con los exponentes desplazados el nuevo exponente es erróneo, dado que 10 + 127 =
137, y –5 + 127 = 122, por lo tanto:
Nuevo exponente = 137 + 122 = 259
El problema es que el desplazamiento se realizó dos veces (una por cada exponente), de
manera que el exponente desplazado es:
Nuevo exponente = (137 + 122) - 127 = 259 – 127 = 132
b) Luego se deben multiplicar las mantisas:
1.110diez
x 9.200diez
0000
0000
2220
9990
10212000diez
Hay tres dígitos a la derecha de cada factor, de manera que deberá haber 6 dígitos a la
derecha del punto decimal del producto: 10.212000diez
Como sólo se pueden mantener 3 dígitos a la derecha del punto decimal, el producto
resultante sería: 10.212diez x 105
c) Este resultado no está normalizado, al normalizarlo se obtiene: 1.0212diez x 106
Después de la multiplicación, el producto puede ser desplazado a la derecha, sumando 1
al exponente, o bien desplazado a la izquierda restándole 1 al exponente. Por lo tanto,
en este paso debe verificarse la presencia de un sobre flujo o bien de un bajo flujo.
d) Se debe redondear al producto a una mantisa de 4 dígitos, de manera que:
1.0212diez x 106 es redondeado a 1.021diez x 10
6
44
e) El signo del producto depende de los signos de los factores, si son iguales el producto
es positivo y si son diferentes, el producto será negativo.
En este caso el resultado es: + 1.021diez x 106
El signo en la suma fue determinado por la suma de las mantisas, pero en el producto el
signo se determina por los signos de los operandos. En la figura 3.27 se muestra el
algoritmo de multiplicación binaria en punto flotante. En donde se muestra que después de
la normalización, es posible que ocurra un error de sobre flujo o bajo flujo; y después del
redondeo, es posible que se requiera normalizar nuevamente.
Fig. 3.27 Algoritmo para la multiplicación en punto flotante
45
Ejemplo: Producto en punto flotante.
Multiplicar 0.5diez x - 0.4375 diez en binario, usando el algoritmo de la figura 3.27.
Respuesta:
0.5diez = 1.000dos x 2-1
- 0.4375diez = - 1.110dos x 2-2
Siguiendo el algoritmo:
1) Se suman los exponentes: -1 + (-2) = -3
2) Se multiplican las mantisas:
1.000 dos
x 1.110 dos
0000
1000
1000
1000
1110000 dos
El producto es 1.110000 dos x 2-3
, si se va a mantener en 4 bits se obtiene: 1.110 dos x 2-3
3) El producto esta normalizado y no hay error de sobre flujo o bajo flujo.
4) El redondeo no cambió al producto.
5) Los signos de los operandos son diferentes, de manera que el resultado es:
- 1.110 dos x 2-3
Instrucciones de Punto Flotante en MIPS
MIPS soporta a los formatos del estándar IEEE 754 para simple y doble precisión, con las
instrucciones:
Suma en simple precisión (add.s) y en doble precisión (add.d)
Resta en en simple precisión (sub.s) y en doble precisión (sub.d)
Multiplicación en simple precisión (mul.s) y en doble precisión (mul.d)
División en simple precisión (div.s) y en doble precisión (div.d)
Comparación en simple precisión (c.x.s) y en doble precisión (c.x.d), donde x puede ser:
igual (eq), no igual (neq), menor que (lt), menor o igual que (le), mayor que (gt) y
mayor o igual que (ge)
Brinco en punto flotante sobre una condición verdadera (bclt) y sobre una condición
falsa (bclf).
46
La comparación en punto flotante ajusta un bit a falso o verdadero, dependiendo de la
condición de la comparación; y el brinco en punto flotante decide si se realizará o no el
brinco, dependiendo de la condición.
Los diseñadores de MIPS decidieron agregar un conjunto separado de registros de punto
flotante, llamados $f0, $f1, $f2, . . .- usados ya sea para simple o doble precisión. Por lo
tanto, también incluyeron instrucciones de carga en punto flotante (lwcl) y almacenamiento
(swcl). Los registros base para las transferencias de datos en punto flotante continúan
siendo registros enteros.
El código MIPS para cargar 2 números de punto flotante de simple precisión, desde la
memoria, para sumarlos y almacenar el resultado en memoria es:
lwcl $f4, x($sp)
lwcl $f6, y($sp)
add.s $f2, $f4, $f6
swcl $f2, z($sp)
Un registro en doble precisión en realidad se forma con dos registros consecutivos de
simple precisión, usando el número par como el nombre del registro.
TAREA 6
1. Construir una tabla donde se muestren los resultados de multiplicar a 13diez con 3diez
dividir al 13diez entre el 3diez, con base en el algoritmo mostrado en la versión final de la
división.
2. Mostrar la representación binaria IEEE 754 en simple precisión para los números
10.5diez y –2/3diez. (Aproxime empleando todos los bits de la mantisa).
3. Siguiendo los algoritmos de la suma y multiplicación en punto flotante, sumar y
multiplicar los números: 6.402 x 101 y 9.510x 10
-1. Tratar a los números en base 10 y
suponer que sólo se tiene 4 dígitos para la mantisa (3 a la derecha del punto decimal).
Practica de Laboratorio 3:
1. Combine el Hardware de las figuras 3.18 y 3.23 en un diseño modular en VHDL,
limitado para trabajar con números de 16 bits (el resultado sería de 32 bits). El módulo
del control deberá ser una máquina de estados y se le deberán agregar 2 entradas y 1
salida externas.
Una entrada para seleccionar si realizará una multiplicación o división (0
multiplicación y 1 división), sólo se evaluará al inicio del proceso.
Una entrada para indicar el inicio de la operación.
Una salida que indicará que la operación (multiplicación o división) ha terminado.