article

Optimizing Tridiagonal Solvers for Alternating Direction Methods on Boolean Cube Multiprocessors

Authors:

S. Lennart JohnssonAuthors Info & Claims

SIAM Journal on Scientific and Statistical Computing, Volume 11, Issue 3

Pages 563 - 592

Published: 01 May 1990 Publication History

Abstract

Sets of tridiagonal systems occur in many applications. Fast Poisson solvers and Alternate Direction Methods make use of tridiagonal system solvers. Network-based multiprocessors provide a cost-effective alternative to traditional supercomputer architectures. The complexity of concurrent algorithms for the solution of multiple tridiagonal systems on Boolean-cube-configured multiprocessors with distributed memory are investigated. Variations of odd-even cyclic reduction, parallel cyclic reduction, and algorithms making use of data transposition with or without substructuring and local elimination, or pipelined elimination, are considered. A simple performance model is used for algorithm comparison, and the validity of the model is verified on an Intel iPSC/ 1. For many combinations of machine and system parameters, pipelined elimination, or equation transposition with or without substructuring is optimum. Hybrid algorithms that at any stage choose the best algorithm among the considered ones for the remainder of the problem are presented.It is shown that the optimum partitioning of a set of independent tridiagonal systems among a set of processors yields the embarrassingly parallel case. If the systems originate from a lattice and solutions are computed in alternating directions, then to first order the aspect ratio of a computational lattice shall be the same as that of the lattice forming the base for the equations.The experiments presented here demonstrate the importance of combining in the communication system for architectures with a relatively high communications start-up time.

References

[1]

B. L. BUZBEE, G. H. GOLUB, AND C. W. NIELSON, On direct methods for solving Poisson's equations, SIAM J. Numer. Anal., 7 (1970), pp. 627-656.

[2]

M. Y. CHAN, Dilation-2 embeddings of grids into hypercubes, Tech. Report UTDCS 1-88, Department of Computer Science, University of Texas, Dallas, TX, 1988.

[3]

W. J. DALLY, Wire-efficient VLSI multiprocessor communication networks, Tech. Report, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, September 1986.

[4]

S. C. EISENSTAT, personal communication, 1988.

[5]

A. GEORGE, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345-363.

[6]

C.-T. Ho AND S. L. JOHNSSON, Distributed routing algorithms for broadcasting and personalized communication in hypercubes, in 1986 Internat. Conference on Parallel Processing, IEEE Computer Society, New York, 1986, pp. 640-648.

[7]

C.-T. Ho AND S. L. JOHNSSON, On the embedding of arbitrary meshes in Boolean cubes with expansion two dilation two, in 1987 Internat. Conference on Parallel Processing, Pennsylvania State University, 1987, pp. 188-191.

[8]

C.-T. Ho AND S. L. JOHNSSON, Spanning balanced trees in Boolean cubes, SIAM J. Sci. Statist. Comput., 10 (1989), pp. 607-630.

[9]

R. W. HOCKNEY AND C. R. JESSHOPE, Parallel Computers, Adam Hilger, Bristol, 1981.

[10]

S. L. JOHNSSON, Odd-even cyclic reduction on ensemble architectures and the solution tridiagonal systems of equations, Tech. Report YALE/DCS/RR-339, Department of Computer Science, Yale University, New Haven, CT, October 1984.

[11]

S. L. JOHNSSON, Data permutations and basic linear algebra computations on ensemble architecture, Tech. Report YALEU/DCS/RR-367, Department of Computer Science, Yale University, New Haven, CT, February 1985.

[12]

S. L. JOHNSSON, Communication efficient basic linear algebra computations on hypercube architectures, J. Parallel Distributed Comput., 4 (1987), pp. 133-172.

[13]

S. L. JOHNSSON, Fast pfe solvers on fine and medium grain architectures, in Advances in Computer Methods for Partial Differential Equations--VI, IMACS, 1987, pp. 405-410.

[14]

S. L. JOHNSSON, Solving tridiagonal systems on ensemble architectures, SIAM J. Sci. Statist. Comput., 8 (1987), pp. 354-392.

[15]

S. L. JOHNSSON AND C.-T. Ho, Spanning graphs for optimum broadcasting and personalized communication in hypercubes, IEEE Trans. Comput., 38 (1989), pp. 1249-1268.

[16]

S. L. JOHNSSON AND C.-T. Ho, Multiple tridiagonal systems, the alternating direction method, and Boolean cube configured multiprocessors, Tech. Report YALEU/DCS/RR-532, Department of Computer Science, Yale University, New Haven, CT, June 1987.

[17]

S. L. JOHNSSON AND C.-T. Ho, Matrix transposition on Boolean n-cube configured ensemble architectures, SIAM J. Matrix Anal. Appl., 9 (1988), pp. 419-454.

[18]

S. L. JOHNSSON AND P. LI, Solutionset for AMA/CS 146, Tech. Report 5085:DF:83, California Institute of Technology, Pasadena, CA, May 1983.

[19]

S. L. JOHNSSON, Y. SAAD, AND M. H. SCHULTZ, Alternating direction methods on multiprocessors, SIAM J. Sci. Statist. Comput., 8 (1987), pp. 686-700; Tech. Report YALE/DCS/RRo382, Department of Computer Science, Yale University, New Haven, CT, August 1985.

[20]

D. S. LIM AND R. V. THANAKIJ, A survey of alternating direction implicit (adi) method implementations on hypercubes, in Hypercube Multiprocessors 1987, Michael T. Heath, ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 1987.

[21]

