A Multilevel Pipelined Processor For The Singular Value Decomposition
Jaime H. Moreno, Tomás Lang · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1986
An evaluation of alternatives for the implementation of a processor for the Singular Value Decomposition (SVD) is presented. Cost and performance of implementations with replication (which includes linear systolic arrays) and pipelining are evaluated. The algorithm used is the parallel method proposed by Brent and Luk, which was adapted for fewer processors. It is shown that the most efficient implementation depends on the throughput required. For low throughput, the optimal architecture is replication (i.e. linear array) of a processor with one pipelined arithmetic unit (AU). However, a single pipelined processor is more efficient for higher throughput than what is achievable with such an array. The architecture devised is a multilevel pipelined system, which uses the local parallelism existing in subcomputations of the algorithm. The realization complexity of this scheme is similar to the linear systolic array, and computes the decomposition of matrices of any size without hardware modifications. The design is based on a systematic methodology which is applicable to multi-instance algorithms implemented with only one type of operation unit, where instances are divided into groups and dependences exist between corresponding instances in those groups. This methodology gives the most efficient solutions for different hardware costs.