Runtime prediction on new architectures
Aleksey A. Sidnev · 2014
This paper formulates the program runtime prediction problem subject to algorithm parameters and characteristics of a computational system to be used to run the algorithm. It is suggested to build a model representing runtime as a function of algorithm parameters and computational system characteristics. This is followed by determination of features to be used for functional dependence recovery. A two-step method of problem solution using linear and non-linear machine learning algorithms is proposed. The paper examines peculiarities of software algorithms and suggests a method for processing experimental data provided by computational systems. It also features a comparative analysis of runtime prediction results for solution of several linear algebra problems on 84 personal computers and servers using a number of machine learning algorithms. Use of a random forest combined with the linear least square method shows an error of less than 15% for most computational systems of similar architecture.