In a hybrid optical multistage interconnection network (MIN), optical signals are routed by electronically controlled switches using directional couplers. A relevant design problem is to minimize the path-dependent lo...
详细信息
In a hybrid optical multistage interconnection network (MIN), optical signals are routed by electronically controlled switches using directional couplers. A relevant design problem is to minimize the path-dependent loss of the optical signal, which is directly proportional to the number of couplers, i.e., the number of switches through which the signal has to pass. In general, given the network size and the type of the MIN, the number of stages is a constant. Hence, an input signal has to pass through a fixed number of couplers to reach the output. In this paper, it is shown that the routing delay and path-dependent loss in a fixed-stage N x N MIN, can be significantly reduced on the average by using a variable-stage shuffle-exchange network instead. An arbitrary N x N permutation P can be routed with minimum delay and minimum path-dependent loss, if the minimum number of stages of the MIN necessary to route P is known. An O(Nn) algorithm (N = 2(n)) is presented here for checking the admissibility of a given permutation P in an m-stage shuffle-exchange network (SEN), where 1 < m < n. The minimum-stage SEN needed to pass P can then be determined in O(Nn log n) time. Furthermore, for n < m less than or equal to 2n - 1, a necessary condition for permutation admissibility is derived which is shown to be necessary as well as sufficient for the special class of BPC (bit-permute-complement) permutations., It has been shown that, for 1 less than or equal to m less than or equal to 2n - 1, the minimum number of stages required to pass a BPC permutation P through a SEN can be determined in O(n(2)) time, and P can be routed through a variable-stage SEN using the minimum number of stages only. In an optical MIN, this technique helps to reduce the path-dependent loss by limiting the number of stages to be traversed by the optical signal. (C) 2003 Elsevier Science B.V. All rights reserved.
Performing permutations of data on SIMD computers efficiently is important for high-speed execution of parallel algorithms. In this correspondence we consider realizing permutations such as perfect shuffle, matrix tra...
详细信息
Performing permutations of data on SIMD computers efficiently is important for high-speed execution of parallel algorithms. In this correspondence we consider realizing permutations such as perfect shuffle, matrix transpose, bit-reversal, the class of bit-permute- complement (BPC), the class of Omega, and inverse Omega permutations on N = 2n processors with Illiac IV-type interconnection network, where each processor is connected to processors at distances of ± 1 and ± N. The minimum number of data transfer operations required for realizing any of these permutations on such a network is shown to be 2(N − 1). We provide a general three-phase strategy for realizing permutations and derive routing algorithms for performing perfect shuffle, Omega, Inverse Omega, bit reversal, and matrix-transpose permutations in 2(N − 1) steps. Our approach is quite simple, and unlike previous approaches, makes efficient use of the topology of the Illiac IV-type network to realize these permutations using the optimum number of data transfers. Our strategy is quite powerful: any permutation can be realized using this strategy in 3(N − 1) steps.
A Benes permutation network capable of setting its own switches dynamically is presented. The total switch setting and delay time for the N input utput self-routing network is O(log N). It is shown that the network is...
详细信息
A Benes permutation network capable of setting its own switches dynamically is presented. The total switch setting and delay time for the N input utput self-routing network is O(log N). It is shown that the network is capable of performing a rich class of permutations. The self-routing scheme leads to efficient O(log N) parallel algorithms to perform the same class of permutations on cube connected and perfect shuffle computers.
A π network, which is a concatenation of 2 Ω networks [2], along with a simple control algorithm is proposed. This network is capable of performing all Ω network realizable permutations and the bit-permute-compleme...
详细信息
A π network, which is a concatenation of 2 Ω networks [2], along with a simple control algorithm is proposed. This network is capable of performing all Ω network realizable permutations and the bit-permute-complement (BPC) class of permutations[5] in 0(log N) time. The control algorithm is actually a multiple-pass control algorithm on the Ω network, which is more general than Pease"s LU decomposition method [6] and Lenfant"s decomposition method[4].
暂无评论