Journal
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
Volume 74, Issue 10, Pages 3045-3055Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jpdc.2014.06.004
Keywords
Rearrangeable networks; Permutation; Interconnection networks; Routing tags; Complexity
Categories
Ask authors/readers for more resources
This paper addresses routing algorithm for a classic network called rearrangeable network with a complexity which is minimum than any other reported algorithms in this class. A new routing algorithm is presented for symmetric rearrangeable networks built with 2 x 2 switching elements. This new algorithm is capable of connection setup for partial permutation, (m) over bar = rho N, where N is the total input numbers and (m) over bar is the number of active inputs. Overall the serial time complexity of this method is O(NlogN)(1) and O((m) over bar .log N) where all N inputs are active and with (m) over bar < N active inputs respectively. The time complexity of this algorithm in a parallel machine with N completely connected processors is O(log(2)N). With <(m)over bar> active requests the time complexity goes down to O(log (m) over bar .log N), which is better than the O(log(2)(m) over bar + log N), reported in the literature for 2(1/2[(log2N-4logN)1/2-logN]) <= rho <= 1. In later half of this paper, modified rearrangeable networks have been demonstrated built with bigger switching elements (>2 x 2) with shorter network depth. Routing algorithm for these new networks have been proposed by modifying the proposed algorithm for smaller switching elements networks. Also we shall look into the application of these networks in optical domain for crosstalk free routing. (C) 2014 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available