Abstract
We address parallel jobs scheduling problem for computational GRID systems. We concentrate on two-level hierarchy scheduling: at the first level broker allocates computational jobs to parallel computers. At the second level each computer generates schedules of the parallel jobs assigned to it by its own local scheduler. Selection, allocation strategies, and efficiency of proposed hierarchical scheduling algorithms are discussed.
This work is partly supported by CONACYT (Consejo Nacional de Ciencia y Tecnología de México) under grant #32989-A, and by RFBR (Russian Foundation for Basic Research),grants 05-01-00798 and 03-07-00198.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Baker, B., Brown, D., Katseff, H.: A 5/4 algorithm for two-dimensional packing. J. of Algorithms 2, 348–368 (1981)
Baker, B., Coffman, E., Rivest, R.: Orthogonal packings in two dimensions. SIAM J. Computing 9(4), 846–855 (1980)
Jansen, K.: Scheduling malleable parallel jobs: an asymptotic fully polynomial-time approximation scheme. In: Euro. Symp. on Algorithms (2002)
Kenyon, C., Remila, E.: A near optimal solution to a two dimensional cutting stock problem. Math. of Operations Res. 25, 645–656 (2000)
Shmoys, D., Wein, J., Williamson, D.: Scheduling parallel machines on-line. SIAM J. Comput. 24, 1313–1331 (1995)
Zhuk, S., Chernykh, A., Kuzjurin, N., Pospelov, A., Shokurov, A., Avetisyan, A., Gaissaryan, S., Grushin, D.: Comparison of Scheduling Heuristics for Grid Resource Broker. In: PCS 2004 Third International Conference on Parallel Computing Systems (in conjunction with ENC 2004), pp. 388–392. IEEE, Los Alamitos (2004)
Foster, Kesselman, C. (eds.): The Grid: Blueprint for a future computing infrastructure. Morgan Kaufmann, San Fransisco (1999)
Sabin, G., Kettimuthu, R., Rajan, A., Sadayappan, P.: Scheduling of Parallel Jobs in a Heterogeneous Multi-Site Environment. In: The Proceedings of the 8th International Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP) (2003)
Smarr, L., Catlett, C.: Metacomputing. Communications of the ACM 35(6), 44–52 (1992)
Vadhiyar, S.S., Dongarra, J.J.: A Metascheduler for the Grid. In: Proc. of 11-th IEEE Symposium on High Performance Distributed Computing (HPDC 2002) (July 2002)
Gehring, J., Streit, A.: Robust Resource Management for Metacomputers. In: Proc. HPDC 2000, pp. 105–111 (2000)
Hamscher, V., Schwiegelshohn, U., Streit, A., Yahyapour, R.: Evaluation of Job-Scheduling Strategies for Grid Computing. In: Buyya, R., Baker, M. (eds.) GRID 2000. LNCS, vol. 1971, pp. 191–202. Springer, Heidelberg (2000)
James, A., Hawick, K.A., Coddington, P.D.: Scheduling Independent Tasks on Metacomputing Systems. In: Proc. Conf. on Parallel and Distributed Systems (1999)
The Grid Forum, http://www.gridforum.org/
Hopper, E., Turton, B.C.H.: An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. Europian Journal of Operational Research (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tchernykh, A., Ramírez, J.M., Avetisyan, A., Kuzjurin, N., Grushin, D., Zhuk, S. (2006). Two Level Job-Scheduling Strategies for a Computational Grid. In: Wyrzykowski, R., Dongarra, J., Meyer, N., Waśniewski, J. (eds) Parallel Processing and Applied Mathematics. PPAM 2005. Lecture Notes in Computer Science, vol 3911. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11752578_93
Download citation
DOI: https://doi.org/10.1007/11752578_93
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34141-3
Online ISBN: 978-3-540-34142-0
eBook Packages: Computer ScienceComputer Science (R0)