Paper Info
Title
A heuristic processor allocation strategy in hypercube systems
Abstract
A new processor allocation scheme for hypercube systems, called the HPA (heuristic processor allocation) strategy, is presented. In this scheme, an undirected graph, called the SC-graph (Subcube-graph), is used to maintain the free subcubes available in system, which are represented by vertices. An allocation request for a k-cube is satisfied by finding a free subcube of dimension k in the SC-graph or by decomposing a nearest higher dimension subcube. If there are more than one subcube of dimension k, a subcube which has minimum degree in the SC-graph is selected to reduce the external fragmentation. For deallocating the released subcube a heuristic algorithm is used to maintain the dimension of free subcube as high as possible. It is theoretically shown that the HPA 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 HPA strategy improves the performance and significantly reduces the allocation/deallocation time compared to the previously proposed schemes.
Year
DOI
Venue
1991
10.1109/SPDP.1991.218248
SPDP
Keywords
Field
DocType
concurrent computing,performance,heuristic algorithm,strontium,satisfiability,scattering,computer science,scheduling,hypercubes
Graph,Heuristic,Vertex (geometry),Computer science,Heuristic (computer science),Scheduling (computing),Parallel computing,Concurrent computing,Heuristic programming,Hypercube,Distributed computing
Conference
ISBN
Citations 
PageRank 
0-8186-2310-1
2
0.41
References 
Authors
2
5
Name
Order
Citations
PageRank
S. Y. Yoon120.41
Ohan Kang220.75
Hyunsoo Yoon3759106.01
Seung Ryoul Maeng48519.68
Jung Wan Cho520.41