The week's pick
Random Articles
Reseach Article
The Framework for Performance Modeling and Evaluation of Parallel Job Scheduling Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 34 - Number 10 |
| Year of Publication: 2011 |
| Authors: Amit Chhabra, Gurvinder Singh |
10.5120/4137-5997
|
Amit Chhabra, Gurvinder Singh . The Framework for Performance Modeling and Evaluation of Parallel Job Scheduling Algorithms. International Journal of Computer Applications. 34, 10 ( November 2011), 30-39. DOI=10.5120/4137-5997
Abstract
The performance of job scheduling algorithms in campus-wide PC-cluster distributed computing environment may be influenced by several input variables (factors) such as sum of the job sizes of all the jobs in the workload, number of PCs in the cluster and even on the type of scheduling algorithm being used. Response surface methodology (RSM) based statistical regression techniques build empirical model for performance prediction of the scheduling system by means of mathematical equation that relate the scheduler performance (response) to the input process parameters. Artificial neural networks (ANNs) can also be successfully employed for modeling of complex non-linear prediction problems. Feed-forward ANN models viz. multilayer perceptron (MLP) and radial basis functions (RBF) are trained with empirical data to approximate the makespan response of job scheduling algorithms and they can be generalized to predict the new large instances of same problem class. Overall predictive capabilities of these modeling techniques are also measured with various statistical goodness-of-fit standards. This paper will focus on comparing the performance of RSM and ANN based modeling schemes to predict makespan values of job scheduling algorithms in PC-cluster based distributed computing environment. Performance of three space-sharing scheduling algorithms namely First-come-first-serve, Fit-processors-first-served and Largest-job-first is also compared in this paper.
References
- Ismail, I.M.1995, “Space-sharing job scheduling policies for parallel computers”, Ph.D thesis, Iowa state university, Iowa, 1995.
- Mohamed, A., Lester Lipsky and L., Ammar, R. 2003, “Performance Modeling of a Cluster of Workstations”. In Proceedings of Communications in Computing'2003. pp.227~233.
- Figueira, S.M. 2004, “Optimal partitioning of nodes to space-sharing parallel tasks”, Parallel Computing, 32(2004), 313-324.
- Iqbal,S., Gupta,R. and Fang,Y.C. 2005 “Planning considerations for job scheduling in HPC clusters”, reprinted from Dell Power Solutions, pp 133-136.
- Schweigelshohn, U. and Yahyapour, R. 1998 “Analysis of first-come-first-serve parallel job scheduling", In Proceedings of the ninth annual ACMSIAM symposium on discrete algorithms, pages 629–638, Philadelphia, PA, Society for Industrial and Applied Mathematics.
- Aida, k. 2000, “Effect of job size characteristics on job scheduling performance” In Job Scheduling Strategies for Parallel Processing, Springer Verlag, Lect. Notes Computer Science vol. 1911, pp. 1—17.
- Sherwani, J., Ali, N., Lotia, N., Hayat, Z. and Buyya, R. “Libra: A Computational Economy based Job Scheduling System for Clusters”, Software: Practice and Experience, vol. 34, no. 6, May 2004, pp.573-590.
- Benitez, N. and McSpadden, A. 1997, “Stochastic Petri Nets Applied to the Performance Evaluation of Static Task allocations in Heterogeneous Computing Environments,” Proceedings of the 6th Heterogeneous Computing Workshop, pp. 185-194, 1997.
- K. Aida, H. Kasahara, and S. Narita.1998 "Job Scheduling Scheme for Pure Space Sharing Among Rigid Jobs", In fourth workshop on Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, vol. 1459, pages 98-121, Springer-verlag.
- Goh, L.K. and Veeravalli, B.2008, “Design and performance evaluation of combined first-fit task allocation and migration studies in mesh multiprocessor systems”, Parallel Computing, 34(9), 508-520, 2008.
- Collins, D. and George, A.2001, “Parallel and Sequential Job Scheduling in Heterogeneous Clusters: A Simulation Study Using Software in the Loop” in SIMULATION, november 2001, vol.77 no. 5-6,169-184.
- Rajaei, H., Dadfar, M. and Joshi, P.2006, “Simulation of job scheduling for small scale clusters”, Proceedings of the 2006 Winter Simulation Conference.
- Montgomery, D.C. 2009 Design and analysis of experiments (5th ed.). New York: Wiley & Sons.
- SPSS 17.0 User’s guide http://www.hks.harvard.edu accessed on October 2011.
- Anderson, M.J. and Whitcomb, P.J. 2005, RSM Simplified: Optimizing processes using response surface methods for design of experiments, CRC press.
- Antony, J. 2003. Design of experiments for engineers and scientists. Elseveir Science & Technology Books 2003.
- Myers, R.H., Montgomery, D.C. and Anderson-Cook, C. M., 2009. Response Surface Methodology: Process and product optimization using designed experiments (3rd ed.).New York: John Wiley and Sons, Inc. 728 pp.
- Anderson, M.J. and Whitcomb, P.J. 2000, DOE Simplified: Practical Tools for Effective Experimentation, Productivity press.
- Design Expert Software version 8.0 user’s guide 2009.
- Haykins, S. Neural networks-A comprehensive foundation, Prentice Hall, 1999.
Index Terms
Keywords