Prime95 FFT log meaning

[snijele]

Hi,

I am trying to figure out meaning behind some logged parameters behind Prime95 logs while doing LL test. Concrete log line is:

Resuming primality test of M63351487 using FMA3 FFT length 3360K, Pass1=448, Pass2=7680, clm=4, 6 threads

M63351487 is obviously number under test
FMA3 is a CPU instruction set emloyed
FFT is Fast Fourier Transform algorithm

1. What is meaning behind Pass1, Pass2 and clm?
2. What is meaning of FFT length? My understanding of FFT is basic.

[Uncwilly]

The FFT length is the size of the FFT that is used. If an FFT is done that is too close to the size of the number that needs to be tested, then the 'noise' at the end of the calculation can cause problems. But, if one uses an FFT that is too large, then the data take too many cycles to complete. For any given exponent, software, and hardware there will be an ideal FFT size.

[Prime95]

Originally Posted by snijele

1. What is meaning behind Pass1, Pass2 and clm?
2. What is meaning of FFT length? My understanding of FFT is basic.

Welcome to GIMPS!

It is not expected that these values would be meaningful to you. These values let me identify exactly which assembly code is being executed. The FFT is split into two "passes". This is not a requirement of FFTs in general, but for best performance one usually wants to load as much FFT data into the L2 or L3 cache and do as much work as possible, then write it back to memory.

Internally, a number of different pass sizes are available which means there are several different ways to implement an FFT size. For example, a 1M FFT could be 512x2K or 1Kx1K or 2Kx512, etc.

In 25 years, I don't think anyone has asked what clm is. clm is a prime95-internals-only abbreviation for cache-line-multiplier. The assembly code can process 1, 2, or 4 cache lines at a time, which sometimes results in a few percent speed difference on various CPU architectures.

[LaurV]

Thanks for explanation George. I was wondering sometimes too, but never dared to ask... Now you gave enough material to kriesel to write another of his interminable tutorials

[henryzz]

Originally Posted by Prime95

Welcome to GIMPS!

It is not expected that these values would be meaningful to you. These values let me identify exactly which assembly code is being executed. The FFT is split into two "passes". This is not a requirement of FFTs in general, but for best performance one usually wants to load as much FFT data into the L2 or L3 cache and do as much work as possible, then write it back to memory.

Internally, a number of different pass sizes are available which means there are several different ways to implement an FFT size. For example, a 1M FFT could be 512x2K or 1Kx1K or 2Kx512, etc.

In 25 years, I don't think anyone has asked what clm is. clm is a prime95-internals-only abbreviation for cache-line-multiplier. The assembly code can process 1, 2, or 4 cache lines at a time, which sometimes results in a few percent speed difference on various CPU architectures.

I was under the impression that clm stood for something related to propagating carries. Is carry propagation always handled the same by GWNUM? I was under the impression that it can be relaxed if you are not near an FFT boundary.

[Prime95]

Carry propagation is handled the same way for all FFT implementations.

[snijele]

Originally Posted by Uncwilly

The FFT length is the size of the FFT that is used. If an FFT is done that is too close to the size of the number that needs to be tested, then the 'noise' at the end of the calculation can cause problems. But, if one uses an FFT that is too large, then the data take too many cycles to complete. For any given exponent, software, and hardware there will be an ideal FFT size.

Thanks! Guess I need to take a deep dive into FFT to figure it out more.

Originally Posted by Prime95

Welcome to GIMPS!

It is not expected that these values would be meaningful to you. These values let me identify exactly which assembly code is being executed. The FFT is split into two "passes". This is not a requirement of FFTs in general, but for best performance one usually wants to load as much FFT data into the L2 or L3 cache and do as much work as possible, then write it back to memory.

Internally, a number of different pass sizes are available which means there are several different ways to implement an FFT size. For example, a 1M FFT could be 512x2K or 1Kx1K or 2Kx512, etc.

In 25 years, I don't think anyone has asked what clm is. clm is a prime95-internals-only abbreviation for cache-line-multiplier. The assembly code can process 1, 2, or 4 cache lines at a time, which sometimes results in a few percent speed difference on various CPU architectures.

Thanks for welcome and explanation. At the moment I am trying to figure out FFT algorithm, so logical step was to try to understand what Prime95 does and how it does it, since I am software engineer, so looking at source code might bring clarity faster than math equations. :)

I have checked the source code a bit, but with all optimizations and assembly code it is a bit overwhelming to be honest. I'll deep dive into forum and literature for time being, and ask further questions on FFT details in appropriate subforum.

Cheers!

[henryzz]

Originally Posted by snijele

Thanks! Guess I need to take a deep dive into FFT to figure it out more.



Thanks for welcome and explanation. At the moment I am trying to figure out FFT algorithm, so logical step was to try to understand what Prime95 does and how it does it, since I am software engineer, so looking at source code might bring clarity faster than math equations. :)

I have checked the source code a bit, but with all optimizations and assembly code it is a bit overwhelming to be honest. I'll deep dive into forum and literature for time being, and ask further questions on FFT details in appropriate subforum.

Cheers!

You might find https://mersenneforum.org/showthread.php?t=120 useful. I would imagine youtube might be a good place to look as well.