Properties of Multistage Interconnection Networks (thesis)

Abstract:

Regular rectangular multistage interconnection networks that are complete and have the single path property are increasingly important in large parallel computing systems. The efficiency of such networks is critical to the overall system performance, and it depends on the structure, functional capabilities
and routing control of the network. Much of the previous research has focused on specific networks. The objective of this dissertation is to study and characterize an important class of such networks. In particular, the relationships between network functionality and topology, switch size, control and modularity. The one-to-one correspondence between topology and functionality is shown, necessary and sufficient totological conditions for a network to realize all the permutations of another network are established, and optimal algorithms to decide if a network realizes all the permutations of another are developed. The single path property makes control via control tags potentially efficient. Two different control schemes are introduced where the control tags are the same as, or a function of, destination tags. The structure of these "easy-to-control" networks is shown to be recursive. Based on this recursiveness, the networks of several interesting network subclasses are shown to be functionally equivalent, namely, the subclass of doubly controllable networks, that is, easy-to-control from left to right and from right to left, the subclass of modular networks where all the stages are identical, and the subclass of r-ary networks, where the stages permute and transform r-ary digits. These single path networks do not realize all permutations. Multiple path Benes networks do but are a slow-to-control alternative. Accordingly, a new scheme for fast control of 3-stage Benes networks is introduced and studied, and several problems are shown to fit the new scheme, namely, bitonic sorting, FFT, tree algorithms and matrix computations. Also, the random walk computation is parallelized and shown to fit this control scheme. (Note: this paper has been copied with two pages per sheet.)