PrimeGrid
Please visit donation page to help the project cover running costs for this month

Advanced search

Message boards : Number crunching : Calculating FFT length

Author Message
Werinbert
Send message
Joined: 9 Jun 13
Posts: 159
ID: 233452
Credit: 354,681,391
RAC: 125,510
321 LLR Amethyst: Earned 1,000,000 credits (1,005,580)Cullen LLR Amethyst: Earned 1,000,000 credits (1,017,956)ESP LLR Gold: Earned 500,000 credits (671,131)Generalized Cullen/Woodall LLR Gold: Earned 500,000 credits (521,209)PPS LLR Jade: Earned 10,000,000 credits (10,000,222)PSP LLR Gold: Earned 500,000 credits (566,492)SoB LLR Gold: Earned 500,000 credits (597,244)SR5 LLR Amethyst: Earned 1,000,000 credits (1,000,484)SGS LLR Amethyst: Earned 1,000,000 credits (1,070,960)TRP LLR Amethyst: Earned 1,000,000 credits (1,004,720)Woodall LLR Gold: Earned 500,000 credits (615,831)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,014,922)Generalized Cullen/Woodall Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,101,470)PPS Sieve Double Bronze: Earned 100,000,000 credits (100,344,557)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (715,073)TRP Sieve (suspended) Gold: Earned 500,000 credits (630,833)AP 26/27 Emerald: Earned 50,000,000 credits (75,127,026)GFN Sapphire: Earned 20,000,000 credits (38,551,940)WW Double Bronze: Earned 100,000,000 credits (100,076,000)PSA Jade: Earned 10,000,000 credits (10,047,861)
Message 152334 - Posted: 21 Nov 2021 | 12:24:35 UTC

How is FFT length calculated? Is is solely based on the the prime being calculated or are there other external factors such as hardware that can affect the FFT being used? And is the choosing of the FFT dynamic? (I am not asking about fitting a given FFT into cache which is covered in other threads.)
____________
Werinbert is not prime... or PRPnet keeps telling me so.
Badge score: 12x3 + 1x4 + 2x6 + 2x7 + 1x8 + 1x9 + 1x10 = 93

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13780
ID: 53948
Credit: 343,976,795
RAC: 9,571
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 2 mega primesFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 2 primes in the 2021 Tour de PrimesFound 2 primes in the 2022 Tour de PrimesFound 1 mega prime in the 2022 Tour de PrimesFound 1 prime in the 2022 Tour de Primes Mountain Stage321 LLR Turquoise: Earned 5,000,000 credits (6,638,389)Cullen LLR Turquoise: Earned 5,000,000 credits (5,038,114)ESP LLR Turquoise: Earned 5,000,000 credits (6,177,890)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,094,541)PPS LLR Sapphire: Earned 20,000,000 credits (23,416,635)PSP LLR Turquoise: Earned 5,000,000 credits (7,956,186)SoB LLR Sapphire: Earned 20,000,000 credits (36,067,618)SR5 LLR Jade: Earned 10,000,000 credits (12,245,906)SGS LLR Turquoise: Earned 5,000,000 credits (5,036,951)TRP LLR Turquoise: Earned 5,000,000 credits (5,084,329)Woodall LLR Turquoise: Earned 5,000,000 credits (5,032,821)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,061,196)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (22,885,121)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,902,645)GFN Emerald: Earned 50,000,000 credits (91,689,221)WW Emerald: Earned 50,000,000 credits (65,888,000)PSA Jade: Earned 10,000,000 credits (12,445,029)
Message 152335 - Posted: 21 Nov 2021 | 13:24:33 UTC - in response to Message 152334.
Last modified: 21 Nov 2021 | 13:26:57 UTC

How is FFT length calculated? Is is solely based on the the prime being calculated or are there other external factors such as hardware that can affect the FFT being used? And is the choosing of the FFT dynamic? (I am not asking about fitting a given FFT into cache which is covered in other threads.)


tl;dr: It's the number and the CPU type, but the details are very complicated.

The number (magnitude, size of the component parts, and I believe the type of number) and the hardware (CPU architecture) both have a role in selecting the FFT size.

