mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Hardware

Reply
 
Thread Tools
Old 2003-12-21, 18:35   #1
tha
 
tha's Avatar
 
Dec 2002

2×52×17 Posts
Default /. Video processor compiler

Slashdot is running an article on a compiler for processors of video cards

Slashdot article
tha is offline   Reply With Quote
Old 2003-12-21, 19:55   #2
PrimeCruncher
 
PrimeCruncher's Avatar
 
Sep 2003
Borg HQ, Delta Quadrant

2·33·13 Posts
Default

Wow. Only works on a few vid cards apparently (GeForceFX and above and ATI 97/9800). Also, briefly reading through the documentation, there appears to be a stumbling block:

From this page:

Quote:
Examples of legal reductions are sum, product, min/max, OR, AND, and XOR bit operations. Examples of invalid reductions include subtraction and dividision.
I might be wrong about this since I don't have much experience in C. Perhaps a more experienced programmer could comment on this?
PrimeCruncher is offline   Reply With Quote
Old 2003-12-21, 19:55   #3
GP2
 
GP2's Avatar
 
Sep 2003

258710 Posts
Default

Unfortunately, all my farm boxes use VGA cards that I bought for literally $1 each on eBay.

GP2 is offline   Reply With Quote
Old 2003-12-21, 20:06   #4
GP2
 
GP2's Avatar
 
Sep 2003

13·199 Posts
Default

Once upon a time, Nick Craig-Wood wrote an integer Lucas-Lehmer tester for the ARM chip.

http://www.craig-wood.com/nick/armprime/

The ARM chip had no divide instruction, but he found an ingenious way to calculate x mod p without division.

Perhaps this code could be revived for use on graphics cards. Unfortunately it doesn't seem like he's worked on it since 1999.
GP2 is offline   Reply With Quote
Old 2003-12-23, 17:39   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

If division isn't available then subtraction of multiples x from p until the amount left is less then x.

If divistion and subtraction aren't available then add multiples of x while less than p.

Shifts can be used for multiplying and dividing by 2.

I think integers in 2's complement will add negatives.
dsouza123 is offline   Reply With Quote
Old 2003-12-24, 06:25   #6
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

1000100102 Posts
Default

For the LL test everything is done mod Mp, so there are other tricks to replace division and subtraction.

-- Tho I'm not sure adding (Mp - 2) instead of subtracting 2 is reasonable.
Maybeso is offline   Reply With Quote
Old 2003-12-24, 06:52   #7
ColdFury
 
ColdFury's Avatar
 
Aug 2002

32010 Posts
Default

http://www.cs.unm.edu/~kmorel/documents/fftgpu/

FFT's can be done on a GPU. However, as usual, the problem is precision. Anyone know any useful tricks to use two singles as a double?
ColdFury is offline   Reply With Quote
Old 2003-12-24, 22:20   #8
Dresdenboy
 
Dresdenboy's Avatar
 
Apr 2003
Berlin, Germany

192 Posts
Default

There is an older thread about using GPUs for calculations:

http://mersenneforum.org/showthread.php?s=&threadid=432

Even something simple like game of life is hard to port to a GPU by using an efficient algorithm (like calculating one life cell per bit)
Dresdenboy is offline   Reply With Quote
Old 2003-12-26, 16:49   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

112·97 Posts
Default

Quote:
Originally posted by GP2
Once upon a time, Nick Craig-Wood wrote an integer Lucas-Lehmer tester for the ARM chip.

http://www.craig-wood.com/nick/armprime/

The ARM chip had no divide instruction, but he found an ingenious way to calculate x mod p without division.
The LL test itself requires no divide, since the modulus has a convenient binary form, and because (since 1994) the Crandall/Fagin DWT algorithm allows us to further effect the mod automatically while doing the trasform-based multiply.

In Nick's case, any mods that would have been needed would have been with respect to the prime he used for his all-integer transform, p = 2^64 - 2^32 + 1. That prime has a nice binary form that allows efficient modding without division.

For general primes of no special form, we can use the well-known Montgomery division-less mod, which effects the mod via a clever precomputation of the inverse of p modulo a power of two, typically one chosen to coincide with the natural wordsize boundary of the hardware. This inverse can be efficiently computed using a Newton-style iteration of the same kind used to quickly find floating-point inverses without dividing, and using the fact that the standard hardware integer multiply of two (say) 64-bit ints is really mod-2^64 multiply. Once one has p^(-1) mod 2^n, a few more muls (including several which require a full double-wide integer product) suffice to return x*y*2^(-n) mod p, which can easily be converted to the desired x*y mod p.

My sieve-based factoring code uses the Montgomery mod. I believe George's uses a completely different (but similarly fast, especially on hardware which doesn't support double-wide integer muls) way to get x*y mod p.
ewmayer is offline   Reply With Quote
Old 2003-12-27, 10:16   #10
optim
 
optim's Avatar
 
Nov 2003
European Union

23·13 Posts
Default BrookGPU

General Programming of GPUs with C:


http://developers.slashdot.org/arti...052&tid=185



http://www.xbitlabs.com/news/video/...1222075229.html



http://graphics.stanford.edu/projects/brookgpu/



http://sourceforge.net/projects/brook


maybe we could use this to speed up Prime95/MPrime ??????
optim is offline   Reply With Quote
Old 2003-12-27, 16:43   #11
PrimeCruncher
 
PrimeCruncher's Avatar
 
Sep 2003
Borg HQ, Delta Quadrant

12768 Posts
Default Re: BrookGPU

Quote:
Originally posted by optim
maybe we could use this to speed up Prime95/MPrime ??????
Maybe if we can't use the GPU for every instruction, maybe we can use it for some and speed things up. George?
PrimeCruncher is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
mprime 28.10 compiler warning Explorer09 Software 1 2017-01-23 02:50
GCC/compiler warnings Dubslow Programming 2 2016-02-27 06:55
compiler/assembler optimizations possible? ixfd64 Software 7 2011-02-25 20:05
Help! Compiler bug R.D. Silverman Cunningham Tables 30 2010-10-02 22:12
Linux32 -> Windows64 C compiler? geoff Programming 3 2007-09-26 03:09

All times are UTC. The time now is 12:45.


Wed Jul 6 12:45:06 UTC 2022 up 83 days, 10:46, 0 users, load averages: 1.39, 1.31, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