Special Issue

ISSN： 1063-7192

Source： Parallel Algorithms and Applications, Vol.18, Iss.1-2, 2003-03, pp. : 49-70

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We design the systolic version of the two-sided block-Jacobi algorithm for the singular value decomposition (SVD) of matrix A∈Rm×n, m≥n and m, n even. The algorithm involves the class CO of parallel orderings on the two-dimensional toroidal mesh with p processors. The mathematical background is based on the QR decomposition (QRD) of local data matrices and on the triangular Kogbetliantz algorithm (TKA) for local SVDs in the diagonal mesh processors. Subsequent updates of local matrices in the diagonal as well as nondiagonal mesh processors are required. We show that all updates can be realized by orthogonal modified Givens rotations. These rotations can be efficiently pipelined in parallel in the horizontal and vertical rings of √p√ processor through the toroidal mesh. Our solution requires, per one mesh processor, O[(m+n)²/p] systolic processing elements (PEs) and additional delay elements. The time complexity can be estimated as T_p≈O[(m+(n^3/2/p^1/4))wΔ] where w is the number of global sweeps in the two-sided block-Jacobi algorithm and Δ is the length of the global synchronization time step. The VLSI area per mesh processor, measured by the number of vertical and horizontal wires required for its construction, can be estimated as A≈O[(m+n)²/p], and the combined VLSI area-time complexity per mesh processor is AT²≈O[((m+n)² m²n³/p^5/4)w²Δ²]. The theoretical speedup can be estimated as S_p≈O(p^1/4m²n/(p^1/4m+n^3/2)). Using the mesh processors of fixed inner size m^×n^, m^, n^ even, it is possible to construct the square two-dimensional toroidal mesh and to compute the SVD of matrix A, the size of the which matches the shape of mesh processors, i.e. m/n=m^/n^. In this sense, the systolic algorithm is scalable.