A Non-Systolic Matrix Product Algorithm

Abstract

Most parallel matrix-matrix product algorithms for MIMD architectures are systolic. These algorithms can be adapted to be used on a general purpose architecture, such as the CHiP or cube machines. When the processors already contain the matrices, the algorithm can still be used by modifying it to circulate the data as if it was being fed in from an external source. We present a non-systolic matrix product algorithm in which the data movement is not the circulation pattern of the adapted systolic algorithms. Rather, it uses technique similar to Strassen's algorithm. The running time is O(n) using n- squared processors for nxn matrices. We compare this algorithm to a systolic algorithm and give experimental results. Keywords: Wavefront array processors; XX Parallel language.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1985
Accession Number
ADA196418

Entities

People

  • Philip A. Nelson

Organizations

  • University of Washington

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Information Systems
  • Language
  • Military Research
  • Preprocessing
  • Standards
  • Universities
  • Wavefronts

Fields of Study

  • Engineering

Readers

  • Linear Algebra
  • Parallel and Distributed Computing.