TY - JOUR
T1 - Partitionable multistage interconnection networks. Part 1
T2 - Dynamic subcube compaction
AU - Ayyaz, Muhammad Naeem
AU - Meliksetian, Dikran S.
AU - Chen, C. Y.Roger
PY - 1998
Y1 - 1998
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=26444581803&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=26444581803&partnerID=8YFLogxK
U2 - 10.1023/a:1019106814571
DO - 10.1023/a:1019106814571
M3 - Article
AN - SCOPUS:26444581803
SN - 1018-4864
VL - 10
SP - 79
EP - 106
JO - Telecommunication Systems
JF - Telecommunication Systems
IS - 1-2
ER -