A model of SIMD machines and a comparison of various interconnection networks

Abstract-A formal mathematical model of single instruc-tion 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 ofthe lower and upper bounds on the tune required for each of the networks discussed to simulate the other networks. SINM 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 ofSIMD mach-ine algorithms, i.e., analyzing the simultaneous flow ofN 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. Index Terms-Algorithm correctness, array processors, computer architecture, Illiac IV, interconnection networks, n-cube array, parallel processing, perfect shuffle, permutation networks, SIMD machines, STARAN. I