Final Report on LLNL Subcontract B503962 Atlas

Dongarra, J ; Falgout, R

Lawrence Livermore National Laboratory

关键词: Lawrence Livermore National Laboratory;    Storage;    Vectors;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;    Algebra;   

DOI  :  10.2172/15002963
RP-ID  :  UCRL-CR-144861
RP-ID  :  W-7405-ENG-48
RP-ID  :  15002963

美国|英语

来源: UNT Digital Library

【 摘 要 】

Determining and characterizing the effectiveness of run-time optimization techniques is particularly relevant to modern sparse linear algebra software libraries that tend to hide from the user the internal storage format. For instance, a certain storage structure may dictate a particular algorithmic approach. Once a general scheme of access has been found based on a storage structure, one promising idea involves analyzing the sparsity pattern of the matrix operand to find places where the efficient static optimization techniques may be re-used. There are numerous ways in which this can be done, and it is almost certain that there will be no provably best way. In this case, it will also be necessary to search the space of available options during run-time. We have experimented with a variety of techniques for optimizing sparse matrix vector multiplication to take instruction sets, functional units, and memory hierarchies into account on the Power 3 architecture. Sparse matrix-vector multiplication is of course the inner loop in any iterative solver, even multigrid, since it includes all the interpolation, restriction, and smoothing operations. The structural properties of the application leads to sparse matrices that feature a sufficiently regular pattern, so that the automatic optimization techniques already integrated in ATLAS can be successfully re-used and applied to generate the appropriate basic sparse linear algebra kernels needed in many applications. Our plan for achieving the necessary and exceptionally high degree of portability and optimization leverages the experience of our team in developing ATLAS technology.