[Pomysł] Tworzenie projektu na GPU

[Troll81]

Po wczorajszym spotkaniu grupy wrocławskiej, doszliśmy do wniosku, że warto by spróbować popracować nad algorytmami przeznaczonymi pod GPU. Zarówno Pan Jarek Wróblewski jak i jego studenci, odjęli pierwsze próby stworzenie czegoś co mogłoby wykorzystać moc GPU. A OxyOne i ja zaoferowaliśmy współpracę w takim zakresie w jakim tylko będziemy mogli być pomocni. Przy odrobinie szczęścia udałoby się może stworzyć coś pożytecznego :D Ten wątek powstał po to by śledzić postępy prac oraz by dyskutować swobodnie na temat tworzenia programów na GPU.

[sesef]

A o jak dużych liczbach w ogóle myślimy?

[Troll81]

64bit powinno wystarczyć z tego co wspominał Pan Jarek Wróblewski

[Jarek Wróblewski]

A o jak dużych liczbach w ogóle myślimy?

Jeśli idzie o samo sito, to myślę, że jest szansa to upchnąć na operacjach 32-bitowych, tylko muszę je nieco inaczej skonstruować.

Problem dotyczy bezpośredniego testowania pierwszości. Jeżeli nie chcemy tego przesyłać do CPU, tylko testować na grafie, to do testowania pierwszości liczb 64-bitowych jak w AP26, potrzeba operacji na liczbach 128-bitowych. Gdyby chcieć w przyszłości używać grafy do nieco innych pokrewnych problemów, może się pojawić potrzeba testowania pierwszości liczb większych, np. 96-bitowych, ale raczej nie wyobrażam sobie wyjścia w przewidywalnej przyszłości poza liczby 128-bitowe, do testowania których wystarczą operacje 256-bitowe. Myślę, że na tę chwile można spokojnie założyć, że testujemy pierwszość liczb 64-bitowych (lub 61-62 bitowych, jeśli to w czymś pomoże).

Jedyna skomplikowana operacja, której faktycznie potrzebujemy do skonstruowania testu pierwszości, to
mulmod(a,b,p)
która dla 64-bitowych a,b,p daje (a*b)%p

128 bitów pojawia się w trakcie obliczeń, ale zarówno argumenty a,b,p jak i wynik to liczby nieujemne 64-bitowe.

[Troll81]

 to jest trochę zasobów co do programowania na GPU Ati

[sesef]

(lub 61-62 bitowych, jeśli to w czymś pomoże).

To akurat nie ma znaczenia bo i tak trzeba emulować 2x 32bit (dla 64bit) i 4x32bit (na 128bit) byleby te liczby złośliwie nie miały 65 bit bo wtedy dochodzi już kolejna zmienna i trzeba albo 3x32 albo 4x32bit co wiążę za sobą więcej operacji.

Z tego co widzę do mulmod trzeba będzie na emulatorze zrobić mnożenie, dzielenie i remainder, w wypadku 64bitowych liczb a i b są tylko 64 bit czy p również?

Może takie trochę głupie przemyślenie, ale nie dałoby rady do tego jakoś użyć liczb zmiennoprzecinkowych double (tylko wtedy ogranicza to ilość modeli kart jakie mogą liczyć)

[Troll81]

dorwałem jeszcze coś takiego

Free – AMD Core Math Library
Many of the applications listed above use common math library functions like BLAS, SGEMM and DGEMM. AMD's Core Math Library (ACML) for the GPU supports these functions today with many more common library functions being ported to the GPU architecture in the coming months. ACML-GPU is freely available by emailing the AMD Stream team at: streamcomputing@amd.com.

może to was wspomoże. Ja jestem programista jak z koziego zadka waltornia...

[sesef]

dorwałem jeszcze coś takiego

Free – AMD Core Math Library
Many of the applications listed above use common math library functions like BLAS, SGEMM and DGEMM. AMD's Core Math Library (ACML) for the GPU supports these functions today with many more common library functions being ported to the GPU architecture in the coming months. ACML-GPU is freely available by emailing the AMD Stream team at: streamcomputing@amd.com.

