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