A parallel algorithm for solving tridiagonal linear systems on coarse grained multicomputer

• E. L. G. Saukas USP
• S. W. Song USP

DOI: https://doi.org/10.5753/sbac-pad.1997.22642

Resumo

The CGM (coarse-grained multicomputer) model has been proposed to be a model of parallelism sufficiently close to existing parallel machines. Despite its simplicity it intends to give a reasonable prediction of performance when parallel algorithms are implemented. Under the CGM model we design a communication-efficient parallel algorithm for the solution of tridiagonallinear systems with n equations and n unknowns. This algorithm requires only a constant number of communication rounds. The amount of data transmitted in each communication round is proportional to the number of processors and independent of n. In addition to showing its theoretical complexity, we have implemented this algorithm on a real distributed memory parallel machine. The results obtained are very promising and show an almost linear speedup for large n indicating the efficiency and scalability of the proposed algorithm.

Palavras-chave: Coarse grained multicomputer, parallel algorithm, tridiagonal linear systems, band matrices, odd-even reduction algorithm

Referências

Caceres, E., Dehne, F., Ferreira, A., Flocchini, P., Rieping, I., Roncato, A., Santoro, N., and Song, S. W. Efficient parallel graph algorithms for coarse grained multicomputers and BSP. Proceedings ICALP'97 - 24th International Colloquium on Automata, Languages, and Programming, P. Degano and A. Marchetti-Spaccamela (editors). Lecture Notes in Computer Science (1997)

Dehne, F., Fabri, A. and Rau-Chaplin, A. Scalable Parallel Geometric Algorithms for Coarse Grained Multicomputers, in Proc. ACM 9th Annual Computational Geometry (1993) 298-307

Dehnc, F., Fabri, A. and Kenyon, C. Scalable and Architecture lndependent Parallel Geometric Algorithms with High Probability Optimal Time, in Proc. 6th IEEE Symposium on Parallel and Distributed Processing (1994) 586-593

Dehne, F., Deng, X., Dymond, P., Fabri, A. and Kokhar, A. A. A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, in Proc. ACM Symposium on Parallel Algorithms and Architectures (SPAA'95) (1995) 27-33

Ericksen, J. Iterative and direct methods for solving Poisson's equation and their adaptability to ILLIAC IV. Center for Advanced Computation Document 60, University of Illinois, 1972.

Kockney, R. The potential calculation and some applications. Meth. Comput. Physics 9 (1970) 135-211

Krechel, A., Plum, H. J. and Stben, K. Solving tridiagonal linear systems in parallel on local memory MIMD machines. GMD technical report 372 (1989)

Leighton, T. Introduction to parallel algorithms and architectures: arrays, trees and hypercubes. Morgan Kaufmann (1991)

Stonc, H. An efficient parallel algorithm for the solution of a tridiagonal linear system of equations. Journal of the ACM 20 (1973) 27-38

Valiant, L. G. et al. General Purpose Parallel Architectures, Handbook of Theoretical Computer Science, Edited by J. van Leeuwen, MIT Press/Elsevier (1990) 943-972