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.
ASJC Scopus subject areas
- Electrical and Electronic Engineering