دانلود رایگان مقاله الگوریتم متناوب موازی با و بدون تداخل در معماریهای چند هسته ای

Abstract

We consider the problem of solving large sparse linear systems where the coefficient matrix is possibly singular but the equations are consistent. Block two-stage methods in which the inner iterations are performed using alternating methods are studied. These methods are ideal for parallel processing and provide a very general setting to study parallel block methods including overlapping. Convergence properties of these methods are established when the matrix in question is either M-matrix or symmetric matrix. Different parallel versions of these methods and implementation strategies, with and without overlapping blocks, are explored. The reported experiments show the behavior and effectiveness of the designed parallel algorithms by exploiting the benefits of shared memory inside the nodes of current SMP supercomputers.

5. Conclusions

In this paper we have studied the problem of solving large consistent linear systems by means of parallel alternating two-stage algorithms with and without overlapping. These algorithms have been applied to both singular and nonsingular large linear systems. In the nonsingular case, the problem to be solved comes from the discretization of the Laplace’s equation while in the singular case the test problems arise from Markov chain modeling. The algorithms have been implemented and tested on distributed and shared memory, and using a distributed shared memory model, obtaining a good scalability and efficiency. Generally, the PALU algorithms behave better than the PAGS algorithms. On the other hand, the overlapping algorithms have sped up the convergence time of the non-overlapping algorithms. The amount of overlap needed to improve the convergence rate is problem specific and depends on the characteristics of the matrix and the block diagonal structure considered in the corresponding parallel algorithm.