Architecture and methodology for automated development of evolvable and reconfigurable hardware applications

Uno de los retos en el ámbito del diseño de circuitos digitales es la necesidad de desarrollar sistemas que sean capaces de adaptarse a condiciones arbitrarias (y a menudo desconocidas) en tiempo de ejecución. Esto puede solucionarse en cierta medida dotando al circuito de varios modos de funcionamiento, o incluso de una funcionalidad programable, como es el caso de los microcontroladores o los procesadores digitales de señales; sin embargo, esta solución carece de autonomía (ya que el circuito necesita ser diseñado o programado explícitamente para tal propósito) y podría no ser lo bastante versátil como para cubrir todos los casos posibles. El hardware evolutivo (EHW) proporciona una metodología para el diseño de circuitos digitales no convencional concebida para solventar esta dificultad. En EHW, la metodología de diseño cambia: en lugar de diseñar un circuito con conocimiento del problema a resolver, se «entrena» un circuito proveyendo un ejemplo de dicho problema junto con la solución que se desea. Para dicho entrenamiento se emplea un algoritmo evolutivo (EA). Los EAs son algoritmos metaheurísticos de optimización que tratan de hallar una solución mediante un proceso iterativo de prueba y error, realizando pequeñas modificaciones a una solución candidata de manera que su comportamiento en ciertas condiciones vaya mejorando incrementalmente, hasta dar con una solución suficientemente buena. En el caso del EHW, este algoritmo se emplearía para modificar partes aleatorias de un circuito hasta que su respuesta a cierta entrada se aproxime lo bastante a la salida deseada. Esto permite diseñar automáticamente circuitos para problemas que se desconoce cómo solucionar, pero para los cuales se conoce un ejemplo de «problema de entrenamiento» y la solución esperada para ese ejemplo. Una vez se ha entrenado el circuito para dicho ejemplo, éste seguramente sea capaz de procesar otros casos del mismo problema para los cuales no se conoce la salida ideal. El EHW tiene aplicaciones en una gran variedad de campos, ya sea porque las condiciones de trabajo cambien con el tiempo, porque el problema no se conoce, o porque el sistema trabaja en un entorno hostil que cause la degradación paulatina del hardware (en este último caso, el EHW puede ser útil al adaptarse a los fallos del hardware según van apareciendo). Entre los ejemplos de aplicaciones del EHW se incluyen el filtrado de imagen y vídeo, clasificación de imágenes, reconocimiento de patrones, control de miembros protésicos, aplicaciones para satélites. . . En el mundo del diseño de circuitos digitales se emplean comúnmente las llamadas matrices de puertas programables o FPGAs, que son circuitos integrados que contienen un gran número de elementos lógicos e interconexiones configurables que permiten la implementación de circuitos digitales arbitrarios, por lo que son una herramienta de gran utilidad para el prototipado de sistemas digitales. Asimismo, las FPGAs se usan para aplicaciones comerciales con bajos volúmenes de producción en las que desarrollar y fabricar un circuito integrado para aplicaciones específicas (ASIC) resultaría muy costoso. Sin embargo, éste no es el único uso de las FPGAs: dado que estos dispositivos (en su mayoría) se pueden reconfigurar tantas veces como se desee, también son útiles en aplicaciones en las que se precise de múltiples circuitos distintos para ser usado uno cada vez; en este caso puede emplearse una única FPGA en la que se cargue un circuito u otro según se necesite. Ciertas FPGAs van más allá proveyendo la capacidad de realizar reconfiguración parcial dinámica (DPR), esto es, la capacidad de modificar una porción del circuito configurado mientras el resto funciona normalmente, sin necesidad de detener su funcionamiento. Esto es muy provechoso para la implementación de EHW, ya que puede hacerse un diseño que conste de varios bloques funcionales cuya funcionalidad se cambie mediante DPR, permitiendo generar configuraciones de circuitos arbitrarias que pueden modificarse empleando un EA. Además, la capacidad de reconfigurar una fracción del circuito mientras el resto sigue trabajando permite implementar un sistema completamente autónomo en la FPGA que ejecute EA, pruebe soluciones candidatas y finalmente use la solución optimizada para procesar datos provistos externamente. El trabajo desarrollado en esta tesis doctoral tiene como antecedente el proyecto fin de carrera del autor en el Centro de Electrónica Industrial (CEI) de la Universidad Politécnica de Madrid (UPM). Este proyecto surgió como un trabajo de integración de los resultados parciales de las tesis de dos estudiantes de doctorado, Andrés Otero y Rubén Salvador. La tesis de Otero exploraba distintas metodologías para la implementación de DPR de grano fino, desde un motor de reconfiguración acelerado en hardware hasta una metodología de diseño para arquitecturas reconfigurables parcialmente. La tesis de Salvador, por otro lado, estudiaba distintos planteamientos para sistemas de EHW autoadaptativos; entre otras cosas, proponía el uso de una arquitectura de array sistólico como la base para una plataforma de EHW. El proyecto consistió en el desarrollo de una aplicación hardware a modo de prueba de concepto que integrara la metodología de reconfiguración de Otero con la arquitectura de array sistólico de Salvador para implementar un filtro de imágenes evolutivo. Este proyecto sirvió como demostración práctica de las metodologías propuestas en estas dos tesis. Sin embargo, durante el desarrollo de dicho proyecto se hizo patente que, a diferencia del desarrollo de hardware convencional en el que los módulos pueden ser fácilmente parametrizados y reutilizados y son mayormente independientes de la plataforma, la metodología requerida para la implementación de EHW basado en DPR era bastante complicada, y requería ser repetida cada vez que se deseara realizar una nueva implementación. Esto suponía un obstáculo importante para la generalización de este paradigma ya que, si bien este proyecto mostraba su viabilidad y uso práctico empleando una aplicación específica, su extensión a nuevas aplicaciones requeriría repetir una gran parte del trabajo. Por esta razón, el autor determinó que era crucial generalizad y automatizar esta metodología de diseño. Esta tesis ha establecido como objetivo principal la generalización de esta metodología de diseño y arquitectura de EHW orientadas a DPR con el fin de hacer su utilización en proyectos futuros lo más sencilla posible. Esto se ha abordado desde distintos flancos: - Reemplazando la arquitectura específica para una única aplicación por un conjunto de módulos reutilizables altamente parametrizados. - Proponiendo y siguiendo una metodología de diseño que automatice lo más posible la generación de sistemas de EHW. - Desarrollando herramientas auxiliares para la generación de sistemas DPR. - Explorando posibles aplicaciones que puedan beneficiarse de este paradigma, estudiando los requisitos que deban tenerse en cuenta a la hora de adaptar la arquitectura hardware a dichas aplicaciones. - Optimizando la arquitectura hardware en la medida de lo posible, con el fin de que sea adecuada aún en tareasmuy exigentes. - Demostrando la idoneidad de la arquitectura de array sistólico propuesta por Salvador para EHW frente a alternativas habituales tales como la programación genética cartesiana. Las aportaciones principales de esta tesis pueden resumirse como sigue: - Una metodología para la implementación de hardware reconfigurable dinámicamente para aplicaciones de EHW. - Una serie de módulos hardware de altas prestaciones fuertemente parametrizados para la implementación de EHW basado en DPR, entre los que se incluyen un módulo de procesamiento de datos basado en un array sistólico y un motor de reconfiguración de grano fino. - Un análisis minucioso de las prestaciones de los módulos desarrollados que muestra su rendimiento para distintos casos de uso, estudiando su escalabilidad, comparando implementaciones alternativas y explorando distintas posibilidades para acelerar su evolución. - Una serie de herramientas de software auxiliares para la elaboración de EHW y hardware reconfigurable dinámicamente, entre las que se incluyen herramientas de extracción de bitstreams parciales para FPGA, modelos de simulación e implementaciones optimizadas de EA. - Varias aplicaciones demostrativas basadas en esta metodología y módulos hardware. Además, durante el desarrollo de esta tesis se han publicado tres artículos en revistas científicas JCR y numerosos artículos en conferencias. Esta tesis ha sido subvencionada por el programa de ayudas de formación de personal investigador (FPI) del Ministerio de Economía y Competitividad de España (referencia de la ayuda BES-2012-060459), asociada al proyecto DREAMS (TEC2011-28666-C04) y su continuación, el proyecto REBECCA (TEC2014-58036-C4-2-R). ----------ABSTRACT---------- One of the challenges in the field of digital circuit design is the need to develop systems that will be able to adapt to arbitrary—and often unknown— conditions at run time. This can be solved to a certain degree by making the circuit have multiple modes of operation, or even a programmable functionality, as is the case for microcontrollers and digital signal processors; however, this solution lacks autonomy—it needs to be explicitly designed or programmed for that purpose—and may not be versatile enough to cover all possible problems. Evolvable hardware (EHW) provides an unconventional methodology for the design of digital circuits that was conceived to overcome this difficulty. In EHW, the design methodology changes: rather than designing a circuit with knowledge of the problem that needs to be solved, a circuit is “trained” by providing an example problem and the desired solution. For this training, an evolutionary algorithm (EA) is employed. EAs are metaheuristic optimization algorithms that attempt to find a solution through an incremental trial-anderror iterative process, making small modifications to a candidate solution so that its behavior under a certain problem is improved incrementally, until a good enough solution has been obtained. In the case of EHW, this algorithm would modify random parts of a circuit until its response to a certain input is close enough to the desired output. This permits the automatic design of circuits for problems whose general solution is unknown, but for which it is known what the solution for a specific “training problem” should be. Once the circuit has been trained for that example problem, it will ideally be able to process similar instances of the same problem for which the ideal output is not known. EHW has applications in a wide variety of fields, whether because the working conditions change over time, the problem is unknown, or because the system works in a hostile environment that causes the degradation of the hardware—in this case, EHW can help by adapting to hardware faults as they appear. Example applications include image and video filtering, image classification, pattern recognition, prosthetic limb control, satellite applications. . . In the field of digital circuit design, it is common to use field-programmable gate arrays (FPGAs). These are integrated circuits containing a large amount of configurable logic elements and interconnections that allow implementing arbitrary digital circuits, and thus are a helpful tool for the prototyping of digital systems. Moreover, FPGAs may be used for commercial applications with low production levels when developing and manufacturing an application-specific integrated circuit (ASIC) would be too costly. But this is not the only benefit of FPGAs: since these devices can be reconfigured on demand (in most cases), they are also useful in applications where multiple different circuits may be needed at different times; in this case, a single FPGA may be used and the required circuit would be loaded each time it is needed. Some FPGAs go one step further and provide the ability to performdynamic partial reconfiguration (DPR), this is, the ability to modify a fragment of its circuit configuration while the rest of it operates normally, without halting its operation. This is very convenient for the implementation of EHW, since a design can be made that consists of multiple functional blocks whose functionality is changed via DPR, thus permitting to generate arbitrary circuit configurations that can be modified using an EA. Furthermore, the ability to reconfigure a fraction of the circuit while the rest of it operates normally allows implementing a completely autonomous system on the FPGA that executes the EA, tests candidate solutions, and eventually uses the optimized solution for processing data provided externally. The precursor of the work carried out in this Ph.D. thesis was the author’s proyecto fin de carrera (B.Sc./M.Sc. final project) in the Centre of Industrial Electronics (CEI) of Universidad Politécnica de Madrid (UPM). This project was born as an integration work between the partial thesis results of two Ph.D. students, Andrés Otero and Rubén Salvador. Otero’s thesis explored different methodologies for the implementation of fine-grain DPR, from a hardware-accelerated reconfiguration engine to a design methodology for partially reconfigurable architectures. Salvador’s thesis, on the other hand, studied different approaches for self-adapting EHW systems; among other things, it proposed the use of a systolic array architecture as the base for an EHWplatform. The project consisted in the development of a proof-of-concept hardware application integrating Otero’s reconfiguration methodology with Salvador’s systolic array architecture to implement an evolvable image filter. This project served as a demonstration of the methodologies proposed in these theses. However, during the development of the aforementioned project, it became apparent that, unlike regular hardware development where modules can be easily parameterized and reused and are rather platform-independent, the methodology required for the implementation of DPR-based EHW was rather difficult, and needed to be repeated on a per-implementation basis. This posed an important obstacle for the generalization of this paradigm since, although this project demonstrated its feasibility and practical use using a specific application, extending it to new applications would require repeating most of the work. For this reason, the author found that the generalization and automation of this design methodology was crucial. This thesis has set the main goal of generalizing this DPR-oriented design methodology and EHW architecture in order to make its use in future projects as straightforward as possible. This has been tackled from several angles: - Replacing the application-specific architecture design with a set of highly parameterized reusable modules. - Proposing and following a design methodology that automates the generation of EHW systems to the extent possible. - Developing tools to assist in the generation of DPR systems. - Exploring possible applications that may benefit from this paradigm, studying the requirements that should be taken into account to adapt the hardware architecture to them. - Optimizing the hardware architecture as much as possible in order to promote its suitability for demanding tasks. - Proving the suitability of the systolic array architecture proposed by Salvador for EHW over commonly used alternatives such as Cartesian genetic programming. The main contributions of this thesis can be summarized as follows: - A methodology for the implementation of dynamically reconfigurable hardware for EHW applications. - A series of highly parameterized and efficient hardware modules for the implementation of DPR-based EHW, including a data processingmodule based on a systolic array and a fine-grain reconfiguration engine. - A thorough analysis of the capabilities of the developed modules showing its performance under several use cases, studying its scalability, comparing alternative implementations, and exploring different possibilities to accelerate its evolution. - A series of software tools to assist in the elaboration of EHW and dynamically reconfigurable hardware, including partial FPGA bitstream extraction tools, simulation models, and optimized EA implementations. - Several demonstrative applications based on this methodology and hardware modules. In addition, three JCR journal articles and numerous conference papers have been published during the development of this thesis. This thesis has been sponsored by the FPI grant program of the Spanish Ministry of Economy and Competitiveness (grant number BES-2012-060459), associated to project DREAMS (TEC2011-28666-C04) and its continuation, project REBECCA (TEC2014-58036-C4-2-R)