Solution of dense linear systems on an optimal systolic architecture
type: Item
instance of: scholarly article
title: Solution of dense linear systems on an optimal systolic architecture
zbMATH Open document ID: 0645.65016
DOI: 10.1016/0045-7906(87)90011-5
author: Ahmed El-Amawy
published in: Computers and Electrical Engineering
publication date: 1987-01-01T00:00:00Z
review text: 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\times n\) in \(4n+1\) time units including I/O time. Data communications are strictly local and the processing elements (PEs) are simple. The complete three-phase algorithms is executed on a single array, employing about \(3n^ 2/2\) PEs without any need for costly inter- phase I/O. 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.
Mathematics Subject Classification ID: 65F05
zbMATH DE Number: 4052885
zbMATH Keywords: matrix triangularization
zbMATH Keywords: Gaussian elimination
zbMATH Keywords: optimal systolic array architecture
zbMATH Keywords: dense systems
zbMATH Keywords: Data communications
zbMATH Keywords: three-phase algorithms
zbMATH Keywords: Design optimality
MaRDI profile type: Publication
full work available at URL: 0045-7906(87)90011-5
OpenAlex ID: W2007545751
description: scientific article; zbMATH DE number 4052885