mfaktc: a CUDA program for Mersenne prefactoring - Page 13

S485122 · 2010-02-12, 06:40

Quote:

Originally Posted by TheJudger

In some cases it misses factors when there are mutiple factors in one class close together but this is not critical. That is a known problem since the first version... This has nothing to do with the calculations itself, it is just how the results are returned from the GPU to the CPU.

But it does mean that, even if those cases are extremely (?) rare, the program can not yet be used to do trial factoring for GIMPS.

Jacob

ATH · 2010-02-12, 07:06

If if only happens with multiple factors and at least one of the factors is always found it doesn't matter. We only need one factor to skip doing LL for that exponent.

TheJudger · 2010-02-12, 13:14

Hi,

it can happen if there is more than one factor found at the same time. On my GTX 275 there are 30720 (30 "multiprocessors" * 256 threads per block * 4 blocks per multiprocessor) threads "in flight" at the same time. The problem is that I haven't written code to handle access to the result array. I need some kind of locking and/or atomic read/writes.

S485122: did you know that prime95 missed some factors asweel?

Oliver

TimSorbet · 2010-02-12, 13:15

IIRC Prime95 always looks for the smallest factor in the bit range. If George considers that important to be a GIMPS-contributing TF algorithm/program, and this program isn't guaranteed to find the smallest of the factors, then that might be a roadblock.

kjaget · 2010-02-12, 14:34

Quote:

Originally Posted by TheJudger

Siever received a nice performace improvement for free by adding "-funroll-all-loops" to the gcc options. :) (only useful for CPU-limited scenarios)

Oliver

If you're looking for a set of useful optimizations, here's what I came up with for gcc 4.4.0 :

g++ -O1 -fno-dce -fno-ipa-reference -fno-split-wide-types -fno-tree-dominator-opts -fno-tree-copyrename -fno-tree-loop-optimize -momit-leaf-frame-pointer -fno-tree-sink -fno-inline-functions-called-once -frerun-cse-after-loop -ftree-pre -fipa-cp -freorder-blocks -fipa-cp-clone -fsee -mtune=nocona -msse4.1

This gained me ~20% over default -O2 or -O3 settings.

I'm testing on my Core2Duo laptop, so obviously results will be different for different CPUs and even different versions of the compilers. Still, give it a shot and see if it helps.

davieddy · 2010-02-12, 15:56

Quote:

Originally Posted by Mini-Geek

IIRC Prime95 always looks for the smallest factor in the bit range. If George considers that important to be a GIMPS-contributing TF algorithm/program, and this program isn't guaranteed to find the smallest of the factors, then that might be a roadblock.

The principal reason for trying potential factors in ascending order is
that the probability of it being a factor decreases with the size of the
trial factor. That this procedure finds the smallest factor is merely an
added bonus.
Besides, does P-1 necessarily find the lowest factor?

David

PS The probability of 2kp + 1 being a factor goes as 1/klogk ?

TimSorbet · 2010-02-12, 16:15

Quote:

Originally Posted by davieddy

The principal reason for trying potential factors in ascending order is
that the probability of it being a factor decreases with the size of the
trial factor. That this procedure finds the smallest factor is merely an
added bonus.

IIRC Prime95 doesn't just search it going from lowest to highest, but something based on the potential factor's value mod...something (120?). Something about being able to do it faster that way, I suppose. But I think then if it finds a factor it keeps looking for a smaller one.

Quote:

Originally Posted by davieddy

Besides, does P-1 necessarily find the lowest factor?

No. Certainly not. But that is a quite different scenario, and doesn't necessarily mean that they don't care about the discovery order for factors found by TF.

axn · 2010-02-12, 16:30

Quote:

Originally Posted by Mini-Geek

But I think then if it finds a factor it keeps looking for a smaller one

It used to ... way back when. Not anymore.

davieddy · 2010-02-12, 16:39

Quote:

Originally Posted by Mini-Geek

something based on the potential factor's value mod...something (120?). Something about being able to do it faster that way, I suppose.

I implemented a TF program about five years ago, and I recall
that 120 business. I think it comes from neatly storing possible primes
mod 30 as eight bits, implicitly excluding multiples of 2,3 and 5.

Any factor found saves the LL tests and is stronger information than
"is composite".

David

ATH · 2010-02-12, 16:46

Quote:

Originally Posted by Mini-Geek

IIRC Prime95 doesn't just search it going from lowest to highest, but something based on the potential factor's value mod...something (120?). Something about being able to do it faster that way, I suppose. But I think then if it finds a factor it keeps looking for a smaller one.

It only checks factors with +-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49 (mod 120), which is only 16 of the 30 classes that corresponds to +/- 1 (mod 8), so it doing it mod 120 "saves" checking factors from 14 of 30 residue classes.

TimSorbet · 2010-02-12, 17:28

Quote:

Originally Posted by ATH

It only checks factors with +-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49 (mod 120), which is only 16 of the 30 classes that corresponds to +/- 1 (mod 8), so it doing it mod 120 "saves" checking factors from 14 of 30 residue classes.

Does it still cover all factors? It seems to me that if you only cover 16 of the 30 potential values, you'd be missing about half the factors.

2010-02-12, 13:14	#135
TheJudger "Oliver" Mar 2005 Germany 1115₁₀ Posts	Hi, it can happen if there is more than one factor found at the same time. On my GTX 275 there are 30720 (30 "multiprocessors" * 256 threads per block * 4 blocks per multiprocessor) threads "in flight" at the same time. The problem is that I haven't written code to handle access to the result array. I need some kind of locking and/or atomic read/writes. S485122: did you know that prime95 missed some factors asweel? Oliver Last fiddled with by TheJudger on 2010-02-12 at 13:15

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
mfakto: an OpenCL program for Mersenne prefactoring	Bdot	GPU Computing	1724	2023-06-04 23:31
gr-mfaktc: a CUDA program for generalized repunits prefactoring	MrRepunit	GPU Computing	42	2022-12-18 05:59
The P-1 factoring CUDA program	firejuggler	GPU Computing	753	2020-12-12 18:07
mfaktc 0.21 - CUDA runtime wrong	keisentraut	Software	2	2020-08-18 07:03
World's second-dumbest CUDA program	fivemack	Programming	112	2015-02-12 22:51

2010-02-12, 07:06	#134
ATH Einyen Dec 2003 Denmark 110101111100₂ Posts	If if only happens with multiple factors and at least one of the factors is always found it doesn't matter. We only need one factor to skip doing LL for that exponent.

2010-02-12, 13:15	#136
TimSorbet Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 11×389 Posts	IIRC Prime95 always looks for the smallest factor in the bit range. If George considers that important to be a GIMPS-contributing TF algorithm/program, and this program isn't guaranteed to find the smallest of the factors, then that might be a roadblock.