Research On Implementation And Acceleration Of Genetic Algorithms Based On FPGA

The genetic algorithm is a computational model based on Darwin's evolutionary theory.It is a stochastic optimization algorithm that searches for the optimal solution of complex problems based on the selection and evolution process of nature.It has been widely used in many fields.The traditional genetic algorithm program implemented by high-level language,but in the case of the vast solution space,the process of searching for the optimal solution will take a lot of time,and it also limits the application of the genetic algorithm in some specific situation.The genetic algorithm is essentially parallelizable,which is bound to the superiority of genetic algorithms in hardware implementation.In this paper,the Field Programmable Gate Array(FPGA)is used to implement the genetic algorithm,and the structure of the genetic algorithm is optimized on the programmable field gate to accelerate the calculation speed of the genetic algorithm.Compared with the software implementation of a genetic algorithm,although the genetic algorithm implemented by field programmable gate circuit has high complexity and high development cost,it has significant advantages in terms of parallelism and computational efficiency compared with software.In order to effectively reduce the complexity of hardware implementation,this paper uses Xilinx HLS development tools for high-level language synthesis(automation process of converting high-level language into RTL gate-level circuit),and realizes the IP core required by hardware through high-level language(Intelligent Property,It is a general term for integrated circuit cores with intellectual property cores),which reduces R&D costs.At the same time,since the address generated by multiple random numbers will cause an access conflict when accessing data,that is,two random numbers select the address in the same BRAM(Block Random Access Memory),due to the BRAM I/O is limited and it is not possible to fetch two data in the same clock cycle.Therefore,this paper designs a novel structure,namely a random number conflict resolution structure,which designs a pair of "ping-pong" structure BUFFER_A and BUFFER_B,and reads the data from BRAM into BUFFER_A according to the address generated by the random number.Then BUFFER_A provides data for the IP core,and at this time BUFFER_B is reading the data of the BRAM.Since the IP core calculation time of the algorithm is much longer than the data reading time,it is only necessary to wait for the BRAM data to read at the beginning,which reduces the delay caused by address conflicts and accelerates the execution speed of the algorithm.This article is based on XILINX's Kintex series of FPGA platforms,using Verilog and C++ as the primary design language to complete the implementation of genetic algorithms.The Verilog is used to implement the random number generation module,the controller module,the BRAM module,etc.The primary calculation process of the genetic algorithm was achieved by using C++,packaged into the IP core,and the module assembled in VIVADO.The field programmable gate circuit used in this paper is XILINX's Kintex7 series FPGA platform,which uses Verilog and C++ as the primary design language to complete the implementation of the genetic algorithm.The Verilog is used to implement the random number generation module,the controller module,the BRAM module,etc.The primary calculation process of the genetic algorithm realized by using C++.By optimizing the structure of the genetic algorithm,it can recognize the pipeline operation and then package the genetic algorithm into IP core,and module assembly in VIVADO,complete the entire program.In the experimental part,this paper adopts six different test sets of intelligent group algorithms,which are used to test the genetic algorithms implemented on the FPGA platform,CPU platform,and GPU platform,to compare the difference in computing performance.On the CPU platform,OpenMP is used to implement multi-threading to implement the genetic algorithm.On the GPU platform,the genetic algorithm implemented by using the acceleration principle of CUDA.By setting different iterations,relevant experimental tests were carried out on the code of the three platforms,and the results recorded.The genetic algorithm optimization strategy and the acceleration structure of the proposed design were verified,and it was apparent compared with other platforms.