THIRD
ANNUAL
ASAP '95 WORKSHOP
|
THIRD
ANNUAL |
SinVaD-An Architecture
|
Charles M. Rader MIT Lincoln Laboratory 244 Wood Street Lexington, MA 02173-9108 email: rader@ll.mit.edu Abstract A highly parallel architecture for computing the singular value decomposition of an N x N square matrix was developed by Brent and Luk, based on the Jacobi algorithm. N/2 simultaneous Jacobi transformations are performed. Each involves both premultiplication and postmultiplication by rotation matrices. The entire matrix is partitioned into (N/2) 2 2 x 2 submatrices and each submatrix is premultiplied by a rotation matrix generated in its row and postmultiplied by a rotation matrix generated in its column, so (N/2) 2 identical operations happen at the same time. Since these operations are rotations, the use of the CORDIC technique is very natural, but determination of the CORDIC control parameters for Jacobi rotations is clumsy and unnatural, which eliminates a major advantage of the CORDIC technique. We have developed an alternative semi-CORDIC technique which has the simplicity of a CORDIC implementation but for which the determination of its control parameters and their use to control Jacobi rotations is very similar. This leads to a highly parallel realization of the algorithm as a hardware array of identical circuits, each of which is very simple. We call it the SinVaD architecture. SinVaD will be capable of decomposing a 100 x 100 real matrix or a 50 x 50 complex matrix in a few milliseconds. |
Direct comments and questions to: webmaster@ll.mit.edu
© MIT Lincoln Laboratory. All rights reserved.
