Predicting scientific computation's running time
Name
Karl-Oskar Masing
Abstract
The thesis consists of two major parts. In the first part,
we present a technique to predict an arbitrary computation’s
running-time based on data gathered from previous executions.
In the second part, we present an implementation along with a
user manual and an example.
Running-time prediction is based on the following observation. We can distinguish between different program calls using
parameters that potentially affect the running time. By recording both parameters and elapsed time, we can derive a model from the data that would estimate the running time. As we are interested in the comprehensibility of the model, we cannot use regular non-parametric regression methods. Hence, we use generalised linear regression with different basis functions such as n*n , n*log(n) and n*n*n*log(n). However, as we approach the problem of finding a relatively simple yet accurate model while traversing the search space by generating different models, basis functions can get even more complicated, involving multiplications of multiple parameters with different powers. Using the found model, it is then possible to predict the running time when parameters are known.
Thesis comes also with a Python library that
uses the described method to estimate an arbitrary program’s
running-time.
Graduation Thesis language
Estonian
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
dr Meelis Kull, dr Sven Laur
Defence year
2013