Research On Heterogeneous Parallel Acceleration Technology For Typical Optimization Solution Algorithms

Optimization problems develop with the development of management decision science.Some basic optimization theories have laid a milestone in the development of optimization theory and described the characteristics of the optimal solution.However,until people used computers to solve various large-scale optimization problems,the solution method of optimization problems has become an effective tool in practical engineering,decision-making,and management.With the development of computer architecture and various new architectures,the computing power of various heterogeneous architectures is becoming stronger and stronger.How to use the huge computing power and parallel acceleration technology to effectively improve the performance of optimization problems have become one of the focuses of current researchers.In this paper,we study the two representative optimization problems and their algorithms.In the field of bioinformatics,using PairHMM forward algorithm to find the best sequence alignment is very popular in many different biological sequence analysis tools,and it is the most widely used dynamic programming algorithm in the genome sequence alignment algorithm.In the field of transportation networks,the estimation of origindestination(OD)flow is very important.To solve the problem of traffic estimation,a new linear forward model is proposed,which includes the problem of multi-objective iterative optimization.How to speed up these two kinds of optimization problems through parallel optimization technology is one of the application problems to be solved in practical application.Firstly,we study the related optimization problems and the development and achievements of parallel optimization technology.Secondly,we use Open MP tools,load balancing and other methods to optimize the algorithm.Finally,we give the performance improvement of the algorithm.The purpose is to provide a basic comparison for further parallel accelerator design on the FPGA platform.Thirdly,we propose a PairHMM forward algorithm accelerator based on the FPGA platform.The accelerator adopts a non-cooperative structure to organize processing units and a task level parallel scheme.We designed a non-cooperative processing element(PE)to perform the calculation of the PairHMM forward algorithm independently.In addition,based on the non-cooperative PE structure,we designed a new chain topology for the accelerator.Experiments show that the new topology further improves the performance of PairHMM forward algorithm accelerator,with a maximum performance improvement of 20 %.Finally,for the linear forward model of network traffic estimation,this paper proposes a further improved model by compressing it,and realizes the acceleration of this application.In this paper,the multivariable optimization problem with nonlinear constraints in the original model is transformed into a standard quadratic programming problem with constraints.Through the optimization of the model level,the improved model in this paper achieves an acceleration ratio of 1.13 times.Furthermore,by selecting the algorithm and optimizing the implementation level,compared with the previous model,the maximum acceleration ratio achieved in this paper is 49 times.