Thread: Prime95 sorcery
View Single Post
Old 2022-05-28, 17:00   #6
May 2022

3 Posts

Originally Posted by kriesel View Post
Welcome to the forum. You may find for other purposes some of the reference info collection useful.

Ernst Mayer wrote Mlucas, and a good article on FFT based multiplication, worth a read.

A few comments on your post:
The FFT length of 2M is not adequate for 127M operands. Because of the need for handling a lot of carries, the usable bit width per word is ~17-20 bits out of the 53 significant bits (mantissa, including the implied leading 1 bit) in a double precision floating point word, not 64 bits. (See binary64 of IEEE754) That applies in general; not only to prime95 and Mlucas, but also GPU applications gpuowl, cudalucas, etc. Bits/word slowly declines as fft length or exponent increase. 2M fft size is good to about 40M exponent; 127M requires ~6.5M fft length.

Well written code is often memory bandwidth bound, and so may use what appears to be less than optimal code sequences to reduce memory bandwidth demands. Use of compound instructions such as FMA3 is common.
Cache effectiveness has a big impact on memory bandwidth requirements.
Benchmarking is done on multiple FFT forms to determine which is best for given hardware, operand, prime95 configuration (# of cores/worker & other variables).
One of the benefits of the IBDWT is unlike traditional FFT, there is no need for zero-padding, reducing fft length by a factor of two compared to what would otherwise be required.
The -2 of an LL test iteration, and the modulo 2p-1 come almost for free, being performed as part of the single pass per iteration for limited-range carry propagation IIRC.

George has put a lot of time and talent into improving Prime95's performance, for over a quarter century, including a lot of CPU-model-specific optimizations. It outperforms general purpose code like Mathematica considerably. The source code is available to browse.
Thanks, those references look very interesting especially the Mlucas article which I am going through.
As both yourself and @axn pointed out even though the word size is required to be smaller, the advances in processor architecture likely account for this and the discrepancy which I had naively calculated.
jtravers is offline   Reply With Quote