Data-flow algorithms for parallel matrix computation
Dianne Prost O’Leary, G. W. Stewart · Communications of the ACM · 1985
In this article we develop some algorithms and tools for solving matrix problems on parallel processing computers. Operations are synchronized through data-flow alone, which makes global synchronization unnecessary and enables the algorithms to be implemented on machines with very simple operating systems and communication protocols. As examples, we present algorithms that form the main modules for solving Liapounov matrix equations. We compare this approach to wave front array processors and systolic arrays, and note its advantages in handling missized problems, in evaluating variations of algorithms or architectures, in moving algorithms from system to system, and in debugging parallel algorithms on sequential machines.
Cited by 90 works. doi:10.1145/4021.4025 Open-access PDF
Authors
References
- Introduction to matrix computations
- Why systolic architectures?
- Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing
- Algorithm 432 [C2]: Solution of the matrix equation AX + XB = C [F4]
- Data Flow Supercomputers
- On the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting Speedup
- A Survey of Parallel Algorithms in Numerical Linear Algebra
- Data-Driven and Demand-Driven Computer Architecture
- Optimization and interconnection complexity for: parallel processors, single-stage networks, and decision trees
- Computation of the Singular Value Decomposition Using Mesh-Connected Processors