CO-ALLOCATION IN GRID COMPUTING USING RESOURCES OFFERS AND ADVANCE RESERVATION PLANNING
Résumé
Computational grids have the potential for solving large-scale scientific problems using heterogeneous and geographicallydistributed resources. However, a number of major technical hurdles must overcome before this potential can be realized. One
problem that is critical to effective utilization of computational grids and gives a certain Quality of Service (QoS) for grid users
is the efficient co-allocation of jobs. The advance reservation technique has been widely applied in many grid systems to
provide QoS, however, it will result in low resource utilization rate and high rejection rate when the reservation rate is high.
This work addresses those problems by describing and evaluating a grid resources co-allocation algorithm using resources
providers offers and planning the advance reservations. In our algorithm, a Metascheduler performs job scheduling based on
resources offers and use advance reservation planning mechanism to reserves the best offers. Offers act as a mechanism in
which resource providers expose their interest in executing an entire job or only part of it. The Metascheduler selects
computational resources based on best offers provided by the resources; Meta-schedulers can distribute a job among various
clusters that are usually heterogeneous in order to speed up the job execution.
The main aims of our algorithm is to minimize the total time to execute all jobs (Makespen), minimize the waiting time in the
global queue, maximize the resources utilization rate and balance the load among the resources. The proposed algorithm has
been compared with other scheduling schemes such as First Come First Served (FCFS), easy backfilling (EBF), Fit Processor
First Served (FPFS) and a simple co-allocation algorithm without offers support (SCOAL). The proposed algorithm has been
verified through an extension of GridSim simulation toolkit and the simulation results confirm that the proposed algorithm
allow us to achieve our goals by minimizing the Makespan and the waiting time, maximizing the resources utilization rate and
load the balance among the resources.
Références
Co-allocation in grid computing using resources offers and advance reservation planning
79
[11] Foster I., Kesseleman C., Tuecke S., "The Anatomy of the
Grid: Enabling Scalable virtual Organizations", International
Journal of Super Computer Applications 15, 3, 2001.
[12] Foster I., Iamnitchia A., "On Death, Taxes, and the
Convergence of Peer-to-Peer and Grid Computing", In
Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003, LNCS, vol.
2735, Springer, Heidelberg, 2003.
[13] Foster I., Roy A., Sander V., "A quality of service
architecture that combines resource reservation and
application adaptation", Proceedings of the 8th International
Workshop on Quality of Service (IWQoS’00), Jun 5-7, 2000,
Pittsburgh, PA, USA. Los Alamitos, CA, USA,IEEE
Computer Society, 181-188, 2000.
[14] He L. G., Jarvis S. A., Spooner D. P., "Allocating non-real-
time and soft real-time jobs in multiclusters", IEEE Trans on
Parallel and Distributed Systems, 17(2), 99−112, 2006.
[15] Herroelen W., De Reyck B., Demeulemeester E, "Resource
constrained project scheduling: A survey of recent
developments", Computers and Operations Research 25,
279–302, 1998.
[16] Leinberger W., Karypis G., Kumar V., "Job scheduling in
the presence of multiple resource requirements", Proceedings
of ACM/IEEE Conf on Supercomputing, Portland IEEE
Computer Society Press, 1999.
[17] Mohamed H. H., Epema D. H. J., "An evaluation of the
close-to-files processor and data co-allocation policy in
multiclusters", Proceedings of Inter Conf on Cluster
Computing, San Diego IEEE Computer Society Press,
287−298, 2004.
[18] Nisan N., London S., Regev O. "Globally distributed
computation over the internet: The POPCORN project",
Proceedings of Inter Conf on Distributed Computing
Systems, Amsterdam, IEEE Computer Society Press,
592−601, 1998.
[19] Roy A., Sander V., "Advance reservation API", Technical
Report GFD-E.5, Scheduling Working Group, Global Grid
Forum, 2002.
[20] Snell Q., Clement M., Jackson D., et al, "The performance
impact of advance reservation metascheduling", Proceedings
of Job Scheduling Strategies for Parallel Processing
(JSSPP’00), May 1-5, 2000, Cancun, Mexico. Los Alamitos,
CA, USA, IEEE Computer Society, 137-153, 2000.
[21] Waldspurger C. A., Hogg T., Huberman B. A., et al,
"Spawn: A distributed computational economy", IEEE Trans
on Software Engineering, 18(2), 103−117, 1992.
[22] Wolski R., Brevik J., Obertelli G., Spring N., "Writing
programs that run EveryWare on the computational grid",
IEEE Trans on Parallel and Distributed Systems, 12(10),
1066−1080, 2001.[1] Abramson D., Giddy J., Foster I. "High performance
parametric modeling with nimrod/G: killer application for
the global grid?", Proceedings of Inter Symp on Parallel and
Distributed Processing, Chicago, IEEE Computer Society
Press, 2000.
[2] Bal H., Bhoedjang R. R., Hofman R., "The distributed ASCI
supercomputer project", ACM Operating Systems Review,
34(4), 76−96, 2000.
[3] Bucur A. I. D., Epema D. H. J., "The performance of
processor co-allocation in multicluster systems", Proceedings
of IEEE/ACM Inter Symp on Cluster Computing and the
Grid, Tokyo, IEEE Computer Society Press, 302−309, 2003.
[4] Bucur A. I. D., Epema D. H. J., "Scheduling policies for
processor co-allocation in multicluster system", IEEE Trans
on Parallel and Distributed Systems, 18(7), 958−962, 2007.
[5] Buyya R., "Economic-based distributed resource
management and scheduling for grid computing",
Melbourne, Monash University, 2002.
[6] Buyya R., Abramson D., Venugopal S., "The grid economy",
Proceeding of the IEEE, 93(3), 698−714, 2005.
[7] Buyya R., Murshed M., "GridSim : A Toolkit for the
Modeling and Simulation of Distributed Resource
Management and Scheduling for Grid Computing", The
Journal of Concurrency and Computation, Practice and
Experience (CCPE), Volume 14, Issue 13-15, Wiley Press,
2002.
[8] Czajkowski K., Foster I., Kesselman C., "Resource
coallocation in computational grids", Proceedings of Inter
Symp on High Performance Distributed Computing,
California IEEE Computer Society Press, 219−228, 1999.
[9] Feitelson D. G., Rudolph R., "Parallel Job Scheduling: Issues
and Approaches", In Feitelson, D.G., Rudolph, L. (eds.)
IPPS-WS 1995 and JSSPP 1995. LNCS, vol. 949, pp. 1–18.
Springer, Heidelberg, 1995.
[10] Foster I., Kesselman C., Lee C., et al, "A distributed resource
management architecture that supports advance reservation
and co-allocation", Proceedings of the 7th International
Workshop on Quality of Service (IWQoS’99), Jun 1-4, 1999,
London, UK. Los Alamitos, CA, USA, IEEE Computer
Society, 27-36, 1999.
79
[11] Foster I., Kesseleman C., Tuecke S., "The Anatomy of the
Grid: Enabling Scalable virtual Organizations", International
Journal of Super Computer Applications 15, 3, 2001.
[12] Foster I., Iamnitchia A., "On Death, Taxes, and the
Convergence of Peer-to-Peer and Grid Computing", In
Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003, LNCS, vol.
2735, Springer, Heidelberg, 2003.
[13] Foster I., Roy A., Sander V., "A quality of service
architecture that combines resource reservation and
application adaptation", Proceedings of the 8th International
Workshop on Quality of Service (IWQoS’00), Jun 5-7, 2000,
Pittsburgh, PA, USA. Los Alamitos, CA, USA,IEEE
Computer Society, 181-188, 2000.
[14] He L. G., Jarvis S. A., Spooner D. P., "Allocating non-real-
time and soft real-time jobs in multiclusters", IEEE Trans on
Parallel and Distributed Systems, 17(2), 99−112, 2006.
[15] Herroelen W., De Reyck B., Demeulemeester E, "Resource
constrained project scheduling: A survey of recent
developments", Computers and Operations Research 25,
279–302, 1998.
[16] Leinberger W., Karypis G., Kumar V., "Job scheduling in
the presence of multiple resource requirements", Proceedings
of ACM/IEEE Conf on Supercomputing, Portland IEEE
Computer Society Press, 1999.
[17] Mohamed H. H., Epema D. H. J., "An evaluation of the
close-to-files processor and data co-allocation policy in
multiclusters", Proceedings of Inter Conf on Cluster
Computing, San Diego IEEE Computer Society Press,
287−298, 2004.
[18] Nisan N., London S., Regev O. "Globally distributed
computation over the internet: The POPCORN project",
Proceedings of Inter Conf on Distributed Computing
Systems, Amsterdam, IEEE Computer Society Press,
592−601, 1998.
[19] Roy A., Sander V., "Advance reservation API", Technical
Report GFD-E.5, Scheduling Working Group, Global Grid
Forum, 2002.
[20] Snell Q., Clement M., Jackson D., et al, "The performance
impact of advance reservation metascheduling", Proceedings
of Job Scheduling Strategies for Parallel Processing
(JSSPP’00), May 1-5, 2000, Cancun, Mexico. Los Alamitos,
CA, USA, IEEE Computer Society, 137-153, 2000.
[21] Waldspurger C. A., Hogg T., Huberman B. A., et al,
"Spawn: A distributed computational economy", IEEE Trans
on Software Engineering, 18(2), 103−117, 1992.
[22] Wolski R., Brevik J., Obertelli G., Spring N., "Writing
programs that run EveryWare on the computational grid",
IEEE Trans on Parallel and Distributed Systems, 12(10),
1066−1080, 2001.[1] Abramson D., Giddy J., Foster I. "High performance
parametric modeling with nimrod/G: killer application for
the global grid?", Proceedings of Inter Symp on Parallel and
Distributed Processing, Chicago, IEEE Computer Society
Press, 2000.
[2] Bal H., Bhoedjang R. R., Hofman R., "The distributed ASCI
supercomputer project", ACM Operating Systems Review,
34(4), 76−96, 2000.
[3] Bucur A. I. D., Epema D. H. J., "The performance of
processor co-allocation in multicluster systems", Proceedings
of IEEE/ACM Inter Symp on Cluster Computing and the
Grid, Tokyo, IEEE Computer Society Press, 302−309, 2003.
[4] Bucur A. I. D., Epema D. H. J., "Scheduling policies for
processor co-allocation in multicluster system", IEEE Trans
on Parallel and Distributed Systems, 18(7), 958−962, 2007.
[5] Buyya R., "Economic-based distributed resource
management and scheduling for grid computing",
Melbourne, Monash University, 2002.
[6] Buyya R., Abramson D., Venugopal S., "The grid economy",
Proceeding of the IEEE, 93(3), 698−714, 2005.
[7] Buyya R., Murshed M., "GridSim : A Toolkit for the
Modeling and Simulation of Distributed Resource
Management and Scheduling for Grid Computing", The
Journal of Concurrency and Computation, Practice and
Experience (CCPE), Volume 14, Issue 13-15, Wiley Press,
2002.
[8] Czajkowski K., Foster I., Kesselman C., "Resource
coallocation in computational grids", Proceedings of Inter
Symp on High Performance Distributed Computing,
California IEEE Computer Society Press, 219−228, 1999.
[9] Feitelson D. G., Rudolph R., "Parallel Job Scheduling: Issues
and Approaches", In Feitelson, D.G., Rudolph, L. (eds.)
IPPS-WS 1995 and JSSPP 1995. LNCS, vol. 949, pp. 1–18.
Springer, Heidelberg, 1995.
[10] Foster I., Kesselman C., Lee C., et al, "A distributed resource
management architecture that supports advance reservation
and co-allocation", Proceedings of the 7th International
Workshop on Quality of Service (IWQoS’99), Jun 1-4, 1999,
London, UK. Los Alamitos, CA, USA, IEEE Computer
Society, 27-36, 1999.
Comment citer
AHMED MAKHLOUF, SID; YAGOUBI, BELABBAS.
CO-ALLOCATION IN GRID COMPUTING USING RESOURCES OFFERS AND ADVANCE RESERVATION PLANNING.
Courrier du Savoir, [S.l.], v. 14, mai 2014.
ISSN 1112-3338.
Disponible à l'adresse : >http://univ-biskra.dz/revues/index.php/cds/article/view/414>. Date de consultation : 22 déc. 2024
Rubrique
Articles
