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 :
- 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.
- 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?