Design And Implementation Of Hybrid Parallel Genetic Algorithm Based On Sunway Many-core Processors

When the traditional genetic algorithm is used to solve the computation-intensive task,the execution time of the fitness function increases rapidly,and the convergence rate of the algorithm is very low when the population size or generation increases.One-level parallel genetic algorithm is designed and implemented on Sunway "Taihu Light" supercomputer which is ranked first in the latest TOP500 list.As the one-level parallel genetic algorithm fails to make full use of the CPE on the supercomputing.A "coarse-grained combined with master-slave" hybrid parallel genetic algorithm(CMPGA)is designed.Two-level parallel architecture is used and also combines with two different programming models which are MPI and Athread.Compared with the traditional genetic algorithm implemented on single-core or multi-core cluster with single-level parallel architecture,the algorithm using two-level parallel architecture is implemented on the Sunway many-core processors,which get better performance and run with higher speedup ratio.By studying the characteristics of Sunway many-core processors and parallel genetics,a "coarse-grained combined with fine-grained" hybrid parallel genetic algorithm(CFPGA)is designed.Through the use of register communication technology to complete the transfer of data from the CPE.This communication method needs to manage each CPE explicitly.Although it faces challenges such as high complexity,difficulty in debugging,and abnormal when using communication media,its extremely high communication efficiency can reduce the execution time of the algorithm.In order to further improve the performance of the algorithm,this paper proposes a dynamic migration strategy.Traditional parallel genetic algorithm is based on fixed generations to perform the migration operation.Its purpose is to improve the diversity of the population.Some population diversity is abundant enough that there is no need to introduce other population individuals.This situation simplifies the migration operation.The efficiency of the algorithm is improved by reducing the amount of communication and computation.A Hybrid Parallel Genetic Algorithm with Dynamic Migration strategy(HBPGA-DM)is designed.In the experiment,when using 2000*64 CPEs,the CPE speedup ratio is more than 40 and parallel efficiency is more than 62%.The maximum speedup ratio exceeds 500.