계산 그리드의 성능 향상을 위한 작업 스케줄링 정책

Abstract

그리드 컴퓨팅은 수많은 이기종 컴퓨팅 자원을 인터넷 환경을 통해서 하나의 가상 환경으로 묶어 전산 작업을 수행할 수 있도록 하는 것이다. 또한 빠른 시간 안에 작업을 수행하기 위해 이러한 환경을 고려한 스케줄링 정책이 필요하다. 그 중 특정 문제에 특화된 스케줄링 정책들이 있으며 그 중 분기한정(Branch & Bound) 알고리즘이 많은 연구가 되고 있다. 이 알고리즘은 최적해를 구하기 위한 알고리즘으로 병행성이 높고 통신량이 적어 분산 컴퓨팅에 적합하지만 O(k^(n)) 이상의 시간복잡도를 가지는 문제점이 있다. 반면에 동적계획법(Dynamic programming)은 분기한정 알고리즘과 같이 최적해를 구하는 알고리즘으로 해결 가능한 문제 제약, n²이상의 공간 요구, 병행성 부족의 문제점이 있지만 그리드 환경의 방대한 저장 공간 및 연산 능력과 부합성이 있으며 대부분의 문제를 O(n^(k)) 안에 해결 가능하다. 본 논문은 그리드 환경에서 동적계획법에 특화된 스케줄링 정책을 제안한다. 이 정책은 동적 테이블의 지역성을 고려하여 분할하고 이미 할당된 동적 테이블과 통신 지연이 적은 노드에 요청된 동적 테이블을 할당하여 네트워크 오버헤드를 줄인다. 또한 병행성 확보를 위해 메모하기(Memorize)을 이용한 하향식 동적계획법을 변형하여 동적 테이블을 구성한다. 제안한 정책에 대한 시뮬레이션을 수행함으로써, 일정 크기 이상의 최적화 문제에 대하여 기존의 분기한정 알고리즘보다 빠른 시간 안에 최적해를 구할 수 있음을 확인하였다. 또한 노드 수 증가에 따라 동적계획법 특성으로 인한 성능 저하가 없음을 확인하였다.; This paper proposes a scheduling strategy for dynamic programming in Grid environment. Grid environment is applying the resources of many computers in a wide area network merging with heterogeneous computing resources, large scale storage devices and high performance devices as well as homogenous computing resources. Branch-and-bound is an intelligent search method often used for optimization problems and suitable for distributed computing. However, the worst case of branch-and-bound time complexity is O(k^(n)) or O(n!). Dynamic programming is faster than branchand- bound can be obtained in time for optimal solution, but a lot of space is needed. These attributes are well suited for Grid environment. Proposed scheduling strategy split the dynamic table to consider recursive property. And nodes in the network delays were fast to dynamically allocate dynamic table.