może to was wspomoże. Ja jestem programista jak z koziego zadka waltornia...

To tylko na liczby rzeczywiste (zmiennoprzecinkowe), dla liczb całkowitych nie działa.

[Jarek Wróblewski]

Wszystkie 3 liczby a,b,p są 64-bitowe.

Czasami ten jeden czy dwa bity mogą być użyte, żeby wygodniej uniknąć przepełnienia.

Co do double, to nie wiem na ile jest to sensowne.

Natomiast remainder można zastąpić odpowiednim mnożeniem, ale to też nie jest banalne. W każdym razie remainder lub jego zastąpienie mnożeniem jest chyba najboleśniejsze do zaimplementowania.

[sesef]

Mam kolejne pytanie co do samego mulmoda ile razy będzie wywoływany przy sprawdzaniu pierwszości? Wystarczy raz czy będzie go trzeba wywołać kilka/kilkanaście/kilkaset razy?

[Jarek Wróblewski]

Mam kolejne pytanie co do samego mulmoda ile razy będzie wywoływany przy sprawdzaniu pierwszości? Wystarczy raz czy będzie go trzeba wywołać kilka/kilkanaście/kilkaset razy?

Będzie wywołany tyle razy, ile bitów ma liczba p, czyli około 60.

Oto przykładowy test pierwszości dla liczb 63-bitowych używający mulmoda i operacji na liczbach 64-bitowych:

// zakladamy, ze p<2^63
int PSPrimeQ(unsigned long long p)
{
unsigned long long out=1;
int i;

for(i=62;i>=0;i--)
{
out=mulmod(out,out,p);
if((p>>i)&(1ULL))
{
out<<=1; // dla p>2^63 tu byloby przepelnienie, ktore w razie potrzeby mozna obejsc
if(out>=p)out-=p;
}
}
return (out==2)?1:0; // 0 oznacza liczbe zlozona, 1 liczbe pierwsza lub pseudopierwsza przy podstawie 2,
// co w praktyce jest rownowazne pierwszosci
}

Jak będziemy mieli funkcję PSPrimeQ, to do reszty (czyli sita) żadna superprecyzja nie będzie potrzebna. Zaimplementowanie powyższej funkcji to wszystko, czego trzeba, żeby na grafie testować pierwszość.

W powyższym kodzie można trochę pooptymalizować - np. kilka początkowych mnożeń (póki są małe liczby) wykonać bez mulmoda, tudzież wywalić ostatnie mnożenie (w razie potrzeby powiem jak), myślę jednak, że w pierwszej wersji liczy się prostota kodu, a nie superoptymalizacja, więc można najpierw zaimplementować powyższe jak jest, a jak będzie chodzić, to dopiero wtedy trochę podcyzelować.

[Jarek Wróblewski]

Samo mnożenie liczb dowolnej precyzji zaimplementowałem kiedyś w oparciu o algorytm z książki Knutha.
Znajduje się ono w pliku mul.h w katalogu http://www.math.uni.wroc.pl/~jwr/cuda/

Jest ono dosyć niezdarne, bo zdaje się, że liczbę trzeba pamiętać w kawałkach 16-bitowych, które być może w pamięci komputera się nie kleją dobrze w większe kawałki - być może trzeba odwrócić kolejność wyrazów w tabeli. Ale powinno liczyć OK.

Co do remaindera, to muszę opracować algorytm wyznaczania go przy pomocy mnożenia przez odwrotność p. Ponieważ w teście pierwszości liczby p mulmod jest wykonywany z tym samym p, to p wystarczy odwrócić tylko raz.
Niby proste w założeniach, ale trzeba być ostrożnym, żeby się wszystkie bity przy zaokrągleniach układały jak trzeba, więc jest trochę żmudnej dziubaniny.

[sesef]

Myślałem czy nie da się zapisać mulmoda jako (a%p)*(b%p), sprawdziłem na liczbach i zdziwiłem się, że to nie działa myślałem, że to %p zostało po prostu "wyciągnięte przed nawias"

