An evaluation of learning and heuristic techniques for application run time predictions

This paper evaluates several main learning and heuris-tic techniques for application run time predictions on clus-ters and parallel supercomputers. Techniques being in-vestigated are based on mining the similarities in histor-ical workload traces. Firstly several feature selection al-gorithms are introduced and compared, such as Rough Set based “Improved Reduct ” and Genetic Algorithms. These algorithms are able to select relevant attributes that identify similar jobs in the past. Secondly two induction methods, namely Similarity Templates and Instance Based Learning (IBL), are empirically evaluated for prediction generation. Our evaluation is based on real workloads with diverse characteristics, which are collected from the LHC Comput-ing Grid, the DAS-2 research cluster, and San Diego Super-computing Center. The experimental results indicate that more computationally efficient methods such as Improved Reduct is able to achieve comparable results in terms of pre-diction accuracy. Moreover, the simple Similarity Templates approach, when combined with proper feature selection al-gorithms, outperforms more sophisticated IBL algorithms on our workloads.