Dogrzewamy mieszkanie czyli AP26 na ATI Radeon

[sesef]

Aktualna wersja: 0.4.6.1

Wymagania na chwilę obecną dla wersji 0.4.6.1:
- sterowniki Catalyst 9.2+ (zalecane 9.12 HotFix)
- system windows app działa na x86 i x64
- karta graficzna z serii Radeon HD2k HD3k HD4k HD5k (zalecana karta z serii HD 4000 lub nowsza)

Link do aktualnej wersji: www.sesef.pl/AP/AP26PGx86-461.zip

Podczas liczenia powinien pojawić się plik SOL-AP26.TXT w nim zapisywany jest wynik, niby u mnie i u Oxy wyniki wyszły poprawne, ale jak ktoś chce sprawdzić to poprawna zawartość pliku SOL jest następująca:

Wynik dla kart serii 2k, 3k, 4k, 57xx (i niższe modele)

11 366384 6998839830228583
10 366384 785468127438811
25 366384 6171054912832631
10 366384 1459178643530617
10 366384 9735298495263823
10 366384 1727805601738891
10 366384 2138118918508471
11 366384 3007107694524497
10 366384 1255892682660361
11 366384 7036595108074969
10 366384 8188609810134857
10 366384 2411963918614357
10 366384 13700995611657901
14 366384 15879407069784169
11 366384 6250872237076277
10 366384 11977568522771779
10 366384 1540799946122147
12 366384 14782924219657043
13 366384 2167218735183577

Wynik dla kart serii 5800, 5900

11 366384 6998839830228583
10 366384 785468127438811
25 366384 6171054912832631
10 366384 9735298495263823
10 366384 1727805601738891
10 366384 2138118918508471
11 366384 3007107694524497
10 366384 1255892682660361
11 366384 7036595108074969
10 366384 8188609810134857
10 366384 2411963918614357
10 366384 13700995611657901
14 366384 15879407069784169
10 366384 1540799946122147
13 366384 2167218735183577

Podziękowania dla:
- Oxy
- Satanetva
- Obix
- Robert_7NBI
- Erni
- Wszystkich którzy siedzieli na ircu i znosili moje marudzenie, że czegoś nie ma w ATI Stream albo, że mi coś nie działa itp.

=======================================================================
Testy:

Interesuje mnie czas z pliku stderr.txt (PrimeTest time: 19.511147 Total time: 115.975238), oraz najlepiej to co pojawi się w konsoli

[Troll81]

zaluje ze nie mam ATI zeby cie wspomoc moimi testami  :shame:

[satanetv]

Maly blad w nicku ale dzieki za podziekowania. No i znowu musze nowy system stawiac :D. Tym razem Vista x64 :D

[satanetv]

XP64 stery 9.8

plik wynikowy:

10 366384 785436737771879
10 366384 16137071418665303
10 366384 13946622976437587
10 366384 8734502163109357
11 366384 6998839830228583
10 366384 785468127438811
11 366384 5581880890832023
25 366384 6171054912832631
10 366384 9684491327954279
10 366384 3267586960583089
10 366384 1459178643530617
10 366384 9735298495263823
10 366384 1727805601738891
10 366384 1574579779396307
10 366384 2138118918508471
11 366384 10613929284401483
10 366384 14083229671187167
11 366384 16518632605478693
11 366384 3007107694524497
10 366384 1255892682660361
11 366384 7036595108074969
10 366384 8188609810134857
10 366384 2411963918614357
11 366384 6569259450263561
10 366384 13700995611657901
14 366384 15879407069784169
11 366384 6250872237076277
10 366384 7687488261269507
10 366384 660669773389609
10 366384 11977568522771779
10 366384 1540799946122147
12 366384 14782924219657043
10 366384 13812949836154363
11 366384 2003229604981763
10 366384 14531182366753699
13 366384 15731878523384263
13 366384 2167218735183577

Czas obliczen - 510 sekund. Obciazenie CPU - od 25% do 32% Obciazenie GPU 41%

[Troll81]

za duże obciążenie CPU :D

[X X X]

