For multi-user multi-tasking hypercube systems, there have been two fundamental problems in the processing of the incoming tasks: subcube allocation and task migration.
In this thesis, we propose a new top-down subcube allocation scheme, called SIG (Subcube Information Graph) strategy, and also present a task migration scheme to solve the fragmentation problem in a hypercube.
The SIG strategy is based on a heuristic and a undirected graph, called FC(Free Cube)-graph, whose vertices represent the available subcubes, and edges response time and internal/external fragmentation, and to generate the higher dimension subcube by the cycle detection in the FC-graph. When a subcube is released, a heuristic algorithm is also used to maintain the available subcubes as large as possible and to reduce the response time.
To effectively utilize non-cubic topology on hypercubes, the SIG strategy is extended to support non-cubic allocation. Using the connectivity information among free subcubes in the FC-graph, the SIG strategy utilizes smaller subcubes which are physically adjacent to each other for non-cubic allocation.
하이퍼큐브 시스템이 규모가 커지고 다중 사용자 환경으로 변화됨으로써 입력되는 타스크를 효과적으로 처리하기 위해서는 서브큐브 할당과 타스크 재배치라는 두가지 근본적인 문제를 해결하여야 한다.
본 논문에서는 SIG(Subcube Information Graph) 기법이라는 새로운 하향식(top-down) 서브큐브 할당기법을 제안하였으며, 서브큐브 할당과 반환을 반복함으로써 발생되는 하이퍼큐브 분할 (fragmentation) 문제를 해결하기 위하여 타스크 재배치 알고리즘인 SC³ 기법을 개발하였다. SIG 기법은 간단한 휴리스틱과 프리큐브 그래프(FC-graph) 라는 무방향(undirected) 그래프를 기본으로 한다. 휴리스틱 알고리즘은 사용 가능한 서브큐브들의 크기를 가능하면 크게 유지하고 알고리즘의 수행시간을 단축시키기 위하여 사용된다. 프리큐브 그래프는 노드가 사용 가능한 서브큐브를 나타내며 링크가 이들 간의 연관관계를 나타내는 것으로 알고리즘의 수행시간을 단축시키고 하이퍼큐브의 내적/외적 분할을 줄이는 도구로 사용된다.
서브큐브의 할당과 반환이 반복되면 하이퍼큐브가 크기가 작은 서브큐브들로 분할됨으로써 시스템의 효율이 저하되는 문제가 발생하는데, 이러한 하이퍼큐브 분할 문제는 타스크 재배치로 해결할수 있다. 타스크 재배치 문제는 서브큐브 할당 기법과 밀접한 연관관계가 있으므로 본 논문에서는 SIG 기법에 기초한 타스크 재배치 기법을 개발하였다.
SIG 기법에서는 프리큐브 그래프에 있는 사용 가능한 서브큐브들 간의 연결정보를 이용함으로써 비큐빅(non-cubic) 할당을 효과적으로 할수 있다.
제안된 알고리즘이 정적(static) 환경에서 최적(optimal) 임을 보여주었으며, 동적(dynamic) 환경에서 존재하는 모든 서브큐브를 인식할수 있다는 것을 증명하였다. 또한 새로운 서브큐브가 반환되었을 때 반환된 서브큐브와 기존의 사용 가능한 서브큐브가 결합하여 차원이 높은 새로운 서브큐브가 형성될 경우에는 프리큐브 그래프에 사이클이 형성된다는 것을 증명하였다.
실험을 통하여 SIG 기법이 기존의 서브큐브 할당기법들 보다 효율이 좋으며 알고리즘 수행시간이 크게 단축되었음을 보여주었다.
