Generalized Parallel Delta Networks: a New Class of Rearrangeable Interconnection Networks

This paper deals with the definition of a class of NxN multistage interconnection networks called Generalized Parallel Delta Networks (GPDNs). This class includes the already known Replicated Delta Networks (RDNs) and Parallel Delta Networks (PDNs). For the GPDNs the rearrangeability condition is given and a routing algorithm for the establishment of any set of connection requests is presented. The proposed algorithm operates in case of GPDNs composed of 2Qx2Q swtching elements and it is able to set-up any permutation with a time complexity equal to O(Nlog2N). As far as the implementation of rearrangeable topologies is concerned, the fields of applicability of RDNs, PDNs and other GPDNs have been investigated. In particular, it has been proved that, if large networks (N)256) have to be implemented, GPDNs structures requires a lower number of switching elements with respect to RDNs and PDNs. This features can be obtained without any impairment on the complexity of the routing algorithm.