New LLT program in the pipe..

[kriesel]

Originally Posted by Dr Autonomy

"PRP" stands for "Probable Prime", right?

Will the EFF accept as a "discovery" that some number is "probably prime"?

I believe the answer is no.

You are right that I don't know much about "Multilevel ffts". But they're sequential algorithms, right? Or has someone parallelized them? Dunno.

I just think that in an increasingly parallel-processed world, you have to rethink the sequential algorithms, especially recursive ones, towards a more uniform parallel computational framework. Because Moore's Law is waning, and it's being replaced by parallel processors/processing, and the software has to change to keep up.

...

As for source code, I have no idea what I might do with it. Maybe just bite the bullet, buy the damn supercomputer, and win both remaining EFF awards with it. Except the hardware isn't quite there yet..

Or I might sell it, lock, stock, and barrel. Dunno.

Or I might publish.

Hard to say.

Probably prime. (Like you probably had a mother; extremely likely, but not proven beyond a mathematician's doubt.) Or definitely, beyond a doubt, composite, which is the case for Mersennes in about 999,999 prime exponents out of a million. And the more likely low exponents have all already been repeatedly tested, so the odds going forward are significantly lower than 1 ppm. And PRP testing with guarding against computational errors is over twice as fast as LL testing with guarding against computational errors. Speed matters when weeding through haystacks for a single needle. https://www.mersenneforum.org/showpo...06&postcount=9
Before a new prime find is accepted as real, not just an error, it is checked by running multiple software on multiple hardware types by multiple people. That's the time for LL testing. Credit for the discovery, and prize award, goes to the first person to complete a PRP or LL on the candidate and generate and report the PRP-P or LL-P result. After verification. https://www.mersenneforum.org/showpo...5&postcount=14

Re multilevel ffts, & has someone parallelized them: I gave you three software examples already. They've been parallelized for years or decades.
Selling your source code that's now documented as ~1000 times too slow to use for DC, and will be relatively slower yet at higher exponents than the current DC level? Too funny. Don't blame the hardware for how slow your software is. Do better. You've already been given the map.

What reference works have you read on parallel programming?

[chalsall]

Originally Posted by kriesel

What reference works have you read on parallel programming?

If I may please give some feedback, while I get the shit kicked out of me for making a mistake.

Sometimes less is more.

Know. Stand. Trust.

[Prime95]

Originally Posted by Dr Autonomy

"PRP" stands for "Probable Prime", right?
Will the EFF accept as a "discovery" that some number is "probably prime"?

Yes, PRP = probable. If successful, several independent LL tests will also be run.
If your program concludes "prime", the EFF will also require you to gather several independent LL tests.

You are right that I don't know much about "Multilevel ffts". But they're sequential algorithms, right? Or has someone parallelized them? Dunno.

FFTs can be parallelized to a modest degree.

I just think that in an increasingly parallel-processed world, you have to rethink the sequential algorithms

Researchers are always looking for ways to improve FFTs, multiplication, and prime proving. Breakthroughs are rare.

Note that LL (and PRP) tests are sequential in that each iteration requires the result of the previous iteration.

...I'd have to suffer another four pages of accusations and name-calling. Nah. Pass.

As for source code, I have no idea what I might do with it. Maybe just bite the bullet, buy the damn supercomputer, and win both remaining EFF awards with it.

My apologies for the rather brutal reception you received. Folks here can be way too critical. BTW, Welcome to the forum!

View this entire episode as a learning experience. You probably learned a bit writing your program. If I may, I'd recommend two more possible "lessons learned":

1) Do more research into the state-of-the-art before diving into a major project. If you had done so, you would have learned how currently available programs tackle the problem and realized that significantly improving on them is a tall order.

2) Learn how to do back-of-the-envelope calculations regarding the difficulty of a task. By doing so you'd realize that achieving the next EFF goal would require large investments of time and GREAT luck. Furthermore, you'll spend more in electricity and hardware than the value of the EFF award. Achieving the billion digit EFF goal is not possible at this time.

Originally Posted by kriesel

Like you probably had a mother

What an odd analogy.

[S485122]

Originally Posted by Dr Autonomy

...
I just think that in an increasingly parallel-processed world, you have to rethink the sequential algorithms, especially recursive ones, towards a more uniform parallel computational framework. Because Moore's Law is waning, and it's being replaced by parallel processors/processing, and the software has to change to keep up.
...

