On-line hierarchical job scheduling on grids with admissible allocation |
| |
Authors: | Andrei Tchernykh Uwe Schwiegelshohn Ramin Yahyapour Nikolai Kuzjurin |
| |
Affiliation: | (1) Samsung Advanced Institute of Technology, Samsung Electronics, Mt. 14-1, Nong-seo-Dong, Giheung-Gu, Yongin-Si, Gyeonggi-Do, 446-712, Republic of Korea;(2) Samsung Networks 8F, ASEM Tower, World Trade Center, 159-1, Samsung-Dong, Kangnam-Ku, Seoul, 135-798, Republic of Korea;(3) The Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA;(4) Lawrence Livermore National Laboratory, Livermore, CA 94551, USA |
| |
Abstract: | In this paper, we address non-preemptive online scheduling of parallel jobs on a Grid. Our Grid consists of a large number
of identical processors that are divided into several machines. We consider a Grid scheduling model with two stages. At the
first stage, jobs are allocated to a suitable machine, while at the second stage, local scheduling is independently applied
to each machine. We discuss strategies based on various combinations of allocation strategies and local scheduling algorithms.
Finally, we propose and analyze a scheme named adaptive admissible allocation. This includes a competitive analysis for different
parameters and constraints. We show that the algorithm is beneficial under certain conditions and allows for an efficient
implementation in real systems. Furthermore, a dynamic and adaptive approach is presented which can cope with different workloads
and Grid properties. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|