Parallel solution of linear systems with striped sparse matrices |
| |
Affiliation: | 1. Energy Conversion Group, Lawrence Berkeley National Laboratory, Berkeley, CA, 94720, USA;2. Nexceris, Lewis Center, OH, 43035, USA;3. Department of Clinical Research, University of Bern, 3010 Bern, Switzerland;4. Experimental Morphology at the Institute of Anatomy, and University of Bern, 3010 Bern, Switzerland;5. Institute of Clinical Chemistry, University of Bern, 3010 Bern, Switzerland |
| |
Abstract: | The multiplication of a vector by a matrix and the solution of triangular linear systems are the most demanding operations in the majority of iterative techniques for the solution of linear systems. Data-driven VLSI networks which perform these two operations, efficiently, for certain sparse matrices are introduced. In order to avoid computations that involve zero operands, the non-zero elements in a sparse matrix are organized in the form of non-overlapping stripes, and only the elements within the stripe structure of the matrix are manipulated. Detailed analysis of the networks proves that both operations may be completed in n global cycles with minimal communication overhead, where n is the order of the linear system. The number of cells in each network as well as the communication overhead, are determined by the stripe structure of the matrix. Different stripe structures for the class of sparse matrices generated in Finite Element Analysis are examined in a separate paper. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|