Elimination of the computational broadcast in systolic arrays: an application to the qr decomposition algorithm

DOI10.1080/00207160008804954MaRDI QIDQ4489982zbMATH OpenOpenAlexWikidataFDO

Authors M. Gušev, D. J. Evans

Publication date 11 March 2001

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160008804954

zbMATH Keywords

affine recurrence equationscomputational broadcast eliminationdata broadcast eliminationQR decomposition algorithmsystolic arrays

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05)

Review text

Computational broadcast elimination is defined in terms of the system of affine recurrence equations. It is shown that it can be eliminated by introducing a new recurrence equation in the single assignment code. Several examples are given to demonstrate the proposed procedure. The QR decomposition algorithm, where computational broadcast occurs for two variables, is localized and implemented on a processor array by using the data dependence method. It is shown that, in some cases, the algorithm can be realized by using only half the processors at the cost of doubling the complexity of processors used.

Recommendations

• A Rotation Method for Computing the QR-Decomposition
• Algorithm transformations for the data broadcast elimination method
• Localized algorithms for vlsi processor arrays
• A systolic array architecture for QR decomposition of block structured sparse systems
• Systolic computation of QZ matrix decomposition

Cites work

• A triangular processor array for computing singular values
• Algorithm transformations for computational and data broadcast
• Double pipelines and fast systolic designs on linear arrays
• scientific article; zbMATH DE number 3628373 (Why is no real title available?)
• scientific article; zbMATH DE number 3892457 (Why is no real title available?)
• On the Analysis and Synthesis of VLSI Algorithms
• Synthesizing systolic arrays from recurrence equations
• The Organization of Computations for Uniform Recurrence Equations
• VLSI processor array IPS cells

Cited in

(1)

• Localized algorithms for vlsi processor arrays

This page was built for publication: Elimination of the computational broadcast in systolic arrays: an application to the qr decomposition algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4489982)