Algorithmic aspects of message transmission strategies for multistage interconnection networks
Philip J. Bernhard · 1988
This thesis is concerned with algorithmic and complexity issues in the representation and transmission of message patterns in multistage interconnection networks. The thesis consists of three parts. In the first part a formalism is described for the compact representation of address sets and message patterns for interconnection networks. In this formalism a descriptor called a mask is used to represent a set of equal-length bit vectors, where the set can be interpreted as either a set of processor addresses or as a set of messages. It is shown that this formalism possesses a number of algebraic properties. Specifically, it is shown that this formalism defines a lattice. This fact is then used in a variety of computations which can be performed on masks. In addition, the problem of deciding whether a set of addresses can be represented by a single mask is considered. It is shown that this problem can be solved in linear time. In the second part we consider the complexity of a particular routing strategy which gives rise to the minimum round partitioning problem. Specifically, the problem is that of partitioning a set of conflicting messages into a minimum number of subsets, called rounds, each free of communication conflicts. In addition to standard Omega networks, this problem is considered for a more general class of networks called bundled Omega networks, where interconnection links in the network are replaced by bundles of wires. Though the partitioning problem has previously been considered in the literature, its computational complexity has remained open. Here it is shown that for a number of cases the problem is NP-complete, but for certain special cases it is solvable in polynomial time. In the third part we discuss implications of the mask language for bundled Omega networks. It is shown that for a number of different types of representations, conflicts and congestion can be detected in polynomial time. In addition, it is shown that this formalism defines a class of message patterns for which the minimum round partitioning problem is solvable in linear time. This extends and generalizes a known result to a more general class of message patterns and a more general class of interconnection networks.