GA-Sim:一种基于分类和实例学习相结合的作业运行时间预测算法

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

在高性能计算作业调度系统中,许多调度算法依赖于对作业运行时间的准确估计,尤其是以EASY为代表的回填算法,而使用用户提供的作业运行时间往往会降低调度性能。提出了一种基于分类和实例学习相结合的作业运行时间预测算法--GA-Sim,该算法在考虑预测准确性的同时考虑了低估问题。在两个实际调度日志上的数值实验结果表明,相较于IRPA和TRIP算法,GA-Sim在取得更高预测精度的同时降低了低估率。对数值实验结果进行了深入分析,并给出了不同情形下选择恰当预测算法的建议。

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.