Design Methodologies and Architectures for Just-in-Time Hardware Composition of Multi Grain Reconfigurable Accelerators
Rafael María Zamacola Alcalde · 2022
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 that a of its by the application of an The of the BbNN is by an evolutionary a to a configuration that behaves as The main of using advanced reconfiguration techniques with is that it the of the at run-time, of the provided by medium grain reconfiguration. This has been to design an evolutionary that automatically the of the to a The of this is to the that is of a To do so, it initially a BbNN with a single a number of the evolutionary has not been to a it a new to the This is a BbNN configuration is The proposed BbNN has been in an XOR classification and in the of for such as the inverted pole or the mountain car in the framework [Brockman’16]. are applications where it is not possible to compose the accelerators using of the two For the advanced grain reconfiguration techniques of IMPRESS have been the ARTICo3 framework to the of the of reconfigurable systems. its ARTICo3 a reconfigurable architecture dynamic to computing power and fault tolerance. Moreover, ARTICo3 run-time support to the low-level reconfiguration from the as as support to design accelerators with or The of IMPRESS the of the reconfigurable architecture from the of the reconfigurable accelerators. the static architecture can be implemented and multiple This combined with the capabilities of IMPRESS, can reduce the speed-up of to the original ARTICo3 its with IMPRESS). The main of this thesis are have been classification of DPR DPR run-time architectures, and applications. • of DPR] classification of DPR techniques by their that categorizes DPR into coarse, medium, and fine grain reconfiguration. The proposed classification a on how to combine multiple granularities in the design to of the of each • design methodology grain reconfigurable systems. This methodology is by IMPRESS, a design tool for Xilinx 7 FPGAs that extends the capabilities of commercial reconfiguration tools. • composition of 2D architectures using a of medium and fine grain reconfiguration. In particular, two different architectures have been proposed and (1) a overlay and composition can be to different (2) BbNN architecture with of DSPs and BRAMs, of and with a • support to compose and configure the architectures, the low-level reconfiguration from the • and ARTICo3 and IMPRESS that design for grain reconfigurable systems. The proposed the to 2.96£ while the footprint by • overlay framework of offloading loop-based of code from the processor to the FPGA, to 3.18£ with the software in the processor. • evolutionary that can automatically the of the BbNN accelerator to the use of used by the BbNN for a The is into The first one this the main and the hardware composition two the advanced DPR techniques used in this It the classification of DPR based on the granularity, a on how to effectively combine multiple granularities in a the and run-time features of IMPRESS, and a the of IMPRESS the ARTICo3 how the deterministic hardware composition approach can be using the advanced DPR techniques of the to compose overlays to offload sections of four how to compose accelerators with an evolutionary approach using that are with an evolutionary The the from this the main the of the and the of