• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

GA-Sim: A job running time prediction algorithm
based on categorization and instance learning

XIAO Yonghao,XU Lunfan,XIONG Min   

  1. (Institute of Computer Application,China Academy of Engineering Physics,Mianyang 621900,China)
  • Received:2018-10-11 Revised:2018-12-17 Online:2019-06-25 Published:2019-06-25

Abstract:

In high performance computing job scheduling, many scheduling algorithms, especially the backfilling algorithm such as EASY, depend on the accurate estimation of job running time. Using user-supplied job running time usually significantly reduce scheduling performance. We propose a job running time prediction algorithm based on categorization and instance learning, named GA-Sim. It considers both prediction accuracy and underestimation problem. Numerical experiments on two actual scheduling logs show that compared with the IRPA and TRIP, the GASim reduces the underestimation rate while achieving higher prediction accuracy. We also make an indepth analysis of the numerical experiment results, and give suggestions for choosing an appropriate prediction algorithm  under different circumstances.

Key words: parallel job scheduling, high performance computing, running time prediction