Adaptive parallel job scheduling with resource admissible allocation on two-level hierarchical grids

详细信息    查看全文

• 作者：Ariel Quezada-Pina^a ; ^{aquezada@cicese.mx}  ; [Author Vitae] ; Andrei Tchernykh^a ; ^{chernykh@cicese.mx}  ; [Author Vitae] ; José ; Luis Gonzá ; lez-Garcí ; a^e ; ^{jose-luis.gonzalez-garcia@gwdg.de}  ; [Author Vitae] ; Adá ; n Hirales-Carbajal^a ; ^b ; ^{ahirales@cicese.mx} ; ^{ahirales@uabc.mx}  ; [Author Vitae] ; Juan Manuel Ramí ; rez-Alcaraz^c ; ^{jmramir@ucol.mx}  ; [Author Vitae] ; Uwe Schwiegelshohn^d ; ^{uwe.schwiegelshohn@udo.edu}  ; [Author Vitae] ; Ramin Yahyapour^e ; ^{ramin.yahyapour@gwdg.de}  ; [Author Vitae] ; Vanessa Miranda-Ló ; pez^a  ; [Author Vitae]
• 关键词：Grid ; Online scheduling ; Resource management ; Job allocation ; Admissible allocation ; Hierarchical
• 刊名：Future Generation Computer Systems
• 出版年：2012
• 出版时间：July, 2012
• 年：2012
• 卷：28
• 期：7
• 页码：965-976
• 全文大小：768 K

文摘

We evaluate job scheduling algorithms that integrate both tasks of Grid scheduling: job allocation to Grid sites and local scheduling at the sites. We propose and analyze an adaptive job allocation scheme named admissible allocation. The main idea of this scheme is to set job allocation constraints, and dynamically adapt them to cope with different workloads and Grid properties. We present 3-approximation and 5-competitive algorithms named and for the case that all jobs fit to the smallest machine, while we derive an approximation factor of 9 and a competitive factor of 11 for the general case. To show practical applicability of our methods, we perform a comprehensive study of the practical performance of the proposed strategies and their derivatives using simulation. To this end, we use real workload traces and corresponding Grid configurations. We analyze nine scheduling strategies that require a different amount of information on three Grid scenarios. We demonstrate that our strategies perform well across ten metrics that reflect both user- and system-specific goals.