Existing programs are already using multiple cores or even threads. If my interpretation of the "whatsnew.txt" file is correct Prime95/mprime has been "parallelised" or multithreaded since version 25.5 in 2007.

The cool reception you got was because you asked the forum members to run a program but "refused" to give results from that program run on your own machine. You could have compared the speed of your program with Prime95 on your own machine...

[Dr Autonomy]

Originally Posted by Prime95

FFTs can be parallelized to a modest degree.

Thanks for your honesty on that score. I would definitely agree with your use of the word "modest" here.

Originally Posted by Prime95

Note that LL (and PRP) tests are sequential in that each iteration requires the result of the previous iteration.

Really?

Originally Posted by Prime95

BTW, Welcome to the forum!

Thanks.

Originally Posted by Prime95

Learn how to do back-of-the-envelope calculations regarding the difficulty of a task

Okay, so let's do that.

I just found out that the "socket" that houses all Threadripper CPUs, including the 64-core incarnation, has a published average DRAM access rate of 102.4 GB/s, implemented by four 72-bit DRAM channels (eight total, four disabled, apparently by design), which translates to 15,728.64 qwords per microsecond. Since GP_LLT requires approximately 274,945,015,808 qword transfers per iteration for a billion decimal digit prime candidate, that works out to approx. 8.74 seconds per iteration on a system with two 64-core Threadripper CPUs. That's approximately 3,672.38 times slower than it needs to be to finish the BDD LLT in three months.

Somewhat disappointing to be sure, but that's today. Tomorrow may yet hold better prospects.

[preda]

Originally Posted by Dr Autonomy

Okay, so let's do that.

I just found out that the "socket" that houses all Threadripper CPUs, including the 64-core incarnation, has a published average DRAM access rate of 102.4 GB/s, implemented by four 72-bit DRAM channels (eight total, four disabled, apparently by design), which translates to 15,728.64 qwords per microsecond. Since GP_LLT requires approximately 274,945,015,808 qword transfers per iteration for a billion decimal digit prime candidate, that works out to approx. 8.74 seconds per iteration on a system with two 64-core Threadripper CPUs. That's approximately 3,672.38 times slower than it needs to be to finish the BDD LLT in three months.

Somewhat disappointing to be sure, but that's today. Tomorrow may yet hold better prospects.

You left the "back of the envelope" unfinished. Does it work out to about 1000 years for one test?

[kriesel]

Originally Posted by Dr Autonomy

Really?

I just found out that the "socket" that houses all Threadripper CPUs, including the 64-core incarnation, has a published average DRAM access rate of 102.4 GB/s, implemented by four 72-bit DRAM channels (eight total, four disabled, apparently by design), which translates to 15,728.64 qwords per microsecond. Since GP_LLT requires approximately 274,945,015,808 qword transfers per iteration for a billion decimal digit prime candidate, that works out to approx. 8.74 seconds per iteration on a system with two 64-core Threadripper CPUs. That's approximately 3,672.38 times slower than it needs to be to finish the BDD LLT in three months.

