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?
$\begingroup$
$\endgroup$
18
-
$\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, 2015 at 8:32
-
3$\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, 2015 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 MeurerSep 27, 2015 at 15:53
-
1$\begingroup$ Factorials are a bit too regular and predictable (usually people try $\pi$ or $\gamma$ - e.g., $\lfloor 10^{10^6}\pi\rfloor$). For example, $10^9!$ is divisible by $2^{10^9-13}$ and by $5^{(10^9-8)/4}$, so the least significant $\sim249,999,998$ decimal digits are just zeros - any computational effort on them is completely wasted. $\endgroup$– KirillSep 30, 2015 at 1:23
-
2$\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$– KirillSep 30, 2015 at 1:35
|
Show 13 more comments
2 Answers
$\begingroup$
$\endgroup$
0
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!$.
answered Sep 29, 2015 at 21:18
$\begingroup$
$\endgroup$
5
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.
-
1$\begingroup$ 2x-4x is not that impressive if the comparsion cpu is a 4-core i7 $\endgroup$ Sep 28, 2015 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$ Sep 28, 2015 at 10:24
-
$\begingroup$ Ah, ok, this is much more interesting, I hadn't read the website, thanks for explaining $\endgroup$ Sep 30, 2015 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$ Oct 4, 2015 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$ Oct 5, 2015 at 11:11