The software tries to pick the fastest (usually the smallest) FFT size and FFT type. It guesses what it thinks the best FFT is, and uses that. If it guesses too aggressively and uses an FFT that is too small, a loss of precision will occur due to rounding errors, which will be detected, and all or part of the calculation will be retried with the next larger FFT.

If the guess is not aggressive enough, then a larger (i.e., slower) FFT is used when a faster FFT would have worked.

It works pretty well, but it's not an exact science.

Note that if you're using multithreading, it's even more complicated because the "best" size (i.e., smallest FFT that won't cause an error overflow) is **NOT** deterministic. Because threads will complete in random order, when you're close to an FFT boundary, some orderings of threads completing may produce an error overflow while other orderings won't. Here's an example...

Suppose there's four threads, and each produces an error of either +1 or -1, that the maximum allowable error is +2 (+2 is ok, but +3 is failure), and that three of the threads produce an error of +1 while one thread produces an error of -1. Consider these two orderings of how the four threads complete:

ordering one:
+1 (cumulative error +1, ok)
-1 (cumulative error 0, ok)
+1 (cumulative error +1, ok)
+1 (cumulative error +2, ok)

ordering two:
+1 (cumulative error +1, ok)
+1 (cumulative error +2, ok)
+1 (cumulative error +3, CALCULATION FAILS)
-1 (don't care)

In the second ordering, the result of the calculation has incurred too much rounding error to be considered valid, but if the threads complete in a different order, the calculation is valid.

That's not exactly how the error calculation works, but it's close enough to demonstrate why multithreading makes the rounding errors non-deterministic.
____________
My lucky number is 75898524288+1

mackerelProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Oct 08
Posts: 2578
ID: 29980
Credit: 548,818,900
RAC: 19,689
Discovered 6 mega primesEliminated 1 conjecture "k"Found 3 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 5 primes in the 2019 Tour de PrimesFound 6 primes in the 2020 Tour de PrimesFound 5 primes in the 2021 Tour de PrimesFound 1 prime in the 2022 Tour de Primes321 LLR Jade: Earned 10,000,000 credits (10,736,922)Cullen LLR Turquoise: Earned 5,000,000 credits (5,903,451)ESP LLR Turquoise: Earned 5,000,000 credits (7,207,880)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (6,714,227)PPS LLR Double Bronze: Earned 100,000,000 credits (119,496,561)PSP LLR Jade: Earned 10,000,000 credits (16,676,406)SoB LLR Sapphire: Earned 20,000,000 credits (20,019,367)SR5 LLR Sapphire: Earned 20,000,000 credits (25,605,231)SGS LLR Turquoise: Earned 5,000,000 credits (7,361,220)TPS LLR (retired) Bronze: Earned 10,000 credits (34,130)TRP LLR Sapphire: Earned 20,000,000 credits (35,623,812)Woodall LLR Turquoise: Earned 5,000,000 credits (8,171,820)321 Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,236,219)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,383,853)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,626,419)PPS Sieve Emerald: Earned 50,000,000 credits (76,969,144)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,293,882)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,012,757)AP 26/27 Sapphire: Earned 20,000,000 credits (27,813,588)GFN Emerald: Earned 50,000,000 credits (89,952,314)WW Sapphire: Earned 20,000,000 credits (34,040,000)PSA Ruby: Earned 2,000,000 credits (2,939,755)
Message 152336 - Posted: 21 Nov 2021 | 13:31:28 UTC - in response to Message 152334.

I don't claim to understand the whole process, but can answer parts of the questions.

FFT size is chosen to optimise performance on the hardware. You want the smallest FFT for highest performance, but the numerical precision scales with size. So the FFT has to be big enough not to introduce errors in calculation. Generally speaking, bigger numbers require bigger FFTs, but this is not a precise thing.

Following applies to Prime95, LLR, PFGW and other implementations using the gwnum library. To my understanding, depending on the CPU architecture, different FFT sizes may be picked. Personally I'd think a FP64 operation is the same as any other FP64 operation, but apparently there are architecture specific optimisations that can affect that. The code will pick from different implementations for best performance. FFT sizes may be slightly bigger or smaller than on other architectures due to this.

