9
$\begingroup$

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:

  1. Is this assumption realistic? Is the runtime function likely to be nearly deterministic?
  2. 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)
  3. Is there preexisting work on this somewhere?
  4. 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.

Improve this question
$\endgroup$
10
$\begingroup$

I have recently been working on exactly this topic. You may want to take a look at our paper: http://arxiv.org/abs/1209.2364.

Why are you interested in the runtime prediction of linear algebra routines? Do you intend to use the model for a certain purpose?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the link. I'll take a look. I'm interested in this for I suspect the same reason you are. Automated algorithm selection and scheduling for matrix expressions. A lot of otherwise impossible problems should be possible in this highly regular and predictable domain. $\endgroup$ – MRocklin Sep 26 '12 at 21:37
6
$\begingroup$

There is lots of preexisting work. Most linear algebra library developers publish performance results in terms of floating-point performance which can be converted into run times.

Googling for "DGEMM performance" for example, yields the following: http://math-atlas.sourceforge.net/timing/3_5_10/index.html.

Generally, you can expect the answers to be non-smooth. There will be jumps or spikes in the vicinity of certain problem sizes (which relate to cache sizes). You should also expect plateaus in rates, and, therefore, linear-ish regions for a broad range of problem sizes. I don't expect polynomial fits to be very helpful.

Given a broad-based benchmarking effort, it might be easier to tabulate results and interpolate as necessary. What's your goal?

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ A flop/s plateau in DGEMM indicates an $n^3$ region because that's the rate the flops are growing with problem size. I agree that a piecewise fit should be much better than trying to fit a single polynomial. $\endgroup$ – Jed Brown Jun 13 '12 at 3:42
  • $\begingroup$ Converting flops to runtimes is, in my experience, difficult. I really only care about runtimes in my case. I'm testing the feasibility of static scheduling. $\endgroup$ – MRocklin Jun 13 '12 at 12:27
  • $\begingroup$ In my experience spikes/plateaus only occur for small problem sizes. Once you get out beyond the cache things are pretty smooth. I agree that adding in piecewise functions would probably improve the fit. $\endgroup$ – MRocklin Jun 13 '12 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.