1) yes really, in practical terms. (Or was that supposed to be a joke?) Per https://en.wikipedia.org/wiki/Lucas%...primality_test the first terms of the sequence are known for sufficiently large p and do not depend on the exponent, but after the mod Mp begins having effect on the full residue, they are almost always dependent on both the exponent and the previous iteration's value. ANY error anywhere in the sequence propagates through following iterations, which means the rest of the sequence is wrong, so the final result of the test is wrong. (Why PRP is the way to go: GEC reliably detects errors, and is not applicable to LL. Known rror checks applicable to LL are less effective at detecting errors.)
One could consider skipping the first few iterations by storing one that is still compact enough to be fast to retrieve, say S4 instead of beginning with S0, but that is approximately a 1-100ppb savings in practice. (I see prime95's first few iterations run faster than the full-Mp-width later iterations, so may be even less potential savings.) Up to the first ~25-30 iterations are unaffected by mod Mp. Reading them from storage is likely to be slower and error prone than generating in place.

Something to consider is whether it pays to switch to higher than res64 at some point. The number of res64 bits that differ from the error-produced res64 0x02 (cudalucas is notorious for that) is limited, at p~1G, and somewhat higher, vanishes. Following are low-128-bit and low-64-bit residues by LL seed 4 iteration number for M999999937.

Perlll6.pl v 0.10 Jan 11 2023		(C) 2019-2023 Kriesel
LL seed 4

begin p=999999937
iter 1  x 0x0000000000000000000000000000000e 0x000000000000000e
iter 2  x 0x000000000000000000000000000000c2 0x00000000000000c2
iter 3  x 0x00000000000000000000000000009302 0x0000000000009302
iter 4  x 0x000000000000000000000000546b4c02 0x00000000546b4c02
iter 5  x 0x00000000000000001bd696d9f03d3002 0x1bd696d9f03d3002
iter 6  x 0x0306f7b285eead7d8cc88407a9f4c002 0x8cc88407a9f4c002
iter 7  x 0xef7e6a06ce335de155599f9d37d30002 0x55599f9d37d30002
iter 8  x 0xf850ea776d9b1220f460d65ddf4c0002 0xf460d65ddf4c0002
iter 9  x 0x8f625008a4fdb542e180d8077d300002 0xe180d8077d300002
iter 10  x 0xe649e87ae88f08849bdb491df4c00002 0x9bdb491df4c00002
iter 11  x 0xa8d39cfc7cbf7ba94cebb477d3000002 0x4cebb477d3000002
iter 12  x 0x903f8514817c09730b97d1df4c000002 0x0b97d1df4c000002
iter 13  x 0x93965c5abff22aa9acef477d30000002 0xacef477d30000002
iter 14  x 0x50dc102b27fef87e9cbd1df4c0000002 0x9cbd1df4c0000002
iter 15  x 0xdbc7f9d128e0bf7902f477d300000002 0x02f477d300000002
iter 16  x 0xa64ec20e91d0d5cd0bd1df4c00000002 0x0bd1df4c00000002
iter 17  x 0xb8fad5312c20d5c42f477d3000000002 0x2f477d3000000002
iter 18  x 0x14703a32fe5b4010bd1df4c000000002 0xbd1df4c000000002
iter 19  x 0x7c14bfb0d6eb9042f477d30000000002 0xf477d30000000002
iter 20  x 0x16f06d113397410bd1df4c0000000002 0xd1df4c0000000002
iter 21  x 0x1d9899224ced042f477d300000000002 0x477d300000000002
iter 22  x 0x93d0b2611cb410bd1df4c00000000002 0x1df4c00000000002
iter 23  x 0x2627a70302d042f477d3000000000002 0x77d3000000000002
iter 24  x 0x06ec73f50b410bd1df4c000000000002 0xdf4c000000000002
iter 25  x 0x008f4e642d042f477d30000000000002 0x7d30000000000002
iter 26  x 0x50152290b410bd1df4c0000000000002 0xf4c0000000000002
iter 27  x 0x1dd31a42d042f477d300000000000002 0xd300000000000002
iter 28  x 0x4f35690b410bd1df4c00000000000002 0x4c00000000000002
iter 29  x 0x0d6c8599332f8b2e266149b63b09f206 0x266149b63b09f206
iter 30  x 0xe2fb7a34e167f4fe3f6b4dc8516d2516 0x3f6b4dc8516d2516
iter 31  x 0xaa4dc1ae5a118ae3517e288a43427713 0x517e288a43427713
iter 32  x 0x364993ae63255462369430ee8cf115ac 0x369430ee8cf115ac

Something similar happens in PRP. From prime95 v30.8b15 (which incurs considerable overhead in generating res64 ASCII output each iteration, so these iteration timings are not representative of what it can do in normal production running on this i5-1035G1):

Jan 12 19:09:10] Worker starting
[Jan 12 19:09:10] Setting affinity to run worker on CPU core #1
[Jan 12 19:09:13] Setting affinity to run helper thread 1 on CPU core #2
[Jan 12 19:09:13] Setting affinity to run helper thread 2 on CPU core #3
[Jan 12 19:09:13] Setting affinity to run helper thread 3 on CPU core #4
[Jan 12 19:09:15] Starting Gerbicz error-checking PRP test of M1168999969 using AVX-512 FFT length 64M, Pass1=2K, Pass2=32K, clm=1, 4 threads
[Jan 12 19:09:15] Preallocating disk space for the proof interim residues file p1168999969.residues
[Jan 12 19:39:34] Error pre-allocating proof interim residues file
[Jan 12 19:39:35] Errno: 28, No space left on device
[Jan 12 19:39:35] DOSerrno: 112
[Jan 12 19:39:35] Will use proof power 8 instead of 10.
[Jan 12 19:39:35] PRP proof using power=8 and 64-bit hash size.
[Jan 12 19:39:35] Proof requires 37.4GB of temporary disk space and uploading a 1315MB proof file.
[Jan 12 19:40:39] M1168999969 interim PRP residue 000000000000001B at iteration 1
[Jan 12 19:40:50] M1168999969 interim PRP residue 000000000000088B at iteration 2
[Jan 12 19:41:00] M1168999969 interim PRP residue 0000000000DAF26B at iteration 3
[Jan 12 19:41:07] M1168999969 interim PRP residue 000231C54B5F6A2B at iteration 4
[Jan 12 19:41:13] M1168999969 interim PRP residue D310B7D97DD4E9AB at iteration 5
[Jan 12 19:41:19] M1168999969 interim PRP residue 2AC0B180838228AB at iteration 6
[Jan 12 19:41:25] M1168999969 interim PRP residue 9B5ACA650265A6AB at iteration 7
[Jan 12 19:41:33] M1168999969 interim PRP residue B47759B0D250A2AB at iteration 8
[Jan 12 19:41:41] M1168999969 interim PRP residue DF36E033DAB69AAB at iteration 9
[Jan 12 19:41:50] M1168999969 interim PRP residue C94525688DC28AAB at iteration 10
[Jan 12 19:42:00] M1168999969 interim PRP residue FC7BEC947CDA6AAB at iteration 11
[Jan 12 19:42:12] M1168999969 interim PRP residue 6346CE367F0A2AAB at iteration 12
[Jan 12 19:42:23] M1168999969 interim PRP residue 628CE0A31369AAAB at iteration 13
[Jan 12 19:42:37] M1168999969 interim PRP residue B332521E7C28AAAB at iteration 14
[Jan 12 19:42:52] M1168999969 interim PRP residue 8FA2E79E4DA6AAAB at iteration 15
[Jan 12 19:43:08] M1168999969 interim PRP residue 4B1EDCC1F0A2AAAB at iteration 16
[Jan 12 19:43:24] M1168999969 interim PRP residue 7CA1EF99369AAAAB at iteration 17
[Jan 12 19:43:42] M1168999969 interim PRP residue 4AD4B787C28AAAAB at iteration 18
[Jan 12 19:44:03] M1168999969 interim PRP residue 9BECD064DA6AAAAB at iteration 19
[Jan 12 19:44:26] M1168999969 interim PRP residue 50E7261F0A2AAAAB at iteration 20
[Jan 12 19:44:53] M1168999969 interim PRP residue 0604619369AAAAAB at iteration 21
[Jan 12 19:45:21] M1168999969 interim PRP residue 9CE1187C28AAAAAB at iteration 22
[Jan 12 19:45:52] M1168999969 interim PRP residue 7D23864DA6AAAAAB at iteration 23
[Jan 12 19:46:25] M1168999969 interim PRP residue 07CC61F0A2AAAAAB at iteration 24
[Jan 12 19:47:00] M1168999969 interim PRP residue 45AE19369AAAAAAB at iteration 25
[Jan 12 19:47:39] M1168999969 interim PRP residue 63B187C28AAAAAAB at iteration 26
[Jan 12 19:48:27] M1168999969 interim PRP residue 28B864DA6AAAAAAB at iteration 27
[Jan 12 19:49:38] M1168999969 interim PRP residue D6C61F0A2AAAAAAB at iteration 28
[Jan 12 19:50:59] M1168999969 interim PRP residue 816D7BEF30D75130 at iteration 29
[Jan 12 19:52:10] M1168999969 interim PRP residue 275063E494808E2A at iteration 30
[Jan 12 19:53:21] M1168999969 interim PRP residue A950797E4050E41B at iteration 31
[Jan 12 19:54:37] M1168999969 interim PRP residue FFB5800303D3F3A4 at iteration 32

