Analysis Techniques for SIMD Machine Interconnection Networks and the Effects of Processor Address Masks

Various techniques for evaluating and comparing interconnection networks for SIMD machines are presented. These techniques are demonstrated by using them to analyze the networks that have been proposed in the literature. The model of SIMD machines used in the first part of the paper requires all data transfers between processing elements to be representable as permutations on the processing element addresses. We use the theory of permutation groups to aid in the analysis of the cycle structures of the different interconnection networks and discuss the importance of the cycle structure to the SIMD machine architect. A processing element address masking scheme, to determine which processing elements will be active, is introduced. The effects of this masking system when used with different networks are examined. Model independent techniques for proving lower bounds on the time required for a network to simulate a particular interconnection are presented. These techniques are used to prove a lower time bound on the simulation of each network by each of the other networks.