How to vectorize the algebraic multilevel iteration

ABSTRACT

We consider the algebraic multilevel iteration (AMLI) for the solution of systems of linear equations as they arise form a finite-difference discretization on a rectangular grid. Key operation is the matrix-vector product, which can efficiently be executed on vector and parallel-vector computer architectures if the nonzero entries of the matrix are concentrated in a few diagonals. In order to maintain this structure for all matrices on all levels coarsening in alternating directions is used. In some cases it is necessary to introduce additional dummy grid hyperplanes. The data movements in the restriction and prolongation are crucial, as they produce massive memory conflicts on vector architectures. By using a simple performance model the best of the possible vectorization strategies is automatically selected at runtime. Examples show that on a Fujitsu VPP300 the presented implementation of AMLI reaches about 85% of the useful performance, and scalability with respect to computing time can be achieved.

REFERENCES

• 1: Owe Axelsson, Iterative solution methods, Cambridge University Press, New York, NY, 1995
• 2: AXELSSON,O.AND NEYTCHEVA, M. 1994. Algebraic multilevel iteration method for Stieltjes matrices. Num. Lin. Alg. Appl. 1, 213-236.
• 3: BARRETT, R., BERRY, M., CHAN, T., DEMMEL, J., DONATO, J., DONGARRA, J., EIJKHOUT, V., POZO, R., ROMINE, C., AND VAN DER VORST, H. 1994. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM.
• 4: CRAY RESEARCH. 1986. Autotasking User's Guide. Cray Research Inc.
• 5: Jack J. Dongarra , Lain S. Duff , Danny C. Sorensen , Henk A. Vander Vorst, Numerical Linear Algebra for High Performance Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 6: FUJITSU HIGH-PERFORMANCE COMPUTING GROUP. 1996. R&D Server VX/VPP300/VPP700 Series SA/SE Handbook. Fujitsu High-Performance Computing Group.
• 7: FUJITSU. 1997. VPP Fortran User's Guide. Fujitsu Ltd.
• 8: GILBERT, W. J. 1976. Modern Algebra and Applications. John Wiley, New York.
• 9: HACKBUSCH, W. 1985. Multigrid Methods and Applications. Springer-Verlag, Berlin, Heidel-berg, New York.
• 10: INOUE, M., FURUI, T., KATAYAMA, H., AND NAKANISHI, K. 1998. Development, concept and overview of the SX-5 series supercomputers. SX World 21, 1-4. see URL http://www.hpc. comp.nec.co.jp/sx-e/sx-world/no23/en4.pdf.
• 11: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 12: C. Maples, Utilizing virtual shared memory in a topology independent, multicomputer environment, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.188-198, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97685]
• 13: Maya G. Neytcheva, Experience in implementing the algebraic multilevel iteration method on a SIMD-type computer, Applied Numerical Mathematics, v.19 n.1-2, p.71-90, Nov. 1995 [doi>10.1016/0168-9274(95)00019-Q]
• 14: NEYTCHEVA, M., ADIY, A., MELLAARD, M., GEOGIEV, K., AND AXELSSON, O. 1996. Scalable and optimal iterative solvers for linear and nonlinear problems. Final Report 9613, Department of Mathematics, University of Nijmegen, The Netherlands.
• 15: Y. Saad, ILUM: a multi-elimination ILU preconditioner for general sparse matrices, SIAM Journal on Scientific Computing, v.17 n.4, p.830-847, July 1996 [doi>10.1137/0917054]
• 16: SCHOENAUER, W. 1999. Scientific Supercomputing: Architecture and Use of Shared and Distributed Memory Parallel Computers, Volume Addendum. Willi Schoenauer, Karlsruhe. see http://www.uni-karlsruhe.de/Uni/RZ/Personen/rz03/book/.
• 17: W. Schönauer, Scientific computing on vector computers, Elsevier Science Inc., New York, NY, 1987
• 18: Marc Snir , Steve W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
• 19: WEISS, R. 1996. Parameter-Free Iterative Linear Solvers. Mathematical Research, vol. 97. Akademie Verlag, Berlin.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Algorithms, Performance

Keywords:
large linear systems, multigrid method, numerical software, parallel processing, preconditioned iterative solver, vector computer