Tesis:
Hardware acceleration of Monte Carlo-based simulations.
- Autor: ECHEVERRIA ARAMENDI, Pedro
- Título: Hardware acceleration of Monte Carlo-based simulations.
- Fecha: 2011
- Materia: Sin materia definida
- Escuela: E.T.S. DE INGENIEROS DE TELECOMUNICACION
- Departamentos: INGENIERIA ELECTRONICA
- Acceso electrónico: http://oa.upm.es/9786/
- Director/a 1º: LOPEZ VALLEJO, María Luisa
- Resumen: Durante los últimos años ha habido un enorme avance en la tecnología y capacidades de las FPGAs. Tradicionalmente, las FPGAs se han utilizado principalmente para el desarrollo de prototipos, ya que ofrecen importantes ventajas a un bajo coste: flexibilidad y facilidad de verificación. Su flexibilidad permite la implementación de las diferentes versiones de una aplicación determinada y permite a los diseñadores modificar las implementaciones hasta el último momento, o incluso corregir errores una vez que el producto esta siendo utilizado. En segundo lugar, la verificación de un diseño en una FPGA es más fácil y más sencillo que en ASIC, donde requieren un esfuerzo de verificación enorme. Además de estas ventajas, los avances tecnológicos han permitido FPGAs con grandes capacidades a la vez que se ha aumentado su rendimiento. Y aunque las FPGAs no sean tan eficientes como los ASIC en términos de rendimiento, recursos o el consumo de potencia, hoy en día pueden ofrecer un mejor rendimiento que un sistema estándar o que uno basado en procesadores digitales de señal (DSP). Esto, junto con la enorme capacidad de recursos lógicos alcanzada por las tecnologías de hoy, hace de las FPGAs una opción atractiva para la implementación de sistemas digitales complejos. Además, con su recientemente adquirida capacidad de procesamiento de señal digital, las FPGAs están ampliando su rol tradicional de prototipos al rol de coprocesador para descargar de cálculos intensivos a los procesadores estándar. Esta tesis se centra en el último punto, el uso de FPGAs para acelerar las aplicaciones com- putacionalmente intensivas. El uso de FPGAs para la aceleración de hardware es un área activa de investigación. Sin embargo, todavía hay varios desafíos relativos al uso de FPGAs como aceleradores: • Disponibilidad de cores de implementación. • Capacidad y rendimiento de las FPGAs. • Necesidad de métodos, algoritmos y técnicas adecuadas para FPGAs. • Herramientas de diseño. • Co-diseño de Hardware-Software y su integración El estudio detallado de cada uno de estos cinco desafíos relacionados con la aceleración de hardware no es factible en tan sólo una tesis. La gran variedad de aplicaciones que pueden ser aceleradas y las diferentes características entre ellas, implica que la complejidad de cada tarea es alta. Por lo tanto, en esta tesis se ha elegido un conjunto de aplicaciones a estudiar, y se ha llevado a cabo la implementación de una aplicación real de este subgrupo. La selección de un subconjunto de aplicaciones complejas, en nuestro caso las simulaciones Monte Carlo, nos permite hacer un análisis general de la aceleración de hardware, nuestro campo principal, desde el estudio, análisis y diseño de una aplicación en particular. Este conjunto de aplicaciones tiene varias características compartidas con otras aplicaciones y nos permite hacer un análisis general de la aceleración de hardware desde el estudio, análisis y diseño de una aplicación dada. En concreto, hemos seleccionado una aplicación financiera, la simulación del LIBOR Market Model basado en Monte Carlo. El desarrollo de las aplicaciones en FPGAs a partir de cero es casi imposible y la disponibilidad de los cores es una necesidad para acortar el tiempo de desarrollo. Siguiendo esta idea, uno de nuestros principales objetivos es el estudio de los elementos comunes que juegan un papel clave en las simulaciones de Monte Carlo y en la aplicación seleccionada (y compartidos con muchas otras aplicaciones). Dos elementos comunes han sido destacados: • Los generadores de números aleatorios que se requieren para las variables aleatorias subyacentes. • Los operadores de punto flotante, que son los elementos base para implementar los modelos matemáticos que se evalúan. De esta manera, el primer objetivo de esta Tesis es el estudio, diseño e implementación de generadores de números aleatorios. En particular, nos hemos centrado en la generación de números aleatorio con distribución Gaussiana y en la implementación de un generador completo y compatible con técnicas de reducción de varianza que se utilizan en la aplicación seleccionada y en otras aplicaciones. En este campo de investigación hemos desarrollado un generador de números aleatorios gaussianos de alta calidad y alto rendimiento. A su vez, este generador es parametrizable y compatible con el módulo parametrizable de hipercubo latino también desarrollado y con un generador Mersenne Twister de alto rendimiento. Los resultados de investigación en este campo demuestran que la generación de números aleatorios es idónea para la aceleración de hardware, tanto como un núcleo aislado o integrado en aceleradores mayores. El segundo objetivo se ha ocupado del desarrollo de operadores matemáticos eficientes y orientados a FPGAs (tanto básicos como complejos y con aritmética de punto flotante). Nos hemos centrado en el diseño, desarrollo y caracterización de las librerías de componentes. En lugar de centrarnos en los algoritmos de los operadores, nuestro enfoque ha sido la de estudiar cómo el formato se puede simplificar para obtener operadores más adecuados para FPGAs y que a su vez presenten un mejor rendimiento. Un objetivo importante aquí buscado ha sido lograr librerías de componentes de propósito general que pueden ser reutilizados en varias aplicaciones y no sólo en una aplicación seleccionada en esta tesis. Diferentes decisiones de diseño se han estudiado y analizado. De este análisis, hemos determinado el impacto de la sobrecarga debido a algunas de las características del estándar de punto flotante. La sobrecargas que presenta este formato implican un mayor uso de los recursos y su reducción es una necesidad para obtener operadores más adecuados para FPGAs y con mejor rendimiento, independientemente de lo que el algoritmo de cálculo subyacente. En particular, el manejo de los números denormalizados tiene un gran impacto en los operadores de FPGA. Con los resultados obtenidos en ese estudio, hemos analizado y seleccionado un conjunto de características que implican un mejor rendimiento y una reducción de los recursos. Este conjunto, ha sido elegido para diseñar dos librerías adicionales para FPGA orientadas a garantizar (o incluso mejorar) la precisión y la resolución dada por el estándar. Los operadores de estas librerías son los componentes básicos para la implementación de la aplicación seleccionada. Además, un segundo análisis se ha llevado a cabo para estudiar las capacidades de los FPGAs para implementar complejos arquitecturas de datos. Este análisis muestra las enormes capacidades de FPGAs actuales que permiten a la implementación de cientos de operadores punto flotante en la misma FPGA. A pesar de esta capacidad, este segundo análisis también demuestra cómo la frecuencia de trabajo de los operadores se ve gravemente afectada por el interconexionado de sus elementos cuando los operadores no están aislados y se están utilizando un alto porcentaje de los recursos de la FPGA. Relacionado con la aplicación de destino, un tercer objetivo de este trabajo ha sido profundizar sobre la implementación de un operador en particular, la función exponenciación. Este operador es utilizado en muchas simulaciones científicas y financieras. Su complejidad, y la falta de las anteriores implementaciones de propósito general han merecido una atención especial. Hemos desarrollado y presentado un operador exponenciación exacto para FPGAs basado en la traducción directa de xy en una cadena de sub-operadores y en la flexibilidad de las FPGA que permite precisones a medida. Tomando ventaja de esta flexibilidad, el análisis de error se centró en determinar que lprecisiones son necesarias en los resultados parciales y en la arquitectura interna de los operadores de sub-para obtener un operador exacto con un error máximo de un ulp. Por último, la integración de este análisis de error y el desarrollo del operador en el proyecto FloPoCo han permitido automatizar la generación de los operadores de exponenciación con precisiones variables. El segundo objetivo se ha ocupado del desarrollo de operadores matemáticos eficientes y orientados a FPGAs (tanto básicos como complejos y con aritmética de punto flotante). Nos hemos centrado en el diseño, desarrollo y caracterización de las librerías de componentes. En lugar de centrarnos en los algoritmos de los operadores, nuestro enfoque ha sido la de estudiar cómo el formato se puede simplificar para obtener operadores más adecuados para FPGAs y que a su vez presenten un mejor rendimiento. Un objetivo importante aquí buscado ha sido lograr librerías de componentes de propósito general que pueden ser reutilizados en varias aplicaciones y no sólo en una aplicación seleccionada en esta tesis. Diferentes decisiones de diseño se han estudiado y analizado. De este análisis, hemos determinado el impacto de la sobrecarga debido a algunas de las características del estándar de punto flotante. La sobrecargas que presenta este formato implican un mayor uso de los recursos y su reducción es una necesidad para obtener operadores más adecuados para FPGAs y con mejor rendimiento, independientemente de lo que el algoritmo de cálculo subyacente. En particular, el manejo de los números denormalizados tiene un gran impacto en los operadores de FPGA. Con los resultados obtenidos en ese estudio, hemos analizado y seleccionado un conjunto de características que implican un mejor rendimiento y una reducción de los recursos. Este conjunto, ha sido elegido para diseñar dos librerías adicionales para FPGA orientadas a garantizar (o incluso mejorar) la precisión y la resolución dada por el estándar. Los operadores de estas librerías son los componentes básicos para la implementación de la aplicación seleccionada. Además, un segundo análisis se ha llevado a cabo para estudiar las capacidades de los FPGAs para implementar complejos arquitecturas de datos. Este análisis muestra las enormes capacidades de FPGAs actuales que permiten a la implementación de cientos de operadores punto flotante en la misma FPGA. A pesar de esta capacidad, este segundo análisis también demuestra cómo la frecuencia de trabajo de los operadores se ve gravemente afectada por el interconexionado de sus elementos cuando los operadores no están aislados y se están utilizando un alto porcentaje de los recursos de la FPGA. Relacionado con la aplicación de destino, un tercer objetivo de este trabajo ha sido profundizar sobre la implementación de un operador en particular, la función exponenciación. Este operador es utilizado en muchas simulaciones científicas y financieras. Su complejidad, y la falta de las anteriores implementaciones de propósito general han merecido una atención especial. Hemos desarrollado y presentado un operador exponenciación exacto para FPGAs basado en la traducción directa de xy en una cadena de sub-operadores y en la flexibilidad de las FPGA que permite precisones a medida. Tomando ventaja de esta flexibilidad, el análisis de error se centró en determinar que lprecisiones son necesarias en los resultados parciales y en la arquitectura interna de los operadores de sub-para obtener un operador exacto con un error máximo de un ulp. Por último, la integración de este análisis de error y el desarrollo del operador en el proyecto FloPoCo han permitido automatizar la generación de los operadores de exponenciación con precisiones variables.