Research Of Parallel GaBP Algorithm In Solving Large-scale Sparse Linear Systems

When many practical problems in natural sciences and social sciences are simu-lated, these problems are generally boiled down to the solving of sparse linear equations. For example:In structural design, numerical weather prediction, oil and gas resource exploration, numerical wind tunnel, stellar atmosphere analysis and simulation of nu-clear and other fields, partial differential equations are often used as the mathematical model. While in the discrete solving of partial differential equations, sparse linear equa-tion plays an important role. Furthermore, sparse linear equations are widely applied in mathematical programming, network analysis, economic points off, discrete Markov chain and many other areas. In the meanwhile, with the increasing of scale of simulation problems, the time proportion in solving sparse linear equations is also growing. In some application areas, its share has accounted for nearly80%It is because that the solving of sparse linear equations are especially important and very time-consuming, the time complexity always goes beyond O(n2), many scientific research institutions and scientists put a lot of manpower and material resources to carry out their research. In particular, with the development of parallel computer systems, the research on scalable parallel solution is in full swing, resulting in endless emergence of new parallel algorithms.Currently, the distributed shared memory system that uses a mixture of heteroge-neous multi-core CPU, many-core MIC and GPU is gradually becoming the mainstream of parallel computing environment. Hence, research on parallel algorithms that are suited for mixed heterogeneous parallel computing environments and feature high-precision, high efficiency and scalability in solving sparse linear equations is of great importance.Gaussian Belief Propagation (GaBP) algorithm is an iterative algorithm aimed at symmetric diagonally dominant linear equations; it is based on recursively updated prob-abilistic inference algorithm with low complexity and high parallelism, which make it suitable in solving large-scale sparse linear equations. GaBP algorithm differs from the classical iterative algorithm and the Krylov subspace algorithms. GaBP algorithm has good convergence in solving symmetric diagonally dominant linear equations.By study the classical GaBP algorithm, the synchronous and asynchronous im-plementations using various programming languages are given and the test results are deeply analyzed. The aim of this paper is to study the high-performance, high-credible GaBP parallel algorithms in solving large-scale linear systems. The main innovative contributions can be summarized as follows.First, the iterative acceleration method and pretreatment method in solving linear equations are studied and GaBP optimization algorithm is proposed with a variety of preconditioned iterative acceleration approaches. The iterative acceleration GaBP algo-rithm is faster than the classical counterpart in convergence speed, while preconditioned GaBP algorithm extends the suitability of GaBP algorithm, making it suitable in solving linear equations that are not completely symmetrical diagonally dominant.Second, the parallel performance evaluations are studied based on parallel com-puting environments. Different sparse matrix storage methods are studied and two new methods are brought forward, thereby the space complexity of the algorithm is reduced and the computing speed of the algorithm is improved. The implementation of parallel GaBP algorithms and parallel optimization strategy under multi-core GPU, many-core GPU and MIC computer system are studied. Optimization strategies and implementation methods on various parallel platforms are proposed. A multicore-based parallel GaBP algorithm with dynamic load balancing is presented; the experimental results show that this algorithm has good speedup and high efficiency.Third, the implementation of multi-core parallel algorithms and parallel optimiza-tion strategies to further tap the parallel nature of GaBP algorithm is explored. The hybrid MPI+OpenMP implementation of parallel algorithms and parallel optimization strategies are studied, a general solution for solving sparse linear equations using hybrid MPI and OpenMP parallel GaBP algorithm is given. By optimizing iterative computation and data communication, a highly scalable hybrid MPI+OpenMP parallel GaBP optimization algorithm for solving tri-diagonal linear equations is given. Based on this algorithm, an updated algorithm for solving striped linear equations is also presented.