To zależy od tego, ile wątków da się równocześnie liczyć na GPU. Jeśli tylko jeden, to może być, a jeśli 4, to trzeba to lekuchno poprawić.

[sesef]

Obciążenie CPU to jest chwila roboty wystarczy dodać w dwóch miejscach sleep(100); i już praktycznie użycie cpu jest znikome, ale jednak wydłuża to czas działania i zaciera prawdziwe wyniki tak więc jak już zejdę odpowiednio nisko z czasem to wtedy będzie można się bawić w dobieranie odpowiedniego sleepa.

[OxyOne]

Dzisiaj sprawdzilem jeszcze raz ten ap26 ustawiłem Sapphirka D0 na 840 /reszta na 500/ i sie zmieniło

Obciazenie GPU 58% czas ok 362sek dziwne musze to przedyskutowac dlaczego.

[EDIT]

10 366384 785436737771879
10 366384 16137071418665303
10 366384 13946622976437587
10 366384 8734502163109357
11 366384 6998839830228583
10 366384 785468127438811
11 366384 5581880890832023
25 366384 6171054912832631
10 366384 9684491327954279
10 366384 3267586960583089
10 366384 1459178643530617
10 366384 9735298495263823
10 366384 1727805601738891
10 366384 1574579779396307
10 366384 2138118918508471
11 366384 10613929284401483
10 366384 14083229671187167
11 366384 16518632605478693
11 366384 3007107694524497
10 366384 1255892682660361
11 366384 7036595108074969
10 366384 8188609810134857
10 366384 2411963918614357
11 366384 6569259450263561
10 366384 13700995611657901
14 366384 15879407069784169
11 366384 6250872237076277
10 366384 7687488261269507
10 366384 660669773389609
10 366384 11977568522771779
10 366384 1540799946122147
12 366384 14782924219657043
10 366384 13812949836154363
11 366384 2003229604981763
10 366384 14531182366753699
13 366384 15731878523384263
13 366384 2167218735183577

[Raptor77]

czas liczenia 4:49 (289s) obciązenie CPU 12.5% - jeden rdzeń na full, obciązenie GPU 49.4% (4890@920), cat 9.8, win7 x64

10 366384 785436737771879
10 366384 16137071418665303
10 366384 13946622976437587
10 366384 8734502163109357
11 366384 6998839830228583
10 366384 785468127438811
11 366384 5581880890832023
25 366384 6171054912832631
10 366384 9684491327954279
10 366384 3267586960583089
10 366384 1459178643530617
10 366384 9735298495263823
10 366384 1727805601738891
10 366384 1574579779396307
10 366384 2138118918508471
11 366384 10613929284401483
10 366384 14083229671187167
11 366384 16518632605478693
11 366384 3007107694524497
10 366384 1255892682660361
11 366384 7036595108074969
10 366384 8188609810134857
10 366384 2411963918614357
11 366384 6569259450263561
10 366384 13700995611657901
14 366384 15879407069784169
11 366384 6250872237076277
10 366384 7687488261269507
10 366384 660669773389609
10 366384 11977568522771779
10 366384 1540799946122147
12 366384 14782924219657043
10 366384 13812949836154363
11 366384 2003229604981763
10 366384 14531182366753699
13 366384 15731878523384263
13 366384 2167218735183577

[Peciak]

