A Parallel Matrix Decomposition Algorithm for Routing on Rearrangeable Clos-Network Switches

Abstract

Matrix decomposition is an important routing approach in a rearrangeable three-stage Clos network. However, most existing routing algorithms based on matrix decomposition were proved to be incomplete. In this paper, a new and efficient decomposition algorithm is proposed to route for rearrangeable Clos-network switches. The proposed algorithm uses a row-wise decomposition manner, which is a totally different decomposition method from the existing ones, to decompose a connection matrix for implementing the switching of all requests. Consequently, the algorithm can effectively overcome the incompleteness of similar algorithms and is capable of decomposing any connection matrices in serial time O(nr^2) or parallel time O(nr). Moreover, we prove the correctness of the proposed algorithm by rigorous mathematical proofs and analyse its time complexity in detail.