Two-dimensional systolic array for the column-by-column QD algorithm

Brudaru, Octav and Megson, Graham M. (1991) Two-dimensional systolic array for the column-by-column QD algorithm. Computers and Digital techniques, IEE Proceedings E, 138 (6). pp. 401-406. ISSN 1350-2387

Full text not available from this repository.
Official URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumbe...

Abstract

A 2D systolic array for the column-by-column QD algorithm is presented. The design requires 4n+R+S-4 steps and (n-1)(2n+2R-1) processors to compute at least R iterations to the roots of S polynomials of degree less than or equal to n. A proof of correctness is given to verify the design and it is shown that the array is asymptotically optimal with respect to processor and bandwidth utilisation. Various extensions to the array are also discussed; in particular it is shown that a rectangular array of O(n2) processors (i.e. independent of R) can be used to produce an unlimited number of iterations.

Item Type: Article
Uncontrolled Keywords: Computational complexity, polynomials, systolic arrays, 2D systolic array, QD algorithm, correctness, polynomials systolic array
Subjects: University of Westminster > Science and Technology > Electronics and Computer Science, School of (No longer in use)
Depositing User: Miss Nina Watts
Date Deposited: 27 Jan 2009 10:40
Last Modified: 19 Oct 2009 13:07
URI: http://westminsterresearch.wmin.ac.uk/id/eprint/5697

Actions (login required)

Edit Item (Repository staff only) Edit Item (Repository staff only)