Automated wordlength optimization framework for multi source statistical interval based analysis of nonlinear systems with control flow structures
El uso de aritmetica de punto fijo es una opcion de diseno muy extendida en sistemas con fuertes restricciones de area, consumo o rendimiento. Para producir implementaciones donde los costes se minimicen sin impactar negativamente en la precision de los resultados debemos llevar a cabo una asignacion cuidadosa de anchuras de palabra. Encontrar la combinacion optima de anchuras de palabra en coma fija para un sistema dado es un problema combinatorio NP hard al que los disenadores dedican entre el 25 y el 50 del ciclo de diseno. Las plataformas hardware reconfigurables, como son las FPGAs, tambien se benefician de las ventajas que ofrece la aritmetica de coma fija, ya que estas compensan las frecuencias de reloj mas bajas y el uso mas ineficiente del hardware que hacen estas plataformas respecto a los ASICs. A medida que las FPGAs se popularizan para su uso en computacion cientifica los disenos aumentan de tamano y complejidad hasta llegar al punto en que no pueden ser manejados eficientemente por las tecnicas actuales de modelado de senal y ruido de cuantificacion y de optimizacion de anchura de palabra. En esta Tesis Doctoral exploramos distintos aspectos del problema de la cuantificacion y presentamos nuevas metodologias para cada uno de ellos: Las tecnicas basadas en extensiones de intervalos han permitido obtener modelos de propagacion de senal y ruido de cuantificacion muy precisos en sistemas con operaciones no lineales. Nosotros llevamos esta aproximacion un paso mas alla introduciendo elementos de Multi Element Generalized Polynomial Chaos (ME gPC) y combinandolos con una tecnica moderna basada en Modified Affine Arithmetic (MAA) estadistico para asi modelar sistemas que contienen estructuras de control de flujo. Nuestra metodologia genera los distintos caminos de ejecucion automaticamente, determina las regiones del dominio de entrada que ejercitaran cada uno de ellos y extrae los momentos estadisticos del sistema a partir de dichas soluciones parciales. Utilizamos esta tecnica para estimar tanto el rango dinamico como el ruido de redondeo en sistemas con las ya mencionadas estructuras de control de flujo y mostramos la precision de nuestra aproximacion, que en determinados casos de uso con operadores no lineales llega a tener tan solo una desviacion del 0.04% con respecto a los valores de referencia obtenidos mediante simulacion. Un inconveniente conocido de las tecnicas basadas en extensiones de intervalos es la explosion combinacional de terminos a medida que el tamano de los sistemas a estudiar crece, lo cual conlleva problemas de escalabilidad. Para afrontar este problema presen tamos una tecnica de inyeccion de ruidos agrupados que hace grupos con las senales del sistema, introduce las fuentes de ruido para cada uno de los grupos por separado y finalmente combina los resultados de cada uno de ellos. De esta forma, el numero de fuentes de ruido queda controlado en cada momento y, debido a ello, la explosion combinatoria se minimiza. Tambien presentamos un algoritmo de particionado multi via destinado a minimizar la desviacion de los resultados a causa de la perdida de correlacion entre terminos de ruido con el objetivo de mantener los resultados tan precisos como sea posible. La presente Tesis Doctoral tambien aborda el desarrollo de metodologias de optimizacion de anchura de palabra basadas en simulaciones de Monte Cario que se ejecuten en tiempos razonables. Para ello presentamos dos nuevas tecnicas que exploran la reduccion del tiempo de ejecucion desde distintos angulos: En primer lugar, el metodo interpolativo aplica un interpolador sencillo pero preciso para estimar la sensibilidad de cada senal, y que es usado despues durante la etapa de optimizacion. En segundo lugar, el metodo incremental gira en torno al hecho de que, aunque es estrictamente necesario mantener un intervalo de confianza dado para los resultados finales de nuestra busqueda, podemos emplear niveles de confianza mas relajados, lo cual deriva en un menor numero de pruebas por simulacion, en las etapas iniciales de la busqueda, cuando todavia estamos lejos de las soluciones optimizadas. Mediante estas dos aproximaciones demostramos que podemos acelerar el tiempo de ejecucion de los algoritmos clasicos de busqueda voraz en factores de hasta x240 para problemas de tamano pequeno/mediano. Finalmente, este libro presenta HOPLITE, una infraestructura de cuantificacion automatizada, flexible y modular que incluye la implementacion de las tecnicas anteriores y se proporciona de forma publica. Su objetivo es ofrecer a desabolladores e investigadores un entorno comun para prototipar y verificar nuevas metodologias de cuantificacion de forma sencilla. Describimos el flujo de trabajo, justificamos las decisiones de diseno tomadas, explicamos su API publica y hacemos una demostracion paso a paso de su funcionamiento. Ademas mostramos, a traves de un ejemplo sencillo, la forma en que conectar nuevas extensiones a la herramienta con las interfaces ya existentes para poder asi expandir y mejorar las capacidades de HOPLITE. ABSTRACT Using fixed point arithmetic is one of the most common design choices for systems where area, power or throughput are heavily constrained. In order to produce implementations where the cost is minimized without negatively impacting the accuracy of the results, a careful assignment of word lengths is required. The problem of finding the optimal combination of fixed point word lengths for a given system is a combinatorial NP hard problem to which developers devote between 25 and 50% of the design cycle time. Reconfigurable hardware platforms such as FPGAs also benefit of the advantages of fixed point arithmetic, as it compensates for the slower clock frequencies and less efficient area utilization of the hardware platform with respect to ASICs. As FPGAs become commonly used for scientific computation, designs constantly grow larger and more complex, up to the point where they cannot be handled efficiently by current signal and quantization noise modelling and word length optimization methodologies. In this Ph.D. Thesis we explore different aspects of the quantization problem and we present new methodologies for each of them: The techniques based on extensions of intervals have allowed to obtain accurate models of the signal and quantization noise propagation in systems with non linear operations. We take this approach a step further by introducing elements of MultiElement Generalized Polynomial Chaos (ME gPC) and combining them with an stateof the art Statistical Modified Affine Arithmetic (MAA) based methodology in order to model systems that contain control flow structures. Our methodology produces the different execution paths automatically, determines the regions of the input domain that will exercise them, and extracts the system statistical moments from the partial results. We use this technique to estimate both the dynamic range and the round off noise in systems with the aforementioned control flow structures. We show the good accuracy of our approach, which in some case studies with non linear operators shows a 0.04 deviation respect to the simulation based reference values. A known drawback of the techniques based on extensions of intervals is the combinatorial explosion of terms as the size of the targeted systems grows, which leads to scalability problems. To address this issue we present a clustered noise injection technique that groups the signals in the system, introduces the noise terms in each group independently and then combines the results at the end. In this way, the number of noise sources in the system at a given time is controlled and, because of this, the combinato rial explosion is minimized. We also present a multi way partitioning algorithm aimed at minimizing the deviation of the results due to the loss of correlation between noise terms, in order to keep the results as accurate as possible. This Ph.D. Thesis also covers the development of methodologies for word length optimization based on Monte Carlo simulations in reasonable times. We do so by presenting two novel techniques that explore the reduction of the execution times approaching the problem in two different ways: First, the interpolative method applies a simple but precise interpolator to estimate the sensitivity of each signal, which is later used to guide the optimization effort. Second, the incremental method revolves on the fact that, although we strictly need to guarantee a certain confidence level in the simulations for the final results of the optimization process, we can do it with more relaxed levels, which in turn implies using a considerably smaller amount of samples, in the initial stages of the process, when we are still far from the optimized solution. Through these two approaches we demonstrate that the execution time of classical greedy techniques can be accelerated by factors of up to x240 for small/medium sized problems. Finally, this book introduces HOPLITE, an automated, flexible and modular framework for quantization that includes the implementation of the previous techniques and is provided for public access. The aim is to offer a common ground for developers and researches for prototyping and verifying new techniques for system modelling and word length optimization easily. We describe its work flow, justifying the taken design decisions, explain its public API and we do a step by step demonstration of its execution. We also show, through an example, the way new extensions to the flow should be connected to the existing interfaces in order to expand and improve the capabilities of HOPLITE.