System operacyjny  Microsoft Windows Vista 64 Home Premium
Dodatek service pack systemu operacyjnego            Service Pack 2
Internet Explorer                                          8.0.6001.18813
DirectX                                                    DirectX 10.1
Typ procesora                                              QuadCore AMD Phenom II X4 810,
Nazwa płyty głównej                                        Gigabyte GA-MA790XT-UD4P 
Pamięć fizyczna                                            4096 MB  (DDR3-1333 DDR3 SDRAM) Dual
DIMM1: Kingston 9905403-011.A02LF 
DIMM2: Kingston 9905403-011.A02LF 
Karta wideo                   Sapphire Radeon HD 4850  625/975
sterowniki ATI Catalyst 9.5
10 366384 785436737771879
10 366384 16137071418665303
10 366384 13946622976437587
10 366384 8734502163109357
11 366384 6998839830228583
10 366384 785468127438811
11 366384 5581880890832023
25 366384 6171054912832631
10 366384 9684491327954279
10 366384 3267586960583089
10 366384 1459178643530617
10 366384 9735298495263823
10 366384 1727805601738891
10 366384 1574579779396307
10 366384 2138118918508471
11 366384 10613929284401483
10 366384 14083229671187167
11 366384 16518632605478693
11 366384 3007107694524497
10 366384 1255892682660361
11 366384 7036595108074969
10 366384 8188609810134857
10 366384 2411963918614357
11 366384 6569259450263561
10 366384 13700995611657901
14 366384 15879407069784169
11 366384 6250872237076277
10 366384 7687488261269507
10 366384 660669773389609
10 366384 11977568522771779
10 366384 1540799946122147
12 366384 14782924219657043
10 366384 13812949836154363
11 366384 2003229604981763
10 366384 14531182366753699
13 366384 15731878523384263
13 366384 2167218735183577

czas 568 sek
GPU 50%
CPU0 - 61-36%
CPU1 - 7-19%
CPU2- 21-28%
CPU3- 2-16%

[sesef]

Posprawdzałem, sito liczy się tak szybko, że tam to ja już nic więcej nie zrobię (znaczy dałoby radę jeszcze podkoksować, ale nie z moja wiedzą bo jedyne co mnie teraz tam ogranicza to liczenie remaindera)

Teraz problemem jest szybkość generowania liczb, które trafiają do GPU. W wersji 0.1 robi to CPU i wygenerowanie zrobiłem małe testy porównawcze wygenerowanie przez CPU 443555 liczb trwa około 0,007 sekundy, może i niewiele, ale jak taką operacje będzie trzeba wykonać 12376 razy to już z tego robi się 86 sec, wygenerowanie takiej samej ilości liczb na gpu trwa 0,00024 sekundy (przy bardzo nie wydajnym algorytmie) przy 12376 wywołaniach to jest jakieś 3,1 sekundy widać kolosalną różnicę jednak jest pewien mankament. Przy generowaniu na GPU zawiesza się pulpit gpu zostaje tak obciążone, że nie daje nawet rady odświeżyć pulpitu, jak uda mi się z tym uporać to program powinien trochę przyspieszyć :).

[Troll81]

3,1 sekundy freeze przeboleć można :D

[sesef]

Niestety generowania liczb na gpu idzie na kołek :( generuje je szybciej niż CPU, ale są one potem potrzebne jeszcze przy sprawdzaniu pierwszości, która jest robiona na CPU, więc muszę te liczby ściągnąć z GPU na CPU, a niestety droga GPU -> jest z 2-2,5x wolniejsza niż CPU->GPU, więc w ogólnym rozrachunku wyszło, że wygenerowanie liczb na gpu+przesłanie ich GPU -> CPU trwa dłużej niż wygenerowanie ich na CPU + przesłanie ich CPU -> GPU (wygenerowane liczby zostaną na CPU więc nie trzeba ich potem ściągać z GPU).

Jako, że generowanie liczb powinno powrócić z powrotem na GPU to mam 2 rozwiązania jakoś pozbyć się tych liczb ze sprawdzania pierwszości, albo wywalić sprawdzanie pierwszości na gpu. Zarówno pierwsze jak i drugie rozwiązanie komplikuje mi sprawę.

[Troll81]

a sprawdzanie pierwszości na gpu??

[sesef]

a sprawdzanie pierwszości na gpu??

Tak trzeba pewnie będzie zrobić, a zbyt proste to nie będzie  :wth: biorąc pod uwagę, że pewnie wszystkie funkcje będę musiał napisać sam bo jak będzie coś potrzebne to pewnie w ATI Stream tego nie będzie :D, ale przynajmniej w swoim czasie będę mógł wpisać w CV "programowanie kart graficznych ATI Radeon w ATI Stream SDK"  :attack:

Na razie wprowadzę w życie inny pomysł, powinno uciąć 50-90 sec.

[sesef]

Dałem nową wersje 0.2 powinno liczyć trochę szybciej, dodatkowo w nowej wersji dodałem czasomierz wystarczy odpalić start.bat i już się samo wszystko uruchomi, jak się skończy przeliczanie to pojawi się tekst typu "Aby kontynuować naciśnij dowolny klawisz..."

Przed naciśnięciem dowolnego klawisza proszę, odczytać dane: Time GPU, Numbers generation time, Prime test time, oraz Total time.

App 0.2 http://www.speedyshare.com/245349402.html (również link zaktualizowany w 1 poście).

[satanetv]

No widze znaczna poprawe. Roznica w stosunku do wersji 0.1 to poprawa o 85 sekund.  :parrrty:

Wyniki poprawne :)