See also https://www.mersenneforum.org/showpo...97&postcount=6
https://www.mersenneforum.org/showpo...72&postcount=9

2) I'm not following your data rate math there.
102.4 GB/s * 1qword/8B = 12.8E9 qword/sec; / (1E6 microsec/second) = 12.8E3 qword/microsec = 12800. qword/microsec.
Also, that's probably a marketing figure, not achievable in real useful software.

Even if it meant GiB/sec, that's a factor of 1.024^3, 12800 * 1.07374... ~13744 qword/microsec.
A link for specifications source would be useful.

Mainly though any code for such large undertakings must be much more efficient in read/write from main ram, mainly using cache well, and George already wrote about what is feasible.

[Dr Autonomy]

I'm not following your data rate math there.

You are quite right. Must have been having a bad day. Don't know what I was thinking.

102.4 GB/s = 12,800 qwords per microsecond.

therefore 274,945,015,808 qword transfers takes 10.74 seconds on a dual 64-core CPU system, 4,512.61 times slower than it needs to be.

So basically, three and a half orders of magnitude. That would be achievable if every die (or better yet, every core) had its own bus, but that could never happen, right? Just thinking out loud..

Oh, the link, right: Wikichip sTRX4

Also, that's probably a marketing figure, not achievable in real useful software.

