División and square root for mobile and scientific computing markets

Resumo

En esta Tesis se analizan los algoritmos para el cículos de la división y la raíz cuadrada para una representación punto flotante con simple y doble precisión y se proponen varias implementaciones alternativas. Los aspectos básicos relacionados con la representación punto flotante, modos de redondeo, valores especiales y excepciones, se resumen en el capítulo 1. El uso que se hace de las funciones de división y raíz cuadrada depende, en gran medida, del mercado al que se dirige la implementación. Por ejemplo, en mercados de computación móvil, tales como PDAs, tablet PC, dónde se requiere la ejecución de aplicaciones de internet, visiónde fotogramas, presentaciones, etc. no se realiza un uso masivo de estas operaciones; por este motivo, una representación de punto flotante con precisión simple es suficiente. Por otra parte, en estos segmentos de mercado, se imponen procesadores con una arquitectura de bajo coste y baja complejidad, pero con rendimiento aceptable. El algoritmo Newton-Raphson (N-R) modificado para cálculo del recíproco y división, que se propone en esta memoria, puede ser adecuado para este mercado. Otra de las implementaciones propuestas, raíz cuadrada de tabla de aproximación inicial (Look.Up Table, LUT) está basado en una modificación del algoritmo N-R. Sin embargo, su rendimiento es algo deficiente, porque cada interación requiere tres ciclos y son necesarias varias iteraciones. El númro total de ciclos que se necesitan para el cálculo de la raíz cuadrada con este algoritmo es, aproximadamente, 50. Creemos que es necesario profundizar todavía más en este algoritmo para lograr una implementación eficiente. Estas funciones son frecuentes en aplicaciones de computación gráfica 3D, aplicaciones de cálculo científico, aplicaciones matemáticas, etc. La mayor parte de estas aplicaciones necesitan utilizar una representación punto flotante de doble precisión. En estos campos de aplicación, el procesador tiene una arquitectura de alto rendimiento con niveles de complejidad y coste aceptables. Otro de los algoritmos propuestos, el método AQA (Accurate Quotient Aproximation) puede ser de utilidad. Además, este método podrá ser utilizado para procesamientos futuros orientados a aplicaciones móviles. Para aumentar el rendimiento de estas implementaciones, la aproximación inicial se obtiene mediante la LUT o la LUT combinada con algoritmos de aproximación lineal o cuadrática para reducir el área necesaria. Esta aproximación inicial está acoplada a las interacciones del algoritmo N-R, el algoritmo de Goldschmidt (GLD) y los algoritmos de dígito recurrencia (DR). En el capítulo 2, se discute de forma detallada la obtención de la aproximación inicial y los algoritmos N-R, GLD y DR. Estas funciones son lentas porque efectúan secuencias de sumas y rests, multiplicaciones y suma-multiplicación, bloqueando la unidad de punto flotante del procesador (FPU) durante el círculo. Algunos procesadores implementan estas funciones en software, por ejemplo el Itanium, y otros en hardware, tales como procesadores de IBM y AMD. La implementación software proporciona un alto grado de paralelismo y no bloquea la FDU, sin embargo su rendimiento es bastante pobre. Las implementaciones hardware obtienen mejores rendimentos, pero a costa de una complejidad y coste mayores. Muchos diseñadores están dispuestos a sacrificar la velocidad para obtener costes y complejidad menores. El rendimiento y la complejidad dependen de la precisión, y la precisión depende a su vez del mercado al que está dirigido el procesador y de los requerimientos de este mercado. En esta memoria se propone un método, el método AQA modificado, que proporciona mejoras significativas en el rendimiento, con una mayor eficiencia en términos de área de silicio que los procesadores convencionales utilizados para cáclulos en precisión simple. En el capítulo 3 se describe una modificación del algoritmo N-R sin LUT para el cálculo del recíproco, que es la implementación de mayor eficiencia en términos de área. Es un algoritmo de latencia variable, con convergencia lineal que requiere un máximo de 22 iteraciones. Un algoritmo de latencia variables es útil en divisores auto-controlados, dónde la capacidad de procesamiento depende de la aplicación. De esta forma, se puede reducir el consumo de potencia sin sacrificar el rendimiento. Para evaluar el método propuesto utilizamos multiplicadores de radix 4 y radix 8. El resultado de la evaluación muestra que puede haber un ligero incremento de tiempo debido a los componentes extra que se necesitan, recodificador de Booth radix 8 y recodificación entre representaciones redundantes. Hemos comparado el método propuesto con implementaciones en procesadores actuales (Tabla 3.4). El método propuesto puede ser implementado en un multiplicador radix 4 y un multiplicador radix 8 con un pequeño incremento de área con respecto al área del multiplicador integrado en el procesador. Por otra parte, se observa un incremento en el rendimiento con respecto al procesador Itanium y a los procesadores de IBM, pero una pérdida con respecto al IBM 603eTM y los procesadores de AMD. Esta pérdida es debida a que se retiran 1,09 bits por interacción y no hay disponible una LUT de tamaño elevado. Por lo tanto, el rendimiento es parecido al rendimiento medio de los procesadores actuales. En el capítulo 4, se propone una modificación del método AQA para división y raíz cuadrada, utilizando una LUT, para aplicaciones de cálculo de alto rendimiento. Esta implementación ofrece algunas estrategias atractivas adicionales a los algoritmos N-R convencional, GLD, DR y Cyrix, que se discuten más adelante. Para evaluar el algoritmo AQA modificado hemos utilizado el multiplicador radix 4 de la FPU del IBM 603TM, orientado a aplicaciones móviles, y el multiplicador radix 8 de la FPU del IBM G5, orientado a aplicaciones de alto rendimiento; en ambos casos se ha utilizado una representación de doble precisión (ver Tabla 4.7). La comparación muestra que se obtiene una mayor eficiencia en términos de área y un mayor rendimiento. Se obtiene una reducción de área respecto a implementaciones tradicionales basadas en LUT. Las principales contribuciones de las propuestas presentadas en la Tesis se resumen a continuación. Con respecto al algoritmo N-R modificado para el círculo del recíproco, podemos destacar que no necesita tablas para la aproximación inicial y que el rendimiento se mantiene similar al obtenido con los procesadores actuales, debido a que se están calculando los resultados intermedios en representación redudante. La aproximación inicial es el complemento a dos del divisor, que puede obtenerse en paralelo con la suma de los productos parciales. ¿Cada iteracción es un ciclo, a diferencia de los dos ciclos por iteración de los procesadores actuales. Los múltiplos del divisor se mantienen constantes durante la iteracción por lo tanto, es necesario generarlos solamente una vez. Además, la operación multiplicación-suma y la recodificación de Booth pueden ser realizadas en el mismo ciclo que la suma de los productos parciales. El resultado es un algoritmo de latencia variable que requiere sólo 22 iteraciones. Este método puede ser extendido al cálculo de la raíz cuadrada y sólo necesita 22 iteraciones. Pero no mejora el rendimiento medio de los procesadores convencionales debido a que en cada iteración hay que calcular el cuadrado del cociente. Cada iteración precisa tres ciclos por lo tanto, son necesarios más de 50 ciclos para obtener el resultado final. Las principales contribuciones y ventajas del método AQA modificado son las siguientes. En comparación con el método N-R, solamente se necesita la aproximación inicila de 30 bits para obtener el cociente. Con respecto al algoritmo GLD, la metodología es parecida, pero la organización del hardware es diferente. Los resultados intermedios en representación redundante se utilizan como multiplicadores y se solapan diversas operaciones. Estas características incrementan el rendimiento. La duración del ciclo no aumenta aunque el número de bits que se retiran en cada iteración es elevado. Esto no ocurre en los algoritmos DR, en los que la duración del ciclo aumenta con el radix. Con respecto al algoritmo Cyrix, el algoritmo AQA modificado necesita una iteración para obtener el resultado en doble precisión. Los 28 bits más significativos y los 28 bits significativos del cociente se generan en paralelo y se suman durante la multiplicación. Para obtener doble precisión con el algoritmo Cyrix se necesitan dos iteraciones. Los 28 bits más significativos y los 28 bits menos significativos del cociente se generan de forma secuencial. Por otra parte, el algoritmo propuesto puede adaptarse a operar con operandos en punto fijo, mientras que el algoritmo Cyrix no es posible adaptarlo. El tamaño de la LUT para la aproximación inicial es, aproximadamente, la mitad que el tamaño de la LUT en los procesadores convencionales. La recodificación Booth puede llevarse a cabo en el mismo ciclo que la suma de los productos parciales y solapándose con alguna de las operaciones necesarias para la obtención del resto, lo cual aumenta el rendimiento. El algoritmo AQA modificado puede ser extendido también al mercado de la computación móvil y al de aplicaciones de alto rendimiento de procesadores futuros. Puede ser incorporado a multiplicadores industriales con poco hardware extra.