Co do mnożenia, to mnożenie liczb 64bit zrobiłem jako zwykłe mnożenie "pod kreską"

            AB
      *    CD
   ----------
     [AD][BD]
[AC][CB]

Gdzie A, B, C, D są 16 bitowymi kawałkami liczb. Przy 128 bitach chcę użyć 32 bitowych kawałków (przy 16bitach tych operacji trochę dużo będzie) i jak na razie mam połowę sukcesu bo tylko połowa liczby się zgadza.

[Jarek Wróblewski]

Zacząłem robić luźne notatki (po angielsku, żeby obcy tez mogli poczytać) dotyczące algorytmu testowania pierwszości przy użyciu operacji 32-bitowych:
http://www.math.uni.wroc.pl/~jwr/AP26/GPU/

[sesef]

Co do remaindera, to muszę opracować algorytm wyznaczania go przy pomocy mnożenia przez odwrotność p. Ponieważ w teście pierwszości liczby p mulmod jest wykonywany z tym samym p, to p wystarczy odwrócić tylko raz.
Niby proste w założeniach, ale trzeba być ostrożnym, żeby się wszystkie bity przy zaokrągleniach układały jak trzeba, więc jest trochę żmudnej dziubaniny.

W czym takie posunięcie ma nam pomóc, i tak dzielenia się nie uniknie.

Co do mnożenia na chwilę obecną wygląda to tak http://www.ee.pw.edu.pl/~jaworows/AP/BigInt.zip myślę że da radę jakoś to jeszcze przyspieszyć.

[Jarek Wróblewski]

Co do remaindera, to muszę opracować algorytm wyznaczania go przy pomocy mnożenia przez odwrotność p. Ponieważ w teście pierwszości liczby p mulmod jest wykonywany z tym samym p, to p wystarczy odwrócić tylko raz.
Niby proste w założeniach, ale trzeba być ostrożnym, żeby się wszystkie bity przy zaokrągleniach układały jak trzeba, więc jest trochę żmudnej dziubaniny.

W czym takie posunięcie ma nam pomóc, i tak dzielenia się nie uniknie.

1. Dzielenie wykonamy raz, tzn. raz obliczymy 1/p, a potem 60 razy użyjemy mulmoda, który dzieleń zawierał nie będzie, ale wykorzysta 1/p.

2. Obliczenie 1/p może być łatwiejsze niż wykonanie dowolnego dzielenia. Także łatwiejsze do zaimplementowania. Postaram się rozpisać szczegółowo algorytm obliczenia 1/p z wymaganą precyzją.

[Troll81]

myślę że niegłupim pomysłem byłoby przyjrzenie się temu pomysłowi

http://www.boincatpoland.org/wiki/12_lipca_2009_Pojawi%C5%82_si%C4%99_nowy_projekt_wykorzystuj%C4%85cy_CUDA

[Troll81]

dla zainteresowanych

Kod [Zaznacz] Rozwiń

http://www.brightsideofnews.com/news/2009/3/22/interview-milkywayhome-meets-the-power-of-graphics.aspx?pageid=1 wywiad z Gipselem ::D kolo ma Polskie nazwisko :D ale można by z nim pogadać :D no i z ludźmi od NV (skoro taki dobry support oferują)

[sesef]

dla zainteresowanych http://www.brightsideofnews.com/news/2009/3/22/interview-milkywayhome-meets-the-power-of-graphics.aspx?pageid=1 wywiad z Gipselem ::D kolo ma Polskie nazwisko :D ale można by z nim pogadać :D no i z ludźmi od NV (skoro taki dobry support oferują)

Support dają doby bo robią dobrą minę do złej gry. OxyOne pokazał już wstępne testy gdzie pół jego karty (albo jak kto woli 1/4 kompa) pogoniła GTX 295.

[Troll81]

