# Whats wrong with my running time calculation?

I am running a linear algebra iterative method (PCG) for solving Ax=b, the dimension of the matrix is 10000x10000.

So, I did 2 preliminary analyses:

• Memory Analysis

The size of the matrix dominates the total storage required. Thats about 1E4 x 1E4 = 1E8 elements of double precision which is approximately 0.8 GB of data. The number of iterations required for convergence was 450. Since this won't fit in cache, I assume no cache benefits, that would mean 450 x 0.8 = 360 GB of data transfer. With a memory bandwidth of 10 GB/s, thats approximately 36 seconds for memory transfers.

• Flop Analysis

I calculated that I will be carrying out 1 matrix vector (dominant operation) per iteration for 450 iterations. That is cN^2 operations/iterations x 450 iterations = 450c N^2 operations with a 2.13GHz processor (ensured to work on a single processor only). That is 21.12c for N=10000.

To find c, I carried out MatVecs for all sizes from 1 to 19000, plotted the graph for No. of Operations vs (Dimension)^2 (Operations = slope x Dim^2) where No. of Operations = Time x 2.13 GHz. I used the slope of this (linear) graph as c . Which came out to be 50.

Thus, total time = 21.12c = 1000 seconds.

Thus, assuming both memory transfer and operations happen concurrently, theoretically, it should take 1000 seconds.

But in reality, the code took 120 seconds maximum. Where did I go wrong? My calculation is fairly off.

• I'd be careful saying that cache doesn't help at all. Even if the data doesn't fit in cache, any amount of locality will still help drastically.
– Mysticial
Apr 18, 2012 at 18:54
• But then, the time for floating point operations is dominant here. Even if I assume that I have a GB worth of cache, I still have 1000 s worth of computation. Apr 18, 2012 at 18:56
• You do realize that a modern computer can do way more than 1 operation/cycle?
– Mysticial
Apr 18, 2012 at 18:58
• @Mysticial How do I account for that? I have tried reading my processor's (i3 330M) documentation but couldn't find out how to account for this. What would it be called? Apr 18, 2012 at 19:00
• It depends on how well the code is written. A Core i3 can do up to 4 (double-precision) floating-point operations per cycle. Then you have to account for the number of cores. And I highly suspect that your equation is wrong - as the implementation is probably using something with fewer operations.
– Mysticial
Apr 18, 2012 at 19:02

## 3 Answers

As Jitse pointed out, the mistake is clearly in your estimate for the cost of $c$. As you probably noticed, the graph for estimating almost any computation as a function of array size is not particularly linear, there's a lot of jitter due to weird cache effects, and there are several clear regions where L1, L3, and main memory dominate. I noticed that Mystical also pointed this out to you in your chat discussion

Additionally, if you have a good estimate of the cost per mat-vec from direct measurement, the $c$ you are calculating takes into account both memory and flop/s.

The overall picture for this sort of computation is messy. It seems like you are trying to get into very fine performance analysis details without a good high-level understanding of computer architecture and pipelined performance. Have you read Hennessy and Patterson's Computer Architecture: A Quantitative Approach?

• I think you are right, I need to brush up on the hardware aspect of my knowledge. Thanks! (Tangentially, what do I do of my other question with an open bounty?) Apr 23, 2012 at 14:43

I find it hard to believe that c is 50. Theoretically, a matrix-vector product requires 2N^2 flops if the matrix is N-by-N, which gives c = 2. In practice, stuff like indexing operations, vectorization and quality of implementation influence this, but c = 50 seems very high.

Additionally, assuming that PCG = preconditioned conjugate gradient, which preconditioner do you use? Are you sure that the cost of preconditioning can be neglected?

• Am I making a mistake in the calculation? Regd preconditioners, my test matrices are fairly well conditioned (low condition numbers, very little eigenvalue spread), so I am running PCG without preconditioners. Apr 19, 2012 at 13:41

Must be in this : No. of Operations = Time x 2.13 GHz , operations in a process can't be caculated this way. There are numbers of variables that will influence this notably the kind of cpu that you are using, heat and parellism.

"The performance or speed of a processor depends on the clock rate (generally given in multiples of hertz) and the instructions per clock (IPC), which together are the factors for the instructions per second (IPS) that the CPU can perform."

The only variable you have here is clock rate.