Is algorithmic analysis by flop-counting obsolete?

Question

In my numerical analysis courses, I learned to analyze the efficiency of algorithms by counting the number of floating-point operations (flops) they require, relative to the size of the problem. For instance, in Trefethen & Bau's text on Numerical Linear Algebra, there are even 3D-looking pictures of the flop counts.

Now it's fashionable to say that "flops are free" because the memory latency to fetch anything not in cache is so much greater than the cost of a flop. But we're still teaching students to count flops, at least in numerical analysis courses. Should we be teaching them to count memory accesses instead? Do we need to write new textbooks? Or is memory access too machine-specific to spend time on? What is the long-term trend going to be in terms of whether flops or memory access is the bottleneck?

Note: some of the answers below seem to be answering a different question like "Should I obsessively rewrite my implementation to save a few flops or improve cache performance?" But what I'm asking is more along the lines of "Is it more useful to estimate algorithmic complexity in terms of arithmetic operations or memory accesses?"

Answer 1

I think the (first order) right thing to do is look at the ratio of flops to bytes needed in the algorithm, which I call $\beta$. Let $F_{\mathrm{max}}$ be the maximum flop rate of the processor, and $B_{\mathrm{max}}$ the maximum bandwidth. If $\frac{F_{\mathrm{max}}}{\beta} > B_{\mathrm{max}}$, then the algorithm will be bandwidth limited. If $B_{\mathrm{max}}\beta > F_{\mathrm{max}}$, the algorithm is flop limited.

I think counting memory accesses is mandatory, but we should also be thinking about:

• How much local memory is required

• How much possible concurrency we have

Then you can start to analyze algorithms for modern hardware.

Answer 2

I don't see why one has to be the "winner"; this isn't a zero-sum game, where flop counts and memory access have to drown the other out. You can teach both of them, and I think they both have their uses. After all, it's hard to say that your $O(N^4)$ algorithm with $O(N)$ memory accesses is necessarily going to be faster than your $O(N \log N)$ algorithm with $O(N^2)$ accesses. It all depends on the relative costs of the different parts (that pesky prefactor that we always ignore in these analyses!).

From a broader perspective, I think that the analysis of algorithmic performance should be "all-inclusive." If we're teaching people to be actual HPC developers and users, then they need to understand what are the costs of programming in the real world. The abstract analysis models we have don't take into account the programmer's time. We should be thinking in terms of "total time to solution," rather than just flop counts and algorithmic efficiency. It makes little sense to spend three or four programmer days to rewrite a routine that will save one second of computer time per job unless you're planning on running a few million calculations. Similarly, a few days' investment to save an hour or two of compute time quickly pays off. That novel algorithm may be amazing, but if it takes months to reprogram your code to take advantage of it, is it really worth it?

Answer 3

As others have pointed out, the answer does of course depend on whether the bottleneck is the CPU or memory bandwidth. For many algorithms that work on some arbitrarily-sized dataset, the bottleneck is usually the memory bandwidth as the dataset does not fit into the CPU cache.

Moreover, Knuth mentions that memory access analysis is more likely to stand the test of time, presumably because it is relatively simple (even when taking into account cache-friendliness) compared to the complexities of modern CPU pipelines and branch prediction.

Knuth uses the term gigamems in Volume 4A of TAOCP, when analysing BDDs. I'm not sure if he uses it in previous volumes. He made the aforementioned comment about standing the test of time in his annual Christmas Tree Lecture in 2010.

Interestingly, You're Doing It Wrong shows that even analysing performance based on memory operations is not always straightforward as there are elements such as VM pressure that come into play if the data does not fit into physical RAM all at once.

Answer 4

How you determine the costs of an algorithm depends on which "level" of scientific computing you work, and which (narrow or broad) class of problems you consider.

If you think about cache-optimization, this is clearly more relevant to, e.g., the implementation of numerical linear algebra packages like BLAS and similar libraries. So this belongs to low-level optimization, and it is fine if you have a fixed algorithm for a specific problem and with sufficient constraints on the input. For example, Cache optimization might be relevant to have a fast implementation of the conjugate gradient iteration if the matrix is promised to be sufficiently sparse.

On the other hand, the broader the class of problems, the less you can predict on the actual computing (like, say, you don't know how sparse the input matrices of your CG implementation will really be). The broader the class of machines your program is supposed to run on, the less you can predict on the Cache architecture.

Furthermore, on a higher level of scientific computing, it might be more relevant to change the problem structure. For example, if you spend time in finding a good preconditioner for a linear system of equations, this kind of optimization usually beats any low-level optimization, because the number of iterations is drastically reduced.

In conclusio, cache optimization is useful only if there is nothing left to optimize by parallelism and reduction of asymptotic number of FLOPs.

I think it is wise to adapt the stance of theoretical computer science: In the end, improving the asymptotic complexity of an algorithm has more return than micro-optimization of some existing lines of code. Therefore, FLOPs counting is still prefered.

Answer 5

I have always refused to even think about counting flops, memory accesses, or whatever you have. That's a concept from the 1960s when what you did was pretty much given and only how you did it was up to algorithmic optimization. Think solving a finite element problem on a uniform x-y-z mesh using either Gaussian elimination of Jacobi iteration.

Now, you can optimize this to hell and save a few flops, gaining 10% of run time. Or you can think about implementing a multigrid method and an optimal block preconditioner, gaining a factor of 10 in run time. This is what we should train our students to do -- think about what complex, outer algorithms can gain you over trying to find a better inner algorithm. Your boss (Keyes) has these slides on progress in MHD computations that make this very point rather obvious.

Answer 6

Yes, obsolete. Algorithmic analysis by flops, or any other method, is only as useful as the abstract model of the machine when considering the size of the problem at hand. Actual performance depends both on the implementation and the hardware, and the applicability of any abstract model for the latter to reality is decreasing over time. For example, as you further parallelize the implementation of a complex algorithm, like molecular dynamics, different aspects become rate limiting on different hardware, and algorithmic analysis has nothing to do with the observations. In one sense, the only important thing is to measure the performance of the implementation(s) of the algorithm(s) on the hardware type(s) in question.

Are such abstractions useful as a learning tool? Yes, like lots of models used for teaching, they are useful as long as they are placed alongside understanding of the limitations of the model. Classical mechanics is fine so long as you appreciate that it won't work on scales of small distance or large velocity...

Answer 7

Not really answering your question, but more adding another variable to consider: something to take into account is the features of the programming language. For example, Python's sort uses the Timsort algorithm, that is designed (among other nice properties) to minimise the number of comparisons, that could be potentially slow for Python objects. On the other hand, compare two floats in C++ is blazing fast, but swapping them is more costly, so they use other algorithms.

Other examples are dynamic memory allocation (trivial in a Python list, fast in both runtime and developers time, just .append()), vs FORTRAN or C, where, though possible and faster when properly implemented, it takes significantly more programming time and brain. See Python is faster than FORTRAN.