Heuristic Subcube Allocation in Hypercube Systems

O Han KANG  Soo Young YOON  Hyun Soo YOON  Jung Wan CHO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.517-526
Publication Date: 1992/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
Keyword: 
hypercube systems,  subcube allocation,  heuristic approach,  cycle detection,  

Full Text: PDF(949.6KB)
>>Buy this Article


Summary: 
The main objective of this paper is to propose a new top-down subcube allocation scheme which has complete subcube recognition capability with quick response time. The proposed subcube allocation scheme, called Heuristic Subcube Allocation (HSA) strategy, is based on a heuristic and undirected graph, called Subcube (SC)-graph, whose vertices represent the free subcubes, and edge represents inter-relationships between free subcubes. It helps to reduce the response time and internal/external fragmentation. When a new subcube is released, the higher dimension subcube is generated by the cycle detection in the SC-graph, and the heuristic is used to reduce the allocation time and to maintain the dimension of the free subcube as high as possible. It is theoretically shown that the HSA strategy is not only statically optimal but also it has a complete subcube recognition capability in a dynamic environment. Extensive simulation results show that the HSA strategy improves the performance and significantly reduces the response time compared to the previously proposed schemes.