Integer and Floating point Trial Factoring in parallel ?

dsouza123 · 2003-09-17, 23:24

I was reading the readme.txt file and came across this

It is also used, to choose between integer based factoring (Cyrix and 486) and floating point based
factoring (Pentium and Pentium Pro).

Is it possible for both to be used in parallel ( interleaving the instructions ) giving a speed increase ?

Or is there some dependency or contention issue ?
Even so would there still be a speed increase ?

Is there some max bit depth for factoring ( 64 ) ?

I took it to mean the factoring mentioned was trial factoring.

Dresdenboy · 2003-09-20, 17:21

This idea can be applied to many algorithms if there exist integer and floating point versions. If you search this forum a bit, you'll find some messages regarding this topic - but for the transform (float/modular transform).

But it's hard to explicitly code this behaviour. It would be easier to take a SMT capable CPU and run a thread doing the floating point version and another thread doing it in integer.

dsouza123 · 2003-09-21, 02:57

Thanks for replying.

I have searched alot of posts but didn't find anything that really addressed it.

Did examine factor64.asm saw the sieve code then special code for the powering algorithm for some bit depths.

It seems that all the trial factoring except maybe the SSE2 has at least some floating point instructions.

It is much more complicated then when I coded the powering algorithm myself to understand it better.

I haven't done the special sieve though, have to figure out the factor q = 2kp + 1 part. Just did the mod operations before.

Maybe I'll try it ( the powering algorithm) in MASM this time instead of Delphi and Visual Basic implementations. An unsigned integer version not a x86 floating point one. I can see how 64 bit registers would help, with two 64 bit registers holding the 128 bit result of a 64 x 64 bit multiply.

I believe the internal x87 floating point format is ( usually ) 80 bits with 64 bits ( for the number, rest for the exponent ) but getting the result out and not losing the full 64 bit integer part is the trick. Maybe extended format or maybe the whole calc is done in x87 and just a check if the answer equals 1.0 at the end is done.

Maybe there are other approaches to optimize the algorithm, exploit some parallelism in the powering algorithm.

mephisto · 2003-09-21, 12:46

Check these threads: They all discuss optimization by interleaving instructions. Search for 'float' and 'integer'.

Mixed floating/integer transform for faster LL testing - http://www.mersenneforum.org/showthr...+point+integer
Could both the x87 and SSE2 be run in parallel/interleaved - http://www.mersenneforum.org/showthr...oating+integer
A more equal distribution of additions and multiplications - http://www.mersenneforum.org/showthr...oating+integer

Don't understand half of it myself, but you're welcome to it.

2003-09-17, 23:24	#1
dsouza123 Sep 2002 2×331 Posts	Integer and Floating point Trial Factoring in parallel ? I was reading the readme.txt file and came across this It is also used, to choose between integer based factoring (Cyrix and 486) and floating point based factoring (Pentium and Pentium Pro). Is it possible for both to be used in parallel ( interleaving the instructions ) giving a speed increase ? Or is there some dependency or contention issue ? Even so would there still be a speed increase ? Is there some max bit depth for factoring ( 64 ) ? I took it to mean the factoring mentioned was trial factoring.

2003-09-21, 12:46	#4
mephisto Feb 2003 Norway 2³·7 Posts	Check these threads: They all discuss optimization by interleaving instructions. Search for 'float' and 'integer'. Mixed floating/integer transform for faster LL testing - http://www.mersenneforum.org/showthr...+point+integer Could both the x87 and SSE2 be run in parallel/interleaved - http://www.mersenneforum.org/showthr...oating+integer A more equal distribution of additions and multiplications - http://www.mersenneforum.org/showthr...oating+integer Don't understand half of it myself, but you're welcome to it.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
floating point operations	ATH	Lounge	3	2006-01-01 20:29
Floating point options for Windows XP 64	dsouza123	Hardware	2	2005-03-12 17:45
LL tests: Integer or floating point?	E_tron	Math	4	2004-01-13 19:44
Floating point precision	lunna	Hardware	11	2003-12-29 16:46
floating point exception in Version 23.4.2	mda2376	Software	2	2003-06-12 04:45

2003-09-20, 17:21	#2
Dresdenboy Apr 2003 Berlin, Germany 551₈ Posts	This idea can be applied to many algorithms if there exist integer and floating point versions. If you search this forum a bit, you'll find some messages regarding this topic - but for the transform (float/modular transform). But it's hard to explicitly code this behaviour. It would be easier to take a SMT capable CPU and run a thread doing the floating point version and another thread doing it in integer.

2003-09-21, 02:57	#3
dsouza123 Sep 2002 2·331 Posts	Thanks for replying. I have searched alot of posts but didn't find anything that really addressed it. Did examine factor64.asm saw the sieve code then special code for the powering algorithm for some bit depths. It seems that all the trial factoring except maybe the SSE2 has at least some floating point instructions. It is much more complicated then when I coded the powering algorithm myself to understand it better. I haven't done the special sieve though, have to figure out the factor q = 2kp + 1 part. Just did the mod operations before. Maybe I'll try it ( the powering algorithm) in MASM this time instead of Delphi and Visual Basic implementations. An unsigned integer version not a x86 floating point one. I can see how 64 bit registers would help, with two 64 bit registers holding the 128 bit result of a 64 x 64 bit multiply. I believe the internal x87 floating point format is ( usually ) 80 bits with 64 bits ( for the number, rest for the exponent ) but getting the result out and not losing the full 64 bit integer part is the trick. Maybe extended format or maybe the whole calc is done in x87 and just a check if the answer equals 1.0 at the end is done. Maybe there are other approaches to optimize the algorithm, exploit some parallelism in the powering algorithm.