Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

Statistical Modeling and Evaluation of Parallel Space-sharing Job Scheduling Algorithms for PC-cluster using Design of Experiments (DOE)

Print
PDF
International Journal of Computer Applications
© 2011 by IJCA Journal
Number 8 - Article 2
Year of Publication: 2011
Authors:
Amit Chhabra
Gurvinder Singh
10.5120/3158-4370

Amit Chhabra and Gurvinder Singh. Article: Statistical Modeling and Evaluation of Parallel Space-sharing Job Scheduling Algorithms for PC-cluster using Design of Experiments (DOE). International Journal of Computer Applications 25(11):17-24, July 2011. Full text available. BibTeX

@article{key:article,
	author = {Amit Chhabra and Gurvinder Singh},
	title = {Article: Statistical Modeling and Evaluation of Parallel Space-sharing Job Scheduling Algorithms for PC-cluster using Design of Experiments (DOE)},
	journal = {International Journal of Computer Applications},
	year = {2011},
	volume = {25},
	number = {11},
	pages = {17-24},
	month = {July},
	note = {Full text available}
}

Abstract

Parallel space-sharing job scheduling algorithms play an indispensible role in efficient allocation of processors of PC-cluster to the competing jobs to achieve one of the performance objective(s) viz. minimized mean response time (MRT), minimized average bounded slowdown or maximized throughput. Traditional performance modeling and evaluation studies of parallel space-sharing job scheduling algorithms are incompetent of predicting the combined or interaction effect on the response resulting due to simultaneous variation of two process variables. Present work is undertaken to predict and quantize the influence of main and interaction effects of the input scheduling process variables on the output MRT values using statistical approach of design of experiments (DOE). DOE based Response surface methodology (RSM) oriented experimental design is chosen to evaluate MRT values for two scheduling algorithms namely First Come First Serve (FCFS) and Fit Processors First Served (FPFS). Two empirical interaction models are suggested for both scheduling algorithms that predict MRT on the basis of multiple regression equations involving main and interaction effect terms of scheduling process variables. High value of adjusted coefficient of determination R2 and insignificant lack of fit represent the goodness of fit of both the models to accurately predict the MRT values. Both the empirical interaction models are validated against additional experimental results. The comparative performance evaluation study on the basis of MRT reveals that the FPFS algorithm tends to outweigh the traditional FCFS policy.

Reference

  • Yeo, C.S., Buyya, R. and Pourreza, H.2006 “Cluster Computing: High-Performance, High-Availability and High-Throughput Processing on a Network of Computers”,vol.29 (6),Springer Science + Business MediaInc,New York,USA,pp.521-551.
  • Ismail, I.M. 1995, “Space-sharing job scheduling policies for parallel computers”, Ph.D thesis, Iowa state university, Iowa.
  • Figueira, S.M. 2004, “Optimal partitioning of nodes to space-sharing parallel tasks”, Parallel Computing, 32,pp 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.
  • Lublin, U and Feitelson, D.G. 2003, "The Workload on Parallel Supercomputers: Modeling the Characteristics of Rigid Jobs", Journal of Parallel and Distributed Computing, 63(11):1105–1122.
  • Aida,K., Kasahara, H. and Narita, S.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.
  • Montgomery, D.C. 2009 Design and analysis of experiments (5th ed.). New York: Wiley & Sons, Inc. 672 pp.
  • 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.
  • Buyya, R., Cortes, T. and Jin, H. 2001. “Single System Image (SSI),” International Journal of High Performance Computing Applications, vol. 15, no. 2, pp. 124-135.
  • 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.
  • Antony, J. 2003. Design of experiments for engineers and scientists. Elsevier Science & Technology Books.