UNIDAD 3: Aritmética de las computadoras. 3.1. Introducción Hasta el momento hemos estudiado algunas métricas para la obtención del rendimiento (segundos, ciclos, instrucciones). También estudiamos el concepto de abstracción y en particular nos interesamos por la abstracción que vincula al hardware con el software de mas bajo nivel, a esta abstracción le denominamos: Arquitectura del repertorio de instrucciones o simplemente Arquitectura de Computadoras. Ya repasamos el repertorio de instrucciones MIPS, que como observamos, es lo suficientemente completo como para implementar cualquier programa. En esta sección iniciaremos con la implementación del hardware, en particular en esta unidad se revisará la aritmética de las computadoras para obtener una Unidad Aritmético Lógica personalizada al repertorio de instrucciones previamente estudiando. Además estudiaremos el mecanismo para realizar multiplicaciones y divisiones con base en nuestra unidad aritmético lógica. Finalmente daremos un repaso a la representación de los números en punto flotante y revisaremos las operaciones de suma y producto en punto flotante. Esbozaremos 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 mas 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á mas a la izquierda (menos significativa). Por ejemplo, si tenemos el número 1011dos, en base 10 nos representa a: (1 x 23) + (0 x 22) + (1 x 21) + (1 x 20) 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

1 0 1 1

0 0 0 0

0 0 0 0

0 0 0 0 0 0 0 0 (32 bits de ancho)

Los números los representamos colocando el menos significativo a la derecha (posición 0) y al mas significativo a la izquierda (posición 31). Como se utilizan 32 bits para representar un número, entonces podemos representar 232 números diferentes, desde el número 0 hasta el 232 – 1 (4, 294, 967, 295diez) : 0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111

0000dos 0001dos 0010dos . . 1101 dos 1110 dos 1111 dos

= 0diez = 1diez = 2diez . . = 4, 294, 967, 293diez = 4, 294, 967, 294diez = 4, 294, 967, 295diez

Es importante tener en mente que los patrones de bits contienen una representación de los números, en realidad tenemos un conjunto infinito de números; 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 necesitamos una representación que haga la distinción de los positivos de los negativos. Una solución obvia consistiría en dedicar uno de los bits para que determine el signo, dejando los 31 bits restantes para la magnitud. A esta representación se le conoce como magnitud y signo, tiene diferentes inconvenientes. En principio, a donde se colocaría el signo, a la derecha o a la izquierda de la magnitud, existen las dos posibilidades. Luego, el hardware que trabaja con números usando magnitud y signo, requiere 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 en un ciclo repetitivo, si el ciclo termina cuando una variable alcanza 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 ha sido descartada. En la búsqueda de otras alternativas se utilizó el complemento de los números positivos para obtener el correspondiente negativo (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 mas 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. 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 . . 0111 0111 0111 1000 10000 10000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111 0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111 0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111 0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111 0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111 0000 0000 0000 . . 1111 1111 1111

0000 0000 0000 . . 1111 1111 1111 0000 0000 0000 . . 1111 1111 1111

0000dos 0001dos 0010dos . . 1101dos 11110dos 1111dos 0000dos 0001dos 0010dos . . 1101 dos 1110 dos 1111 dos

= 0diez = 1diez = 2diez . . = 2, 147, 483, 645diez = 2, 147, 483, 646diez = 2, 147, 483, 647diez = - 2, 147, 483, 648diez = - 2, 147, 483, 647diez = - 2, 147, 483, 646diez . . = - 3diez = - 2diez = - 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 esta balanceada por que el número - 2, 147, 483, 648diez no tiene un número positivo correspondiente. Este hecho llega a ser una preocupación de los desarrolladores de software, en contraparte con la representación de magnitud y signo que además preocupaba a los desarrolladores de hardware. El hecho de que el bit mas 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 Respuesta: Considerando la posición de cada bit tenemos: (1 x -231) + (1 x 230) + (1 x 229) + . . . + (1 x 22) + (0 x 21) + (0 x 20) 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 si el signo del resultado de una operación no corresponde con el signo esperado, por ejemplo, si sumamos dos números positivos relativamente grandes, 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 manejarán variables que puedan tomar valores positivos o negativos, y en otras ocasiones sólo se requerirá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 tipo int es para tratar enteros con signo y el tipo unsigned int es para tratar números sin signo. Las comparaciones tratan con esta dicotomía, si un número tiene un 1 en su bit mas significativo y es tratado en complemento a 2, será un numero negativo y por lo tanto será menor que todos aquellos que tengan 0 en su bit mas significativo. Pero si el mismo número es interpretado como entero sin signo, será mayor que todos aquellos que tengan 0 en su bit mas significativo. Estas situaciones deben 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 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 mas 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

Otra idea que habrá que considerar durante la implementación es la siguiente, en el repertorio estudiado se consideraron instrucciones que manejan constantes de 16 bits. Cuando estas constantes son operadas por medio de la ALU con otro operando de 32 bits, que ocurre con los 16 bits que completan a la constante, ¿Cuál debe ser su valor? Si se trabajan números en complemento a 2, su valor dependerá del bit mas significativo de la constante (el bit 15) si este bit es 0 no hay problema, se completa con 0’s y la magnitud se conserva (los 0’s a la derecha no tienen valor), pero si se trata de un 1, al completar con 1’s, ¿también se conservará la magnitud? Si, se conserva la magnitud por que al extender a 32 bits se debe seguir manteniendo el hecho de que un número sumado a su complemento debe generar una cadena de 32 unos, de manera que si en un número positivo se tiene una cantidad infinita de 0’s a su derecha, en un número negativo se debe tener un número infinito de 1’s a su derecha. Finalmente, en ocasiones resulta mas fácil utilizar al sistema octal o al hexadecimal para la representación y manipulación de los números, esto por que 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, cada dígito en octal corresponderá a 3 bits y cada dígito en hexadecimal tendrá una correspondencia de 4 bits. 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 en que las realizamos en base 10, es decir, de derecha a izquierda se va sumando dígito a dígito y si se el resultado es mayor al dígito mas 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 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

cin 0 1 0 1 0 1 0 1

s 0 1 1 0 1 0 0 1

cout 0 0 0 1 0 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 mas significativo:

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 mas significativo”, cuando el minuendo es menor que el sustraendo. Sin embargo a nivel de hardware esto es mas díficil, lo mas 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 mas 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, solo en algunos casos tiene sentido hablar de sobreflujo. Sobre todo cuando se trabaja en complemento a 2, por ejemplo, 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

A+B A+B A–B A–B

0