(A) processor allocation strategy for the hypercube computer

Abstract

In hypercube computers that support a multiuser environment, it is important for the operating system to be able to allocate subcubes of different dimensions. The main objective of the processor allocation problem is to maximize the utilization of available resources as well as minimize the inherent system fragmentation. Previously proposed allocation strategies, such as the buddy strategy and GC strategy, may fragment the hypercube excessively and the performance of the strategy is degraded. To solve processor allocation problem efficiently, we suggest the concept of MCDS. The free nodes of an n-cube can be represented by covering disjoint subcubes. A CDS which is greater than or equal to all others are defined as MCDS. The processor allocation and deallocation problem is stated simply as maintaining the greatest MCDS after every allocation and deallocation. A new processor allocation strategy, called as MCS strategy, is presented. The MCDS, strategy is not only statically optimal as the previous strategies but it gives perfect subcube recognition ability in a dynamic environment. Buddy strategy is newly described using the concept of MCDS. The subcube recognition ability of this strategy is same as old``s. But the average time complexity is better than. Various processor allocation and deallocation strategies have been implemented and simulated under several conditions. The MCDS. strategy have a considerably higher performance, measured by the cube-usage and averagedelay, than the other strategies.