As for FFT size being dynamic, it can change during a test. Because of the required precision and performance balance, the best transition point may not be exactly calculated. The software can detect rounding errors, and if they happen, it'll repeat the calculation from last checkpoint. It may first repeat at the same FFT size first to check if it might be a transient error, such as bad hardware. If the error is repeatable, then it may increase FFT size.

Werinbert
Send message
Joined: 9 Jun 13
Posts: 159
ID: 233452
Credit: 354,681,391
RAC: 125,510
321 LLR Amethyst: Earned 1,000,000 credits (1,005,580)Cullen LLR Amethyst: Earned 1,000,000 credits (1,017,956)ESP LLR Gold: Earned 500,000 credits (671,131)Generalized Cullen/Woodall LLR Gold: Earned 500,000 credits (521,209)PPS LLR Jade: Earned 10,000,000 credits (10,000,222)PSP LLR Gold: Earned 500,000 credits (566,492)SoB LLR Gold: Earned 500,000 credits (597,244)SR5 LLR Amethyst: Earned 1,000,000 credits (1,000,484)SGS LLR Amethyst: Earned 1,000,000 credits (1,070,960)TRP LLR Amethyst: Earned 1,000,000 credits (1,004,720)Woodall LLR Gold: Earned 500,000 credits (615,831)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,014,922)Generalized Cullen/Woodall Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,101,470)PPS Sieve Double Bronze: Earned 100,000,000 credits (100,344,557)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (715,073)TRP Sieve (suspended) Gold: Earned 500,000 credits (630,833)AP 26/27 Emerald: Earned 50,000,000 credits (75,127,026)GFN Sapphire: Earned 20,000,000 credits (38,551,940)WW Double Bronze: Earned 100,000,000 credits (100,076,000)PSA Jade: Earned 10,000,000 credits (10,047,861)
Message 152337 - Posted: 21 Nov 2021 | 19:30:20 UTC

Thank you both.
I find that the variations found in PG tasks to be small and more or less consistent. Great for projecting long term credit and hourly goals. SRBase tasks on the other hand seem to have FFTs that are all over the place which in turn makes for inconsistent credit/hr calculations.

____________
Werinbert is not prime... or PRPnet keeps telling me so.
Badge score: 12x3 + 1x4 + 2x6 + 2x7 + 1x8 + 1x9 + 1x10 = 93

Profile dannyridel
Volunteer tester
Avatar
Send message
Joined: 3 Feb 19
Posts: 958
ID: 1097922
Credit: 29,510,006
RAC: 71,122
Discovered 1 mega prime321 LLR Gold: Earned 500,000 credits (652,718)Cullen LLR Silver: Earned 100,000 credits (221,150)ESP LLR Gold: Earned 500,000 credits (517,207)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,021,028)PPS LLR Ruby: Earned 2,000,000 credits (2,745,972)PSP LLR Gold: Earned 500,000 credits (616,940)SoB LLR Gold: Earned 500,000 credits (533,625)SR5 LLR Silver: Earned 100,000 credits (156,121)SGS LLR Gold: Earned 500,000 credits (726,147)TRP LLR Silver: Earned 100,000 credits (247,743)Woodall LLR Silver: Earned 100,000 credits (144,022)321 Sieve (suspended) Gold: Earned 500,000 credits (506,814)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (30,033)PPS Sieve Ruby: Earned 2,000,000 credits (3,566,518)AP 26/27 Amethyst: Earned 1,000,000 credits (1,770,834)GFN Turquoise: Earned 5,000,000 credits (5,572,098)WW Jade: Earned 10,000,000 credits (10,108,000)PSA Silver: Earned 100,000 credits (373,034)
Message 152340 - Posted: 22 Nov 2021 | 0:37:31 UTC - in response to Message 152337.
Last modified: 22 Nov 2021 | 0:37:50 UTC

The reason of FFT inconsistency lies within the bases that LLR are facing with SRBase, from base 2 all the way up to base 1030, which complicates with the FFT calculations of LLR.
____________
My lucky number is 6219*2^3374198+1


Post to thread

Message boards : Number crunching : Calculating FFT length

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.92, 0.64, 0.70
Generated 26 May 2022 | 5:30:54 UTC