I would like to predict runtimes for dense linear algebra operations on a specific architecture using a specific library. I would like to learn a model that approximates the function
$F_{op} \;::\; $input sizes$ \rightarrow $runtime
for operations like matrix-multiply, element-wise add, triangular solve, etc....
I suspect that these runtimes are mostly predictable due to the regularity of the operations once you get beyond problem sizes that fit comfortably in cache.
Questions:
- Is this assumption realistic? Is the runtime function likely to be nearly deterministic?
- Can I assume that this function will be polynomial in the sizes of the inputs? (i.e. I expect dense matrix multiply to look something like $\alpha n\times k\times m$ for $A_{nk}\times B_{km}$ and $\alpha$ some scalar coefficient)
- Is there preexisting work on this somewhere?
- My current plan is to do least squares regression with an $L_1$ regularizer. Any other suggestions?
Edit: To be clear I'm looking for runtimes, not FLOPs or any other common performance metric. I'm willing to restrict myself to one particular architecture.