Hardware Acceleration of Monte Carlo-based Simulations

During the last years there has been an enormous advance in FPGAs. Traditionally, FPGAs have been used mainly for prototyping as they offer significant advantages at a suitable low cost: flexibility and verification easiness. Their flexibility allows the implementation of different generations of a given application and provides space to designers to modify implementations until the very last moment, or even correct mistakes once the product has been released. Second, the verification of a design mapped into an FPGA is easier and simpler than in ASICs which require a huge verification effort. Additionally to these advantages, the technological advances have added great capabilities and per- formance to FPGAs, and even though FPGAs are not as efficient as ASICs in terms of performance, area or power, it is true that nowadays they can provide better performance than standard or digital signal processor (DSP) based systems. This fact, in conjunction with the enormous logic capacity allowed by today’s technologies, makes FPGAs an attractive choice for implementation of complex digital systems. Furthermore, with their newly acquired digital signal processing capabilities, FPGAs are now expanding their traditional prototyping roles to help offload computationally intensive functions from standard processors. This Thesis is focused on the last point, the use of FPGAs to accelerate computationally intensive applications. The use of FPGAs for hardware acceleration is an active research field. However, there are still several challenges concerning the use of FPGAs as accelerators: • Availability of Cores. • Capability and performance of FPGAs. • Methods, algorithms and techniques suited for FPGAs. • Design tools. • Hardware-Software co-design and integration. Studying in depth each one of these five challenges related to hardware acceleration is not feasible in just one Thesis. The great variety of applications that can be accelerated and the different features among them imply that the complexity of each task is high. Therefore, in this Thesis we have chosen one subset of applications to be studied, dealing with the implementation of a real application of this subset. Selecting a complex subset of applications, in our case Monte Carlo simulations, allows us to make a general analysis of the main topic, hardware acceleration, from the study, analysis and design of a particular application. This subset of applications has several features shared with other applications and allows us to make a general analysis of the main topic, hardware acceleration, from the study, analysis and design of a given application. Specifically, we have selected a financial application, the Monte Carlo based LIBOR Market Model. Developing an FPGA application from scratch is almost impossible and availability of cores is a must for shorten development time. Following this idea, one of the main objectives is to study the common elements that play a key role in Monte Carlo simulations and in our target application (and shared with many other applications). Two common elements have been outstood: • The random number generators that are required for the underlying random variables, • Floating-point operators, which are the base elements for implementing the mathematical models that are evaluated. In this way, the first objective of this Ph.D. Thesis is the study, design and implementation of random number generators. In particular, we have focused on Gaussian random number generation and the implementation of a complete generator compatible with variance reduction techniques that can be used for our target application and for other applications. In this field we have developed a high-quality high-performance Gaussian random number generator which is parameterizable and compatible with the also developed parameterizable Latin Hypercube core and a high performance Mersenne Twister generator. Research results in this field demonstrate that random number generation is ideal for hardware acceleration, as an isolated core or within bigger accelerators. Meanwhile, the second objective has dealt with the implementation of efficient and FPGA-oriented mathematical operators (both basic and complex and using floating-point arithmetic). We focused on the design, development and characterization of libraries of components. Instead of focusing on the algorithms of the operators, our approach has been to study how the format can be simplified to obtain operators that are better suited for FPGAs and present better performance. One important goal searched here was to achieve libraries of general purpose components that can be reused in several applications and not just in a particular target application. Different design decisions have been studied and analyzed, and from this analysis, the impact of the overhead due to some of the floating-point standard features has been determined. The format overhead implies a major use of resources and reducing it is a must to obtain operators, independently of what underlying calculation algorithm, that are better suited for FPGAs while present better performances. In particular, the handling of denormalized numbers has a major impact on the FPGA operators. Following the results obtained in that studied, we have discussed and selected a set of features that implies improved performance and reduced resources. This set, has been chosen to design two additional hardware FPGAs-oriented libraries that ensure (or even improve) the accuracy and resolution given by the standard. The operators of these libraries are the base components for the implementation of target application. Additionally, a second analysis has been carried out to study the capabilities of FPGAs to implement complex datapaths. This analysis shows the huge capabilities of current FPGAs which allow up to hundreds of single floating-point operators. Although this capacity, this second analysis has also demonstrate how the working frequency of the operators is severely affected by the routing of their elements when the operators are not isolated and a high percentage of the resources of an FPGA are used. Related to the target application, a third objective of this work was to deepen on the implementation of a particular operator, the exponentiation function. This operator is required in many scientific and financial simulations. Its complexity and the lack of previous general purpose implementations have deserved special attention. We have developed and presented an accurate exponentiation operator for FPGAs based on the straightforward translation of xy into a chain of sub-operators and on the FPGA flexibility which allows tailored precisions. Taking advantage of this flexibility, the provided error analysis focused on determining which precisions are needed in the partial results and in the internal architectures of the sub-operators to obtain an accurate operator with a maximum error of one u. Finally, the integration of this error analysis and the development of the operator within the FloPoCo project have allowed to automatize the generation of exponentiation operators with variable precisions. The next objective we tackle was related to the global purpose of the Thesis of validating all the previously developed elements for the implementation of a complex Monte Carlo simulation which involves all the features that can be found in Monte Carlo simulations. In this way, we have deal with the implementation of the target application, the LIBOR Market Model (LMM). Special attention was devoted to all the features, requirements and circumstances that affect to the performance of the accelerator. A complete LMM hardware core has been developed and its results validated against the original software implementation. Three main features were analyzed: • Correctness of the results obtained. • Accuracy. • Speedup factors obtained by the global application and by each of the main components. Finally, the last objective was the integration of the hardware accelerator within the original software application. All issues related to the communication mechanism are studied putting special focus on how performance is affected by data transfers and by the hardware-software partitioning policy implemented. Following the partitioning policy selected, we have developed the infrastructure (both hardware and software) required to make possible the integration of our accelerator within a software application. A mechanism, based on the use of two RAM memory zones and a PCI-E core with Bus Master capabilities in the FPGA, has been proposed and implemented. And it has allowed us to extend the intrinsic parallelism of Monte Carlo simulations to how the CPU and the FPGA work together. In this way, we exploit the CPU to work in parallel with the FPGA, overlapping their execution times. Hence, the software execution time affecting the performance is reduced to the initial and final processing and to the product valuation in case it is slower that LMM plus the random generator in the FPGA. With this scheme we have achieved high speedups, around 18 times, and close to the theoretical limit for our cases: when there is no software not ported to Hardware or which execution is overlapped with the FPGA execution (the LMM plus RNG achievable speedup). In this case, the speedup achieved could be considerably improved using new FPGAs and several LMM cores in parallel. 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.