GPU time: 232 sekundy
Numbers generation time: 56 sekund
Prime test time: 133 sekundy
Total time: 426 sekund.

Z niecierpliwoscia czekam na wersje 0.3  :parrrty:

EDIT
Zapomnialem dopisac:

GPU - 32%
CPU - Obciaza tylko jeden rdzen w 80% (ogolnie 20% quada mi obciaza)

[Peciak]

GPU time: 210, 399459 sekundy
Numbers generation time: 66, 399459 sekund
Prime test time: 136, 969848 sekundy
Total time: 417, 702246 sekund.

obciążenie
CPU0 - 63-73%
CPU1 - 12%
CPU2 - 15%
CPU3 - 10%
GPU - 43% - mało  :(
10 366384 785436737771879
10 366384 16137071418665303
10 366384 13946622976437587
10 366384 8734502163109357
11 366384 6998839830228583
10 366384 785468127438811
11 366384 5581880890832023
25 366384 6171054912832631
10 366384 9684491327954279
10 366384 3267586960583089
10 366384 1459178643530617
10 366384 9735298495263823
10 366384 1727805601738891
10 366384 1574579779396307
10 366384 2138118918508471
11 366384 10613929284401483
10 366384 14083229671187167
11 366384 16518632605478693
11 366384 3007107694524497
10 366384 1255892682660361
11 366384 7036595108074969
10 366384 8188609810134857
10 366384 2411963918614357
11 366384 6569259450263561
10 366384 13700995611657901
14 366384 15879407069784169
11 366384 6250872237076277
10 366384 7687488261269507
10 366384 660669773389609
10 366384 11977568522771779
10 366384 1540799946122147
12 366384 14782924219657043
10 366384 13812949836154363
11 366384 2003229604981763
10 366384 14531182366753699
13 366384 15731878523384263
13 366384 2167218735183577

[Raptor77]

GPU time: 104.376681,
Numbers generation time: 37.294324,
Prime test time: 70.462979
Total time: 215.607056

GPU @ 42%
CPU @ 12% (jeden rdzeń na 100%)

10 366384 785436737771879
10 366384 16137071418665303
10 366384 13946622976437587
10 366384 8734502163109357
11 366384 6998839830228583
10 366384 785468127438811
11 366384 5581880890832023
25 366384 6171054912832631
10 366384 9684491327954279
10 366384 3267586960583089
10 366384 1459178643530617
10 366384 9735298495263823
10 366384 1727805601738891
10 366384 1574579779396307
10 366384 2138118918508471
11 366384 10613929284401483
10 366384 14083229671187167
11 366384 16518632605478693
11 366384 3007107694524497
10 366384 1255892682660361
11 366384 7036595108074969
10 366384 8188609810134857
10 366384 2411963918614357
11 366384 6569259450263561
10 366384 13700995611657901
14 366384 15879407069784169
11 366384 6250872237076277
10 366384 7687488261269507
10 366384 660669773389609
10 366384 11977568522771779
10 366384 1540799946122147
12 366384 14782924219657043
10 366384 13812949836154363
11 366384 2003229604981763
10 366384 14531182366753699
13 366384 15731878523384263
13 366384 2167218735183577

[Jarek Wróblewski]

Geoff Reynolds umieścił w
http://www.geocities.com/g_w_reynolds/AP26/PrimeQ_gen.zip
procedurę testującą pierwszość przy wykorzystaniu jedynie arytmetyki 64-bitowej. Wygląda, że jest to znacznie lepsze rozwiązanie od tego, które ja proponowałem.

Być może da się to jakoś wsadzić na grafę i tam testować pierwszość.

Poprawności procedury Geoffa nie sprawdzałem, milcząco zakładam, że jest OK.

Myślę, że w razie potrzeby można ją trochę przyspieszyć.

[satanetv]

Ach gdyby trochę więcej funkcji było w ATI stream SDK. No trzeba jeszcze sporo zejść z czasem obliczeń testowego zakresu, więc jest co przyśpieszać.

[sesef]

Geoff Reynolds umieścił w
http://www.geocities.com/g_w_reynolds/AP26/PrimeQ_gen.zip
procedurę testującą pierwszość przy wykorzystaniu jedynie arytmetyki 64-bitowej. Wygląda, że jest to znacznie lepsze rozwiązanie od tego, które ja proponowałem.

Być może da się to jakoś wsadzić na grafę i tam testować pierwszość.

Poprawności procedury Geoffa nie sprawdzałem, milcząco zakładam, że jest OK.

Myślę, że w razie potrzeby można ją trochę przyspieszyć.

Widziałem ta procedurę największy problem to pozbycie się uint64_t q1 = two63/anc; i uint64_t q2 = two63/d; z getMagic. Kombinowałem również testem z Millera-Rabina, ale niestety typ double jest za mały i obcinało mi 3 ostatnie cyfry  w liczbie (http://edu.i-lo.tarnow.pl/inf/alg/001_search/0018.php w tym algorytmie typ ulong zastąpiłem typem double) już przy liczeniu a^b mod n :(

[Jarek Wróblewski]

Widziałem ta procedurę największy problem to pozbycie się uint64_t q1 = two63/anc; i uint64_t q2 = two63/d; z getMagic.

To wytłumacz mi, w czym problem. Czy na grafie nie ma dzielenia uint64 ? To jakie operacje są dostępne?

[satanetv]

Problem w tym że wiele operacji można wykonać w double ale wynik już jest floatem. Więc albo trzeba pisać samemu funkcje. I tutaj przyda się twój umysł matematyczny w celu skrócenia pewnych obliczeń. Albo czekać na pojawienie sie ATI stream SDK 2.0

[sesef]

Widziałem ta procedurę największy problem to pozbycie się uint64_t q1 = two63/anc; i uint64_t q2 = two63/d; z getMagic.

To wytłumacz mi, w czym problem. Czy na grafie nie ma dzielenia uint64 ? To jakie operacje są dostępne?

Na kartach ATI nie ma po prostu typu całkowitego 64bit, największy możliwy typ to double który z tego co pamiętam ma 54bity czy coś koło tego. Natomiast dla 32bitowego typu dostępne są wszystkie podstawowe operacje +, - *, /, >>, <<, &, |, ^, ~.

Np z braku obsługi właśnie liczb 64bit trzeba liczyć remainder w ten sposób, do tego dochodzi problem, że jeszcze grafika nie ma obsługi funkcji floor dla typu double (tylko na float liczy, jak się podaje double to konwertuje sobie liczbę na float i dopiero liczy). Jak jest jakaś inna metoda na policzenie % to by się bardzo przydała, przyspieszyłoby to sito :)

kernel int
Rem(double a, double n)
{
   /*double aa = floor(a / n);
   double db = n * aa;
   double c1 = a - db;*/

   double c1;
   double db;

   double ga = a / n;
   float gp = floor((float)ga);
   double gd = ga - (double)gp;
   int ab = (int)gd;
   double ac = gp + (double)ab;
   //double br = ac - ga;

   if(ac > ga)
   {
      ac -= 1.0;
   }

   db = n * ac;
   c1 = a - db;

   return (int)c1;
}

[Jarek Wróblewski]

W pliku

http://www.math.uni.wroc.pl/~jwr/cuda/PrimeQ-2009-09-03.zip

są 2 testy.
test.c jest do uruchomienia na CPU jako wzorzec - powinien drukować to samo, co test31.c:

Kod [Zaznacz] Rozwiń


1 1000000000000000003
2 1000000000000000009
3 1000000000000000031
4 1000000000000000079
5 1000000000000000177
6 1000000000000000183
7 1000000000000000201
8 1000000000000000283
9 1000000000000000381
10 1000000000000000387
11 1000000000000000507
12 1000000000000000523
13 1000000000000000583
14 1000000000000000603
15 1000000000000000619
16 1000000000000000621
17 1000000000000000799
18 1000000000000000841
19 1000000000000000861
20 1000000000000000877
21 1000000000000000913
22 1000000000000000931
23 1000000000000000997
Naciśnij dowolny klawisz, aby kontynuować . . .


Czy wygląda na to, że da radę bez większego bólu uruchomić test31.c na grafie?

Dzielenie two63/d wobec two63=2^31 jest de facto 32-bitowe (dla d>2^31 jest zero, a dla d<2^31 wykonujemy dzielenie 32-bitowe).

[sesef]

przy 32bitowym two63 nie powinno być problemów chyba, że znowu się znajdzie coś o czym w tej chwili nie wiem.

Najpierw jednak muszę na GPU przenieść ify bo jak na razie leżały sobie na CPU, a na GPU tylko sito było liczone. Teraz nastał pewien problem

for(b=0;b<64;b++)
{
   if((val>>b)&1)
   {
      ...
   }
}

Przy naszych liczbach ile razy w tej pętli może if okazać się prawdziwy? Wszystkie testy robię dla K=366384 i są przypadki, że przechodzi po 2x, tak jest szansa, że przejdzie tego ifa 3x albo 4x lub więcej?

[Jarek Wróblewski]

Sito i PrimeQ to są dwie dość niezależne rzeczy, więc można przetestować na grafie samo PrimeQ - do takiego testu nadaje się test31.c.

Co do sita, to ja nad tym jeszcze poważnie nie myślałem, ale być może da się je inaczej zorganizować.

Jeśli chodzi o cytowanego przez Ciebie if-a, to z grubsza raz na 7500^n pętli będzie prawdziwy n+1 razy.

Lub inaczej:

Pętli w każdym K powinno być ok. 47,000,000.

2 x zdarzy się ok. 18,000 razy w każdej próbce (ok. 6,000 razy w każdym K).

3 x zdarzy się średnio 2.5 raza w każdej próbce (mniej niż raz w każdym K).

4 x zdarzy się średnio raz na 3,000 próbek.

5 x zdarzy się średnio raz na 22,500,000 próbek - zakładając, że AP26 będzie trwać np. 30,000,000 próbek, 5 x w jednej pętli trafi się może raz albo dwa, a szanse na wystąpienie 6x są mniejsze niż 0.02%, czyli na 99.98% 6x się nigdy nie pojawi.

Liczby, które podaję powyżej, mogą nie być dokładne, ale powinny mieć właściwy rząd wielkości - jeśli gdzieś nie popełniłem błędu w obliczeniach, to raczej nie mylę się więcej niż o czynnik 2. Jeśli zliczysz wszystkie pętle dla testowego K oraz pętle z 2x, będziesz wiedział, w którą stronę i o ile się mylę.

[sesef]

Czy ten PrimeQ_gen31 ma działać tylko dla jakiś zakresów konkretnych? W ramach testów dałem n = 37814740008933888LL; co przy pierwszym wykonaniu pętli powinno dać 25 wyraz najnowszego AP25, a jednak liczba nie została uznana za pierwszą, przy oryginalnym PrimeQ_gen poszło bez problemów. W kodzie nic nie zmieniałem, odpaliłem wszystko tak jak było na CPU tylko liczbę dałem inna.

Edit

Sprawdziłem jedną rzecz, zamieniłem to dzielenie całkowite na dzielenie zmiennoprzecinkowe

float q1f = (float)two63 / (float)anc;
float q2f = (float)two63 / (float)d;

Wyniki wystarczy zaokrąglić w dół (tyle GPU potrafi na typach float, więc nie będzie problemów) i jest taki sam jak przy dzieleniach całkowitych.

[Jarek Wróblewski]

PrimeQ-gen31 będzie działał dla wszystkich zakresów, jeżeli w linijce:

Kod [Zaznacz] Rozwiń


   } while (p<=122);
   
