Research Of Parallel Evolutionary Algorithm Based On Sunway Manycore Architecture

Evolutionary algorithms,as classical heuristic search algorithms,have become an important tool for solving various practical problems due to their excellent performance.As evolutionary algorithms are more and more widely used in science and industry,the demand for the efficiency of solving evolutionary algorithms is increasing.However,the performance of evolutionary algorithms in solving large-scale optimization problems can hardly meet the demand for high efficiency.It is of great practical importance to solve this problem by conducting parallelization studies on high-performance clusters.Sunway Taihu Light has a peak computing performance over 125 PFlops,and its powerful computing capabilities that provide an ideal platform for improving the efficiency of evolutionary algorithms.The Heterogeneous Many-Core Sunway Processor used in Sunway Taihu Light has made great innovations in physical architecture,which not only has powerful computing power but also performs well in terms of energy consumption ratio,but the change in architecture makes the memory model and programming model change dramatically,and the original parallel algorithm cannot play the role of Sunway Taihu Light's.The parallelism of the algorithm needs to be redesigned in both process-level and thread-level ways according to the architectural characteristics.In this paper,we conduct a series of parallelization studies on the solution process of large-scale problems by using Self-adaptive Differential Evolution with Neighborhood Search(Sa NSDE)as the optimization algorithm,and the main work are as follows:(1)The Sunway Cooperative Co-evolution Sa NSDE(sw CCSa NSDE)is designed and implemented for the dimensional parallelism of large-scale problems.The process level uses the cooperative coevolution model as a parallel model to decompose the high-dimensional problem into low-dimensional subproblems and distribute them across different processes to perform the subproblem solution operations simultaneously.In order to relieve the computational pressure on a single process,the individual fitness evaluation is accelerated using CPEs and a reasonable access data granularity is designed to address the problem of insufficient memory bandwidth in the SW26010 architecture,using DMA for batch access.It is demonstrated sw CCSa NSDE has better convergence results compared with the serial algorithm and the algorithm using island model and achieved the maximum speedup ratio of239.01 compared to the serial algorithm.(2)The Sunway Pool Sa NSDE(swPSaNSDE)is designed and implemented for parallelism of populations in large-scale problems.The algorithm uses a pool model with the population distribution principle to realize the parallelism of each subpopulation optimization process.To reduce the dependence on access from the CPE,a cellular model is implemented using CPEs,distributing individuals on each CPE,and data sharing of individual information among the CPEs is achieved through register communication.It is experimentally demonstrated that the algorithm exhibits good scalability.(3)The Sunway Hierarchical Sa NSDE(swHSaNSDE)is designed and implemented for the parallelization of dimensional and population layers of large-scale problems.For the large-scale problem,the parallelism between the optimization processes of each subproblem is first achieved by using a cooperative coevolutionary model for grouping in terms of dimensions.Subsequently,the pooling model is used to achieve parallelism of the optimization process for each subpopulation.Finally,the CPEs performance is optimized: In order to solve the problem of discrete access the discrete stored data is adjusted to continuous storage,which not only facilitates the DMA batch access,but also effectively improves the data hit rate within the MPE;the double buffering method is used to overlap the CPEs access with the computation,which effectively hides the CPEs access time.Experimentally,the overall performance of the swHSaNSDE algorithm is further improved and achieved the maximum speedup ratio of 290.93 compared with the serial algorithm.