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 MCDS 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 average-delay, than the other strategies.
다중사용자 환경을 제공하는 하이퍼큐브 컴퓨터 에서의 운영체계 시스템은 각각의 사용자가 필요로하는 규모의 서브큐브들을 하이퍼큐브 시스템 으로부터 할당하고 또한 작업이 끝난 서브큐브들은 다음에 사용할수있도록 해야한다. 이러한 서브큐브의 Allocation 과 Deallocation 은 복합적으로 발생하여 비록 많은수효의 사용가능한 프로세서들이 시스템내부에 존재한다하여도 이들이 큐브구조를 가지지 못함으로서 이들 프로세서 자원의 이용도를 저하시키게 된다. 이러한 문제를 해결하기 위하여 본논문에서는 사용가능한 프로세서들을 잘표현할수있는 MCDS 를 제안하고 이를사용하여 완전한 큐브인식도를 가지는 프로세서 할당 알고리즘을 제시하고 이를 MCDS Strategy 라고 하였다. MCDS Strategy 는 정적상황하 에서는 최선의 결과를 얻을수 있으며 동적인 상황하에서는 완전한 큐브인식도를 가짐으로서 자원의 이용도를 높일수 있다. 또한 기존의 잘알려진 Buddy Strategy 를 MCDS 의 개념을 사용하여 재구성하였는데 기존의 알고리즘과 동일한 순서로 프로세서를 할당하면서 알고리즘의 복잡도는 O(2")에서 O(n) 으로 향상될수 있었다.
제안된 MCDS Strategy 의 성능을 측정하기 위하여 여러가지 환경하에서 시믈레이션을 하였는데 모든경우에서 기존의 Strategy 보다 나은 결과를 얻었으며 하이퍼큐브 시스템의 디멘젼이 커질수록 더욱더 좋아지는 현상을 보였다. 이러한 결과는 완전한 큐버인식도에서 기인한다고 할수있다. 제시된 문제는 근본적으로 NP-hard 의 범주에 속하는 문제이므로 제안된 알고리즘도 역시 지수함수적인 복잡도를 가지는데 MCDS 의 개념을 사용하면 기존의 Buddy, GC Strategy 보다 나으면서도 간단한 할당알고리즘을 상수다항식의 복잡도 를 가지도록 구성할수 있다.
