Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

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

A Point-based Scheduling Algorithm for GRID Environment

그리드 시스템을 위한 포인트 기반 스케줄링 알고리즘

  • 오영은 (로커스테크놀로지스) ;
  • 김진석 (서울시립대학교 컴퓨터과학부)
  • Published : 2005.12.01
Download PDF
⟨ Previous Next ⟩

Abstract

GRID environments have been developed in distributed heterogeneous computing infrastructure for advanced science and engineering Therefore efficient scheduling algorithms for allocating user job to resources in the GRID environment are required. Many scheduling algorithms have been proposed, but these algorithms are not suitable for the GRID environment. That is the previous scheduling algorithm does not consider network bandwidth between multiple resources. In this paper, we propose a new scheduling algorithm for Global GRID environment and show that our algorithm has better performance than other scheduling algorithms through extensive simulation.

과학 기술이 발전함에 따라 대량의 정보를 분석하고 처리하기 위해 대두된 그리드 시스템은 이질적인 시스템 위에 구축된 환경이므로 사용자 작업을 효율적으로 할당하기 위한 스케줄링 알고리즘이 필요하다. 현재까지 여러 스케줄링 알고리즘이 연구되어 왔지만, 대부분 자원 사이의 네트웍 대역폭을 고려하지 않는 문제점을 가지고 있다. 본 논문에서는 이러한 문제점을 해결하기 위하여 글로벌 그리드 시스템에서의 스케줄링 알고리즘을 제안하였다. 또한 글로벌 그리드 시스템에서 사용되는 여러 알고리즘의 점수를 각각 계산하여 가장 점수가 낯은 알고리즘을 선택하는 포인트 기반 스케줄링 알고리즘을 제안하였으며, 시뮬레이션을 통하여 다른 스케줄링 알고리즘보다 성능이 뛰어남을 보였다.

Keywords

References

  1. I. Foster, C. Kesselman, and S. Tuecke, 'The Anatomy of the Grid: Enabling Scalable Virtual Organizations,' Journal of the International Supercomputer Applications, vol. 15, no. 3, pp. 200-222, 2001 https://doi.org/10.1177/109434200101500302
  2. R. F. Freund, M. Gherrity, S. Ambrosius, M. Campbell, M. Halderman, D. Hensgen, E. Keith, T. Kidd, M. Kussow, J. D. Lima, F. Mirabile, L. Moore, B. Rust, and H. J. Siegel, 'Scheduling Resources in Multi-User Heterogeneous, Computing Environments with SmartNet,' Proc. of the 7th IEEE Heterogeneous Computing Workshop, pp. 184-199, March, 1998 https://doi.org/10.1109/HCW.1998.666558
  3. T. D. Braun, H. J. Siegel, and N. Beck, 'A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems,' Journal of Parallel and Distributed Computing, vol. 61. pp. 810-837, 2001 https://doi.org/10.1006/jpdc.2000.1714
  4. O. H. Ibarra and C. E. Kim, 'Heuristic Algorithm for Scheduling Independent Tasks on Nonidentical Processors,' Journal of the ACM, vol. 24, no. 2, pp. 280-289, April, 1977 https://doi.org/10.1145/322003.322011
  5. M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund, 'Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems,' Proc. of the 8th Heterogeneous Computing Workshop, pp. 30-44, April. 1999 https://doi.org/10.1109/HCW.1999.765094
  6. Srisan E and Uthayopas P, 'Heuristic Scheduling with Partial Knowledge under Grid Environment,' Proc. of the 2nd International Symposium on Communications and Information Technology, p. 4, October, 2002
  7. M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Prentice Hall, NJ, 1995
  8. M. Maheswaran, T. D. Braun, and H. J. Siegel, 'Heterogeneous Distributed Computing,' Encyclopedia of Electrical and Electronics Engineering, J. G. Wdbster, editor, John Wiley and Sons, vol. 8, pp. 679-690. 1999
  9. S. Venkataramaiah and J. Subhlok, 'Performance Estimation for Scheduling on Shared Networks,' Proc. of the 9th Workshop on Job Scheduling Strategies for Parallel Processing, pp. 148-165, June 2003 https://doi.org/10.1007/10968987_8
  10. B. R. de Supinski and N. T. Karonis, 'Accurately Measuring MPI Broadcasts in a Computational Grid,' Proc. of the 8th IEEE International Symposium on High Performance Distributed Computing, pp. 29-37, August, 1999 https://doi.org/10.1109/HPDC.1999.805279