4 ms·

I'm more surprised, assuming their algorithm is somewhat parallelizable, that they couldn't run their algo on an actual supercomputer, it likely wouldn't have t

I'm more surprised, assuming their algorithm is somewhat parallelizable, that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months. EDIT: reading a wiki page, this sounds like recreational mathematics, not actual research math, which is a shame really

dspillett 4y ago
> that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months I am assuming that is how the result was verified much faster - >1,000x the computer power used. Without looking deeper (like actually reading the article!) I couldn't say way that would be in this particular case, but such a disparity between power used to make a finding and power used to verify it by repetition is often the case when the initial result is discovered by a recreational researcher or small group, not a better funded group. Not unlike the human scaling seen when one individual or a small group publishes a proof that could be significant, and many others poor over it to see if they can find a flaw before it is generally accepted as a genuine new finding (an order of magnitude or more of human brains to check, than to initially find).
- cedilla 4y ago
  The results aren't verfied by running the same calculations again. Rather, there's a verification method used along with some information from the original solution - that's the certificate they mention. Imagine factoring a non-prime number. It would take you quite long to factor 695587 with nothing but a cheap calculator, but you could very quickly verify my factorization if I give you the information that it is divisible by 71 and 101.
  - dspillett 4y ago
    Though the factor-checking like verification won't work for “this number is prime” the same as it will for “this number is not prime”. A test that results in saying a number is prime doesn't output any factors to test because if such existed the number would not be prime. I'll have to read up on the certification/verification process to comment any further though.
    - cedilla 4y ago
      It does work that way, just not as straightforwardly. See https://en.wikipedia.org/wiki/Certificate_%28complexity%29 https://en.wikipedia.org/wiki/Certificate_%28complexity%29 if you're interested in learning more.
pclmulqdq 4y ago
This problem is also hard to parallelize. There is a lot of reuired communication between computation lanes (sections of the number), and the calculation takes a lot of dependencies on that communication. You could probably design a supercomputer specifically for prime searches, but it would be a weird one.
- dragontamer 4y ago
  I've calculated ~20kB to store this number in particular. GPU __shared__ memory is 64kB. A 1024-wide workgroup would be able to store 4096 bytes per register, if the whole workgroup was just working on one number. So ~6 registers x 1024 shader workgroup to store the full 20kB number. __shared__ memory would allow for very quick shader-to-shader communications. I think... it can work. But its difficult for me to visualize the full program. Its going to be complex, but probably doable. Its also not really a design pattern that a lot of GPU code (ex: Thrust) works in very well, you'd have to use harder to use libraries like CUB instead.
  - pclmulqdq 4y ago
    To be clear, this problem (prime searching) works well on a single compute node. It doesn't work well if you have to scale to many nodes, because communication latency quickly bounds your speed. That's why GIMPS is the way it is: with volunteers offering computers that are separated and do a siloed calculation.
    - dragontamer 4y ago
      I can believe that. But the fact that this was done on a Threadripper 3990x, a high-core count (but slow interconnect / core-to-core communication) kind of computer, makes me believe that there's a degree of parallelism in this problem. Otherwise, another computer (ie: higher GHz / less core count) could have been used instead. --------- I really don't know this specific algorithm: ECPP. It comes down to how that works... especially its parallelization.
      - 4y ago

dspillett 4y ago

> that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months I am assuming that is how the result was verified much faster - >1,000x the computer power used. Without looking deeper (like actually reading the article!) I couldn't say way that would be in this particular case, but such a disparity between power used to make a finding and power used to verify it by repetition is often the case when the initial result is discovered by a recreational researcher or small group, not a better funded group. Not unlike the human scaling seen when one individual or a small group publishes a proof that could be significant, and many others poor over it to see if they can find a flaw before it is generally accepted as a genuine new finding (an order of magnitude or more of human brains to check, than to initially find).

cedilla 4y ago
The results aren't verfied by running the same calculations again. Rather, there's a verification method used along with some information from the original solution - that's the certificate they mention. Imagine factoring a non-prime number. It would take you quite long to factor 695587 with nothing but a cheap calculator, but you could very quickly verify my factorization if I give you the information that it is divisible by 71 and 101.
- dspillett 4y ago
  Though the factor-checking like verification won't work for “this number is prime” the same as it will for “this number is not prime”. A test that results in saying a number is prime doesn't output any factors to test because if such existed the number would not be prime. I'll have to read up on the certification/verification process to comment any further though.
  - cedilla 4y ago
    It does work that way, just not as straightforwardly. See https://en.wikipedia.org/wiki/Certificate_%28complexity%29 https://en.wikipedia.org/wiki/Certificate_%28complexity%29 if you're interested in learning more.

pclmulqdq 4y ago

This problem is also hard to parallelize. There is a lot of reuired communication between computation lanes (sections of the number), and the calculation takes a lot of dependencies on that communication. You could probably design a supercomputer specifically for prime searches, but it would be a weird one.

dragontamer 4y ago
I've calculated ~20kB to store this number in particular. GPU __shared__ memory is 64kB. A 1024-wide workgroup would be able to store 4096 bytes per register, if the whole workgroup was just working on one number. So ~6 registers x 1024 shader workgroup to store the full 20kB number. __shared__ memory would allow for very quick shader-to-shader communications. I think... it can work. But its difficult for me to visualize the full program. Its going to be complex, but probably doable. Its also not really a design pattern that a lot of GPU code (ex: Thrust) works in very well, you'd have to use harder to use libraries like CUB instead.
- pclmulqdq 4y ago
  To be clear, this problem (prime searching) works well on a single compute node. It doesn't work well if you have to scale to many nodes, because communication latency quickly bounds your speed. That's why GIMPS is the way it is: with volunteers offering computers that are separated and do a siloed calculation.
  - dragontamer 4y ago
    I can believe that. But the fact that this was done on a Threadripper 3990x, a high-core count (but slow interconnect / core-to-core communication) kind of computer, makes me believe that there's a degree of parallelism in this problem. Otherwise, another computer (ie: higher GHz / less core count) could have been used instead. --------- I really don't know this specific algorithm: ECPP. It comes down to how that works... especially its parallelization.
    - 4y ago