Happy Bastille Day! We are now looking at GPU integration for GROMACS. We may need a little help with this integration. Here is a thread I started which includes links to related code. There is a msvc solution for building gromacs and there are various pre-compiled libraries for integrating cuda called OpenMM, read more http://boinc.drugdiscoveryathome.com/forum_thread.php?id=84 

news na stronie drugsdiscovery@home może się wam przydadzą te biblioteki :D

[sesef]

news na stronie drugsdiscovery@home może się wam przydadzą te biblioteki :D

Do ATI się na pewno nie przyda, a jakbym ja miał robić AP27 to NV nie planuje zbyt szybko.

[Jarek Wróblewski]

myślę że niegłupim pomysłem byłoby przyjrzenie się temu pomysłowi

http://www.boincatpoland.org/wiki/12_lipca_2009_Pojawi%C5%82_si%C4%99_nowy_projekt_wykorzystuj%C4%85cy_CUDA

Z punktu widzenia programowania problem Collatza to pikuś. W tym problemie iteruje się operację:
x -> (3x+1)/2
Jedyne, co trzeba zaprogramować, to mnożenie przez 3, dodawanie 1 i dzielenie przez 2.

[OxyOne]

myślę że niegłupim pomysłem byłoby przyjrzenie się temu pomysłowi

http://www.boincatpoland.org/wiki/12_lipca_2009_Pojawi%C5%82_si%C4%99_nowy_projekt_wykorzystuj%C4%85cy_CUDA

Z punktu widzenia programowania problem Collatza to pikuś. W tym problemie iteruje się operację:
x -> (3x+1)/2
Jedyne, co trzeba zaprogramować, to mnożenie przez 3, dodawanie 1 i dzielenie przez 2.

Pan Pikuś

rzeczywiscie takie operacje wykonuje sie w glowie

[Pigu]

jakieś 10lat temu napisaliśmy z braciakiem program który liczył Collatza (jeszcze na celku 466) i z pół roku trwały poszukiwania - naturalnie bez rezultatu %)

jak mniemam celem tego projektu jest obalenie twierdzenia poprzez znalezienie pierwszej liczby która go nie spełnia?

[Jarek Wróblewski]

jak mniemam celem tego projektu jest obalenie twierdzenia poprzez znalezienie pierwszej liczby która go nie spełnia?

Eeehmm... Wątpię. Każdy, kto się trochę poważniej tym problemem pobawił, nabiera przekonania, że twierdzenie jest prawdziwe, aczkolwiek beznadziejnie trudne do udowodnienia. Trudno więc oczekiwać znalezienia kontrprzykładu, bo takowy najprawdopodobniej nie istnieje.

Myślę, że bezpośrednim celem projektu jest znajdywanie rekordowych liczb - takich, od których trzeba wykonać możliwie dużo (w stosunku do rozmiaru liczby) iteracji, aby dojść do liczby 1.

Celem może też być osiąganie wyników w stylu: Hipoteza Collatza jest prawdziwa dla liczb mniejszych od ***.

[sesef]

myślę że niegłupim pomysłem byłoby przyjrzenie się temu pomysłowi

http://www.boincatpoland.org/wiki/12_lipca_2009_Pojawi%C5%82_si%C4%99_nowy_projekt_wykorzystuj%C4%85cy_CUDA

Z punktu widzenia programowania problem Collatza to pikuś. W tym problemie iteruje się operację:
x -> (3x+1)/2
Jedyne, co trzeba zaprogramować, to mnożenie przez 3, dodawanie 1 i dzielenie przez 2.

Pan Pikuś

rzeczywiscie takie operacje wykonuje sie w glowie

Jak potrafisz w miarę szybko zamienić daną liczbę na zapis binarny to wykonanie dzielenia dla liczb o dowolnej długości przez 2 (lub kolejne potęgi 2) jest rzeczywiście proste, a mnożenie dużo łatwiej zaprogramować od zwykłego dzielenia nie mówiąc o dodawaniu.