Right again. I can't find the link right now, but one extensive test I read about showed very average mem access speed for a dual Threadripper system. Disappointing.

As for PRP, I looked at the math. It's above my pay grade. Might as well try to convince me to pursue a metric tensor simulation. "A man's got to know his limitations" - Clint Eastwood..

P.S. (an hour after the OP; sorry): I believe ECC is sufficient for ensuring the accuracy of the LLT, and CRC32 sufficient for ensuring file integrity.

[slandrum]

Originally Posted by Dr Autonomy

I believe ECC is sufficient for ensuring the accuracy of the LLT...

And you'd be wrong. ECC won't ensure the integrity of the LLT - it will just make it much more likely that the result is not corrupted due to a memory error, but definitely won't guard against program bugs or any of a number of other things that can go wrong in the hardware during the computation.

[retina]

Originally Posted by Dr Autonomy

I believe ECC is sufficient for ensuring the accuracy of the LLT, ...

I believe it is necessary, but not sufficient.

Originally Posted by Dr Autonomy

... and CRC32 sufficient for ensuring file integrity.

For protection from non-malicious changes CRC32 might be fine, but for large inputs I'd much prefer MD5.

For protection from malicious changes SHA3 is likely a far better choice. But be mindful of how you handle the hash, that can also suffer damage and/or be altered. It's tricky.

However none of that is important because there is already a robust system in place for this stuff, known as the Gerbicz error check, that is used for the PRP runs. Unless there is something better to improve on that, then things like CRC and SHA are not needed. But ECC is still necessary IMO.

[kriesel]

Insisting on staying with LL for production testing will prevent acceptance of the program by end users.
Moot while it is orders of magnitude too slow. Fix the design, algorithmic and implementation related speed issues, and all-LL/no-PRP is still a showstopper for many. Staying with LL only, no PRP, locks in a factor of more than two computing cost disadvantage, for verified result, inherently, as a number theoretic bound on run time. A factor of two speed disadvantage is enough to deter widespread usage. (Gpuowl replaced cllucas on AMD GPUs while still LL based, before the GEC was posted by R. Gerbicz.) At the GIMPS project level, LL first testing is deprecated, and LL DC is discouraged too; PRP with proof generation is faster and more reliable, given observed error rate of the best available code on the actual hardware fleet. Without a strong error detection method capable of >99% error detection rate on the fly during the test, LL is essentially wasted cycles in practice in production testing. No such high error detection rate check is known for the LL sequence.

That said, a great deal of programming related to improving performance of GP_LLT applies to either LL or PRP. Both need fast squaring, and a variety of fft lengths to do it.

A possible niche for LL-only GP_LLT is for new-prime verification only, not discovery, where computation rate disadvantage of two or slightly more could be tolerated.

Another small niche is for users who are irrational, preferring the LL theoretically definitive test that is only of order 98% reliable, over the PRP test that is essentially 100% reliable, and despite PRP offering several orders of magnitude faster verification. (Yes, literally, hundreds or thousands of times faster; optimal proof power 9 or 10 or 11, equate to ~512 or 1024 or 2048 times verification speed advantage, even assuming LL would only ever require a single retest.)

If GP_LLT were made equally as fast per test as prime95 PRP or LL, I would stay with prime95 PRP on CPU, including on the ECC-equipped systems, because of the >2:1 advantage per exponent completed for the project, due to PRP proof generation and verification at low cost relative to full retest and superior error detection rate. (Automatic work flow via PrimeNet API is a convenience, not a decisive requirement, although it might be required for such as curtisc.) Also I run PRP first tests on GPU with gpuowl, because of overall speed and far superior reliability. Haven't run CUDALucas in production for years. To displace prime95 or gpuowl, an LL-only program would need to be more than twice as fast per completed primality test as the PRP&proof capable program it competes with.