## 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