// instead of 122 take 62+number_of_significant_bits_of_d


dokona się odpowiedniej korekty. W tym celu należy wyznaczyć liczbę bity taką, że
2^(bity-1) < d < 2^bity
a następnie zamiast 122 umieścić 62+bity

Ja na szybko robiłem wersję, która miała sprawdzić, czy to w ogóle pójdzie, więc wpisałem ręcznie liczbę odpowiednią do danych testowych. Liczby w moim teście były 60-bitowe.

Liczba, którą podajesz, jest 56-bitowa, więc dla celu testów możesz zmienić 122 na 118. Ale na poważnie, to trzeba w programie bity wyliczyć w zależności od d.

[Jarek Wróblewski]

Sprawdziłem jedną rzecz, zamieniłem to dzielenie całkowite na dzielenie zmiennoprzecinkowe

float q1f = (float)two63 / (float)anc;
float q2f = (float)two63 / (float)d;

Wyniki wystarczy zaokrąglić w dół (tyle GPU potrafi na typach float, więc nie będzie problemów) i jest taki sam jak przy dzieleniach całkowitych.

Ale tu jest wredna pluskiewka. Otóż liczby anc i d na ogół są dość losowe, czyli duże. Ilorazy są stosunkowo małe, więc floaty są zazwyczaj wystarczająco dokładne, aby pamiętać zaokrąglenia (tych małych liczb) w odpowiednia stronę. Boję się, że jeśli anc i d będą małe, wyniki mogą być dość losowe. Będzie też problem, gdy ilorazy będą bardzo bliskie liczbie całkowitej - float nie spamięta wystarczającej dokładności, aby zaokrąglić w odpowiednią stronę. To się zdarzy niesłychanie rzadko, niemniej jednak jest to pluskwa, bo program nie zadziała poprawnie dla wszystkich możliwych danych. Spróbuj wypisać takim programem liczby pierwsze z przedziału 100-200. Boję się, że nie będzie żadnej, bo obliczenia się losowo zwichrują.

