4 ms·

You should probably assume that people using supercomputers have thought about "just using a GPU."

xiphias2 8y ago
Don't assume anything. They are not using GPUs and from the paper it looks like they haven't thought about it. I think a GPU cluster would be a speedup, but big number multiplication is relatively slow on GPUs, so maybe not as big speedup as with other algorithms.
- Jweb_Guru 8y ago
  A GPU cluster, sure. But the discussion was about running the algorithm on a single GPU on your desktop.
  - xiphias2 8y ago
    Sure, you're right I was comparing cost of the 2 systems, with 1 GPU it's an interesting question, but as the author had CPU cluster available, it was the logical choice for him.
dragontamer 8y ago
Why? GPU Programmers cost a lot more than a month-worth of supercomputer time. Its probably cheaper and easier to just port your code to Amazon cloud or Google Cloud for a month, rather than to port your code to a GPU.
- xiphias2 8y ago
  Generally yes, but actually porting this is probably a fun pet project that could be done in a few weeks for fun to find the secret number for 42 :). It's too bad the paper doesn't have a GitHub link.
  - dragontamer 8y ago
    Oh yeah, that's why I'm interested in that algorithm :-) Honestly, the more and more I look into this, it seems like GPUs are the ideal computational platform for this problem. We're talking about a simple equation, with numbers that fit inside the 64-bit integer space (less than 10^19). GPUs can calculate that somewhat easily (The compiler probably turns 64-bit multiplies into 4x32-bit multiplies + adds, but that's still low in memory usage...) I'm not sure if one GPU would be enough to compute everything. But we're talking about 512-cpu cores at 1-month of computing. A GPU probably can solve it within 6 months. I'm talking about replicating the work done on "33" by the way, not on 42. If 10^19 is sufficient for a search space, then 64-bit ints can be used. ------------ It won't be an easy port btw. The three variables are written as x^2 - 2xy + y^2 == (33 - z^3) / d, where d = (x+y). The Numberphile video said that "d" is brute-force searched, because there are very few values of "z" that would satisfy the above formula. So every shader probably can brute-force d on its own in a GPU. Overall, seems pretty efficient to run this on a GPU. Very little memory, everything probably fits in GPU-register space.
    - xiphias2 8y ago
      X^2 doesn't fit in 64 bits, but after a little bit of search I found the __mul64hi PTX instruction that makes it easy :)
    - qlk1123 8y ago
      What you are talking about is to exploit the mass parallelism of GPU, but I suspect that there are huge differences between each of the calculation/evaluation, which is not a good pattern for GPU threads. As GPU threads work together in bundles, or warp, the cost on sync'ing each thread may be high. But still, worth a try if you have one, and don't forget SHOW HN once you have luck ;)
      - dragontamer 8y ago
        > but I suspect that there are huge differences between each of the calculation/evaluation Its a (nearly) linear brute-force search. Every thread is going to run "guess d", and then calculate "(33 - z^3) / d = x^2 -2xy + y^2". All values must be integer, so (33 - z^3) / d must be an integer value. Which means the selected value "d" must be a factor of (33 - z^3). So "z" is going to be a small search space. I would expect that similar "d" values would have similar amounts of "z" values that satisfy this solution, so thread divergence doesn't seem to be a major issue. That's about as uniform as it gets. Its a guess-and-check search, very much akin to cryptocoin mining. It seems like the GPU is the best architecture to the algorithm.

Don't assume anything. They are not using GPUs and from the paper it looks like they haven't thought about it. I think a GPU cluster would be a speedup, but big number multiplication is relatively slow on GPUs, so maybe not as big speedup as with other algorithms.

Jweb_Guru 8y ago
A GPU cluster, sure. But the discussion was about running the algorithm on a single GPU on your desktop.
- xiphias2 8y ago
  Sure, you're right I was comparing cost of the 2 systems, with 1 GPU it's an interesting question, but as the author had CPU cluster available, it was the logical choice for him.

dragontamer 8y ago

Why? GPU Programmers cost a lot more than a month-worth of supercomputer time. Its probably cheaper and easier to just port your code to Amazon cloud or Google Cloud for a month, rather than to port your code to a GPU.

xiphias2 8y ago
Generally yes, but actually porting this is probably a fun pet project that could be done in a few weeks for fun to find the secret number for 42 :). It's too bad the paper doesn't have a GitHub link.
- dragontamer 8y ago
  Oh yeah, that's why I'm interested in that algorithm :-) Honestly, the more and more I look into this, it seems like GPUs are the ideal computational platform for this problem. We're talking about a simple equation, with numbers that fit inside the 64-bit integer space (less than 10^19). GPUs can calculate that somewhat easily (The compiler probably turns 64-bit multiplies into 4x32-bit multiplies + adds, but that's still low in memory usage...) I'm not sure if one GPU would be enough to compute everything. But we're talking about 512-cpu cores at 1-month of computing. A GPU probably can solve it within 6 months. I'm talking about replicating the work done on "33" by the way, not on 42. If 10^19 is sufficient for a search space, then 64-bit ints can be used. ------------ It won't be an easy port btw. The three variables are written as x^2 - 2xy + y^2 == (33 - z^3) / d, where d = (x+y). The Numberphile video said that "d" is brute-force searched, because there are very few values of "z" that would satisfy the above formula. So every shader probably can brute-force d on its own in a GPU. Overall, seems pretty efficient to run this on a GPU. Very little memory, everything probably fits in GPU-register space.
  - xiphias2 8y ago
    X^2 doesn't fit in 64 bits, but after a little bit of search I found the __mul64hi PTX instruction that makes it easy :)
  - qlk1123 8y ago
    What you are talking about is to exploit the mass parallelism of GPU, but I suspect that there are huge differences between each of the calculation/evaluation, which is not a good pattern for GPU threads. As GPU threads work together in bundles, or warp, the cost on sync'ing each thread may be high. But still, worth a try if you have one, and don't forget SHOW HN once you have luck ;)
    - dragontamer 8y ago
      > but I suspect that there are huge differences between each of the calculation/evaluation Its a (nearly) linear brute-force search. Every thread is going to run "guess d", and then calculate "(33 - z^3) / d = x^2 -2xy + y^2". All values must be integer, so (33 - z^3) / d must be an integer value. Which means the selected value "d" must be a factor of (33 - z^3). So "z" is going to be a small search space. I would expect that similar "d" values would have similar amounts of "z" values that satisfy this solution, so thread divergence doesn't seem to be a major issue. That's about as uniform as it gets. Its a guess-and-check search, very much akin to cryptocoin mining. It seems like the GPU is the best architecture to the algorithm.