Journal of KIISE:Computing Practices and Letters (한국정보과학회논문지:컴퓨팅의 실제 및 레터)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

An Efficient Job Scheduling Strategy for Computational Grid

계산 그리드를 위한 효율적인 작업 스케줄링 정책

  • 조지훈 (코리아와이즈넛 연구소) ;
  • 이원주 (인하공업전문대학 컴퓨터정보과) ;
  • 전창호 (한양대학교 컴퓨터공학과)
  • Published : 2008.11.15
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we propose a new scheduling strategy for dynamic programming in Grid environment. The key idea of this scheme is to reduce the execution time of a job by dividing the dynamic table based on the locality of table and allocating jobs to nodes which minimize network latency. This scheme obtains optimal concurrency by constructing the dynamic table using a distributed top down method. Through simulation, we show that the proposed Grid strategy improves the performance of Grid environment compared to previous branch-bound strategies.

본 논문은 그리드 환경에서 동전계획법을 위한 새로운 스케줄링 정책을 제안한다. 이 스케줄링 정책의 특징은 동적 테이블의 지역성을 고려하여 테이블을 분할하고, 네트워크 지연이 최소인 노드에 작업을 할당함으로써 작업의 실행시간을 단축하는 것이다. 또한 최적의 병행성을 얻기 위해 분산 하향식으로 동적 테이블을 구성한다 시뮬레이션을 통하여 제안하는 그리드 스케줄링 정책이 그리드 환경의 성능 향상 면에서 기존의 분기-한정(branch-bound) 알고리즘에 비해 더 효과적임을 보인다

Keywords

References

  1. I. Foster, C. Kesselman and S. Tuecke, "The Anatomy of the Grid: Enabling Scalable Virtual Organizations," International Journal of Supercomputer Applications, 15(3), 2001
  2. 류경후, 이원주, 전창호, "다중 그리드 사이트에서 어플리케이션 특성을 고려한 동적 작업 재배치 정책", 한국컴퓨터정보학회 논문지, 제13권, 제4호, pp. 31-37, 2008
  3. Paul Ruth, Junghwan Rhee, Dongyan Xu, Rick Kennell, and Sebastien Goasguen, "Autonomic live adaptation of virtual computational environments in a multi-domain infrastructure," In the 3rd IEEE International Conference on Autonomic Computing (ICAC'06), 2006
  4. A. Iamnitchi and I.Foster. "A Problem-Specific Fault-Tolerance Mechanism for Asynchronous, Distributed Systems," Proceedings of the 2000 International Conference on Parallel Processing, 2000
  5. Tgomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introductiontoalgorithms," The MIT Press Publishers USA, 1999
  6. Bergroth L., Hakonen H. and Raita T. "A survey of longest common subsequence algorithms," String Processing and Information Retrieval, 2000
  7. I.Foster, H.Kishimoto, A.Savva, D.Berry, "The Open Grid Services Architecture, Version 1.0," Informational Document, Global Grid Forum (GGF), Jan., 29, 2005
  8. SIMGRID Project, http://simgrid.gforge.inria.fr
  9. The Adaptive Communication Environment(ACE), http://www.cs.wustl.edu/~schmidt/ACE.html