Mnożenie przez 3 też można łatwo wykonac (x << 1) + x i mamy x pomnożony przez 3. Najtrudniejszy problem dla człowieka to zamienić ten x na zapis binarny bo potem to już chwila moment i jest wynik. W tym wypadku nawet można się pokusić o to żeby wykonać działanie x + x + x bo może być nawet mniej operacji niż przy przesuwaniu bitów.

[OxyOne]

kiedys nie było komputerów kalkulatorów na egzaminie (zreszta które całe zadania licza)

[sesef]

kiedys nie było komputerów kalkulatorów na egzaminie (zreszta które całe zadania licza)

Tak tylko egzamin ma sprawdzić to czy znasz metodę, a nie to czy umiesz wykonać działanie (3x + 1)/2 dla 512 bitowego x no chyba, że to jedyne zadanie na egzaminie to jeszcze można się pokusić o takie coś, ale jestem przekonany, że jakby od siebie nie ściągali to tyle ile osób byłoby na sali tyle byłoby wyników.

[Jarek Wróblewski]

Co do mnożenia na chwilę obecną wygląda to tak http://www.ee.pw.edu.pl/~jaworows/AP/BigInt.zip myślę że da radę jakoś to jeszcze przyspieszyć.

W tym samym stylu postarałem się napisać algorytm wyznaczania odwrotności. Okazuje się, że to jednak wymaga posługiwania się po drodze liczbami 192-bitowymi.

Algorytm obliczania odwrotności jest w pliku Inv.h w katalogu http://www.math.uni.wroc.pl/~jwr/AP26/GPU/

Jeśli dopiszesz brakujące makra, funkcja Inv powinna liczyć odwrotność z właściwą precyzją.

To jest chyba najbardziej upierdliwy kawałek procedury testowania pierwszości, dalej powinno być z górki  :)

[sesef]

Tak na szybko spojrzałem, problemów większych nie powinno być po za jednym.

result.hi.hi=(uint32_t)(9223372028264841216/p.hi);

9223372028264841216/p.hi da rade to jakoś zamienić czy muszę robić dzielenie 64 bit? I nie bardzo rozumiem działanie Fun96(Int96 n); ma policzyć 2^96 - 2n; ?

[Jarek Wróblewski]

Tak na szybko spojrzałem, problemów większych nie powinno być po za jednym.

result.hi.hi=(uint32_t)(9223372028264841216/p.hi);

9223372028264841216/p.hi da rade to jakoś zamienić czy muszę robić dzielenie 64 bit?

Cały dowcip polega właśnie na tym, żeby uniknąć pisania własnego dzielenia. Tu chcemy wykonać dzielenie zmiennopozycyjne z precyzją 32 bitową.

Ja napisałem "9223372028264841216." (z kropką na końcu) i mam nadzieję, że to zostanie wykonane jako działanie zmiennopozycyjne. Chodzi o to, że najpierw trzeba wyliczyć odwrotność p z dokładnością, powiedzmy ok. 30 bitów (ważne, żeby było zaokrąglane w dół).

No więc liczbę 2^63-2^33=9223372028264841216 trzeba zapisać w postaci zmiennopozycyjnej z dokładnością 32 bitów. Mam nadzieję, że napis "9223372028264841216." da taki właśnie efekt, ale może można to uzyskać inaczej.

Tę liczbę należy podzielić przez p.hi (górne 32 bity p) - w dzieleniu wobec zmiennopozycyjnej dzielnej to powinno być automatycznie zamienione na 32-bitową liczbę zmiennopozycyjną.

Następnie zmiennopozycyjny iloraz, który tu jest mniejszy od 2^32, powinien być zamieniony na liczbę całkowitą i wpisany do result.hi.hi (zaokrąglenie jest nieistotne - mieści się w granicach błędu).

I nie bardzo rozumiem działanie Fun96(Int96 n); ma policzyć 2^96 - 2n; ?

Tak, taki dziwoląg się pojawia we wzorze. Przy tym liczba n będzie ciut poniżej 2^95, zatem 2n będzie ciut poniżej 2^96. Tu można w liczbie 2n zmienić wszystkie 96 bitów na przeciwne i dodać 1.

