A Model of SIMD Machines and a Comparison of Various Interconnection Networks

A formal mathematical model of single instruction stream-multiple data stream (SIMD) machines is defined. It is used as a basis for analyzing various types of interconnection networks that have been discussed in the literature. The networks are evaluated in terms of the lower and upper bounds on the time required for each of the networks discussed to simulate the other networks. SIMD machine algorithms are presented as proofs of the upper time bounds on these simulation tasks. These simulations are used to demonstrate techniques for proving the correctness of SIMD machine algorithms, i.e., analyzing the simultaneous flow of N data items among N processors. Processor address masks, a concise notation for activating and deactivating processors, are used in the algorithms. The methods used to prove the lower bounds and to construct (and prove correct) simulation algorithms to show the upper bounds can be generalized and applied to the analysis of other networks.