Partitionable multistage interconnection networks. Part 1: Dynamic subcubecompaction

A new subcube compaction scheme for most effectively utilizing the availabl e resources is proposed for multiprocessor systems based on multistage inte rconnection networks (MINs) in a multiuser environment. It effectively comb ines 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 compactio n for MIN-based systems. An important concept of partitional-disjointness i s introduced; through that, problems with earlier work are pointed out. Bas ed on the concept, a versatile free subcube disjointing algorithm is develo ped 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 s ystems over a wide range of load distributions have shown that the proposed scheme gives very good system utilization and requires rather small comput ing time for problems of all practical purposes, and can be used for real-t ime system management.