[sesef]

Liczba zmiennopozycyjna to to samo co liczba zmiennoprzecinkowa? Pierwszy raz spotkałem się z tym określeniem zawsze w książkach, artykułach spotykałem się z określeniem zmiennoprzecinkowe (widać w informatyce przyjeło się zmiennoprzecinkowa, w matematyce zmiennopozycyjna), dodatkowo zmylił mnie brak 0 po "." dlatego kropkę uznałem to za literówkę (pozostałość po .hi albo .lo).

Działanie tego typu 9223372028264841216./p.hi owszem da się wykonać tyko teraz powstaje problem jak ma być to dokładne. Tak te liczby będą wyglądać przed dzieleniem

float jest mniej dokładny jednak będzie działać na wszystkich kartach, które umożliwiają liczenie użycie typu double dającego większą precyzje, ale jednocześnie ogranicza ilość kart ma których będzie można uruchomić program, tylko najwyższe serie kart mają zaimplementowaną obsługę double (kart z serii Radeon HD 38xx HD 47xx HD HD48xx)

Przy float błąd będzie większy, przy double mniejszy.

[Jarek Wróblewski]

A w pliku PsPrimeQ.h jest algorytm testowania pierwszości.

Najważniejsze, żeby to w ogóle poszło i dawało poprawne rezultaty. Potem sobie można będzie optymalizować kawałek po kawałku.

[Jarek Wróblewski]

Liczba zmiennopozycyjna to to samo co liczba zmiennoprzecinkowa?

Ja u Kernighana, Ritchie, Język ANSI C, mam float i double opisane jako typy zmiennopozycyjne. Jak zwał tak zwał, chyba nic innego tu nie można rozumieć.

Działanie tego typu 9223372028264841216./p.hi owszem da się wykonać tyko teraz powstaje problem jak ma być to dokładne.

Będzie tak dokładne jak będzie. Cały algorytm obliczania odwrotności składa się z dwóch części:
1. Obliczyć odwrotność z jakąś dokładnością.
2. Zastosować wzorki zwiększające dokładność.

Ja nie żądam jakiejś konkretnej dokładności, ale muszę wiedzieć, z jaką dokładnością mamy do czynienia, bo od tego zależą wzorki zwiększające dokładność.

Pisząc program oparłem się na swojej wyobraźni o dostępnych operacjach i założyłem, że dzielenie 32-bitowe da przynajmniej 30 bitów precyzji.

Jeżeli rzeczywista precyzja będzie inna, to trzeba tylko wiedzieć jaka i program można banalnie poprawić.

Ja nie wiem jaką dokładność ma float, to nawet może zależeć od systemu. Jeśli testy pokażą, że mniejszą niż założyłem, to się zrobi proste poprawki, które to uwzględnią.

[sesef]

wczoraj zacząłem się zastanawiać jak ten program będzie wyglądał na GPU i przyszły mi do głowy dwie koncepcje.

1. Pętlę, które generują liczby zostają na CPU, przy obecnym programie AP26 dla k=366384 jest to ponad 4 mld liczb, więc powiedzmy pętle generowałyby po 80k liczb do puszczenia przez sito. Jak liczby zostaną wygenerowane to przesyłamy je do gpu i na GPU lecą sobie przez sito. W takim rozwiązaniu co te 80k liczb można zrobić checkpoint, więc nie ma problemu z zapisaniem stanu programu, zmienia to jeszcze jedną rzecz do GPU trzeba wysłać informacje o zaalokowanej pamięci na wynik czyli muszę wysłać nie tylko tablice 80k liczb pierwszy (~625 kB), ale również tablice na wynik gdzie będą zapisywane dane, które liczby przeszły przez sito (~80 kB) i przy takim rozwiązaniu nie wiem czy jest sens bawić się z sprawdzanie pierwszości na GPU ponieważ i tak będą dane, które liczby przeszły sito więc po wykonaniu się sita dla tych 80k liczb można na szybko sprawdzić już na CPU te liczby, które przeszły sito bo za wiele ich nie będzie (ile odpadnie z tych 80k? 3/4?) i przejść do generowania kolejnych 80k liczb.

