mfaktc: a CUDA program for Mersenne prefactoring

[Prime95]

Originally Posted by Christenson

Looked at it -- don't understand the theory very well.

Originally Posted by Christenson

Next dumb question: Is it worth downloading the mprime source and working on automating the assignment process?

Not to be rude, but why would you start coding a solution when you admittedly do not understand the problem?

ECM and P-1 get slower as Mersenne numbers get larger. This is because FFTs are required to do multiplications. TF to specified bit level actually gets faster as numbers get larger (fewer candidates to test). The crossover point where it makes sense to switch from TF to P-1/ECM would be difficult to calculate and dependent on your particular hardware.

My gut feel is that TF below M1000000 is a complete waste of time (you will find few or no factors) and TF below M5000000 is also a waste in that you'd find a lot more factors in the same amount of time with ECM than you would with TF.

[xilman]

Originally Posted by Prime95

Not to be rude, but why would you start coding a solution when you admittedly do not understand the problem?

To be fair, there are reasons which make some sort of sense. One is as an exercise in reading, understanding and extending another's code. In my opinion, the much the same exercise could be applied elsewhere to a program that may subsequently be more useful in practice.

Confession: many years ago I coded Fermat's factoring algorithm (in Algol60 no less) and tried to factor 10^41-1. At that time I had rather little knowledge of the field and was unaware of any significantly better algorithms for finding large prime factors. This was long before the availability of email, let alone Google, and so it was markedly harder to find out what was going on outside ones own speciality. I was then a first-year undergraduate chemist with only an amateur's interest in computational number theory. I did not, of course, factor 10,41- but I did learn quite a lot about efficient implementation of multiprecision arithmetic and optimization of code.


Paul

[Christenson]

Originally Posted by Prime95

Not to be rude, but why would you start coding a solution when you admittedly do not understand the problem?

It is also true that there is a recent, significant reduction in the cost (10-100x) of TF, due to mfaktc running CUDA. This implies that there may be some places where TF makes sense where it formerly did not. We already routinely do an extra bit or two with our TF. This large reduction in cost is the source of my casting about.

But you are right about my not having a deep understanding of when it is best to TF, P-1, ECM, or LL, which is why I was asking for more information. However, the web server behind the publised web interface at www.mersenne.org presumably embodies that understanding, and I didn't think copying over the code from Prime95/mprime that automates talking to the web server (getting assignments and reporting results) would be that difficult, and I do think it might be useful.

I have zero intention of messing with the TF code proper at the moment, though i have made some suggestions concerning buffering the stream of TFs to allow the CPU half of the system to be better shared, noting that at least my machine has lots more buffer memory available (900Meg) on both the CPU and GPU sides, and one of our members has implied that he/she wants to create the stream of TF numbers on the GPU proper and is prepared to program it.

Additionally, we've already bumped into limits on the www.mersenne.org server due to the large volume of TF getting done -- that 4096 byte limit on the result posts.

[James Heinrich]

Originally Posted by Christenson

that 4096 byte limit on the result posts.

Which, as I said elsewhere before, should be trivial to fix by simply changing the form method from "get" to "post". Depending on how the server code is written, the other changes needed could range between "nothing" and "very simple".

[S34960zz]

Originally Posted by Christenson

Additionally, we've already bumped into limits on the www.mersenne.org server due to the large volume of TF getting done -- that 4096 byte limit on the result posts.

Of course, you can also directly upload the entire results.txt file, instead of cut/paste into the browser 4k-limit window. The direct file upload can handle a far larger chunk of information (though TheJudger did generate even a results.txt file that caused problems not too long ago).

Possibly (wild guess) the ~4k limit is because the text pasted into the window gets passed back to the server as an URL (look in the address line immediately after submitting). Not sure what would have been the limitation for handling TheJudger's results.txt file.

[Christenson]

Originally Posted by Christenson

Next dumb question: Is it worth downloading the mprime source and working on automating the assignment process, fetching TF work from GIMPS?

That is, the mprime source probably has the automatic part of getting assignments and reporting them down nicely, so an intelligent copy of that part over to mfaktc seems to me to be reasonable and worthwhile. I was wondering if that would be duplicating anyone's effort?

[nucleon]

I'd rather the manual submissions code doesn't change. :)

I can submit automatically now with a bash script invoking lynx. I have 10x instances of mfaktc across 4 machines. I'd hate to go back to manual submissions on those.

I found that the file submissions broke at around 500lines. It takes time to process every line, and if it takes too long watchdog processes kick in and shutdown the submissions process. (well that's my understanding)

-- Craig

[Prime95]

Originally Posted by Christenson

That is, the mprime source probably has the automatic part of getting assignments and reporting them down nicely, so an intelligent copy of that part over to mfaktc seems to me to be reasonable and worthwhile. I was wondering if that would be duplicating anyone's effort?

It would be great to add getting assignments and reporting results to mfaktc. The code you want is in primenet.c and primenet.h. The client-server protocol is documented somewhere in the left-side menus at mersenne.org.

The manual results submission is restricted to 4KB and/or 3 minutes to avoid inadvertent or malicious submissions from burying the server in work.

If you do this, the server will give you TF assignments and expect you to complete one bit level. Automatically bump this up several bit levels or to
a pre-determined bit level based on the exponent size so that the work units last a reasonable amount of time.

[Christenson]

Originally Posted by nucleon

I'd rather the manual submissions code doesn't change. :)

I can submit automatically now with a bash script invoking lynx. I have 10x instances of mfaktc across 4 machines. I'd hate to go back to manual submissions on those.

I found that the file submissions broke at around 500lines. It takes time to process every line, and if it takes too long watchdog processes kick in and shutdown the submissions process. (well that's my understanding)

-- Craig

No problem. I'm not proposing that manual assignments be dropped or changed; there are too many advantages to having them available, including it being an important simplification when new methods are being developed.

I'm more into the idea that we have a standard, automatic web interface for internet-connected machines, and not everyone writes bash scripts the way you can, or even has bash available! (Yes, I can run mingwin, but that's beyond the willingness of many). Although, getting my card up under xubuntu wasn't what I'd call trivial, but this is not the place to scratch that particular itch.

[Christenson]

Originally Posted by Prime95

It would be great to add getting assignments and reporting results to mfaktc. The code you want is in primenet.c and primenet.h. The client-server protocol is documented somewhere in the left-side menus at mersenne.org.

The manual results submission is restricted to 4KB and/or 3 minutes to avoid inadvertent or malicious submissions from burying the server in work.

If you do this, the server will give you TF assignments and expect you to complete one bit level. Automatically bump this up several bit levels or to
a pre-determined bit level based on the exponent size so that the work units last a reasonable amount of time.

What's your idea of a minimum reasonable amount of time for a work unit? 30 minutes? Judger, would it be OK if we simply kept increasing the bit level until that 30 minute threshold had been crossed?

[nucleon]

Increasing bit levels client side has it's disadvantages.

It's ok, as long as you submit results for the increased bit levels in 'one-hit'. If you get allocated say P,70,71, and extend that to P,70,77; if you submit the result for 70,71 as soon as completed, then someone could get allocated P,71,72 which means 2x people working on the same task.



-- Craig