2
$\begingroup$

I've been working on calculating large factorials ($N>10^9$) and I was wondering if it wasn't faster to use the GPU to run the calculations on something like openCL. What I realized however was that, not only I didn't know if it was worth it in that case, I couldn't tell when it is or isn't appropriate to use a GPU for number crunching. So, basically, what are the pros and cons of using GPU and CPU for such large numbers ($10^9!$) or when is it worth it at all to do GPU implementation?

$\endgroup$
  • $\begingroup$ Mathematical notation can be used in your posts here with MathJax and $\LaTeX$, although this is not supported on all StackExchange sites (nor on Meta.SciComp.SE). $\endgroup$ – hardmath Sep 27 '15 at 8:32
  • 2
    $\begingroup$ Stirling's approximation tells me $10^9!$ will have over eight and a half billion digits. If required, outputting the result in full would also take time regardless of how it is computed. $\endgroup$ – hardmath Sep 27 '15 at 14:31
  • $\begingroup$ @hardmath I'm aware it will take time hahaha. I'm preparing 128Gb of DDR4 plus 4 512Gb SSDs on RAID 0 configuration to handle all the data. My options are an i7 extreme or two GTX980's tho for the calculation. $\endgroup$ – Bernardo Meurer Sep 27 '15 at 15:53
  • $\begingroup$ Just out of curiosity, why do you need the exact value of the factorial of such a large number? $\endgroup$ – Hydro Guy Sep 28 '15 at 1:34
  • 1
    $\begingroup$ @Arengorn Ah, okay. I looked it up at mathworld.wolfram.com/BrocardsProblem.html and it cites Berndt & Galway - but they computed $n!+1$ modulo some primes, and then established whether a solution existed via the Chinese remainder theorem. That is vastly more efficient than computing $n!$ directly. They seem to have been using mid-1990's hardware, so I bet this should be easy now. Can I recommend that you ask a separate question explicitly stating the goal and all the context? You might get more direct/helpful responses for your actual problem. $\endgroup$ – Kirill Sep 30 '15 at 1:35
6
$\begingroup$

This may have gone unnoticed in the comments under the original question, but computing $10^9!$ yields a number with 8.5 billion digits, that is it is on the order of $10^{9\cdot 10^9}$. Given that $10^{9\cdot 10^9}=1000^{3\cdot 10^9} \approx 1024^{3\cdot 10^9}=(2^{10})^{3\cdot 10^9}=2^{3\cdot 10^{10}}$, you need approximately $3\cdot 10^{10}$ bits, or around $4\cdot 10^9$ bytes to simply represent such a number. That's a sizable amount of memory.

Now imagine that you want to compute this number in parallel by having each processor compute a part of the factorial. For example, processor $p$ computes $Q_p=\prod_{k=N_{p-1}}^{N_p} k$, then the total can be computed by $N_P! = \prod_{p=1}^P Q_p$ if you choose $N_0=1$ and $P$ is the number of processors. But generally, each one of the $Q_p$ are going to be of the same order of magnitude as the final result (well, not quite, but you get the general idea), so if you have $P$ processors, you need to provision $P$ times as much memory as it takes to store the final result.

On a GPU, you have many processors, $P={\cal O}(1000)$. If each of the numbers you have to store already takes 4 GB of memory, then if you have to store it 1000 times over, you very quickly end up with an amount of memory that is not only not available on a typicaly GPU, but in fact not even in regular desktop computers.

I think what this means is that you are biting off more than you can likely chew if you try to compute $10^9!$.

$\endgroup$
2
$\begingroup$

It is a bit old, but the CUDA Multiprecision Arithmetic Library probably supports the operations you need, and reports 2-4x speed-ups vs a CPU socket. It claims to have a GMP-like interface, so porting you code could be straight-forward, relative to writing custom kernel code.

$\endgroup$
  • 1
    $\begingroup$ 2x-4x is not that impressive if the comparsion cpu is a 4-core i7 $\endgroup$ – Hydro Guy Sep 28 '15 at 1:42
  • $\begingroup$ 2x-4x was against the dual socket opteron, which was the more relevant comparison in its day. The website, and all the hardware on it, is out of date. $\endgroup$ – Max Hutchinson Sep 28 '15 at 10:24
  • $\begingroup$ Ah, ok, this is much more interesting, I hadn't read the website, thanks for explaining $\endgroup$ – Hydro Guy Sep 30 '15 at 2:02
  • $\begingroup$ If GPU folks claim a speed up less than 10x, it's probably useless, because the majority of their performance claims are wildly exaggerated and tailored towards cases where they win. $\endgroup$ – Jeff Oct 4 '15 at 22:14
  • $\begingroup$ @Jeff do you have a specific criticism of their performance analysis? They avoid the cardinal sin of comparing to a single CPU core, which is the only way a GPU could ever top 10x, and they do a parameter sweep that includes some of the ramp-up region. I'd like to also see vector lengths that were lower and operations with higher arithmetic intensity, sure, but what they have done seems common enough and robust. $\endgroup$ – Max Hutchinson Oct 5 '15 at 11:11

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.