Aceleración de la computación en altas prestaciones mediante FPGA

Resumen

Actualmente, cada vez es más común ver algoritmos implementados para arquitecturas heterogéneas, en las que se distinguen más de un tipo de elemento procesador. En esta tesis se quieren presentar las increíbles ventajas que pueden aportar las FPGA a este tipo de computación, ya que permiten la posibilidad de actuar como aceleradores de algoritmos. La principal ventaja de las FPGA es su capacidad de reprogramación, es decir, su diseño lógico no es estático y fijo como ocurre con la mayor parte de los circuitos integrados (ASIC). Esta característica es dada en las FPGAs gracias a que se componente esencial es una matriz de bloques lógicos programables interconectados a través de rutas también programables. Una vez se describe la funcionalidad deseada en un lenguaje de descripción Hardware, el software de programación se encarga de habilitar las conexiones y rutas necesarias para su implementación. Las ventajas son múltiples, ya que permiten construir diseños hardware sin el coste de desarrollo que conlleva una implementación ASIC. En esta tesis se presentan varias implementaciones en FPGA para dos tipos de algoritmos bastante bien diferenciados: la factorización de matrices QR a través del método de rotaciones de Givens y la resolución de los problemas de planificación Job Shop Scheduling (JSSP) a través de un algoritmo genético. En cada uno de los casos se muestran varios aspectos que ayudan a crear arquitecturas en FPGA que permiten optimizar su implementación a nivel de productividad y/o utilización de recursos. Para la descomposición QR por el método Givens se presentan dos modelos hardware diferentes aplicados a contextos distintos. El primero de ellos cuenta con un diseño iterativo y aplicable a tamaños de matrices que abarca un amplio rango, desde la matriz más simple de un tamaño 4x4 hasta algunas de una envergadura que ronda un tamaño de 256 _ 256. En el se diferencian claramente dos secciones, una encargada de la rotación y otra del cómputo de ángulos de rotación. En cada una de ellas se ha utilizado una configuración CORDIC específica para la computación de la rotaciones y vectorizaciones. Manifestar también la diferencia de cómputo existente entre las matrices Q y R, siendo de un orden superior la primera matriz. Por tal motivo se han analizado arquitecturas descompensadas en cuanto a elementos rotadores, favorable a la sección de la matriz Q que requiere de un mayor número de operaciones. El segundo modelo destinado a la factorización de matrices QR de tamaño mucho más pequeño con el objetivo de mejorar el rendimiento, utiliza un nuevo tipo de arquitectura sistólica donde se han optimizado los nodos de procesamiento. La arquitectura se presenta como una matriz sistólica bidimensional que hace uso del algoritmo CORDIC segmentado y rediseñado para acelerar el cómputo. Dicho enfoque permite un flujo continuo y una producción constante de factorización de matrices. La arquitectura se ha implementado en formato punto fijo, siendo estudiada y analizada para matrices de un tamaño 4x4 aunque es totalmente exportable a otras dimensiones. En ambas arquitecturas se ha estudiado la reducción de la cantidad de rotaciones realizadas por los algoritmos CORDIC, parte esencial y de gran influencia en la precisión de los algoritmos. Resaltar también la importancia del solapamiento a nivel de operaciones que permite reducciones de en los tiempos de procesamiento, como por ejemplo el solapamiento de instrucciones y paralelización del cómputo de los ángulos con las rotaciones. Por último recalcar la diferencia en el uso de recursos entre ambas arquitecturas, iterativa y sistólica, siendo esta primera mucho más liviana que la segunda, aunque la capacidad de cómputo es superior en la sistólica. Otro diseño propuesto en esta tesis es la implementación FPGA para la resolución de problemas de planificación JSSP por medio de un algoritmo genético. Los problemas JSSP son problema NPcompletos y pertenecen a unos de los grupos más complejos. En este caso se trata de un problema de minimización de tiempos en el momento de ordenar una secuencia de tareas y trabajos a realizar. La implementación del algoritmo genético ha sido diseñada por completo, partiendo del formato de representación de la solución, una secuencia de los trabajos a realizar. El diseño se ha realizado utilizando parámetros que permitan ajustar el diseño del problema para conseguir la resolución de múltiples configuraciones, acotando de este modo la cantidad de recursos utilizados. Para la implementación del algoritmo genético ha sido necesario el diseño de operando específicos para el algoritmo genético óptimos para un desarrollo que permita el solapamiento de instrucciones. Por ello se ha seguido un diseño modular donde en todos los módulos se ejecuta de forma paralela. Destacar que en la operación de cruce de soluciones se ha utilizado un operador segmentado que habilita el cómputo paralelo de la posterior evaluación de los datos. Los resultados para solventar problemas JSSP son muy positivos, puesto que el área ocupada permiten un replicación hasta más de 12 veces el mismo algoritmo en la FPGA utilizada (FPGA Virtex-6 XV6VLX240T velocidad -2), obteniendo de este modo hasta 12 ejecuciones paralelas del algoritmo en busca de la solución. Se ha presentado una comparación con una CPU, donde la FPGA se muestra entre 5 y 18 veces más rápida, dependiendo del problema analizado y la cantidad de iteraciones. También, indicar que la cantidad de aciertos ha sido bastante favorable para la FPGA, aunque es cierto que hallar la mejor solución puede depender de la casuística y la probabilidad. Para finalizar con el resumen, indicar que aún se quedan varios frentes abiertos en los se puede seguir investigando. Como por ejemplo utilizar nuevos tipos de operandos en el algoritmo genético, analizar el consumo de las FPGA, o probar nuevas técnicas que afectan a la mejora del conjunto de soluciones.