Efficiency comparison of parallel implementations Thomas algorithm: pipelined Thomas algorithm, parallel Thomas algorithm

Abstract

Study the problem of solutions a series of tridiagonal systems of equations Thomas algorithm for use in three-dimensional problems such as heat conduction problem for large mesh sizes (1000 3 and more). At Supercomputing performance growth requires the use of highly efficient parallel programs. The Thomas algorithm examine of because of that that he is a direct method, economical and easy to implement in the case of a sequential program, but it’s hard to parallelize because of information dependencies between the operations of the algorithm. This method is also used for solving the three-dimensional and two-dimensional problems, which gives rise to a series of Thomas algorithm. And an efficient algorithm parallelization Thomas algorithm will allow to solve such problems on supercomputers with a good performance. The paper summarizes the two algorithm parallelization Thomas algorithm, the example of the one-dimensional solutions of an elliptic equation with different sizes of servings, using MPI standard, as well as a comparison of their efficiency by using a series Thomas algorithm. The results of numerical experiments to study the optimum size of servings, to draw conclusions about the applicability of the studied algorithms for large three-dimensional problems on supercomputers containing tens of thousands of compute nodes and more.