Research On CPU-GPU Cooperative Parallel Interior Point Algorithm For Solving Structural Nonlinear Programming Problems

In recent years,the Graphics Processing Units(GPU)has achieved fruitful research results in the field of non graphics processing.Meanwhile,to rely on the CPU to solve large-scale problems encountered the difficulty of insufficient resources in the field of optimal calculation.Therefore,this paper designs a cooperative parallel method to solve the structural nonlinear programming based on the CPU and GPU.All the constraints of structured nonlinear programming constitute the set of constraints,and each of constraint in the constraint set is coupled and independent.The formation of the modified equation coefficient matrix has a block edge arrow type structure after using efficient interior point algorithm to solve this kind of problem.In engineering applications,many practical problems with such features,such as:the unit commitment of power system and optimal power flow problem,logistics management in multi commodity network flow problem and network protection problems in the communication,and the unit commitment problem is a typical representative of this kind of problem.Therefore,the study of structured nonlinear programming can help to make better decisions.When using the primal dual interior point method to solve the structured nonlinear programming such as continuous relaxation of the unit commitment problems,through reasonable grouping of variables and constraints,the coefficient matrix of Newton's modified equation generated in the iterative processes has a special structure of block edge.In this paper,the Newton correction equations are decoupled based on the fast decoupling method,the whole Newton correction equation can be decomposed into multiple independent sub-problems and be quickly solved by the collaborative way of CPU and GPU with coarse-grained parallel.Targeting at solving the problem that the coarse-grained parallel computing sub-linear system is difficult to make full use of the GPU resources,this paper puts forward the further optimization of the coarse-grained parallel model.The sub-problem of the Newton equation which is the most time-consuming problem in the processing is solved independently,and the sub-problem is also solved by designing the parallel Gauss Jordan algorithm from the fine-grained level.In this paper,from the coarse grain level,we use the CPU-GPU cooperative parallel to solve the two kinds of application problem whose coefficient matrix of modified equation is respectively in sparse and dense type.The different scale of sub-problems is tested.And the results show that when considering the structured nonlinear programming,for the preprocessing model,especially the structured nonlinear programming with the sub-problem in dense type,the method can get good parallel effect.In addition,from the fine-grained level,the parallel Gauss Jordan algorithm for solving the sub-problem of Newton modified equation has also gain a certain speedup ratio.Therefore,in this paper,the parallel algorithm,designed from coarse-grain aspect and fine-grain aspect,has the potential to solve the structured nonlinear programming.