Using checkpointing to recover from poor multi-site parallel job scheduling decisions

ABSTRACT

Recent research in multi-site parallel job scheduling leverages user-provided estimates of job communication characteristics to effectively partition the job across multiple clusters. Previous research addressed the impact of inaccuracies in these estimates on overall system performance and found that multi-site scheduling techniques benefit from these estimates, even in the presence of considerable inaccuracy. While these results are encouraging, there are many instances where these errors result in poor scheduling decisions that cause network over-subscription. This situation can lead to significantly degraded application runtime performance and turnaround time.

In this paper, we explore the use of job checkpointing to selectively stop offending jobs in order to alleviate network congestion and subsequently restart them when (and where) sufficient network resources are available. We then characterize the conditions and the extent to which checkpointing improves overall performance. We demonstrate that checkpointing is beneficial even when the overhead of doing so is costly.

REFERENCES

• 1: A. I. D. Bucur , D. H. J. Epema, The Performance of Processor Co-Allocation in Multicluster Systems, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.302, May 12-15, 2003
• 2: Carsten Ernemann , Volker Hamscher , Achim Streit , Ramin Yahyapour, Enhanced Algorithms for Multi-site Scheduling, Proceedings of the Third International Workshop on Grid Computing, p.219-231, November 18, 2002
• 3: W. M. Jones. The impact of error in user-provided bandwidth estimates on multi-site parallel job scheduling performance. In The 19th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2007), to appear November 2007.
• 4: William M. Jones , Walter B. Ligon, III , Louis W. Pang , Dan Stanzione, Characterization of Bandwidth-Aware Meta-Schedulers for Co-Allocating Jobs Across Multiple Clusters, The Journal of Supercomputing, v.34 n.2, p.135-163, November 2005 [doi>10.1007/s11227-005-2337-x]
• 5: J. Ngubiri, M. van Vliet, and R. U. Nijmegen. Group-wise performance evaluation of processor co-allocation in multi-cluster systems. In Job Scheduling Strategies for Parallel Processing. Springer Verlag, 2007. to appear in Lect. Notes Comput. Sci.
• 6: A. J. Oliner , R. K. Sahoo , J. E. Moreira , M. Gupta, Performance Implications of Periodic Checkpointing on Large-Scale Cluster Systems, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 18, p.299.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.337]
• 7: James S. Plank , Michael G. Thomason, Processor allocation and checkpoint interval selection in cluster computing systems, Journal of Parallel and Distributed Computing, v.61 n.11, p.1570-1590, November 2001 [doi>10.1006/jpdc.2001.1757]
• 8: Jinhui Qin , Michael A. Bauer, An Improved Job Co-Allocation Strategy in Multiple HPC Clusters, Proceedings of the 21st International Symposium on High Performance Computing Systems and Applications, p.18, May 13-16, 2007 [doi>10.1109/HPCS.2007.7]
• 9: Dan Tsafrir , Yoav Etsion , Dror G. Feitelson, Backfilling Using System-Generated Predictions Rather than User Runtime Estimates, IEEE Transactions on Parallel and Distributed Systems, v.18 n.6, p.789-803, June 2007 [doi>10.1109/TPDS.2007.70606]
• 10: Ahuva W. Mu'alem , Dror G. Feitelson, Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling, IEEE Transactions on Parallel and Distributed Systems, v.12 n.6, p.529-543, June 2001 [doi>10.1109/71.932708]
• 11: Z. Weizhe, F. Binxing, H. Mingzeng, L. Xinran, Z. Hongli, and G. Lei. Multisite co-allocation scheduling algorithms for parallel jobs in computing grid environments. Science in China Series F: Information Sciences, 49(6):906--926, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Keywords:
checkpointing, clusters, computational grid, job scheduling