Structured sparse matrix-vector multiplication on massively parallel SIMD architectures
Autor: | V. Sperling, T. Dehn, K. Giebermann, Michael Eiermann |
---|---|
Rok vydání: | 1995 |
Předmět: |
Spanning tree
Computer Networks and Communications Computer science Diagonal Sparse matrix-vector multiplication Parallel computing Computer Graphics and Computer-Aided Design Matrix multiplication Theoretical Computer Science Matrix (mathematics) Artificial Intelligence Hardware and Architecture Graph (abstract data type) Distributed memory Multiplication SIMD Massively parallel Software |
Zdroj: | Parallel Computing. 21:1867-1894 |
ISSN: | 0167-8191 |
Popis: | We propose an algorithm for the cost-effective evaluation of structured sparse matrix-vector multiplications on massively parallel SIMD computers with distributed memory. Under the assumption that a large percentage of the nonzero entries of the matrix is concentrated on almost full diagonals, a specific data transport problem arises, for which we derive an equivalent graph theoretical formulation. We find an optimal solution of this communication problem in terms of a minimum-cost spanning tree. We demonstrate the efficiency of our matrix-vector multiplication on a MasPar MP-1 with 16,384 processors. |
Databáze: | OpenAIRE |
Externí odkaz: |