Las FPGA se utilizan cada vez más como motores de proceso en paralelo para aplicaciones de proceso de señal digital de alto nivel. Los resultados de las pruebas de rendimiento indican que, con cargas altamente paralelizables, las FPGA pueden lograr unas mayores prestaciones y una relación superior coste/prestaciones respecto los procesadores de señal digital (DSP) y las CPU de aplicación general. No obstante, hasta la fecha las FPGA se han venido utilizando de manera casi exclusiva en diseños de DSP de coma fija. No se ha considerado que las FPGA constituyan una plataforma eficaz para aplicaciones que exijan cálculos de coma flotante de altas prestaciones.

La eficiencia y las prestaciones de la FPGA en coma flotante se han visto limitadas debido a las prolongadas latencias y a la congestión del enrutamiento. Además, el flujo de diseño tradicional de FPGA, basado en escribir descripciones de hardware a nivel de transferencia de registro en Verilog o VHDL, no se adapta bien a la implementación de algoritmos complejos de coma flotante.

Altera ha desarrollado un nuevo flujo de diseño de coma flotante que tiene como objetivo agilizar el proceso de implementación de algoritmos de proceso de señal digital de coma flotante sobre FPGA de Altera, y permitir que estos diseños logren los mayores niveles de prestaciones y de eficiencia registrados hasta ahora. En lugar de construir una ruta de datos consistente en operadores elementales de coma flotante (por ejemplo, multiplicación seguida de suma seguida de cálculo del cuadrado), el compilador de coma flotante genera una ruta de datos que combina operadores elementales en una única función o ruta de datos. Gracias a ello se eliminan las redundancias presentes en los diseños tradicionales de FPGA de coma flotante. Además, el flujo de diseño de Altera es un flujo de diseño de alto nivel basado en modelo que utiliza el DSP Builder Advanced Blockset de Altera con MATLAB y Simulink de MathWorks. Altera espera que el trabajo a alto nivel los diseñadores de FPGA estarán en condiciones de implementar y verificar algoritmos complejos de coma flotante con mayor rapidez que el diseño tradicional basado en HDL.

BDTI ha llevado a cabo un análisis independiente del flujo de diseño de DSP de coma flotante de Altera. El objetivo de BDTI era conocer las prestaciones que se pueden alcanzar mediante las FPGA de Altera para aplicaciones de alto nivel de DSP de coma flotante, así como evaluar la facilidad de uso del flujo de diseño de DSP de coma flotante de Altera. Este artículo presenta las conclusiones de BDTI, así como información de referencia y detalles sobre la metodología aplicada.

1. Introducción
Dos ejemplos de diseño de coma flotante
Los avances introducidos en los chips digitales permiten que los algoritmos complejos que hasta ahora se habían visto limitados al ámbito de la investigación hagan su entrada en aplicaciones comunes de informática embebida. Por ejemplo, durante muchos años se ha empleado el álgebra lineal (y en concreto la resolución de sistemas que implique grandes conjuntos de ecuaciones lineales simultáneamente) principalmente en el ámbito de la investigación, donde hay recursos de cálculo a gran escala y generalmente no se exigen cálculos en tiempo real. La resolución de grandes sistemas exige inversión matricial o algún tipo de descomposición matricial. Además de los requisitos en cuanto a capacidad de cálculo, estas técnicas pueden sufrir una inestabilidad numérica si no se utiliza el rango dinámico suficiente. Por tanto, la implementación eficiente y precisa de estos algoritmos solo resulta práctica en dispositivos de coma flotante.
Altera presentó recientemente la capacidad de cálculo con coma flotante en el paquete de herramientas DSP Builder Advanced Blockset para simplificar la implementación de algoritmos DSP de coma flotante en las FPGA de Altera, así como para mejorar las prestaciones y la eficiencia de los diseños de coma flotante respecto a las tradicionales técnicas de diseño con FPGA. En un artículo anterior [1], BDTI analizó y evaluó las prestaciones y la eficiencia del paquete de herramientas de software Quartus II v11.0 de Altera en un ejemplo de implementación del solucionador Cholesky monocanal de coma flotante, sintetizada para las FPGA de 40 nm Stratix IV y Arria IV.

En este artículo evaluamos la efectividad de la propuesta de Altera que utiliza la nueva versión 12.0 de la herramienta de software Quartus II y conocer las prestaciones de las FPGA de 28 nm Stratix V y Arria V de Altera. Para llevar a cabo esta evaluación, BDTI se centró en la resolución de un gran número de ecuaciones lineales simultáneas mediante dos tipos de descomposiciones: una descomposición matricial de Cholesky multicanal y la descomposición QR con el proceso Gram-Schmidt. Estas descomposiciones, junto con las sustituciones progresiva y regresiva, constituyen una solución para el vector x en un grupo simultáneo de ecuaciones lineales con la forma Ax = B.

