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?"

  • 1
    > "Is it more useful to estimate algorithmic complexity in terms of arithmetic operations or memory accesses?". From a practical point of view, embedded systems are still limited by FPU speed rather than memory bandwidth. Thus, even if flops counting was deemed to be obsolete by HPC standards, it is still of practical use to other communities. – Damien Mar 25 '14 at 6:36
up vote 29 down vote accepted

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.

  • 3
    I agree with Matt, but I want to point out that $\beta$ is now reasonably commonly found defined in the literature as "arithmetic intensity" and "numerical intensity". I think the Roofline model by Williams, Waterman, and Patterson is probably a good start to thinking about these problems. I think this should be extended to an algorithm's memory/flop access ratio in time. – Aron Ahmadia Nov 30 '11 at 21:46
  • 2
    David doing more 8 years prior. – Matt Knepley Dec 1 '11 at 0:53
  • 3
    Okay, so there is a better, more complex model (as always). But this model gives an answer that is machine-dependent. What should we teach students to use as a first analysis? – David Ketcheson Dec 3 '11 at 4:36
  • 3
    The point is that the machine has been reduced to a single number, the ratio of peak flops to peak bandwidth, as has the algorithm. This is as simple as it gets. Without a computational model, any complexity estimate is useless and this is the simplest realistic one. – Matt Knepley Dec 3 '11 at 19:55
  • 1
    I think you misunderstand the problem. We already have optical transport that can carry large loads. The problem is getting that on a chip. You only have so many wires and a top clock rate. Optical transport would only alleviate this problem on an optical chip. – Matt Knepley Mar 3 '12 at 16:43

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?

  • 7
    An $O(N \log N)$ algorithm that performs $O(N^2)$ data access? :) – Andreas Klöckner Mar 30 '12 at 3:00
  • 1
    Why not? If $O(N\log N)$ only refers to the floating point ops, maybe there are additionally a significant number of integer ops that cause the $O(N^2)$ data accesses :) – kini Apr 18 '16 at 18:45

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.

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.

  • "cache optimization is useful only if there is nothing left to optimize by parallelism and reduction of asymptotic number of FLOPs". I disagree. If you want to compute a large expression of a big bunch of numbers, it is better to perform one step at a time with all the numbers than all the steps for each number. Both have the same number of FLOPS, but one is better in memory access. Bonus if you select the size of the bunch to fit in cache (or the compiler does it for you). This is what numexpr does in Python: – Davidmh Mar 27 '14 at 11:47

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.

  • Actually I was asking about the kind of high-level thinking you suggest, not low-level optimization. What metric should you use to determine whether multigrid and your preconditioner will be faster than the alternatives? – David Ketcheson Dec 16 '11 at 8:41
  • I wouldn't know how to count -- by hand -- FLOPS or any other instruction count for complex algorithms that run over tens or thousands of lines of code. Think, for example, how complex the analysis and construction phase of AMG algorithms is. There are so many parts of these algorithms, and all of those depend on the actual data that you can't predict the number of operations. – Wolfgang Bangerth Dec 16 '11 at 14:56
  • 1
    I think I at first misunderstood what you were getting at, but I still disagree with your point. "Outer algorithms" can (and I would argue, should) still be designed with asymptotic complexity in mind. Surely you would not claim that a drop from a quadratic algorithm to a near-linear algorithm would at best lead to a 10% reduction in runtime; yet, how else to quantify the asymptotic complexity than through the flops and/or memory-ops? – Jack Poulson Dec 16 '11 at 21:39
  • 7
    I think this "throw up your hands" approach to algorithms is crap. You need to simplify the analysis by only looking at first-order costs, and by simplifying the model so that it is tractable, but to say you cannot analyze something like MG or Cholesky because it is too complicated is flatly wrong. – Matt Knepley Dec 18 '11 at 23:49
  • 1
    Well, but what does it mean to analyze MG or Cholesky when every FLOP you count is hidden behind several layers of latency caused by hyperthreaded processors, caches, slow RAM, multiscalar processors and automatic vectorization? The point I'm making is that within a factor of 5-10, you can't predict the run-time of your algorithms any more without timing it. That was completely different back in the 50s and 60s when people starting this FLOP counting. – Wolfgang Bangerth Jan 10 '12 at 5:16

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

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.

  • This is true, but, as you say, does not answer the question. It's on a different topic. – David Ketcheson Mar 28 '14 at 6:33
  • Well, in a proper analysis it is something to take into account when deciding which algorithm to implement. – Davidmh Mar 28 '14 at 8:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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