An NxN Benes network B(n), (n=log/sub 2/N), being a rearrangeable network, can realize any NxN permutation in a single pass. But even in the presence of a single switch fault in B(n), no NxN permutation can be implemented in one pass, it requires either recirculation through intermediate nodes, or reconfiguration of the system in a degraded mode. We characterize a class C of multiple switch faults in B(n), in the presence of which the network is always capable of realizing any arbitrary NxN permutation P in two passes. By this technique, every source-destination path is set up in a single pass, only the whole set of N source-destination paths of P is partitioned in two subsets and are realized in two successive passes. The novelty of the routing technique lies in the fact that the exact locations of the faults are not important here, only the information of an optimal region of the network containing the faulty switch is sufficient. This feature actually enables us to develop here, very fast and simple procedures for multiple switch fault detection and location as well. In this paper, we have shown that just two one bit test vectors are sufficient to detect and locate all single faults, all double faults and also many cases with 3, 4, 5 and 6 faults. Given a set F of multiple switch faults, we detect and locate its equivalent fault set F' by the fault location technique presented.

We propose a VLSI implementable architecture called Cube Connected Tree having advantages of both trees and hypercubes. This structure has fixed low degree nodes for any size of network, unlike hypercubes, where the node degree is dependent on the size of the hypercube. Complexity of VLSI layout of this structure has been addressed within the grid model of C.D. Thompson (1984). By using spare links and PE's, fault-tolerance capabilities of the system has been enhanced. Easy programmability of this structure has been demonstrated by designing polyalgorithmic algorithms for sorting and discrete Fourier transform.

This paper explores a new hierarchy among different permutation classes, that has many applications in multistage interconnection networks. The well-known LC (linear-complement) class is shown to be merely a subset of the closure set of the BP (bit-permute) class, known as the BPCL (bit-permute-closure) class; the closure is obtained by applying certain group-transformation rules on the BP-permutations. It indicates that for every permutation P of the LC class, there exists a permutation PI in the BP class, such that the conflict graphs of P and P* are isomorphic, for n-stage MIN's. This obviates the practice of treating the LC class as a special case; the existing algorithm for optimal routing of BPC class in an n-stage MIN can take care of optimal routing of the LC class as well. Finally, the relationships of BPCL with other classes of permutations, e.g., LIE (linear-input-equivalence), BPIE (bit-permute-input-equivalence), BPOE (bit-permute-output-equivalence) are also exposed. Apart from lending better understanding and an integral view of the universe of permutations, these results are found to be useful in accelerating routability in n-stage MIN's as well as in (2n-1)-stage Benes and shuffle-exchange networks.>

A study on the isomorphism of conflict graphs in multistage interconnection networks (MINs) and its applications is outlined. A concept called group-transformation is introduced for the baseline network, which induces an equivalence partition on the set of all permutations. All members belonging to the same equivalence class have isomorphic conflict graphs. Thus, determination of conflict resolution of one permutation results in determination of conflict resolution of all other equivalent members. The BPCL (bit-permute-closure) class of permutations is defined, for which the conflict resolution problem can be settled in linear time by an earlier algorithm developed only for the BPC (bit-permute-complement) permutations. It is proved that for an N*N MIN, mod BPCL mod >or=n 2N-1, in contrast to mod BPC mod n 2n, (nlog/sup 2/ N). Conflict graphs for BPCL permutations are also characterized. An O(N) time algorithm to check membership of a given permutation to the BPCL class is described. All of these results are generalized to extend their applicability to other unique-path full-access MINs.>