Implementation of Dynamic Reconfiguration of Data Flow Control Based on FPGA

Abstract Based on the download control method of FPGA basic data flow, the FPGA is programmed and configured by using genetic algorithm and single-chip microcomputer to control data flow, so as to realize self-reconstruction and make the system have the characteristics of self-adaptation, self-organization and self-repair.
Keywords FPGA; genetic algorithm; dynamic reconstruction; single-chip microcomputer

The concept of reconfigurable computing was proposed by Geraid Estrin of the University of California in the 1960s, and a system prototype was developed. In the late 1970s, Suetlana P Kartas-hev and Dr. Steven I. Kartashev proposed the concept of dynamic reconfigurable system. In the 1990s, reconfigurable technology became a research hotspot. In recent years, reconfigurable computing and hardware-software co-design are the two cores of current computer research. Most of its task modeling platforms are FPGA-based dynamic reconfigurable systems, which are hot topics in this field in recent years and have been widely used in many fields.

This paper implements the hardware evolution process based on genetic algorithm. The population is randomly generated by MCU, good genes are selected for crossover mutation to produce offspring, and then the appropriate genes are tested to find the best reconstruction solution. The best solution is selected and applied to the hardware to achieve self-repair and self-adaptation.

1 Software Algorithm
Genetic Algorithm (GA) is an adaptive global optimization search algorithm proposed and gradually developed by Professor John Holland of the University of Michigan in the 1970s. It simulates the reproduction, crossover and gene mutation phenomena that occur in natural selection and natural genetic processes. In each iteration, a set of candidate solutions is retained, and the better individuals are selected from the group solutions according to a certain indicator. These individuals are combined using genetic operators to generate a new generation of candidate solution groups until a certain convergence indicator is met, and finally the optimal solution or approximate solution to the problem is obtained.

The basic genetic algorithm consists of four parts: (1) Coding (generating the initial population). (2) Fitness function calculation. (3) Genetic operators (selection, crossover, mutation). (4) Operation parameters.

1.1 Selection
Genetic algorithms first generate an initial population, usually called chromosomes. Chromosomes are composed of genes, such as 11001, and each binary digit is a gene variable. Then, qualified chromosomes are detected through the fitness function, and qualified chromosomes are selected for the next step of crossover and mutation to obtain new individuals.

The fitness in the genetic algorithm indicates the adaptability of an individual to the environment and the ability of the individual to reproduce. The fitness function of the genetic algorithm is also called the evaluation function, which is an indicator used to judge the quality of individuals in the group. It is evaluated based on the objective function of the problem being solved.

The fitness selection function mode here uses a feedback mode to evaluate the generated individuals through simulation detection. If the requirements are met, the evaluation results are stored in the storage module, and then all the function results are weighted in a roulette manner to determine the ratio of the fitness of each gene to the weighted sum, that is, a decimal between (0, 1), and a value greater than, for example, 0.8 is selected as qualified. After evaluating the fitness of all individuals in the group, individuals with a fitness greater than 0.8 are selected for storage, and then wait for new individuals generated by the crossover mutation module.

1.2 Crossover mutation
The crossover mutation module obtains two individuals from the selection module, and compares the random number generated by the random number module with the crossover probability to determine whether to perform a crossover operation. The crossover operator randomly exchanges certain genes between two individuals in the population according to the crossover rate, which can generate new gene combinations, hoping to combine beneficial genes together.

If two parent genes are found, crossover is required to find the intersection of the genes, and the intersection of the genes is crossed with the gene variables to form new gene variables. Mutation is to find the gene mutation point of each gene and try to find a suitable solution through gene mutation, as shown in Figure 1.

1.3 Gene download
The obtained excellent gene is the required solution, which is directly downloaded to achieve controllable, reconfigurable and adaptive implementation. As shown in Figure 2.

The basic genetic algorithm uses a certain coding mechanism to abstract objects into strings of specific symbols arranged in a certain order, just like chromosomes are strings of genes. Here, binary coding is used, and a 5-bit binary string is obtained. The program is as follows:



2 Basic structure of FPGA
At present, mainstream FPGAs all use a lookup table structure based on SRAM technology. Some military and aerospace-grade FPGAs also use a lookup table structure based on Flash or fuse and anti-fuse technology. The method of changing the content of the lookup table by burning a file can realize the repeated configuration of the FPGA.
The lookup table (Look-Up-Table) is abbreviated as LUT. Currently, 4-input LUTs are mostly used in FPGAs, so each LUT can be regarded as a RAM with 4-bit address lines. In this way, each input of a signal for logical operation is equivalent to inputting an address to look up the table, find the content corresponding to the address, and then output it.

[page]
2.1 Multiplexer
Based on the principle of this 4-input LUT structure, a 4-input multiplexer is used. In the process of multi-channel data transmission, any one of them can be selected according to the need. It is also called a multiplexer or a multi-way switch. This paper uses the 5-bit data stream generated by the controller to control the selection of the 4 input ports through a shift register, as shown in Figure 3.

2.2 Shift Register
In digital circuits, registers are usually used to store binary data or codes, as shown in Figure 4. The select bit of the Mux is generated by the data stream generated by the controller and then output after being cached. SelA[1,0] and SelB[1,0] act on two multiplexers respectively. The control bits of the output control multiplexer in the shift register are shown in Table 1.

2.3 NAND Gate
NAND gate is the basic gate that constitutes various circuits. Different gates can be built with NAND gates according to needs, as shown in Figure 5. Different NAND gate structures can realize other functions such as AND gate or OR gate, and realize dynamic reconfiguration.

3 Unit structure construction of reconfigurable system
According to the structural principle of 4-input LUT, this circuit uses 2 4-input MUXs to select the input port of the NAND gate, and then uses 1 2-input MUX to select the output of the data. The selection bits of the 3 MUXs are controlled by SelB[1,0], SelA[1,0], and Sel-out respectively, and the shift register is used as a cache of 5-bit serial binary numbers, as shown in Figure 6. It can be seen that the NAND gate can form various digital circuits through the selection of 4 inputs of east, west, south, and north. This unit structure can be further expanded to 2×2 or more units to realize complex digital circuits. Here, the simple structure of the AND gate and OR gate formed by the unit structure is demonstrated to further illustrate the feasibility of reconfiguration.

When the generated data stream passes through the cache to reconstruct the circuit, you can see the functions implemented by the new familiar circuit, as shown in Figure 7. By observing the relationship between the input and output terminals, the best solution for the required circuit is obtained through testing, which can be downloaded to the hardware to complete the required task.

4 Hardware platform structure
The hardware structure is based on the communication between the microcontroller and the FPGA. The MCU selects MSP430, communicates with the FPGA through RS232, and the PC downloads the program to the central chip through the JTAG interface. Among the peripheral devices, select 2 8-bit LEDs, 4-bit input buttons, 1 12864 LCD display, and reserve a 32-bit expansion interface. As shown in Figure 8, the FPGA selected is Ahera's EP1C16Q240C8.

5 Conclusion
The implementation of circuit reconfiguration technology has become a new hot spot in the research of computing systems. It makes hardware gradually software-oriented. It configures it through a microprocessor combined with multiple FPGAs to achieve dynamic partial reconfiguration. It has strong versatility and adaptability and is suitable for modular design. Based on 5-bit data stream, this paper implements partial dynamic reconfiguration of FPGA and can generate the required hardware structure in real time. Dynamic reconfiguration can make full use of reconfigurable hardware, especially in reconfigurable computing. This technology has made great progress in theory. One of the future development directions of FPGA is to make SOPC hardware that supports dynamic reconfiguration.