Heuristics Analysis for Distributed Scheduling using MONARC Simulation Tool

Simulation is a very powerful method used for highperformance and high-quality design in distributed system, and now maybe the only one, considering the heterogeneity, complexity and cost of distributed systems. In Grid environments, foe example, it is hard and even impossible to perform scheduler performance evaluation in a repeatable and controllable manner as resources and users are distributed across multiple organizations with their own policies. In addition, Grid test-beds are limited and creating an adequately-sized test-bed is expensive and time consuming. Scalability, reliability and fault-tolerance become important requirements for distributed systems in order to support distributed computation. A distributed system with such characteristics is called dependable. Large environments, like Cloud, offer unique advantages, such as low cost, dependability and satisfy QoS for all users. Resource management in large environments address performant scheduling algorithm guided by QoS constrains. This paper presents the performance evaluation of scheduling heuristics guided by different optimization criteria. The algorithms for distributed scheduling are analyzed in order to satisfy users constrains considering in the same time independent capabilities of resources. This analysis acts like a profiling step for algorithm calibration. The performance evaluation is based on simulation. The simulator is MONARC, a powerful tool for large scale distributed systems simulation. The novelty of this paper consists in synthetic analysis results that offer guidelines for scheduler service configuration and sustain the empirical-based decision. The results could be used in decisions regarding optimizations to existing Grid DAG Scheduling and for selecting the proper algorithm for DAG scheduling in various actual situations.

Authors:

• Florin Pop

Keywords:

• Scheduling
• Simulation
• Performance Evaluation
• QoS
• Distributed Systems
• MONARC

References:

[1] Florin Pop. 2011, Simulation based Evaluation of QoS-guided
Scheduling for Distributed Computing in Large Environments, In Proc.
of ESM 2011, The 2011 European Simulation and Moelling Confernce,
October 24-26, University of Minho, Portugal, pp: 84-90.
[2] Ciprian Dobre, Florin Pop, and Valentin Cristea. 2009. New Trends in
Large Scale Distributed Systems Simulation. In Proceedings of the 2009
International Conference on Parallel Processing Workshops (ICPPW
'09). IEEE Computer Society, Washington, DC, USA, 182-189.
[3] Fatos Xhafa and Ajith Abraham. 2010. Computational models and
heuristic methods for Grid scheduling problems. Future Gener. Comput.
Syst. 26, 4 (April 2010), 608-621.
[4] Florin Pop and Valentin Cristea. 2009. Decentralised meta-scheduling
strategy in Grid environments. Int. J. Grid Util. Comput. 1, 3 (August
2009), 185-193.
[5] Li Chunlin and Li Layuan. 2007. Optimization decomposition approach
for layered QoS scheduling in grid computing. J. Syst. Archit. 53, 11
(November 2007), 816-832.
[6] Peng Li and Binoy Ravindran. 2004. Fast, Best-Effort Real-Time
Scheduling Algorithms. IEEE Trans. Comput. 53, 9 (September 2004),
1159-1175.
[7] Zhiang Wu, Junzhou Luo, and Fang Dong. 2006. Measurement model of
grid QoS and multi-dimensional QoS scheduling. In Proceedings of the
10th international conference on Computer supported cooperative work
in design III (CSCWD'06), Weiming Shen, Junzhou Luo, Zongkai Lin,
Jean-Paul A. Barthos, and Qi Hao (Eds.). Springer-Verlag, Berlin,
Heidelberg, 509-519.
[8] Florin Pop, Ciprian Dobre, and Valentin Cristea. 2008. Performance
Analysis of Grid DAG Scheduling Algorithms using MONARC
Simulation Tool. In Proceedings of the 2008 International Symposium
on Parallel and Distributed Computing (ISPDC '08).
[9] Fabricio A. B. da Silva and Hermes Senger. 2011. Scalability limits of
Bag-of-Tasks applications running on hierarchical platforms. J. Parallel
Distrib. Comput. 71, 6 (June 2011), 788-801.
[10] N.M. Amato, P. An. 2000. Task scheduling and parallel mesh-sweeps in
transport computations, Technical Report TR00-009, Department of
Computer Science, Texas A&M University, January 2000.
[11] Hamed Nooraliei and Amir Nooraliei. 2009. Path Planning Using Wave
Front's Improvement Methods. In Proceedings of the 2009 International
Conference on Computer Technology and Development - Volume
01 (ICCTD '09), Vol. 1. IEEE Computer Society, Washington, DC,
USA, 259-264.
[12] Marek Wieczorek, Andreas Hoheisel, and Radu Prodan. 2009. Towards
a general model of the multi-criteria workflow scheduling on the
grid. Future Gener. Comput. Syst. 25, 3 (March 2009), 237-256.
[13] Dalibor Klus├í─ìek, Lud─øk Matyska, and Hana Rudov├í. 2007. Alea: grid
scheduling simulation environment. In Proceedings of the 7th
international conference on Parallel processing and applied
mathematics (PPAM'07), Roman Wyrzykowski, Konrad Karczewski,
Jack Dongarra, and Jerzy Wasniewski (Eds.). Springer-Verlag, Berlin,
Heidelberg, 1029-1038.
[14] Hui Li and Rajkumar Buyya. 2009. Model-based simulation and
performance evaluation of grid scheduling strategies. Future Gener.
Comput. Syst. 25, 4 (April 2009), 460-465.
[15] Sugree Phatanapherom, Putchong Uthayopas, and Voratas
Kachitvichyanukul. 2003. Dynamic scheduling II: fast simulation model
for grid scheduling using HyperSim. In Proceedings of the 35th
conference on Winter simulation: driving innovation (WSC '03). Winter
Simulation Conference 1494-1500.
[16] Yanfang Fu and Yan Fan. 2010. Research of the Simulation Grid System
Based on Multi-agent Dynamic Scheduling. In Proceedings of the 2010
Second International Conference on Computer Modeling and Simulation
- Volume 03 (ICCMS '10), Vol. 3. IEEE Computer Society, Washington,
DC, USA, 392-395.
[17] Ciprian Dobre, Corina Stratan, and Valentin Cristea. 2008. Realistic
Simulation of Large Scale Distributed Systems using Monitoring.
In Proceedings of the 2008 International Symposium on Parallel and
Distributed Computing (ISPDC '08). IEEE Computer Society,
Washington, DC, USA, 434-438