4 ms·

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,

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.
- qlk1123 8y ago
  What about the RHS of the equation? x^2-xy+y^2 are three big-number multiplications and two big-number adds, where digit number do matters.
  - dragontamer 8y ago
    Not as "big number" as you might think. The x, y, and z terms were: (8,866,128,975,287,528)³ + (–8,778,405,442,862,239)³ + (–2,736,111,468,807,040)³ = 33. The biggest number will fit inside of 53 bits, 54 if you include the sign bit. Which means all of the values fit inside of 64-bits (including the sign bit). The cubes will fit within 192-bits. If this truly were a "big number" problem, then brute-force wouldn't be a valid methodology!
    - qlk1123 8y ago
      I got your point. It seems that we are just not on the same page. As the product of any cube can turn out to be 192-bit, it should be impossible to fit into a GPU instruction or even a single CUDA C statement. That's why I call it big-number calculation: manual carry/overflow handling, larger-than-register size operands, tedious indexing/bug prone if coding from scratch, ... but of course you can still argue that it is not "big." Or maybe now GPGPUs have big integer support? The last time I did actual GPU computing was CUDA 7 I guess, using cublas in daily basis so never ever been familiar with integer computation in GPU.
      - dragontamer 8y ago
        > That's why I call it big-number calculation: manual carry/overflow handling, larger-than-register size operands, tedious indexing/bug prone if coding from scratch, ... but of course you can still argue that it is not "big." Its not a general big-integer implementation which can be arbitrarily sized. Since you know all results fit inside of 192 bits, and that all operands are less than 64-bits, you can easily code for this special case. 192-bit x 64-bit is way easier to debug and test than 192-bit x 192-bit. Its probably the bulk of your work, but I don't foresee any major complication here. Its just grade-school arithmetic. struct cube{ long long val[3]; } cube multiply(cube x, long long y){ cube toReturn; toReturn.val[0] = x.val[0] * y; toReturn.val[1] = x.val[1] * y + __umul64hi(x.val[0] * y); toReturn.val[2] = x.val[2] * y + __umul64hi(x.val[1] * y); return toReturn; } This is grade-school arithmetic level. This isn't very difficult at all. The only thing you needed to know is that CUDA has an intrinsic to take the top 64-bits of a 128-bit multiplication. Without any if-statements, the GPU can calculate the above across different threads without any divergence. You can likely optimize this further with MAD instructions, but the above would be a good "first step" towards this problem. As I said earlier: this wouldn't be an "easy" port, but it would be possible, and it would likely be very efficient. I'm not going to think through all the edge cases, but the bulk of the algorithm seems very easy to do efficiently on the GPU architecture to me.
        dragontamer 8y ago

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.

qlk1123 8y ago
What about the RHS of the equation? x^2-xy+y^2 are three big-number multiplications and two big-number adds, where digit number do matters.
- dragontamer 8y ago
  Not as "big number" as you might think. The x, y, and z terms were: (8,866,128,975,287,528)³ + (–8,778,405,442,862,239)³ + (–2,736,111,468,807,040)³ = 33. The biggest number will fit inside of 53 bits, 54 if you include the sign bit. Which means all of the values fit inside of 64-bits (including the sign bit). The cubes will fit within 192-bits. If this truly were a "big number" problem, then brute-force wouldn't be a valid methodology!
  - qlk1123 8y ago
    I got your point. It seems that we are just not on the same page. As the product of any cube can turn out to be 192-bit, it should be impossible to fit into a GPU instruction or even a single CUDA C statement. That's why I call it big-number calculation: manual carry/overflow handling, larger-than-register size operands, tedious indexing/bug prone if coding from scratch, ... but of course you can still argue that it is not "big." Or maybe now GPGPUs have big integer support? The last time I did actual GPU computing was CUDA 7 I guess, using cublas in daily basis so never ever been familiar with integer computation in GPU.
    - dragontamer 8y ago
      > That's why I call it big-number calculation: manual carry/overflow handling, larger-than-register size operands, tedious indexing/bug prone if coding from scratch, ... but of course you can still argue that it is not "big." Its not a general big-integer implementation which can be arbitrarily sized. Since you know all results fit inside of 192 bits, and that all operands are less than 64-bits, you can easily code for this special case. 192-bit x 64-bit is way easier to debug and test than 192-bit x 192-bit. Its probably the bulk of your work, but I don't foresee any major complication here. Its just grade-school arithmetic. struct cube{ long long val[3]; } cube multiply(cube x, long long y){ cube toReturn; toReturn.val[0] = x.val[0] * y; toReturn.val[1] = x.val[1] * y + __umul64hi(x.val[0] * y); toReturn.val[2] = x.val[2] * y + __umul64hi(x.val[1] * y); return toReturn; } This is grade-school arithmetic level. This isn't very difficult at all. The only thing you needed to know is that CUDA has an intrinsic to take the top 64-bits of a 128-bit multiplication. Without any if-statements, the GPU can calculate the above across different threads without any divergence. You can likely optimize this further with MAD instructions, but the above would be a good "first step" towards this problem. As I said earlier: this wouldn't be an "easy" port, but it would be possible, and it would likely be very efficient. I'm not going to think through all the edge cases, but the bulk of the algorithm seems very easy to do efficiently on the GPU architecture to me.
      - dragontamer 8y ago