A novel resource co-allocation model with constraints to budget and deadline in computational grid

Abstract

To address the issue of resource co-allocation with constraints to budget and deadline in grid environments, a novel co-allocation model based on virtual resource agent was proposed. The model optimized resources deployment and price scheme through a three-side co-allocation mechanism, and applied queuing system to model the work of grid resources for providing quantitative deadline guarantees for grid applications. The validity and solutions of the model were presented theoretically. Extensive simulations were conducted to examine the effectiveness and the performance of the model by comparing with other co-allocation policies in terms of deadline violation rate, resource benefit and resource utilization. Experimental results show that compared with the three typical co-allocation policies, the proposed model can reduce the deadline violation rate to about 3.5% for the grid applications with constraints to budget and deadline. Also, the system benefits can be increased by about 30% compared with the those widely-used co-allocation policies.

Keywords

co-allocation / computational grid / grid economy / queuing theory / deadline

References

[1] FosterI., KesselmanC.The grid: Blueprint for a new computing infrastructure [M], 2004, Singapore, Elsevier Inc

[2] CzajkowskiK., FosterI., KesselmanC.. Resource coallocation in computational grids [C]. Proceedings of Inter Symp on High Performance Distributed Computing, 1999, California, IEEE Computer Society Press: 219-228

[3] LewisM. J., FerrariA. J., HumphreyM. A.. Support for extensibility and site autonomy in the legion grid system object model [J]. Journal of Parallel and Distributed Computing, 2003, 63(5): 525-538

[4] WolskiR., BrevikJ., ObertelliG., SpringN.. Writing programs that run EveryWare on the computational grid [J]. IEEE Trans on Parallel and Distributed Systems, 2001, 12(10): 1066-1080

[5] LeinbergerW., KarypisG., KumarV.. Job scheduling in the presence of multiple resource requirements [C]. Proceedings of ACM/IEEE Conf on Supercomputing, 1999, Portland, IEEE Computer Society Press

[6] MohamedH. H., EpemaD. H. J.. An evaluation of the close-to-files processor and data co-allocation policy in multiclusters [C]. Proceedings of Inter Conf on Cluster Computing, 2004, San Diego, IEEE Computer Society Press: 287-298

[7] HeL. G., JarvisS. A., SpoonerD. P.. Allocating non-real-time and soft real-time jobs in multiclusters [J]. IEEE Trans on Parallel and Distributed Systems, 2006, 17(2): 99-112

[8] BucurA. I. D., EpemaD. H. J.. Scheduling policies for processor co-allocation in multicluster system [J]. IEEE Trans on Parallel and Distributed Systems, 2007, 18(7): 958-962

[9] BucurA. I. D., EpemaD. H. J.. The performance of processor co-allocation in multicluster systems [C]. Proceedings of IEEE/ACM Inter Symp on Cluster Computing and the Grid, 2003, Tokyo, IEEE Computer Society Press: 302-309

[10] BalH., BhoedjangR. R., HofmanR.. The distributed ASCI supercomputer project [J]. ACM Operating Systems Review, 2000, 34(4): 76-96

[11] BuyyaR., AbramsonD., VenugopalS.. The grid economy [J]. Proceeding of the IEEE, 2005, 93(3): 698-714

[12] WaldspurgerC. A., HoggT., HubermanB. A., et al.. Spawn: A distributed computational economy [J]. IEEE Trans on Software Engineering, 1992, 18(2): 103-117

[13] NisanN., LondonS., RegevO.. Globally distributed computation over the internet: The POPCORN project [C]. Proceedings of Inter Conf on Distributed Computing Systems, 1998, Amsterdam, IEEE Computer Society Press: 592-601

[14] AbramsonD., GiddyJ., FosterI.. High performance parametric modeling with nimrod/G: killer application for the global grid? [C]. Proceedings of Inter Symp on Parallel and Distributed Processing, 2000, Chicago, IEEE Computer Society Press

[15] BuyyaR.Economic-based distributed resource management and scheduling for grid computing [D], 2002, Melbourne, Monash University

[16] KwokY. K., HwangK., SongS.. Selfish grids: Game-theoretic modeling and NAS/PSA benchmark evaluation [J]. IEEE Trans on Parallel and Distributed Systems, 2007, 18(5): 621-636

[17] RzadcaK., TrystramD., WierzbickiA.. Fair game-theoretic resource management in dedicated grids [C]. Proceedings of Inter Symp on Cluster Computing and the Grid, 2007, Rio de Janeiro, IEEE Computer Society Press: 343-350

[18] KhanS. U., AhmadI.. Non-cooperative, semi-cooperative, and cooperative games-based grid resource allocation [C]. Proceedings of Inter Symp on Parallel and Distributed Processing, 2006, Rhodes Island, IEEE Computer Society Press

[19] OsborneM., RubinsteinA.A course in game theory [M], 1994, Cambridge, Massachusetts Institution of Technology Press

[20] MohamedH. H., EpemaD. H. J.. Experiences with the KOALA co-allocating scheduler in multiclusters [C]. Proceedings of Inter Symp on Cluster Computing and the Grid, 2005, Cardiff, IEEE Computer Society Press: 784-791

[21] GrossD., HarrisC. M.Fundamentals of queuing theory [M], 19983rd ed.New Jersey, John Wiley and Sons Inc

[22] BuyyaR., MurshedM.. GridSim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing [J]. Concurrency and Computation: Practice and Experience, 2002, 14: 1175-1220

[23] LublinU., FeitelsonD. G.. The workload on parallel supercomputers: Modeling the characteristics of rigid jobs [J]. Journal of Parallel and Distributed Computing, 2003, 63(11): 1105-1122

[24] DumitrescuC. L., RaicuI., FosterI.. The design, usage, and performance of GRUBER: A grid usage service level agreement based brokering infrastructure [J]. Journal of Grid Computing, 2007, 5(1): 99-126

[25] BertenV., GoossensJ., JeannotE.. On the distribution of sequential jobs in random brokering for heterogeneous computational grids [J]. IEEE Trans on Parallel and Distributed Systems, 2006, 17(2): 113-124