A formal model

Formally, we wish to solve the following problem:

Given:

• Several versions of an algorithm $A = \{a_1, a_2, \ldots, a_m\}$, where all versions have identical inputs and outputs.

• A set of samples $X = \{x_1, x_2, \ldots, x_n\}$ from the algorithm's input space S (i.e., $X \subseteq S$).

• The execution time T(a,x) for algorithm a on input x.

Find:

• A decision function f(x), where $f:X \rightarrow A$, i.e., a mapping from an input to an algorithm.

This is illustrated in fig. 1 (left). In general, for a given algorithm we will identify the formal parameters above, assume a parametric form for the mapping, and construct an appropriate cost function in terms of the execution times T(a,x). We will determine the parameters of the map by optimizing the cost.

  

Figure 1: ( Left) A hypothetical two-dimensional input spaces. Our task is to determine the boundaries (dashed lines). This is similar to general clustering or classification problems. ( Right) A matrix multiply operation C = C + AB is specified by three dimensions, M, K, N.