Iloraz two63/d może w tej metodzie być błędnie liczony zarówno dla małych d, jak i dla takich d, że two63/d jest prawie całkowite i małe, np. dla d około two63/3, two63/5.

Ponadto nie wykluczam, że PrimeQ-gen31 będzie działać szybciej - dla testów prędkości trzeba zwiększyć przedział testowy, a znalezionych liczb pierwszych nie wypisywać, tylko zliczać. Chociaż najprawdopodobniej różnica prędkości nie będzie zauważalna, bo getMagic zabiera stosunkowo mało czasu w stosunku do całego testu pierwszości.

[sesef]

Teraz zaczynam się zastanawiać jaki sens ma to dzielenie uint64_t q2 = two63/d; skoro d będzie >32bit chyba, że w AP mogą się trafić liczby pierwsze <=32bit

[Jarek Wróblewski]

Teoretycznie mogą być wyrazy mniejsze od 2^32, ale nie jest znany żaden AP21 lub dłuższy o wyrazie mniejszym niż 2^32.

Jednak boję się, że mogą być takie wredne d>2^32, dla których to dzielenie przez floaty da zły wynik. Nie ma też specjalnej kontroli nad dzieleniem przez anc.

Chyba najbezpieczniej będzie dopracować wersję z PrimeQ-gen31.

