Solution of dense linear systems on an optimal systolic architecture |
| |
Authors: | Ahmed El-Amawy |
| |
Affiliation: | Department of Electrical and Computer Engineering, Louisiana State University, Baton Rouge, LA 70823, U.S.A. |
| |
Abstract: | The paper presents an optimal systolic array architecture for rapid solution of dense systems of linear equations. The array solves a system of size n×n in 4n + 1 time units including I/0 time. Data communications are strictly local and the processing elements (PEs) are simple. The complete three-phase solution algorithm is executed on a single array, employing about 3n2/2 PEs without any need for costly inter-phase I/0. Due to a novel data steering mechanism, the three algorithmic phases are maximally overlapped. Design optimality is established using systolic precedence diagrams. It is also shown that merging the functions of two adjacent PEs into a single PE is possible resulting in maximal PE utilization. An interesting result regarding cascading phase-optimal arrays is obtained. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|