Research And Realization Of Master-Slave Parallel Genetic Algorithm Based On MIC

With the development of high-technology, scientific research, national defense and economy have meet challenges on its way to high-tech field. The scale of problems needed to be solved expands exponentially on the depth and breadth. Faced with this phenomenon, new research area of high performance computing and big data appears. In our social life, there exit many problems of TSP, combination and task distribution. The problems are NP-Hard that it not possible to find the accurate solution. Genetic Algorithm is a heuristic searching algorithm derived from biological evolutionism to resolve optimization problems. It is proved to be the appropriate method to solve the NP-Hard problems with the characteristic of random, efficient and global search.Parallel Genetic Algorithm (PGA) extends Genetic Algorithm (GA) in parallel with the aim to speed up searching approximate solution. It is a valuable research topic in the data explosion age. There are three popular parallel schemes:master-slave, cellular and island. Different parallel genetic algorithm has its own merits and shortcoming. The traditional master-slave scheme assumes existing only one population, and one master node and several slave nodes are allocated. The master node does the most work of the genetic operation and the slave nodes just evaluate the population, which can not fully utilize computing resource of slave nodes. Compared with master-slave PGA, cellular PGA also assumes existing only one population and every individual is independent. The individuals only can do crossover operation with the individuals connected to it. Different from two PGAs introduced above, island PGA has more than two subpopulations, and it can exchange individuals if the established condition has reached. Individuals of subpopulations immigrate occasionally to keep the diversity of the subpopulation. The importance of exchanging individuals in different populations is to attain the diversity of all the entity, which is a real portrayal of essence of nature keeping the distinction.In this paper, improved Xeon Phi-based Master-Slave PGA (IPMSPGA) is proposed. This algorithm improves traditional master-slave PGA a lot and is able to make full use of salves’computing resources. The characteristic of MIC are multi-core multi-treads, SIMD and library function provided by VPU. We have two types of IPMAPGA, one is IPMSPGA_All the ohter is IPMSPGA_Part. The next generation of IPMSPGA_all comes from crossover and the offspring in IPMSPGA Part half comes from initialization half comes from crossover. The implementation of IPMSPGA needs a large number of high-quality random numbers. The general random numbers generators call the system clock, which can result in interruption on Xeon Phi and much time wasting due to threads waiting. Furthermore, high quality random numbers will worsen time wasting caused by multi-iteration. To resolve this problem, asynchronous transmission is taken into consideration and Xeon Phi has professional instruction set to support asynchronous transmission using PCIe bus connected Xeon Phi and the host CPU. IPMSPGA introduces a two-level parallel scheme of thread-level parallelism and VPU-level parallelism, in which multi-threading implements the SIMD parallelism and Knights Corner instructions (KCi) of VPU achieve more data parallelism. The experimental results show that IPMSPGA can achieve 12X performance improvement for CPU-based traditional master-slave PGA and more than 4X for multi-core master-slave PGA implemented on the host.IPMSPGA is implemented on one Intel Xeon Phi card and the future work can extend on more cards or next generation Xeon Phi. And most PGAs prefer the solutions quality more than execution’s speedups, so more work can concentrate on accelerating the execution time in the condition of assuring the solution quality. In addition, more VPUs implemented in initializing and crossover and converting the different instructions into SIMD are our next work to accelerate the parallel genetic algorithm execution. On more cards, we can let N cards simulate N population and the population does the evolution independently. The populations can exchange when the condition meets. And the host just acts as random number generator, the random number pass to the MIC by the PCIe bus.