5 ms·
The paper ends with "The total computation used approximately 23 core-years over one month of real time.", so yes, I think running this on your 8-core desktop i
by ConceptJunkie 8y ago
The paper ends with "The total computation used approximately 23 core-years over one month of real time.", so yes, I think running this on your 8-core desktop is not going to cut it.
- Rychard 8y ago1 core year = 12 core months 23 core years = 276 core months So, 276 cores running for one month? Is this right?
- dragontamer 8y agoBut what about a $400 GPU with 4096 shaders? I haven't looked at the algorithm, but a linear search probably can be GPGPU computed in parallel. A Vega64 is around $400 and runs 16384 threads on 4096 physical shaders at roughly 1.2GHz. The main issue is if whatever data-structures used for this search will actually fit inside the microscopic amount of memory that is available to each shader.
- ars 8y ago> I haven't looked at the algorithm You can see it here: https://youtu.be/ASoz_NuIvP0?t=393 https://youtu.be/ASoz_NuIvP0?t=393 Rewind a couple of minutes if you want the explanation.
- dragontamer 8y agoThat's actually really simple and clever. That definitely makes the search space much smaller and brute-force is now possible.
- Jweb_Guru 8y agoYou should probably assume that people using supercomputers have thought about "just using a GPU."
- xiphias2 8y agoDon'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 agoA GPU cluster, sure. But the discussion was about running the algorithm on a single GPU on your desktop.
- xiphias2 8y agoSure, 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 agoWhy? 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 agoGenerally 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 agoOh 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.