plusy tego rozwiązania:
+ dość łatwo można zrobić checkpointy
+ te 80k liczb można dać jako parametr, który ludzie będą sobie mogli ustawić indywidualnie dla swojej karty. Aplikacje pod GPU ATI odpala się trochę inaczej niż inne aplikacje pod CUDA czy CPU, ponieważ boinc nie obsługuje GPU ATI to trzeba uruchamiać je przez dodanie do aplikacji specjalnie wypełnionego pliku app_info.xml, w którym można ustawić z jakimi parametrami ma wywołać program, więc można zrobić jakieś pseudo ustawienia.
+ zadania nie muszą być długie, 1 zadanie zawierające 4-5 liczb k do sprawdzenia nadal można policzyć również na CPU

minusy:
- teoretycznie większe użycie CPU niż w wypadku 2 koncepcji

2. W tej koncepcji, myślałem nad wrzuceniem prawie całej funkcji "void SearchAP26(int K, int SHIFT)" na GPU. Wtedy dane zadanie zawierałoby 800 liczb k do sprawdzenia i na każdym rdzeniu uruchamiana byłaby jedna liczba k do sprawdzenia. Jednak tutaj pojawiają się 2 problemy pierwszy to brak checkpointów (nie wiem czy GPU podczas liczenia może coś wysyłać do CPU, nawet jak może to pewnie nie będzie to dość proste, a jak na pierwszy program to nie chciałbym się pchać na głęboką wodę), drugim jest to, że tylko najwyższe 3 modele kart maja po 800 rdzeni, poprzednie mają odpowiednio 640 i 320. O ile przy 320 rdzeniach wielkich różnic nie będzie, to przy 640 pojawia się problem, w pierwszym przebiegu na kartę poleci do sprawdzenia 640 liczb, w miarę jak wątki będą się kończyć karta będzie uzupełniać braki, aż osiągnie przydział 800 liczb jednak jak skończy się ta pierwsza seria to na GPU zostanie tylko 160 działających wątków co obciąża tylko 1/4 karty. Dodatkowo przewiduję, że pojedynczy wątek będzie liczył się około 20-30 min więc trochę szkoda na tak długi czas zostawiać obciążone tylko 1/4 katy. Pomysł na rozwiązanie tego problemu może być podobny do tego jak teraz w AP26 są robione checkpointy, dany przedział liczby k zostałby podzielony na mniejsze fragmenty (w 1 fragmencie pętle startowałby od 0, w 2 fragmencie już od jakiejś konkretnej liczby, itd) taki podział skróci czas wykonywania się jednego wątku oraz umożliwi dodanie checkpointów. To na ile fragmentów podzieliłoby się dane K decydowałaby ilość rdzeni karty przykładowo dla 800 rdzeni podział n 1/2/4 lub 8 części, dla 640 podział na 4 lub 8 części dla 320 również na 4 albo 8 części. W tej koncepcji większość operacji odbyłaby się na GPU, łącznie ze sprawdzaniem pierwszości.

plusy:
+ jeżeli MAKES.H będzie 32 bitowe to można je policzyć bez problemów na GPU, wted ilośc danych potrzebnych do wysłania z CPU na GPU byłaby minimalna.
+ teoretycznie mniejsze użycie procesora niż w przypadku pierwszej koncepcji
+ teoretycznie tutaj będzie widać bardzo duże przyspieszenie, najlepsza karta w 20-30 min powinna sprawdzić do 800 liczb K (obecnie najlepszy komputer w primegrid.com składający się z 4 procesorów opteron w ciągu 30 min jest w stanie sprawdzić około 96 liczb K)