Jak będę miał chwilę czasu, to spróbuję to zrobić i pomyślę o jakichś optymalizacjach.

[Jarek Wróblewski]

W katalogu
http://www.math.uni.wroc.pl/~jwr/cuda/PrimeQ_gen/
jest druga wersja PrimeQ_gen31 wraz z programem testującym prędkość.

Jeśli wyśledzisz, że test.c oraz test31v2.c produkują inne wyniki, daj znać - dla wszelkich sensownych danych powinny działać tak samo.

Na oko działają tak samo szybko - superdokładnych testów nie robiłem. W argumencie podajemy liczbę parzystą.

[Jarek Wróblewski]

W tym samym katalogu wersja trzecia - powinna być nieco szybsza.

[sesef]

Częściowo już na gpu kod napisałem, funkcja getMagic będzie wyglądać tak:

void getMagic(uint2 d, uint2 *pMagic, uint *pShift)
{
   uint two63 = 0x80000000;

   uint p = 31;          
   uint q2 = 0;
   uint r2 = two63;
   if(d.x == 0)
   {
      q2 = two63/d.y;
      r2 = r2 - q2*d.y;
   }
   uint2 q2a = uint2(0, q2);
   uint2 r2a = uint2(0, r2);
   uint bits = 62;
   uint check = 0;

   if(d.x == 0)
      check = d.y;
   else
   {
      check = d.x;
      bits += 32;
   }

   while (check)
   {
      bits++;
      check >>= 1;
   };
   

   do
   {      
      q2a = ShiftLeft1bit(q2a);
      r2a = ShiftLeft1bit(r2a);

      if(CompareLess(d, r2a))
      {
         r2a = sub(r2a, d);
         q2a = add2(q2a, 1);
      }
      p++;
   } while(p <= bits);


   *pMagic = add2(q2a, 1);

   *pShift = p - 64;
}

