Partitionable multistage interconnection networks. Part 1: Dynamic subcube compaction

Muhammad Naeem Ayyaz, Dikran S. Meliksetian, C. Y.Roger Chen

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


A new subcube compaction scheme for most effectively utilizing the available resources is proposed for multiprocessor systems based on multistage interconnection networks (MINs) in a multiuser environment. It effectively combines idle processors to form the largest possible, and as many as possible, free subcubes. This problem is referred to as subcube compaction. We show how re-setting of the underlying MIN switches can provide subcube compaction for MIN-based systems. An important concept of partitional-disjointness is introduced; through that, problems with earlier work are pointed out. Based on the concept, a versatile free subcube disjointing algorithm is developed which greatly helps in controlling the space and time complexity of the solution, and makes it possible to successfully apply the solution in real-time. Experimental results for small-scale, medium-scale and large-scale systems over a wide range of load distributions have shown that the proposed scheme gives very good system utilization and requires rather small computing time for problems of all practical purposes, and can be used for real-time system management.

Original languageEnglish (US)
Pages (from-to)79-106
Number of pages28
JournalTelecommunication Systems
Issue number1-2
StatePublished - 1998

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Partitionable multistage interconnection networks. Part 1: Dynamic subcube compaction'. Together they form a unique fingerprint.

Cite this