minusy:
- przy 800 liczbach w jednym zadaniu, jak ktoś będzie chciał liczyć na CPU to przy słabszych komputerach dość dużo czasu zajmie przeliczenie tych 800 liczb (nawet jak 32bit sito będzie tak samo wydajne jak 64bitowe sito obecnie w AP26 na 64bit maszynie) teoretycznie przy 5 minutach na jedno K daje to prawie 3 dni na policzenie 1 WU. Koncepcja eliminuje praktycznie komputery 1 rdzeniowe i większość tych, które uruchomione są tylko kilka godzin dziennie, bo danie miesięcznego deadline dla przeliczenia zadania, według mnie mija się z celem.

[Jarek Wróblewski]

Ja sobie wyobrażałem, że w jednym momencie będzie liczone tylko jedno K.

To wymaga przepisania sita, ale myślę, że z grubsza wiem jak to zrobić.
Funkcja void SearchAP26(int K, int SHIFT) daje się w naturalny sposób rozbić na praktycznie dowolną liczbę niezależnych funkcji (ta sama funkcja z różnymi parametrami), więc nawet przy jednym K można podzielić obliczenia na tysiące wątków.

Żeby to jednak zrobić, trzeba rozumieć całość algorytmu, no więc to robota dla mnie.

[sesef]

Może głupie pytanie, ale pomoże uniknąć potem szukania głupich błędów.

W Fun96 te 2^96 jest traktowane jako

2^96 = 79 228 162 514 264 337 593 543 950 336
2^96 - 1 =79 228 162 514 264 337 593 543 950 335 (tyle wejdzie maksymalnie wejdzie w zmienną)

Ja jak wiadomo muszę zastosować wersje 2^96-1 bo inaczej dojdzie do przepełnienia i teraz nie wiem czy na końcu dodawać 1 po tym odejmowaniu czy nie.

I jeszcze mam pytanie o Mul192High tutaj mam pomnożyć te górne 96 bit czy wykonać mnożenie 192bit*192bit i dopiero z wyniku takiego mnożenia wyciąć te 96bit

[Jarek Wróblewski]

Może głupie pytanie, ale pomoże uniknąć potem szukania głupich błędów.

W Fun96 te 2^96 jest traktowane jako

2^96 = 79 228 162 514 264 337 593 543 950 336
2^96 - 1 =79 228 162 514 264 337 593 543 950 335 (tyle wejdzie maksymalnie wejdzie w zmienną)

Ja jak wiadomo muszę zastosować wersje 2^96-1 bo inaczej dojdzie do przepełnienia i teraz nie wiem czy na końcu dodawać 1 po tym odejmowaniu czy nie.

I jeszcze mam pytanie o Mul192High tutaj mam pomnożyć te górne 96 bit czy wykonać mnożenie 192bit*192bit i dopiero z wyniku takiego mnożenia wyciąć te 96bit

Fun96(n) ma zwrócić 2^96-2n. Można obliczyć (2^96-1)-2n+1. Można też obliczyć 2*(2^95-n).
Liczbę (2^96-1)-x można obliczyć zmieniając wszystkie 96 bitów liczby x na przeciwne.

Mul192High(a,b) ma zwrócić 192 górne bity 384-bitowego iloczynu a*b.

[sesef]

W końcu znalazłem trochę czasu, żeby znaleźć upierdliwy błąd, który mi się wkradł i dokończyłem implementacje Inv, wyniki jakie otrzymałem dla liczby 62869009767207037 są następujące (w zależności czy przy dzieleniu użyto pojedynczej czy podwójnej precyzji):

195008070949974272295174430164308712609 double
195008071108430597334274514058086358609 float

Tutaj jest source może kod nie jest najpiękniejszy, ale na razie ma tylko działać bo na GPU to będzie całkowicie inaczej wyglądać: http://www.ee.pw.edu.pl/~jaworows/AP/AP27.zip

Mam nadzieje, że to są w miarę poprawne wyniki i nie ma jeszcze jakiegoś skitranego błędu.

[Jarek Wróblewski]

Niezależnie od sposobu liczenia powinno wyjść
195008071104087968748069929440865585042

Natomiast obawiam się, że proponowana przeze mnie procedura testowania pierwszości nie jest najlepsza  :shame:
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.