A cluster is a collection of workstations or PCs that are interconnected via network technology, which emerges as new way of achieving high performance at a reduced cost. Inappropriate scheduling of tasks may degenerate the true potential of a cluster and offset the gain from parallelism. The thesis presents a new queue delay model used in job scheduling system for clusters and presents a new processor management scheme based on the k-ary n-cube networks because arbitrary networks employed in clusters can be approximated to a high dimensional topology such as k-ary n-cube.
In a dynamic scheduling, FCFS scheduling may not efficiently utilize a cluster due to two drawbacks - one is to block smaller jobs, the other is to frequently fragment the system. Reduing parallelism of jobs with a queue model overcomes the weaknesses of FCFS. In other words, If the immediate allocation fails, the job scheduler should decide whether to wait or to assign a smaller subcube to the job. The decision is made depending on the wait or queue delay time. An accurate queue model is critical for enhancing the system performance. Previous studies of queue delay model have attempted to predict the queue delay analytically based on the number of busy processors, not busy subcubes. A main disadvantage of the processor-based prediction is that the number of busy processors does not accurately explain the queue delay. We call our new queue delay model as job-based queue delay model because we view the allocation moment when all the existing jobs, not the busy processors, in one of the possible subcubes complete their execution.
Since allocation on a cluster is difficult due to its topological irregularity, k-ary n-cube system is chosen as a rough approximation of the irregular topology of a cluster due to its topological generality and flexibility. Even if the topology of a cluster is irregular and very complex, the proposed allocation method - Isomorphic Allocation allocation method may be adapted for irregular topology. The proposed algorithm systematically partitions the network topology and enhances the system utilization as well as job latency, and the partitioned subcubes maintain the advantages of the high order architecture.
Extensive simulation comparing the predicted time and real queue time of a task at the head of queue shows that the effectiveness of the job-based queue delay model, and also reveals the superiority of the proposed scheme based on the Isomorphic Partitioning, compared with other previous scheme.
워크스테이션이나 PC를 특수한 스위치나 아주 빠른 네트워크로 서로 연결한 클러스터 시스템은 적은 비용으로 고성능 병렬처리가 가능하여 관심을 끌고 있다. 클러스터 시스템이 범용으로 사용됨에 따라 여러 일들이 동시에 처리되어야 한다. 이런 일들을 적절하게 스케쥴링하지 못하면 클러스터가 제공해주는 병렬화의 이점을 살리지 못한다. 본 연구는 클러스터 시스템의 효율적인 스케쥴링에 사용될 수 있는 새로운 queue delay 모델과 k-ary n-cube 네트워크에 기반한 프로세서 관리기법을 소개한다. 프로세서 관리 기법에서 k-ary n-cube를 채택한 이유는 클러스터의 불규칙적인 네트워크 연결이 고차원 네트워크 연결 구조인 k-ary n-cube로 근사화 할 수 있기 때문이다.
클러스터 시스템의 스케쥴링 방법으로 FCFS는 간단하면서 starvation이 발생하지 않지만 blocking property, system fragmentation이란 두 가지 약점을 가지고 있다. 그러나 이런 약점들은 queue delay 모델을 이용하여 일의 병렬화를 조절함으로써 극복할 수 있다. 즉, 스케쥴링 큐에 있는 첫번째 일이 allocation을 실패했을 경우, 스케쥴러는 이 일이 allocation에 성공할 때까지 기다릴 것인가, 이 일이 요구하는 클러스터의 자원(프로세서)을 줄여서 allocation을 다시 시도할 것인가를 결정해야한다. 이 결정의 기중은 일이 allocation에 성공할 때까지 기다려야 하는 시간이다. 기다려야 하는 시간이 긴 경우 이 일의 전체 수행 시간이 길어지기 때문에 일의 병렬성을 축소하여 빨리 수행하는 것이 유리하며, 그렇지 않은 경우 기다리는 것이 유리하다. 그러므로 queue delay 모델의 정확한 일의 대기 시간 예측은 클러스터 시스템의 성능 향상에 결정적인 역할을 하게 된다. 기존의 queue delay 모델은 시스템에서 사용 중인 프로세서의 수를 기준으로 예측하였다. 이 방법은 시스템에 일을 수행할 수 있는 자원-가용 프로세서들의 개수가 충분한 데도 allocation에 실패하는 경우를 설명하지 못한다. allocation이 성공하는 순간은 일이 실행될 수 있는 시스템 영역들 중 하나가 완전히 비는 경우이며 이 영역들에서 수행되던 작은 일들이 완료된 상태를 말한다. 본 연구는 이런 관찰을 토대로 새로운 queue delay 모델인 job-based queue delay 모델을 제시하였다.
클러스터의 불규칙적인 연결 구조 때문에 클러스터 상에서 프로세서를 효율적으로 관리하기 어렵다. k-ary n-cube는 hypercube나 mesh를 포함할 수 있는 일반적이며 유연한 네트워크 연결 구조로 클러스터의 불규칙적인 연결 구조를 포함할 수 있기 때문에 프로세서 관리 기법의 대상 시스템으로 선택되었다. 본 연구는 k-ary n-cube 시스템을 조직적으로 관리할 수 있는 Isomorphic allocation 기법을 제시하였다. 이 새로운 기법은 시스템을 고차원 연결구조를 유지하면서 분할하기 대문에 프로세서 간 평균 거리가 짧은 고차원 구조의 장점을 유지시켜 주며 효율적으로 시스템을 사용한다.
시뮬레이션을 통해 job-based queue delay 모델의 정확도와 Isomorphic allocation 우수한 성능을 다른 기존의 k-ary n-cube allocation 방법과 비교하여 입증하였다.
