2
$\begingroup$

The number 1 response to this question was great.

Is algorithmic analysis by flop-counting obsolete?

Now, the only problem is that I don't really understand it. Here's my example of why it's not clear to me. Please let me know what I'm doing wrong.

Applying the above analysis to the FFT:

Say I want to compute the fft of a vector of doubles length n. Then I need to do approximately nlog(n) flops. The bytes required to do the computation are 8n, assuming a 64bit system. So $\beta$ = log(n)/8.

Suppose my processor works at 2GHz=Fmax and I have 8Gbytes=Bmax of RAM. Then, I have equality when:

log(n)/8 (flops/byte) = (Bmax/Fmax) (bytes/Hz) = 4 This implies

log(n) = 32 => n = 2^32 = 4,294,967,296

So, I should be able to compute the fft of a vector of size n? I don't know. Also, why don't the units cancel?

|cite|improve this question
$\endgroup$
2
$\begingroup$

You misunderstood what Matt wanted to say about $\beta$. It's not the ratio of total number of operations divided by amount of memory required for the algorithm (or the other way around) but instead the ratio of total number of operations divided by total number of memory accesses. In your case, you may need $8n$ memory locations, but you will most certainly need to read every location more than just once. In fact, in most applications, the number of memory accesses is proportional to the number of floating point operations, and this ratio is then $\beta$. This factor is different for different algorithms, however.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the response. Let me see if I understand this. So, for my example, the number of operations is around nlog(n). Then, I need to figure out how many times each array element is accessed. I don't what it is for the fft but let's say it's $\sqrt{n}$ then $\beta$ = $\frac{nlog(n)}{(\sqrt{n} n)}$? Now, I can compare this with the ratio of Bmax/Fmax. I see now. Bmax is bytes/sec and Fmax is flops/sec. So the units work out now. Thank you. $\endgroup$ – plancherel Mar 25 '14 at 16:21
  • $\begingroup$ Yes. But it can't be that you only have $\sqrt n$ memory accesses because then for large enough $n$ you wouldn't even touch every memory location once. It needs to be more than $O(n)$. In general practice, it is usually a multiple of the floating point operations you do, based on the observation that every operation needs to load one or more operands from memory. So $\beta$ is often a constant independent of $n$. $\endgroup$ – Wolfgang Bangerth Mar 26 '14 at 1:46
  • $\begingroup$ Thank you for your response. Do you know of an example of $\beta$, $F_{max}$, and $B_{max}$ being worked out for a real system and algorithm? I would like to see how this is really done in practice. Thanks. $\endgroup$ – plancherel Mar 26 '14 at 16:31
  • $\begingroup$ Think what you would get if you did a dense matrix-vector product. This should give a realistic example. $\endgroup$ – Wolfgang Bangerth Mar 27 '14 at 2:34
1
$\begingroup$

Matt's answer over there isn't about whether or not you can compute a problem of a particular size. It's about whether your algorithm is likely to be memory access limited or compute limited on a particular architecture. So, backing $n$ out of this bound doesn't make sense. $n$ is an input along with $B_{max}$ and $F_{max}$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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