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

Resumo

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-and-error 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 perform dynamic 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 EHW platform. 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 processing module 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).