A. RANADE AND S. L. JOHNSSON, The communication efficiency of meshes, Boolean cubes, and cube connected cycles for wafer scale integration, in 1987 Internat. Conference on Parallel Processing, IEEE Computer Society, New York, 1987, pp. 479-482.

[22]

E. M. REINGOLD, J. NIEVERGELT, AND N. DEO, Combinatorial Algorithms, Prentice-Hall, Englewood Cliffs, NJ, 1977.

[23]

C. L. SEITZ, Concurrent VLSI architectures, IEEE Trans. Comput., 33 (1984), pp. 1247-1265.

[24]

C. L. SEITZ, Experiments with VLSI ensemble machines, J. VLSI Comput. Syst., 1 (1986), pp. 311-334.

[25]

I. E. SUTHERLAND AND C. A. MEAD, Microelectronics and computer science, Scientific American, September 1977, pp. 210-228.

[26]

H. H. WANG, A parallel method for tridiagonal equations, ACM TOMS, 7 (1981), pp. 170-183.

Cited By

Zhang YCohen JOwens J(2010)Fast tridiagonal solvers on the GPUACM SIGPLAN Notices10.1145/1837853.169347245:5(127-136)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1837853.1693472
Zhang YCohen JOwens JGovindarajan RPadua DHall M(2010)Fast tridiagonal solvers on the GPUProceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/1693453.1693472(127-136)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1693453.1693472
Yuan LGuo HYin Z(2009)On optimal message vector length for block single parallel partition algorithm in a three-dimensional ADI solverApplied Mathematics and Computation10.1016/j.amc.2009.08.052215:7(2565-2577)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.amc.2009.08.052
Show More Cited By

Index Terms

Optimizing Tridiagonal Solvers for Alternating Direction Methods on Boolean Cube Multiprocessors
1. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Partial differential equations
  2. Mathematical software
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

Alternating-Direction Line-Relaxation Methods on Multicomputers

We study the multicom.puter performance of a three-dimensional Navier–Stokes solver based on alternating-direction line-relaxation methods. We compare several multicomputer implementations, each of which combines a particular line-relaxation method and a ...
Note on the Parallel Efficiency of the Frederickson-McBryan Multigrid Algorithm

Standard multigrid algorithms must lead to processor idle time on large-scale parallel computers because the coarsest grids have fewer points than processors. In some cases, this may be considered to be a disadvantage. Frederickson and McBryan [...
A Parallel Two-Level Hybrid Method for Tridiagonal Systems and Its Application to Fast Poisson Solvers

Abstract--A new method, namely, the Parallel Two-Level Hybrid (PTH) method, is developed to solve tridiagonal systems on parallel computers. PTH has two levels of parallelism. The first level is based on algorithms developed from the Sherman-Morrison ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific and Statistical Computing

SIAM Journal on Scientific and Statistical Computing Volume 11, Issue 3

1990

203 pages

ISSN:0196-5204

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 May 1990

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YCohen JOwens J(2010)Fast tridiagonal solvers on the GPUACM SIGPLAN Notices10.1145/1837853.169347245:5(127-136)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1837853.1693472
Zhang YCohen JOwens JGovindarajan RPadua DHall M(2010)Fast tridiagonal solvers on the GPUProceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/1693453.1693472(127-136)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1693453.1693472
Yuan LGuo HYin Z(2009)On optimal message vector length for block single parallel partition algorithm in a three-dimensional ADI solverApplied Mathematics and Computation10.1016/j.amc.2009.08.052215:7(2565-2577)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.amc.2009.08.052
Sun XZhang W(2004)A Parallel Two-Level Hybrid Method for Tridiagonal Systems and Its Application to Fast Poisson SolversIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2004.126479415:2(97-106)Online publication date: 1-Feb-2004
https://dl.acm.org/doi/10.1109/TPDS.2004.1264794
Povitsky A(2002)Parallel ADI solver based on processor schedulingApplied Mathematics and Computation10.1016/S0096-3003(01)00174-6133:1(43-81)Online publication date: 25-Nov-2002
https://dl.acm.org/doi/10.1016/S0096-3003%2801%2900174-6
Povitsky A(1999)Parallelization of Pipelined Algorithms for Sets of Linear Banded SystemsJournal of Parallel and Distributed Computing10.1006/jpdc.1999.156859:1(68-97)Online publication date: 1-Oct-1999
https://dl.acm.org/doi/10.1006/jpdc.1999.1568
Bruck JHo CUpfal EKipnis SWeathersby D(1997)Efficient Algorithms for All-to-All Communications in Multiport Message-Passing SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/71.6429498:11(1143-1156)Online publication date: 1-Nov-1997
https://dl.acm.org/doi/10.1109/71.642949
Hofhaus JVan de Velde E(1996)Alternating-Direction Line-Relaxation Methods on MulticomputersSIAM Journal on Scientific Computing10.1137/S106482759325387217:2(454-478)Online publication date: 1-Mar-1996
https://dl.acm.org/doi/10.1137/S1064827593253872
Bruck JHo CKipnis SWeathersby DSnyder LLeiserson C(1994)Efficient algorithms for all-to-all communications in multi-port message-passing systemsProceedings of the sixth annual ACM symposium on Parallel algorithms and architectures10.1145/181014.181756(298-309)Online publication date: 1-Aug-1994
https://dl.acm.org/doi/10.1145/181014.181756
Sun XZhang HNi L(1992)Efficient Tridiagonal Solvers on MulticomputersIEEE Transactions on Computers10.1109/12.12744141:3(286-296)Online publication date: 1-Mar-1992
https://dl.acm.org/doi/10.1109/12.127441

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents