4
$\begingroup$

Assume I am running an iterative method, I have a rough estimate of how many iterations it will need, How do best estimate the time it will run for in serial?

For instance, If I have Conjugate Gradient (for Ax=b), how do I estimate how long it will run for given that I know the matrix dimension?

Specifically, I wish to ask :

  1. One can carry out a rough calculation by ignoring caches and compiler optimizations but is there any way to account for them? Of course, accounting for each one of them is impossible but at least the significant ones. I was intrigued by the analysis posted on my other question and wished to be able to find out estimates for other algorithms but with a tighter bound.
  2. How do you find out cost of optimized operations? For instance, MatVecs are $O(N^2)$. When calculating for BLAS DGEMV, what leading constant do you assume?

3. Given that I know the time it ran in serial mode, how I can estimate the time for parallel mode? I've looked into Amdahl's law but I'm not sure how to use it for iterative methods. Answered

P.S : An online PDF (or any reference) for finding out more on this would be great!

Update : For solving a 10000x10000 CG Problem with the DGEMV as bottleneck, I did the following: I took matrices of size from 2k x 2k to 19k x 19k and plotted a graph of Time (for random matvec) vs Size^2. I multiplied time with 2.13E9 (for GHz) to give the graph of Total Operations vs Size^2. Then I approximate the slope of the line which gives me Operations = (slope) * N^2. In my case, the constant was 45.45454545 and the graph was dead straight. For a 10k x 10k CG problem, it takes 1 matvec per iteration (no preconditioner) and 550 such iterations. That's a total of 550 matvecs $\approx$ 550*45.45*N^2 operations $\approx$ 550*45.45*1e8 / 2.13e9 seconds $\approx$ 1000 seconds.

It turns out that (I have requested the moderator at SO to delete that question):

  • I am not accounting for Instructions per Second (and per clock). Consequently, my running time is 120 seconds in reality (for 10k x 10k CG) while my calculations are at 1000 seconds! How do I account for IPS/IPC?

  • 45 is too huge a leading constant for MatVecs. Ideally, it should be around 2. Where did I go wrong in this calculation?

How do I improve my theoretical predictions?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$
  1. It's pretty hard to get a meaningful analysis of cache effects and optimizations since the benefit you get from them depends on the implementation. (For example, are you accessing memory row-wise or column-wise? This will affect memory locality and cache hits. Are the inner loops possible to unroll? What intrinsics are available for your platform?)
  2. Finding constants for BLAS implementations is very platform specific so you should probably try some benchmarks (try some datasets with a size N, N^2, N^3 etc)
  3. A good introduction to Amdahl's law with some modifications for heterogenous environments is the paper "Amdahl's law in the multicore era" found here. Generally, for rough estimates, try to divide the operation into parallel operations, communication costs (not always applicable) and serial operations. You can then use Amdahl's law to see what kind of speedup you might expect.

While run time analysis a priori is a useful tool, determining constants and the like is better done empircally, in my opinion. There are a lot of subtle stuff going on in the background when compiling and running scientific apllications.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How would I determine the constant by running datasets? I thought of: Plotting a graph of Time vs Size^2. (I know it's O(N^2)) Multiply time with 2.13E9 (for GHz) to give the graph of Total Operations vs Size^2. Then I approximate the slope of the line which gives me Operations = (slope) * N^2. In my case, the constant was 45.45454545 and the graph was dead straight. Seems OK? $\endgroup$
    – Inquest
    Commented Apr 16, 2012 at 19:34
  • $\begingroup$ Yes, that sounds like a good approach, as long as the sizes selected are sufficiently large (which they probably were if the line was straight and the line fitting good) $\endgroup$
    – moyner
    Commented Apr 16, 2012 at 19:55
  • $\begingroup$ Good answer. The memory cache thing is basically impossible to predict without compiling/running/testing on the architecture in question. Many sophisticated compilers (icc etc.) have some model of the systems memory built into the process, so the answer is really hard to say. The "subtle stuff" mentioned is really hard to predict in a void of other information. $\endgroup$
    – meawoppl
    Commented Apr 23, 2012 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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