Singular value decomposition on processor arrays with a pipelined bus system

Singular value decomposition (SVD) is used in many applications such as real-time signal processing where fast computation of these problems is needed. In this paper, parallel algorithms for solving the singular value decomposition problem are discussed. The algorithms are designed for optically interconnected multiprocessor systems where pipelined optical buses are used to connect processors. In a pipelined bus system, messages can be transmitted concurrently in a pipelined fashion. However, certain restrictions may apply in a pipelined bus system. For example, a processor can send at most one message and receive one message during a bus cycle. Pipelined bus interconnection requires us to rethink how we write parallel algorithms. Fully exploring the properties of concurrent message transmissions requires careful mapping of data, an efficient addressing mechanism, and a set of efficient basic data movement operations. In this paper, these issues are addressed in detail. Analysis of the parallel computation times of the SVD algorithms shows that they are asymptotically equivalent to those implemented on the hypercube while using substantially less hardware. The results obtained in this paper further demonstrate that optically interconnected multiprocessor systems are very promising as a new multiprocessor architecture. (C) 1996 Academic Press Limite