Fast Solving Linear Equations On Heterogeneous Parallel Machines

Solving large sparse linear systems arise in numerous science and engineering prob-lems. Since it represents the dominant cost in the entire calculation time, it becomes the key to quickly solving the linear systems for the efficient numerical simulation. Nowadays, the GPU has evolved into a highly parallel coprocessor which is suited to compute-intensive, highly parallel computation. And more and more supercomputers are equipped with GPUs, developing the efficient parallel algorithm for heterogeneous computers has important significance.To solve the large sparse linear systems, the Krylov subspace iterative method is the best choice, and the sparse matrix-vector multiplication(SpMV) is the most important part of the Krylov subspace iterative method. For these general matrices, a new data structure based on the bisection ELLPACK format, BiELL, is designed to realize the load balance better. Besides, based on the same idea of JAD format, the BiJAD format can be obtained. Experimental results on various matrices show that the BiELL and BiJAD formats perform better than other similar formats, especially when the number of non-zero elements per row varies a lot.Then we complete the Kryloy subspace iterative method with the SpMV kernel based on these two formats. Similar conclusions are obtained that for the most un-structured matrices, the performance of solver with BiELL and BiJAD formats are superior to others. Neumann polynomial preconditioning with three parameters are used to accelerate the convergence, numerical results show that when the degree of the polynomial is odd, the convergence rate has significantly improved, and the choice of the optimal degree is considered. Besides, compared with the ILUT/IC preconditioning, the polynomial preconditioning has the higher performance.Finally, for the linear systems obtained from using the five-point finite difference method to discrete the Poisson equations, we use the conjugate gradient algorithm(CG) to solve it in the heterogeneous parallel computers, the iterative time reduced compared with completing the CG with MPI. When realize the SpMV, the technique to overlap the computing and communication and used, which means that send data to its neighbor first, then compute the inner data in GPUs, and simultaneously receive the data and compute the boundary data in CPUs, numerical results show that the program has improved the performance.