La descomposición matricial se utiliza en numerosas aplicaciones de radares militares como el proceso adaptativo de espacio-tiempo (Space-Time Adaptive Processing, STAP) y varios problemas de estimación en comunicaciones digitales. La descomposición QR se suele utilizar en cualquier matriz A de m por n, mientras que la descomposición de Cholesky es el algoritmo más empleado para una matriz cuadrada, simétrica y definida positiva por su elevada eficiencia de cálculo. Ambas descomposiciones utilizan algoritmos que exigen muchos cálculos y necesitan una alta precisión de los datos, por lo que se deben realizar operaciones matemáticas con coma flotante. Además, los dos ejemplos estudiados en este artículo emplean productos escalares y bucles anidados dentro del algoritmo, y estas operaciones están presentes en un gran número de aplicaciones de proceso de señal digital relacionadas con el álgebra lineal y los filtros de respuesta finita al impulso (finite impulse response, FIR).

En los ejemplos descritos en el presente artículo se resuelven grupos simultáneos de ecuaciones lineales de datos complejos con ambos métodos y se indican los resultados. Mediante el uso del solucionador QR, tal como se explica en la Sección 4, una FPGA Stratix V de Altera es capaz de realizar 315 descomposiciones matriciales por segundo de tamaño 400x400, a una velocidad de 203 MHz y logrando 162x109 operaciones de coma flotante por segundo (GFLOPS).
Los dos ejemplos de diseño evaluados en este artículo forman parte de la herramienta de software DSP Builder v12.0 o se pueden solicitar a

Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Flujo de diseño de coma flotante
Las FPGA no han sido hasta ahora, en general, la plataforma escogida para aplicaciones de coma flotante de alto nivel. Aunque los suministradores de FPGA disponen de bibliotecas primitivas de coma flotante, las prestaciones de las FPGA en aplicaciones de coma flotante se han visto muy limitadas. La ineficiencia de los diseños tradicionales de FPFA de coma flotante se debe en parte a la naturaleza marcadamente segmentada y a las estructuras muy aritméticas de los operadores de coma flotante, que crean grandes latencia en la ruta de datos y congestión en el enrutamiento. A su vez, estas latencias generan problemas de difícil manejo en diseños con alta dependencia respecto a los datos. El resultado final es a menudo un diseño con una baja frecuencia operativa.
El flujo de la herramienta DSP Builder Advanced Blockset de Altera afronta estos obstáculos tanto al nivel de la arquitectura como de diseño del sistema. El compilador de coma flotante de Altera une grandes secciones de la ruta de datos en una sola función de coma flotante en lugar de generarlos por composición de operadores elementales de coma flotante. Esto se lleva a cabo mediante el análisis de crecimiento de los bits en la ruta de datos y escogiendo la normalización de entrada óptima para asignar la precisión suficiente a lo largo de la ruta de datos con el fin de eliminar tantos pasos de normalización y desnormalización como sea posible, tal como muestra la Figura 1. El formato IEEE 754 solo se utiliza en los límites de la ruta de datos; en la ruta de datos se utilizan mayores anchos de la mantisa para aumentar el rango dinámico y disminuir la necesidad de pasos de normalización y desnormalización entre operadores sucesivos. Las funciones de normalización y desnormalización utilizan desplazadores rápidos (barrel shifters) con un ancho de hasta 48 bits para un número de coma flotante de precisión sencilla. Esto consume una notable cantidad de recursos lógicos y de enrutamiento y es la principal razón por la cual no han sido eficientes las implementaciones de coma flotante mediante FPGA. La metodología de ruta de datos combinada elimina un número significativo de desplazadores rápidos. Las multiplicaciones con mantisas de mayor precisión utilizan el modo multiplicador de 27 bit x 27 bit de Altera en los dispositivos Stratix V y Arria V. La Figura 1(b) compara la metodología de ruta de datos combinada para el caso sencillo de una cadena con dos sumadores y la implementación tradicional mostrada en la Figura 1(a). La ruta de datos combinada de la Figura 1(b) elimina la redundancia de interoperador al suprimir la desnormalización de la salida del primer sumador y la normalización de la entrada del segundo sumador. La eliminación de la lógica y del enrutamiento añadidos, junto con el uso de multiplicadores de hardware, hace que resulten predecibles la sincronización y la latencia en las rutas de datos complejas. Se implementan algoritmos de coma flotante IEEE 754 de precisión sencilla y doble con menos recursos lógicos y mayores prestaciones. Altera afirma que una ruta de datos combinada reduce en un 50% los recursos lógicos y la latencia que la ruta de datos equivalente realizada mediante operadores elementales [2]. Además, como resultado de la representación con más ancho de los datos internos, la exactitud de los datos suele ser en general mayor que la lograda por una biblioteca con operadores elementales de coma flotante IEEE 754.

