Mejora de los algoritmos de latencia variable para el cálculo de la división, la raíz cuadrada y sus recíprocos

Resumo

RESUMEN En las dos décadas pasadas se han hecho múltiples avances en el diseño de microprocesadores. Estos avances han hecho posible la construcción de aplicaciones que resuelven problemas más complejos. Estas aplicaciones demandan cada vez más velocidad y requerimientos de rendimiento más severos. Por estas razones, existe una fuerte demanda de cálculos en punto flotante de alto rendimiento. La división, el recíproco, la raíz cuadrada y la raíz cuadrada recíproca en punto flotante son funciones matemáticas muy importantes en este tipo de aplicaciones. Un calculo lo más rápido y exacto posible de estas operaciones matemáticas se ha vuelto irrenunciable. Se ha demostrado que el cómputo eficiente de estas funciones produce mejoras muy notables en el rendimiento de los procesadores. La importancia cada vez más grande de la división, el recíproco, la raíz cuadrada y la raíz cuadrada recíproca impone la necesidad de algoritmos para el cálculo de estas funciones que sean más eficientes. Con el paso del tiempo, las soluciones más eficientes se han decantado por el uso de algoritmos multiplicativos debido a su rápido ritmo de convergencia y la posibilidad del reuso del multiplicador ya existente en el sistema. A lo largo de los últimos años los algoritmos multiplicativos han sido objeto de estudios. La mayoría de ellos han sido dedicados a la mejora de la parte que calcula el resultado. Se consiguieron buenos resultados a través de la obtención de muy diversas formas de obtener buenas aproximaciones iniciales para reducir el número de iteraciones. Por otro lado, también se han realizado avances en la implementación del algoritmo para una obtención más eficiente del resultado. Sin embargo, este tipo de algoritmos tienen un problema que sigue lastrando su rendimiento. No producen de manera directa ni el resultado directamente redondeado ni el resto. Las soluciones más eficientes adoptan un método de redondeo consistente en la modificación del resultado mediante la suma de una constante y el cálculo del resto . En función del valor del resto y el valor de los bits de redondeo se decide la acción de redondeo adecuado. Este cálculo del resto supone la realización de la multiplicación que en algunos casos puede llegar a ser una penalización del 30% del tiempo de cálculo total. Todos estos aspectos básicos de introducción al tema han sido descritos en el primer capítulo dedicado a los fundamentos de los algoritmos para el cálculo de la división, la raíz cuadrada y sus recíprocos. También se describe cómo se redondean tradicionalmente estos algoritmos. Se han propuesto, pues, en este trabajo una serie de métodos para mejorar los métodos de redondeo existentes hasta el momento. Todos ellos son métodos de latencia variable, es decir, métodos que consiguen evitar el cálculo del resto en un porcentaje de casos respecto del total de casos posibles. Evidentemente, los métodos de latencia variable serán tanto mejores cuanto menor sea el porcentaje de casos en los que es necesario el cálculo del resto. A continuación se presentan las principales contribuciones descritas a lo largo de este trabajo: En el segundo capítulo se presenta un trabajo previo a la presentación de los distintos métodos de redondeo. Una de los requisitos necesarios para realizar el redondeo de manera adecuada es obtener el resultado con una precisión y una exactitud adecuadas. Se presenta un método de diseño para unidades de división, raíz cuadrada y sus recíprocos para el algoritmo de Goldschmidt (el mismo método para el algoritmo de Newton-Raphson se presenta en un apéndice al final de este trabajo). Este método permite determinar el tamaño óptimo de las operaciones intermedias para un tamaño de aproximación inicial y un número de iteraciones determinado a partir de los requerimientos de precisión y exactitud. Este método está basado en un análisis preciso del error que tiene en cuenta las distintas contribuciones al error del resultado del algoritmo para una iteración dada. De este análisis se obtiene una expresión analítica del error final del resultado de una iteración cualquiera. A través de esta expresión es posible calcular límites para el valor de dicho error. A través de estas expresiones, fijando el tamaño de la aproximación inicial se obtiene el tamaño de palabra óptimo para las operaciones intermedias. Obtener un tamaño de palabra óptimo reduce entre otras cosas el tamaño del multiplicador produciendo un ahorro de área y de tiempo en las implementaciones hardware. Como resultado, este método fue aplicado al rediseño de la unidad del AMD-K7. Se obtuvieron mejoras significativas en forma de reducción del número de productos parciales del multiplicador, es decir, de su tamaño. Tanto con respecto a la propia solución como a otros métodos previos que ya mejoraban dicha implementación El tercer capítulo presenta el primero de los métodos de latencia variable que mejora la e ciencia de los métodos preexistentes. Este método es una modificación de los métodos previos y es independiente del algoritmo multiplicativo utilizado. Basta con obtener el resultado con la exactitud adecuada. Permite una reducción de los casos donde el cálculo del resto es necesario en un 40 %. El cálculo del resto se produce en un 15% de las ocasiones cuando se usa un bit extra en la aproximación al resultado a redondear. Este porcentaje es de un 9% si se usan dos bits en dicha aproximación. Porcentajes aun menores se consiguen si se aumentan el número de bits extra de la aproximación. Este método está basado en utilizar información adicional para evitar el cálculo del resto en más casos que en el método tradicional. En el redondeo convencional, el resultado obtenido del algoritmo se modifica para obtener otra aproximación con algunos bits extra, además de aquellos requeridos por la precisión mínima necesaria. Teniendo en cuenta el valor de estos bits extra se decide si es necesario o no realizar el cálculo del resto. En este nuevo método se examinan, también, bits del resultado obtenido directamente del algoritmo. Examinando estos bits, además de los usados tradicionalmente, se reduce el número de casos en los que es necesario el cálculo del resto. El cuarto capítulo contiene la descripción de un nuevo método de redondeo. Este forma parte de un grupo de dos métodos, que se presentan en este capítulo y el siguiente, que son completamente nuevos. El resultado de la aplicación de este método es que se consigue evitar la latencia asociada al cálculo del resto en una gran parte de los casos. Concretamente, al 9% de los casos para la división y el recíproco, y al 15% en el caso de la raíz cuadrada y la raíz cuadrada recíproca. Estamos, entonces ante un método de latencia variable. El método se compone de la obtención del valor del resto en paralelo con la ejecución del algoritmo y un nuevo método de redondeo. Se propuso un método que obtiene el resto del resultado directamente obtenido del algoritmo. El cálculo del resto implica la operación de multiplicación. Esto obligó al diseño de un método basado en esta aproximación al resultado sin modificar. Consiste en comparar el resto con constantes fácilmente calculables. La constante utilizada depende de los últimos bits del resultado obtenido. Los resultados obtenidos muestran importantes reducciones en el número de veces en que hay que calcular el resto de manera tradicional respecto de trabajos previos. El ultimo de los capítulos presenta también un método para el algoritmo de Goldschmidt que obtiene un valor para el resto en paralelo con su ejecución. Evita el cálculo convencional del resto en la mayora de los casos. Dicho cálculo se realiza en el 9% de las veces para la división y el recíproco. 12% en el caso de la raíz cuadrada y la raíz cuadrada recíproco. Igual que en el caso anterior, el valor del resto obtenido corresponde al resultado del algoritmo sin ninguna modificación. La diferencia es que el cálculo del resto es mucho más sencillo que en el caso anterior. De esta manera se ahorra la necesidad de un multiplicador adicional. Esto provoca un ahorro de hardware muy significativo en las implementaciones respecto del método anterior.