The Theory Underlying the Partitioning of Permutation Networks

Academic Article


  • The age of the microcomputer has made feasible large-scale multiprocessor systems. In order to use this parallel processing power in the form of a flexible multiple-SIMD (MSIMD) system, the interconnection network must be partitionable and dynamically reconfigurable. The theory underlying the partitioning of MSIMD system permutation networks into independent subnetworks is explored. Conditions for determining if a network can be partitioned into independent subnetworks and the ways in which it can be partitioned are presented. The use of the theory is demonstrated by applying it to the Cube, Illiac, PM2I, and Shuffle-Exchange SIMD machine interconnection networks. Both recirculating (single stage) and multistage network implementations are considered. Copyright © 1980 by The Institute of Electrical and Electronics Engineers, Inc.
  • Authors

    Published In

    Digital Object Identifier (doi)

    Author List

  • Siegel HJ
  • Start Page

  • 791
  • End Page

  • 801
  • Volume

  • C-29
  • Issue

  • 9