Realization of permutations on generalized INDRA networks

Abstract

The realization of permutations of data on a class of redundant-path interconnection networks, called generalized INDRA networks, is studied. This class of networks is constructed by combining L layers (copies) of subnetworks in parallel preceded by a distribution stage, the subnetwork chosen being a delta network constructed from R × R switching elements. Redundant links are provided on the input side of the network so that failures in the distribution stage could be sustained. The problem of realizing an arbitrary permutation on such networks has a one-to-one correspondence with the problem of performing the same permutation in multiple passes on a delta network. This problem is reduced to that of finding a vertex coloring for the conflict graph of the permutation. Although the general problem of finding optimal colorings for graphs of arbitrary permutations is unsolved, classes of permutations with some regularity can be mapped optimally; we illustrate this with the BPC class of permutations. Conflicts in a permutation in the BPC class are described by means of conflict cubes, and these cubes are used to obtain an optimal mapping of the permutation on the network using a minimum number of layers. Several examples are provided to illustrate the underlying concepts of our work. © 1988.