DGSchedSim: a trace-driven simulator to evaluate scheduling algorithms for desktop grid environments



This paper describes DGSchedSim, a trace driven simulator to evaluate scheduling algorithms focused on minimising turnaround time of applications executed in heterogeneous desktop grid systems. The simulator can be used to model task farming applications comprised of a set of independent and equal sized tasks similarly to numerous @Home public computing projects like the popular SETI@Home. DGSchedSim permits to assess scheduling policies under several scenarios allowing to control parameters such as the application's requirements (number of tasks, individual requirements of tasks like needed CPU time), the properties of the environment (machines computing capabilities and availabilities) and the characteristics of the execution (frequency and storage location of checkpoints, etc.). The simulations are driven by traces collected from real desktop grid systems.

Besides DGSchedSim, the paper presents the Cluster Ideal Execution Time (CIET) algorithm that computes the ideal wall-clock time required by a fully dedicated and totally reliable cluster of M heterogeneous machines to process the T tasks of an application.
As a test to the simulator capabilities, the paper analyses the suitability of two scheduling algorithms, FCFS and MinMax, for delivering fast turnaround time in desktop grids. Both algorithms, when combined with a centrally stored checkpoint policy, achieve efficiency close to 50% of CIET for certain scenarios.


desktop grid, simulator, checkpointing


Desktop Grid

Cited by

Year 2013 : 1 citations

 Gil, Joon-Min and Kim, SungSuk and Lee, JongHyuk, ”Task Replication and Scheduling Based on Nearest Neighbor Classification in Desktop Grids”, Ubiquitous Information Technologies and Applications, pp. 889-895, 2013, Springer.

Year 2012 : 2 citations

 Da Costa, Georges, ”Heterogeneity: the key to achieve Power-Proportional Computing”, 13th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), pp 656-662, 2013.

 Pearce, Michael and Zeadally, Sherali and Hunt, Ray, ”Virtualization: Issues, security threats, and solutions”, ACM Computing Surveys (CSUR), vol. 45(2), 2013.

Year 2010 : 5 citations

 Al-Azzoni, I., Down, D.G., “Dynamic scheduling for heterogeneous Desktop Grids”, Journal of Parallel and Distributed Computing, 70(12), pp 1231-1240, 2010. DOI: 10.1016/j.jpdc.2010.08.001

 Farkas, Z., Marosi, A.C., Kacsuk, P., “Job Scheduling in Hierarchical Desktop Grids”, pp. 79-97, 2010.

 Al-Daoud, H., Al-Azzoni, I., Down, D.G., “Power-Aware Linear Programming based Scheduling for heterogeneous computer clusters”, 2010 International Green Computing Conference, pp. 325-332, 2010.

 Farkas, Z. and Marosi, A.C. and Kacsuk, P., “Job Scheduling in Hierarchical Desktop Grids”, Remote Instrumentation and Virtual Laboratories, pp. 79-97, 2010

 AL-DAOUD, HADIL, "POWER-AWARE SCHEDULING FOR SERVER CLUSTERS" (2010), Master Thesis. Open Access Dissertations and Theses. Paper 4101.

Year 2009 : 2 citations

 Majd Kokaly, Issam Al Azzoni, Douglas G. Down, “MGST: A Framework for Performance Evaluation of Desktop Grids”, Proc. 3rd Workshop on Desktop Grids and Volunteer Computing Systems (PCGrid 2009), Rome, Italy, In Workshops Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium, IEEE Computer Society.

 Estrada, T., Taufer, M., Anderson, D.P.,” Performance Prediction and Analysis of BOINC Projects: An Empirical Study with EmBOINC”, Journal of Grid Computing, volume 7, issue 4, pp. 537-554, 2009, Springer.

Year 2008 : 1 citations

 I. Al-Azzoni and D.G. Down, Dynamic Scheduling for Heterogeneous Desktop Grids, The 9th IEEE/ACM International Conference on Grid Computing (Grid 2008), Tsukuba, Japan, October 2008.

Year 2007 : 1 citations

 K. Watanabe, M. Fukushi, S. Horiguchi, “Expected-credibility based Job Scheduling for Volunteer Computing Systems”, Proceedings of the 2nd International Conference on Advances in Information Technology (IAIT2007), pp 222-229, 2007.