Design Methodologies and Architectures for Just-in-Time Hardware Composition of Multi Grain Reconfigurable Accelerators

El uso de plataformas de cómputo heterogéneas está considerado como una estrategia eficaz para crear sistemas de altas prestaciones. En lugar de utilizar un único procesador, los sistemas heterogéneos combinan diferentes elementos de cómputo especializados en ejecutar distintos tipos de aplicaciones. El uso de elementos de procesamiento especializados tiene varias ventajas, como una mayor capacidad de cómputo y un menor consumo de energía. El principal reto de los sistemas heterogéneos es hacerlos accesibles a todo tipo de usuarios, sin necesidad de requerir amplios conocimientos de bajo nivel de las arquitecturas subyacentes. Para simplificar el diseño de los sistemas heterogéneos, muchos fabricantes han desarrollado flujos de diseño basados en lenguajes de programación que abstraen la arquitectura del sistema. Las FPGAs pueden combinarse eficazmente con procesadores de propósito general formando este tipo de sistemas heterogéneos. En este contexto, el procesador ejecuta aplicaciones de control, mientras que la lógica programable de la FPGA se utiliza para implementar circuitos específicos que explotan el paralelismo de aplicaciones con grandes necesidades de cómputo. Además, la flexibilidad que ofrece la lógica programable de las FPGAs puede incrementarse utilizando reconfiguración parcial y dinámica (DPR). La DPR permite cambiar parte del circuito mientras el resto sigue en funcionamiento. Esto puede utilizarse por diversas razones como, por ejemplo, para intercambiar diferentes aceleradores a lo largo del tiempo, permitir la adaptación dinámica en entornos cambiantes o para replicar un acelerador múltiples veces para mejorar el rendimiento o tener tolerancia frente a fallos. La mayoría de los fabricantes de FPGAs están tratando de simplificar el uso de sus dispositivos, permitiendo utilizar síntesis de alto nivel para diseñar aplicaciones con lenguajes de programación. Aunque esto simplifica el diseño, sigue siendo necesario tener conocimientos sobre FPGAs para poder realizar diseños eficientes. Por otro lado, el uso de DPR todavía se considera un flujo de diseño avanzado con una curva de aprendizaje pronunciada. Esta tesis pretende simplificar el uso de las FPGAs en determinadas aplicaciones, presentando una metodología de diseño para construir aceleradores automáticamente mediante el uso de DPR. Para ello es necesario generar una biblioteca de elementos básicos de cómputo (PEs) que estén preimplementados para poder ser reconfigurados en tiempo de ejecución. Estos PEs pueden combinarse de múltiples maneras para componer arquitecturas 2D adaptadas a cada aplicación. La metodología propuesta se ha implementado mediante el diseño de herramientas de reconfiguración, arquitecturas y aplicaciones que muestran cómo puede utilizarse en diferentes escenarios. La metodología propuesta requiere el uso de técnicas avanzadas de DPR que no están disponibles en las herramientas de reconfiguración comerciales actuales. Por este motivo se ha diseñado e implementado IMPRESS, una nueva herramienta de reconfiguración que amplía las capacidades ofrecidas por las herramientas comerciales. En particular, IMPRESS ha sido diseñado para ser compatible con DPR de diferentes granularidades. Los diseños con diferentes granularidades se benefician de diferentes capacidades de reconfiguración. Por esta razón, esta tesis propone una nueva clasificación que categoriza la DPR en reconfiguración de grano grueso, medio y fino. La reconfiguración de grano grueso consiste en intercambiar módulos monolíticos que suelen abarcar grandes regiones de la FPGA. En cambio, la reconfiguración de grano medio se utiliza para reconfigurar PEs individuales que forman parte de aceleradores modulares que se componen de varios PEs interconectados entre sí (por ejemplo, overlays o matrices sistólicas). Por último, la reconfiguración de grano fino se utiliza en aplicaciones en las que sólo es necesario modificar la configuración de primitivas individuales de la FPGA (por ejemplo, la tabla de verdad de una look-up table). IMPRESS es la primera herramienta de reconfiguración que ofrece características avanzadas para cada granularidad, permitiendo combinar varias granularidades en un único diseño. En particular, las reconfiguraciones de grano medio y fino pueden combinarse eficazmente para componer aceleradores en tiempo de ejecución. Para ello el sistema estático se diseña con una región reconfigurable que inicialmente está vacía. Después, en tiempo de ejecución, se puede usar la reconfiguración de grano medio para insertar PEs dentro de la región reconfigurable formando una arquitectura 2D. Posteriormente se puede utilizar la reconfiguración de grano fino para configurar cada PE rápidamente, sin necesidad de tener una comunicación directa con el sistema estático, lo que mejora la escalabilidad de la arquitectura. Para validar la metodología propuesta y las capacidades de reconfiguración proporcionadas por IMPRESS, esta tesis propone dos alternativas para automatizar la composición de los PEs y su configuración. La primera alternativa sigue un enfoque determinista en el que los aceleradores se describen utilizando lenguajes de programación software. Este enfoque utiliza overlays reconfigurables para mover el cómputo de bucles software sin sentencias de control del procesador a la FPGA. Las aplicaciones se mapean en el overlay en tiempo de diseño. Para ello el código de software de alto nivel se compila para obtener su representación intermedia en LLVM que, posteriormente, se transforma en un DFG (data flow graph) que se mapea en un overlay genérico. La composición y la configuración del overlay se guardan en un bitstream que puede utilizarse en tiempo de ejecución para construir el overlay mediante el uso de la reconfiguración de grano medio y fino. Por último, para poder transferir el cómputo del procesador a la FPGA, el código original se transforma en llamadas a funciones que gestionan las transferencias DMA (Direct Memory Access) para mover los datos entre el overlay y el procesador. El rendimiento del overlay depende del número de iteraciones, del tamaño del DFG y del número de entradas/salidas, obteniendo una aceleración máxima de 3.18£ para una aplicación de multiplicación de matrices, seleccionada como uno de los ejemplos. La segunda alternativa propuesta utiliza un enfoque evolutivo para componer los aceleradores. Esta alternativa se basa en redes neuronales basadas en bloques (BbNNs) que tienen un PE configurable que se replica en una cuadrícula 2D. Cada PE está conectado a sus cuatro vecinos más cercanos, siendo cada puerto configurable como puerto de entrada/salida. Cada puerto de salida del PE se comporta como una neurona de una red neuronal convencional que realiza una suma ponderada de todas las entradas del PE y procede a la aplicación de una función de activación. El entrenamiento de la BbNN se realiza mediante un algoritmo evolutivo que, dado un objetivo de referencia, trata de encontrar una configuración que se acerque a dicho objetivo. La principal ventaja de utilizar técnicas de reconfiguración avanzada con la BbNN es que es posible cambiar el tamaño de la red en tiempo de ejecución utilizando reconfiguración de grano medio. Esto se ha aprovechado para diseñar un algoritmo evolutivo que escala automáticamente el tamaño de la red para encontrar una solución válida. El objetivo de dicho algoritmo es encontrar el menor tamaño de red capaz de resolver una aplicación determinada. Para ello, inicialmente se fija una red con una sola fila. Si pasado un número de generaciones el algoritmo evolutivo no ha conseguido encontrar una solución válida, se añade una nueva fila a la red. Este proceso se repite hasta que se logra encontrar una configuración de la BbNN válida. La BbNN propuesta se ha aplicado con éxito en un problema de clasificación XOR y también en la implementación de controladores para dispositivos físicos como en las aplicaciones de inverted pole y mountain car disponibles en la plataformaOpenAI [Brockman’16]. Hay aplicaciones en las que no es posible componer los aceleradores utilizando ninguno de los dos enfoques anteriores. Para estos escenarios, las técnicas avanzadas de reconfiguración de grano grueso de IMPRESS se han integrado en la plataforma ARTICo3 para mejorar la productividad de la implementación de sistemas reconfigurables multi-acelerador. ARTICo3 incluye una arquitectura reconfigurable que permite la adaptación dinámica del sistema, donde el usuario puede cambiar el número total de acelerador para mejorar el rendimiento de la aplicación, reducir el consumo de energía o tener tolerancia frente a fallos. Además, ARTICo3 facilita la reconfiguración de los aceleradores ocultando al usuario los detalles de bajo nivel. Por último, ARTICo3 también facilita el diseño de aceleradores permitiendo utilizar tanto lenguajes de descripción hardware como con herramientas de síntesis de alto nivel. La integración de IMPRESS permite desacoplar la implementación de la arquitectura reconfigurable de la implementación de los aceleradores reconfigurables. De esta manera, la arquitectura estática puede implementarse una vez y reutilizarse en múltiples ocasiones. Esta característica, combinada con las capacidades de reubicación de módulos de IMPRESS, permite reducir significativamente los tiempos de implementación. Los resultados muestran un aumento de la velocidad de implementación de entre 2.66£ y 2.96£ con respecto a la versión original de ARTICo3 (antes de su integración con IMPRESS). Las principales aportaciones de esta tesis se resumen a continuación. • [Clasificación de DPR] Una clasificación de las técnicas de DPR basada en la granularidad de reconfiguración que categoriza la DPR en grano grueso, medio y fino. La clasificación propuesta incluye una discusión sobre cómo combinar múltiples granularidades en un mismo diseño para aprovechar las ventajas de cada una de ellas. • [Diseño] Una metodología de diseño de sistemas reconfigurables con múltiples granularidades. Esta metodología se apoya en IMPRESS, una herramienta de diseño para FPGAs de la serie Xilinx 7 que amplía las capacidades de reconfiguración las herramientas comerciales. • [Arquitecturas] Composición en tiempo de ejecución de arquitecturas 2D escalables utilizando una combinación de reconfiguración de grano medio y fino. En particular, se han propuesto e implementado dos arquitecturas: (1) un overlay cuyo tamaño y composición pueden adaptarse dinámicamente para mapear diferentes aplicaciones descritas con lenguajes de programación, (2) una BbNN escalable con uso reducido de bloques de DSPs y BRAMs, capaz de tener bucles de retroalimentación y con una función de activación optimizada para su implementación en la FPGA. • [Ejecución] Herramientas para poder componer y configurar en tiempo de ejecución las mencionadas arquitecturas 2D escalables. Estas herramientas eliminan la necesidad de tener que conocer los detalles de reconfiguración de bajo nivel. • [Diseño y Ejecución] Un flujo de herramientas que integra ARTICo3 e IMPRESS para mejorar la productividad en la implementación de sistemas reconfigurables multi-acelerador. El flujo de herramientas propuesto reduce el tiempo de implementación hasta 2.96£, a la vez que reduce 4.54£ la memoria total necesaria para guardar los bitstreams parciales. • [Aplicación]Un framework para generar overlays capaz de trasladar demanera automática el cómputo de bucles software complejos a la FPGA, logrando un rendimiento hasta 3,18 veces superior al del procesador. • [Aplicación] Un algoritmo evolutivo capaz de escalar de manera automática el tamaño de una BbNN para optimizar el número de recursos utilizado por la BbNN en una aplicación dada. El resto del documento se divide en cinco capítulos. El primero motiva la tesis, establece los objetivos principales e introduce la metodología de composición de hardware en tiempo de ejecución. El segundo capítulo describe las técnicas avanzadas de DPR. Incluye la clasificación de DPR basada en la granularidad, una discusión sobre cómo combinar eficazmente múltiples granularidades en un diseño. También incluye una descripción de las capacidades que ofrece IMPRESS para el diseño de sistemas reconfigurables y su integración con ARTICo3. El tercer capítulo detalla cómo se puede lograr la composición de hardware determinista utilizando las técnicas avanzadas de DPR descritas en el capítulo anterior para componer overlays escalables que permitan trasladar de manera automática el cómputo de bucles software a la FPGA. Del mismo modo, el cuarto capítulo detalla cómo componer hardware con un enfoque evolutivo utilizando una BbNN escalable entrenada con un algoritmo evolutivo. El último capítulo presenta las conclusiones de este trabajo incluyendo las principales contribuciones, el impacto de la tesis y las futuras líneas de trabajo. ----------ABSTRACT---------- The use of heterogeneous computing platforms is considered an efficient strategy to design high-performance computing systems. Instead of using a single powerful processor, heterogeneous systems combine different computing fabrics tailored to specific application domains. Using specialized computing fabrics has several advantages, such as increased performance and lower power consumption. The main challenge of heterogeneous systems is how to make them accessible to general users without extensive low-level expertise on the underlying architectures. In order to simplify the design of heterogeneous systems, many manufacturers are trying to develop software-centric design flows that abstract as much as possible the system architecture. Field Programmable Gate Arrays (FPGAs) can be effectively combined with general-purpose processors in this type of heterogeneous systems. In this context, the processor executes control-intensive applications while the programmable logic of the FPGA is used to implement custom circuits that exploit the parallelism of computing-intensive applications. Moreover, the flexibility offered by the programmable logic of FPGA can be further exploited by using Dynamic Partial Reconfiguration (DPR) to change part of the circuit while the rest remains unaltered. This can be used for various reasons, such as offloading different accelerators over time, enabling dynamic adaptation, or replicating an accelerator multiple times for enhanced computing performance or fault tolerance. Most FPGA manufacturers are trying to simplify the use of their devices by allowing to use high-level synthesis to design applications with software-based languages. While this simplifies FPGA designs, it is still required device-level knowledge of FPGAs to make efficient designs. Moreover, the use of DPR is still considered an advanced design flow with a steep learning curve. This thesis aims at simplifying the use of FPGAs in certain applications by presenting a design methodology to automatically build accelerators using DPR. To do so, it is necessary to generate a library of preimplemented Processing Elements (PEs) that can be reconfigured at run-time. These PEs can be combined in multiple ways to compose 2D architectures tailored to different applications. The proposed methodology has been implemented by designing reconfiguration tools, architectures, and applications that show how it can be used in different scenarios. The proposed methodology requires using advanced DPR techniques that are not available in current commercial reconfiguration tools. For this reason, it has been necessary to design IMPRESS, a new reconfiguration tool that extends the capabilities offered by commercial tools. In particular, IMPRESS has been designed to support DPR with different footprint granularities. Designswith different footprint granularities benefit from different reconfiguration capabilities. For this reason, this thesis proposes a new classification that categorizes DPR into coarse, medium, and fine grain reconfiguration. Coarse grain reconfiguration consists of swapping monolithic modules that usually span large FPGA regions. In contrast,medium grain reconfiguration is used to change individual PEs of modular accelerators that are composed of several interconnected PEs (e.g., systolic arrays, overlays). Finally, fine grain reconfiguration is used in applications where it is only necessary tomodify the configuration of individual primitives of the FPGA (e.g., the configuration of a lookup table). IMPRESS is the first reconfiguration tool to offer advanced features for each granularity, allowing to combine several granularities in a design. In particular, mediumand fine reconfiguration can be effectively combined to compose hardware accelerators on the fly. To do this, the static system is initially designed with an empty reconfigurable region. Then, at run-time, medium grain reconfiguration can be used to allocate PEs to compose an interconnected 2D architecture. Once the 2D architecture has been built, fine grain reconfiguration can be used to configure each PE quickly without needing direct communicationwith the static system, which enhances the scalability of the architecture. To validate the proposed methodology and the support provided by IMPRESS, this thesis proposes two alternatives to automate the composition and configuration of the PEs. The first alternative follows a deterministic approach where accelerators are described using software languages. This approach uses reconfigurable overlays to offload loop-based sections of code without control sentences from the processor to the FPGA. Applications are mapped onto the overlay at design time. To that end, the high-level software code is compiled to obtain its LLVM intermediate representation, which is then transformed into a Data Flow Graph (DFG) that is mapped onto a generic overlay. The composition and configuration of the overlay are saved as an overlay bitstream that can be loaded at run-time to compose the specific overlay using medium and fine grain reconfiguration. Additionally, to offload the computation to the overlay, the original code is transformed into function calls that manage the Directed Memory Access (DMA) transfers necessary to move the data between the overlay and the processor. The performance of the overlay depends on the number of iterations, DFG size, and the number of inputs/outputs, obtaining a maximum of 3.18£ speed-up for a matrix multiplication application, selected as one of the example applications. The second alternative uses an evolutionary approach to compose accelerators. It is based on Block-based Neural Networks (BbNNs) that have one configurable PE that is replicated on a 2D grid. Each PE is connected to its four nearest neighbors, with each port being configurable as an input/output port. Each output port of the PE behaves as a regular neuron that performs a weighted addition of all its inputs followed by the application of an activation function. The training of the BbNN is carried out by an evolutionary algorithm that, given a reference goal, tries to find a network configuration that behaves as expected. The main advantage of using advanced reconfiguration techniques with BbNNs is that it allows changing the size of the network at run-time, taking advantage of the modularity provided by medium grain reconfiguration. This has been leveraged to design an evolutionary algorithm that automatically scales the size of the network to find a valid solution. The goal of this algorithm is to find the smallest network size that is capable of solving a given application. To do so, it initially builds a BbNN with a single row. If after a number of generations the evolutionary algorithm has not been able to find a valid solution, it adds a new row to the network. This process is repeated until a valid BbNN configuration is found. The proposed BbNN has been successfully applied in an XOR classification problem and also in the implementation of controllers for physical devices, such as the inverted pole or the mountain car found in the OpenAI framework [Brockman’16]. There are applications where it is not possible to compose the accelerators using any of the two previous approaches. For these scenarios, the advanced coarse grain reconfiguration techniques of IMPRESS have been integrated within the ARTICo3 framework to enhance the productivity of the implementation of multiaccelerator reconfigurable systems. At its core, ARTICo3 includes a reconfigurable architecture supporting dynamic user-driven adaptation to trade-off computing performance, power consumption, and fault tolerance. Moreover, ARTICo3 includes run-time support to hide the low-level reconfiguration details from the user as well as design-time support to design compliant accelerators with Hardware Description Languages (HDLs) or High-Level Synthesis (HLS). The integration of IMPRESS allows decoupling the implementation of the reconfigurable architecture from the implementation of the reconfigurable accelerators. Therefore, the static architecture can be implemented once and reused multiple times. This feature, combined with the module relocation capabilities of IMPRESS, can significantly reduce the implementation times. Results showan implementation speed-up of 2.66-2.96£with respect to the original ARTICo3 version (i.e., before its integration with IMPRESS). The main contributions of this thesis are summarized below. They have been categorized as: classification of DPR, DPR design-time support, DPR run-time support, architectures, and applications. • [classification of DPR] A classification of DPR techniques motivated by their floorplanning granularity that categorizes DPR into coarse, medium, and fine grain reconfiguration. The proposed classification includes a discussion on how to combine multiple granularities in the same design t