El flujo de diseño de DSP de coma flotante de Altera incorpora el DSP Builder Advanced Blockset de Altera y la herramienta de software Quartus II de Altera, así como MATLAB y Simulink de MathWorks. El entorno Simulink permite que el diseñador trabaje al nivel de comportamiento algorítmico para describir, depurar y verificar sistemas complejos. Funciones de Simulink como la propagación de tipos de datos y proceso de datos vectoriales se incorporan a DSP Builder Advanced Blockset, permitiendo así que el diseñador pueda llevar a cabo una rápida exploración del espacio de diseño algorítmico.

Con el fin de evaluar la eficiencia y las prestaciones del flujo de diseño de coma flotante de Altera, BDTI utilizó la herramienta DSP Builder Advanced Blockset para validar dos ejemplos, ambos consistentes en resolver un conjunto de ecuaciones lineales simultáneas utilizando tipos de datos complejos en una representación de coma flotante de precisión sencilla. Una solución se obtiene mediante la descomposición de Cholesky, mientras que la otra emplea la descomposición QR por medio del proceso Gram-Schmidt. La Sección 2 del presente artículo describe la implementación  de los dos ejemplos de coma flotante. La Sección 3 explica la experiencia de BDTI con el flujo de diseño y el paquete de herramientas. La Sección 4 presenta las prestaciones de la implementación con dos FPGA de Altera: el dispositivo de gama alta y tamaño medio Stratix V 5SGSMD5K2F40C2n y el dispositivo de gama media Arria V 5AGTFD7K3F40I3N. Finalmente, la Sección 5 presenta las conclusiones de BDTI.

2. Implementación
Información de referencia
Numerosas aplicaciones incluyen conjuntos de ecuaciones lineales del tipo Ax = b. Tanto si se trata de un problema de optimización que incluya mínimos cuadrados lineales, un filtro de Kalman para la predicción de un problema o la estimación en un canal de comunicación MIMO, el problema sigue consistiendo en hallar una solución numérica para un conjunto de ecuaciones lineales del tipo Ax = b. Para una matriz general de tamaño m por n, donde m es la altura de la matriz y n su anchura, se puede utiliza la descomposición de QR para resolver el vector x. Al algoritmo descompone A en una matriz ortonormal Q de tamaño m por n y una matriz triangular superior R de tamaño n por n. Dado que Q es ortonormal, QTQ = I y Rx = QTb. Dado que R es una matriz triangular superior, x se puede resolver fácilmente mediante sustitución regresiva sin necesidad incluso de invertir la matriz original A. En el ejemplo de QR de este artículo trabajamos con matriz sobredeterminadas en las que m Ž n.

Cuando la matriz A es simétrica y definida positiva, como en las matrices de covarianza que surgen en muchos problemas, se suelen utilizar la descomposición y el solucionador de Cholesky. El algoritmo halla la inversa de la matriz A, resolviendo así el vector x como x = A-1b. La descomposición de Cholesky es al menos el doble de eficiente que la descomposición QR, dependiendo de los algoritmos empleados para la descomposición. Dado que estos algoritmos de descomposición son de naturaleza recurrente e incluyen divisiones, se necesita un gran rango dinámico numérico ya que aumenta el tamaño de la matriz. En la mayoría de los casos, incluso para matrices de tamaño tan pequeño como 4x4, por ejemplo en la estimación de un canal MIMO, se realizan operaciones de coma flotante. Para sistemas de mayor tamaño que exijan un mayor rendimiento, como en aplicaciones militares, la velocidad de funcionamiento con coma flotante suele ser prohibitiva para los sistemas embebidos. Con frecuencia los diseñadores abandonan el algoritmo por completo en busca de una solución menos óptima o bien recurren a procesadores de coma flotante de altas prestaciones, con el aumento de costes y del esfuerzo de diseño.

Autor:

Por el equipo de Berkeley Design Technology, Inc. Octubre 2012

(Continua en el mes de Febrero)

Más información o presupuesto