For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Heuristic Subcube Allocation in Hypercube Systems
O Han KANG Soo Young YOON Hyun Soo YOON Jung Wan CHO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/07/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
hypercube systems, subcube allocation, heuristic approach, cycle detection,
Full Text: PDF(949.6KB)
>>Buy this Article
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.