MOB forms: a class of multilevel block algorithms for dense linear algebra operations

ABSTRACT

Multilevel block algorithms exploit the data locality in linear algebra operations when executed in machines with several levels in the memory hierarchy. It is shown that the family we call Multilevel Orthogonal Block (MOB) algorithms is optimal and easy to design and that using the multilevel approach produces significant performance improvements. The effect of interference in the cache, of the TLB misses, and of page faults are also considered. The multilevel block algorithms are evaluated analytically for an ideal memory system with M cache levels without interferences. Moreover, experimental results of the MOB forms in some present high performance workstations are presented.

REFERENCES

• Ande92: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• Aspr93: Tom Asprey , Gregory S. Averill , Eric DeLano , Russ Mason , Bill Weiner , Jeff Yetter, Performance Features of the PA7100 Microprocessor, IEEE Micro, v.13 n.3, p.22-35, May 1993 [doi>10.1109/40.216746]
• CaKe92: S. Carr , K. Kennedy, Compiler blockability of numerical algorithms, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.114-124, November 16-20, 1992, Minneapolis, Minnesota, United States
• Chen91: Dingju Chen, Hierarchical blocking and data flow analysis for numerical linear algebra, Proceedings of the 1990 conference on Supercomputing, p.12-19, October 1990, New York, New York, United States
• DoMR91: J. J. Dongarra, P. Mayes and G. Radicati, The IBM RISC System/6000 and Linear Algebra Operations. Supercomputer, July 1991, pp. 15-30.
• DoGK84: J. Dongarra, F. Gustavson and A. Karp, Implementing linear algebra algorithms for dense matrices on a vector pipeline machine. SIAM Rev., 26 (1984), pp. 91-112.
• Dutt92: T.A. Dutton et al., The Design of the DEC 3000 AXP Systems, Two High-Perform~.nce Workstations, Digital Technical Journal, Vol 4, Num. 4 1992. pp 66-81
• GaJM88: K. Gallivan, W. Jalby, U. Meier, and A. Sameh, Impact of hierarchical memory systems on linear algebra algorithm design. Intl. J. Supercomputer Appl., 2(1988), pp. 12-48
• GaPS90: K. A. Gallivan , R. J. Plemmons , A. H. Sameh, Parallel algorithms for dense linear algebra computations, SIAM Review, v.32 n.1, p.54-135, March 1990 [doi>10.1137/1032002]
• HePa91: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• JaMe86: W. Jalby and U. Meier, Optimizing matrix operations on a parallel multiprocessor with a hierarchical memory system, in Proc. Intl. Conf. Par. Processing, IEEE Computer Society Press, New York, 1986, pp. 429-432
• LaRW91: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• McCo69: A. C. McKellar , E. G. Coffman, Jr., Organizing matrices and matrix operations for paged memory systems, Communications of the ACM, v.12 n.3, p.153-165, March 1969 [doi>10.1145/362875.362879]
• NaJV93: J.J. Navarro, A. Juan, M. Valero~ J.M. Llaberia and T. Lang, Multilevel Orthogonal Blocking for Dense Linear Algebra Computations, IEEE Computer Society TC on Computer Architecture Newsletter, Fall 1993, pp. 10-14
• OeGr90: R. R. Oehler , R. D. Groves, IBM RISC System/6000 processor architecture, IBM Journal of Research and Development, v.34 n.1, p.23-36, Jan. 1990
• TeGJ93: O. Temam , E. D. Granston , W. Jalby, To copy or not to copy: a compile-time technique for assessing when data copying should be used to eliminate cache conflicts, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.410-419, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169762]
• Wolf87: Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Measurement, Performance, Theory