A heuristic processor allocation strategy in hypercube systems

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