uint2 jest to typ wektorowy dostępny na kartach ati składa się po prostu z 2 liczb uint x i y. Jak nie będzie jakiś przeciwności to jutro będzie można już protestować prędkość i popróbować jakiś optymalizacji.

[sesef]

Jak na razie wszystko mam przepisane na GPU, i prawie działa, ale nie do końca. Gdzieś musi być jeszcze błąd bo podaje tylko część wyników

1000000000000000009
1000000000000000031
1000000000000000079
1000000000000000177
1000000000000000183
1000000000000000201
1000000000000000371
1000000000000000449
1000000000000000491
1000000000000000563
1000000000000000583
1000000000000000695
1000000000000000799
1000000000000000841
1000000000000000913
GPU time: 0.524404
Aby kontynuować, naciśnij dowolny klawisz . . .

[Jarek Wróblewski]

Rozumiem, że CPU i GPU dają inne rezultaty.

No to trzeba wyśledzić, gdzie obliczenia CPU i GPU się rozjeżdżają.

Na końcu getMagic trzeba wydrukować *pMagic oraz *pShift

Na końcu mulmod trzeba wydrukować r

Trzeba porównać wyniki drukowane przez CPU i GPU.

getMagic i mulmod nie mają prawa zwracać innych wyników na GPU niż na CPU - obliczenia muszą przebiegać identycznie.

Dla każdej testowanej liczby pierwszej będzie drukowanych kilkadziesiąt liczb, więc trzeba wybrać jedną liczbę, dla której test pierwszości na CPU i GPU wypada inaczej, i uruchomić śledzenie dla tej liczby.

[sesef]

Trochę czasu spędziłem nad tym i jak zwykle szukałem w złym miejscu :(

Okazało się, że ATI ma chyba problem z warunkiem >= w pętli.

w psp2 jest pętla

for (i=62;i>=0;i--)

normalnie dla CPU kończy się ona z i = -1 jednak na GPU jest inaczej bo kończy się z i = 0. Przy debugowaniu wszystko było normalnie bo wszystko jest liczone na CPU, a normalny program jak był odpalany na GPU to już był problem z tą pętlą.

Prosta modyfikacja na:

for (i=62;i>=-1;i--)

I wszystko pięknie śmiga :) Biorąc pod uwagę, że całe sprawdzanie pierwszości to jakieś 400 linijek kodu to nigdy bym się nie spodziewał, że błąd będzie akurat w tym miejscu.

[Jarek Wróblewski]

To zaskakujące, że tak proste elementy, jak ta pętla, nie przenoszą się bezpośrednio na GPU.

Najważniejsze, żeby program produkował poprawne wyniki.