AP26 search

[sesef]

Wie ktoś jakie taktowanie ma taki Cell?

http://www.primegrid.com/show_host_detail.php?hostid=108301

Liczy szybciej niż XQ9650 Erniego.

[Troll81]

z tego co wiem to 3,2Ghz

[sesef]

Już się wyjaśniło, nie jest podawany pełny czas przeliczania próbki. Całkowity czas jest ~2h

[Jarek Wróblewski]

Po przeszukaniu wyników zebranych w trakcie AP26 Search okazało się, że jakiś czas temu pobite zostały rekordy AP22 i AP23 w kategorii: AP o najmniejszym znanym wyrazie początkowym.

Gratulacje dla sosnahojna torun - nowego rekordzisty AP22 w tej kategorii.

Ogłoszenie PrimeGrid'a znajduje się w poście:
http://www.primegrid.com/forum_thread.php?id=1246&nowrap=true#15859

Rekord powinien się niedługo pojawić w tabeli:
http://users.cybercity.dk/~dsl522332/math/aprecords.htm#minimalstart

[Troll81]

juz tyle rekordów pobilim że nie zauważamy nowych??

[stn]

Wiadomo czy trwają jakieś próby do zaimplementowania AP26 w CUDA?  Chętnie użyczyłbym moją grafe.

[Jarek Wróblewski]

Wiadomo, że w przewidywalnej przyszłości nie będzie AP26 na grafę :(

Z grafami jest następujący problem. To jest technologia w powijakach. Trzeba dużo samozaparcia i wiedzy, żeby coś na grafę zaimplementować. Z drugiej strony to daje pewne fory w BOINC, bo jest mało programów na grafy, więc jak ktoś ma projekt liczący na GPU, to gromadzi sporo liczących.

Główna bariera to brak gotowych procedur liczących na grafach w precyzji wystarczającej dla projektów typu AP26. CUDA/nVidia obsługuje arytmetykę 32-bitową, a tu trzeba większej precyzji (64 i więcej). Nie jest jasne, jaka byłaby wydajność takich obliczeń większej precyzji wydziubanych przy pomocy operacji 32-bitowych.

Ja się coś staram z kilkoma studentami tu zrobić, ale brak czasu mojego i ich powoduje, że idzie to dość wolno. Jednak pierwsze testy prędkości są obiecujące - na programie testowym, który używał tylko operacji 32-bitowych, grafa dawała kilkudziesięciokrotne przebicie. Za przejście do wyższej precyzji zapłaci się słono wydajnością, ale jeszcze powinno coś z tego przebicia zostać. Być może w perspektywie kilku miesięcy uda nam się zmontować procedury umożliwiające pisanie programów.

Kolejną barierą będzie wówczas stworzenie sensownego programu. Nie jest prawdą, że można wziąć program na CPU i po prostu przepisać go na GPU. To jest nieco inna filozofia programowania i trzeba w dużej mierze napisać program od nowa - oczywiście opierając się na podobnym algorytmie i wykorzystując pewne kawałki kodu.

Po przejściu tych barier można byłoby otrzymać program działający na lokalnym komputerze i wówczas kolejnym problemem do rozwiązania byłoby zaadaptowanie tego do BOINC. Niby standard, ale trzeba to umieć - pamiętajmy, że AP26 jest dostępny pod Windows dzięki sesefowi - administratorzy PrimeGrida nie mieli w tym względzie doświadczenia i nie byli w stanie dokonać sprawnej kompilacji. Z drugiej strony AP26 jest jedynym podprojektem PrimeGrida, który doczekał się wersji na Mac OS (czy tu siedzi Darwin 9.7.0, na którym Worldwide Center of Mathematics za parę dni wskoczy na 3-cie miejsce w AP26?). Podejrzewam, że problemem jest kompilacja. Profesjonalne programy przeważnie są pisane w asemblerze i pewnie ciężko się je przenosi z systemu do systemu, natomiast AP26 jest głównie w gołym C i tu jest łatwiej - tak to sobie wyobrażam, ale mogę się mylić.

Podsumowując: W perspektywie kilku miesięcy AP26 na grafę nie ma szans. A co dalej, nie wiadomo.

[AiDec]

Zatem Jarku powinniscie (Ty i Twoj zespol) wciaz kontynuowac wspolprace z Sesefem, a do tego jeszcze z TJM. Sesef i TJM pracuja z kolei nad Enigma-CUDA. Sadze ze taka wspolpraca moze Wam wyjsc na dobre, a jedyne nad czym sie zastanawiam, to czy spolka Sesef-TJM pomoze wiecej Wam, czy Wasz zespol spolce S-T  ;D.

[stn]

A ma ktoś jakiś pomysł jak wykorzystać AP26 np. w kryptografii?

[sesef]

Zatem Jarku powinniscie (Ty i Twoj zespol) wciaz kontynuowac wspolprace z Sesefem, a do tego jeszcze z TJM. Sesef i TJM pracuja z kolei nad Enigma-CUDA. Sadze ze taka wspolpraca moze Wam wyjsc na dobre, a jedyne nad czym sie zastanawiam, to czy spolka Sesef-TJM pomoze wiecej Wam, czy Wasz zespol spolce S-T  ;D.

Łatwiej będzie przenieść sito z AP26 (tylko przenoszenie sita ma sens) na GPU niż coś z Enigmy. Enigma niby nie będzie wymagała 64 bitowych liczb więc nie trzeba się bawić w emulacje 2x 32 bit, ale sam algorytm jest bardziej skomplikowany do tego najpierw trzeba zrozumieć algorytm dopiero potem zacząć myśleć nad napisaniem czegoś.

@stn na kryptografie to tutaj są za małe liczby

[Jarek Wróblewski]

A ma ktoś jakiś pomysł jak wykorzystać AP26 np. w kryptografii?

Nie ma takiej opcji. W kryptografii można wykorzystać liczby pierwsze, które:
1. Mają po kilkaset cyfr.
2. Nigdzie nigdy nie były publikowane.

Generowanie liczb pierwszych dla potrzeb kryptografii nie jest żadnym wyzwaniem obliczeniowym - przetestowanie pierwszości liczby np. 400-cyfrowej zajmuje rzędu 2 milisekund - żeby trafić na liczbę pierwszą, trzeba przetestować kilkaset kandydatów, więc liczbę pierwszą odpowiedniej wielkości znajdujemy w czasie poniżej 1 sekundy. Do stworzenia klucza RSA potrzebne są dwie liczby pierwsze, więc to jest kwestia najwyżej paru sekund.

Liczby pierwsze znajdowane przez PrimeGrid, zarówno te mające ponad milion cyfr, jak i te kilkunastocyfrowe znajdowane przez AP26 Search, w kryptografii bezpośrednio się nie przydadzą.

[Jarek Wróblewski]

Łatwiej będzie przenieść sito z AP26 (tylko przenoszenie sita ma sens) na GPU niż coś z Enigmy. Enigma niby nie będzie wymagała 64 bitowych liczb więc nie trzeba się bawić w emulacje 2x 32 bit, ale sam algorytm jest bardziej skomplikowany do tego najpierw trzeba zrozumieć algorytm dopiero potem zacząć myśleć nad napisaniem czegoś.

No nie wiem. Rozumiem, że chciałbyś robić sito na grafie, a testowanie pierwszości na procku. No więc ja tu widzę potencjalnie dwa duże problemy:

1. Komunikacja grafy z prockiem może zeźreć tyle czasu, że cały interes będzie nieopłacalny - tylko gdybam, bo oczywiście tego nie wiem.

2. Jeśli istotną część obliczeń wykonuje procek, a część grafa, to jedno nie będzie nadążało za drugim. Stosunek wydajności grafy do procka dla różnych komputerów może przyjmować tak różne wartości, że trudno będzie to uniwersalnie zsynchronizować.

Oczywiście sito też używa 64 bitów, ale to jeszcze można próbować obejść w samym kodzie programu - jednak bardzo istotnie go zmieniając - w tej chwili trudno mi powiedzieć jaka byłaby cena wydajności. To akurat nie jest problem, bo cokolwiek się będzie chciało robić na grafie, to trzeba tam wsadzić sito, więc to tak czy siak trzeba kiedyś zrobić.

Inny problem: AP26 większość czasu spędza w sicie, ale inne podobne programy mają odwrotne proporcje - większość czasu zajmuje im testowanie pierwszości - tam przeniesienie samego sita na grafę niewiele by dało.

Pytanie: Czy masz jakąś działającą platformę testową (możliwość kompilacji i uruchamiania programu na GPU - niekoniecznie CUDA)?
Bez tego trudno cokolwiek poważnie zaczynać.

[sesef]

Łatwiej będzie przenieść sito z AP26 (tylko przenoszenie sita ma sens) na GPU niż coś z Enigmy. Enigma niby nie będzie wymagała 64 bitowych liczb więc nie trzeba się bawić w emulacje 2x 32 bit, ale sam algorytm jest bardziej skomplikowany do tego najpierw trzeba zrozumieć algorytm dopiero potem zacząć myśleć nad napisaniem czegoś.

No nie wiem. Rozumiem, że chciałbyś robić sito na grafie, a testowanie pierwszości na procku. No więc ja tu widzę potencjalnie dwa duże problemy:

1. Komunikacja grafy z prockiem może zeźreć tyle czasu, że cały interes będzie nieopłacalny - tylko gdybam, bo oczywiście tego nie wiem.

2. Jeśli istotną część obliczeń wykonuje procek, a część grafa, to jedno nie będzie nadążało za drugim. Stosunek wydajności grafy do procka dla różnych komputerów może przyjmować tak różne wartości, że trudno będzie to uniwersalnie zsynchronizować.

Oczywiście sito też używa 64 bitów, ale to jeszcze można próbować obejść w samym kodzie programu - jednak bardzo istotnie go zmieniając - w tej chwili trudno mi powiedzieć jaka byłaby cena wydajności. To akurat nie jest problem, bo cokolwiek się będzie chciało robić na grafie, to trzeba tam wsadzić sito, więc to tak czy siak trzeba kiedyś zrobić.

Inny problem: AP26 większość czasu spędza w sicie, ale inne podobne programy mają odwrotne proporcje - większość czasu zajmuje im testowanie pierwszości - tam przeniesienie samego sita na grafę niewiele by dało.

Pytanie: Czy masz jakąś działającą platformę testową (możliwość kompilacji i uruchamiania programu na GPU - niekoniecznie CUDA)?
Bez tego trudno cokolwiek poważnie zaczynać.

Tak testowanie pierwszości zostawiłbym prockowi GMP sobie dobrze z tym radzi. Co do samego sita mamy przykładową próbkę AP26 czyli te 3 liczby k najpierw odpalane są procedury które będą liczyć na gpu czyli w naszym wypadku sito. GPU sobie mieli i po przejściu zadanego zakresu zostawi potencjalne liczby pierwsze (ja to tak rozumiem) które zostaną przesłane na CPU żeby sprawdził sobie ich pierwszość i wybrał z tego, te które pasują do AP. Podczas sprawdzania pierwszości GPU by się nudziło, bo jakby się chciało sprawdzać podczas pracy GPU już pierwszość liczb to za dużo czasu schodziłoby na inicjowanie komunikacji CPU->GPU i te sprawy najlepiej przesłać wszystko na raz. Tylko w takim wypadku trzeba przemyśleć dokładność takiego sita, bo żeby w przypadku zbyt małej dokładności nagle tych liczb do sprawdzenia nie zrobiło się 100-150 MB, a w przypadku zbyt dużej niewiele się zyska na użyciu GPU.

Co do platformy nie mam w tej chwili żadnej, jednak aplikacje pod CUDA można kompilować w trybie emulowanym gdzie można sprawdzić czy wszystko działa po za oczywiście szybkością, ale myślę że jakby już powstało nawet samo sito to osoby do przetestowania wydajności się znajdą.

Don't have a CUDA-capable GPU board on your PC but still want to try running this program? Easy! Just add the following option to the Custom Build Step command line: -deviceemu. This will link-in a CUDA device emulator that runs on the host. The emulator becomes the target for all the CUDA API calls and executes the kernel. The program will run just like a CUDA device is there, except slower.  (Here is the project file with the -deviceemu option.)

Takie pytanie dla danego K jaki to jest przedział liczb?

[Jarek Wróblewski]

Muszę to sobie przemyśleć. Tak czy siak, na grafie musi być sito, które pluje kandydatami, a co się z nimi zrobi (sprawdzi na bieżąco na GPU, prześle do CPU pojedynczo, na raz, czy w paczkach) to dalsza sprawa.

Przedział liczb jest duży, ponad 10^16, ale bardzo mało z tych liczb jest branych pod uwagę, mniejsza o szczegóły techniczne. W tej chwili nie powiem dokładnie, ale w sekundzie sito wypluwa chyba kilkadziesiąt tysięcy kandydatów - taki jest rząd wielkości. Może grafa wypluje małe kilkaset tysięcy, po 8 bajtów (64 bity) na liczbę, to daje rzędu 1MB danych do przesyłu z każdej sekundy. Do pewnego stopnia to można regulować głębokością odsiewu. Jeśli grafa będzie zbyt wydajna, to nie wiem, czy proc nadąży testować pierwszość. No ale to już czyste wróżenie z fusów, bez testów trudno cokolwiek więcej powiedzieć. W każdym razie głębszy odsiew to więcej pracy dla grafy, a mniej dla proca, więc to się jakoś powinno dać wyregulować i zgrać.

W każdym razie tu trzeba praktycznie zaprojektować od nowa całe sito, czego przed wakacjami nie będę miał czasu zrobić. A co więcej, w tej chwili nie wiem jeszcze, ile bólu przysporzy ograniczenie do operacji 32-bitowych.

[stn]

A wie ktoś coś może o OpenCL? Podobno w tym napisano optymalke pod ATI dla Milky. Różnica pomiedzy 32bitami a 64 bitami na cpu jest jak 1/3 albo 1/,25. Czy karta graficzna poradziłaby sobie z zaimplementowaną własną arytmetyką? Czy w tamtym programowaniu są tablice i wektory? Jeżeli tak to możnaby spróbować jak wyglądałoby sito na GPU. Czy system liczbowy o podstawie np. 10^9 będzie wyglądał po wymnożeniu tak samo jak dziesiętny? Jeżeli tak to teoretycznie taka arytmetyka nie byłaby taka straszna. Wypadałoby przestudiować algorytm AP26 ale obawiam się, że moge wszystkiego nie zrozumieć. Na czym polega sito z AP26?

Jeżeli ja byłbym twórcą takiego algorytmu to wyglądałoby to mniej więcej tak:
Stworzyłbym tablice liczb pierwszych np. z sita Eratostenesa z przedzialu [2...10^16], które każdy otrzymywałby z serwera i obliczał różnice dla danego zakresu, a potem szukal czy wystapily AP. Liczby pierwsze byłyby już zaindeksowane w tablicy, a poszczególne komputery zajęłyby się liczeniem. Tylko nie wiem jak takie coś miałoby działać dla wielu komputerów. Oczywiście pomijam tu wszystkie aparaty matematyczne, bo nie studiowałem matematyki. Teoretycznie możnaby znaleźć jakiś AP metodą brute force.

pierwsze[0..n-1] - n liczb pierwszych
roznice[0][1]=pierwsze[n-1]-pierwsze[n-2] itd.

potem zastosować jakiś algorytm, aby zinterpretować wyniki i gotowe.

[sesef]

Jeśli grafa będzie zbyt wydajna, to nie wiem, czy proc nadąży testować pierwszość.

Tutaj się nie ma czym martwić czy procesor nadąży, nie ma sensu robić tych 2 rzeczy równolegle bo wszystko najpewniej polegnie na komunikacji GPU<->CPU najpierw sito potem przesłanie danych do CPU i dopiero sprawdzanie pierwszości.

To że obecnie dostępne są tylko 32 bitowe liczby nie jest największym problemem, ostatnio czytałem na forum ATI/AMD gdzie ktoś miał pewne problemy z kompilacją programu, który na grafie emulował sobie liczby 512 bit (16x 32bit) tak więc da się to zrobić (przykład liczby 128 bit przy użyciu 2x 64bit na CPU http://svn.gnucash.org/docs/HEAD/group__Math128.html). Bardziej bym się martwił tym jak rozwiązać najlepiej sprawdzanie pierwszości tak żeby nie trzeba było za dużo danych przesyłać, a jednocześnie korzystanie z  sita na grafie było opłacalne.

[Jarek Wróblewski]

Sito z AP26 nie ma nic wspólnego z sitem Eratostenesa. Trudno byłoby wyłożyć jego szczegóły krótko i zrozumiale.

Opis algorytmu AP26 (po angielsku) znajduje się w pliku
http://www.math.uni.wroc.pl/~jwr/AP26/AP26v3.pdf
ale trudno mi wyrokować, na ile jest on strawny.

Jak rozumiem, OpenCL to język programowania, w którym można pisać programy pod grafy różnych typów, co jednak nie rozwiązuje problemu dostosowania algorytmu do możliwości GPU.

W zasadzie widzę tylko jedną drogę do uruchomienia AP26 na grafach. Ja (raczej nikt mnie tu nie zastąpi) musiałbym przeprojektować algorytm na potrzeby GPU. Niekoniecznie napisać gotowy program na grafę, ale dostosować sam algorytm do wymagań i możliwości kart graficznych.

Karta graficzna oczywiście poradzi sobie z zaimplementowaną własnoręcznie arytmetyką, ale stworzenie takiej arytmetyki wymaga czasu, bo potrzeba wielu dość specyficznych operacji, których wydajność jest kluczowa. Nie jest jasne, czy lepiej przeprojektować sito na 32 bity, czy zrobić sobie arytmetykę 64-bitową.

Oprócz arytmetyki kluczowa jest struktura samego programu. Istota wydajności grafów polega na jednoczesnym uruchamianiu dużej liczby wątków jednocześnie. Program, który jednym ciągiem liczy tylko jeden wątek, na grafie nie ma szansy osiągnąć sensownej wydajności. Tu trzeba podzielić obliczenia na masę niezależnych segmentów, które się odpala jednocześnie. To także musi być uwzględnione w czasie projektowania algorytmu.

[Jarek Wróblewski]

Bardziej bym się martwił tym jak rozwiązać najlepiej sprawdzanie pierwszości tak żeby nie trzeba było za dużo danych przesyłać, a jednocześnie korzystanie z  sita na grafie było opłacalne.

I dlatego poważnie rozważam testowanie pierwszości na grafie.

Inny problem, którego się nie przewidzi, a który może zrobić niezłe kuku, jest następujący:

Grafa uruchamia wielkimi paczkami wątki, które liczą to samo na różnych danych. To znaczy wszystkie wątki z paczki wykonują jednocześnie tę samą operację, tylko na różnych liczbach. Sito z AP26 jest na pewnym etapie naćpane IF-ami, co może spowodować, że większość wątków szybciej skończy segment programu i będzie czekać na jedyny wątek z paczki, który przeszedł przez wszystkie IF-y. Jeśli to byłby problem, trzeba byłoby zmienić strukturę programu tak, aby wątki, które skończyły pracę, były oddzielane od tych, które jeszcze pracują. Nie mam bladego pojęcia, czy akurat to będzie problemem, przed napisaniem i uruchomieniem programu nikt tego nie przewidzi.

W sumie morał jest taki: Jest stanowczo za wcześnie, żeby w detalach dyskutować o implementacji AP26 na grafie, najpierw trzeba się nauczyć programować i rozpoznawać różne tego typu pułapki. To jest trochę tak, jak gdyby wejść do świata komputerów działających na trochę innych zasadach i uczyć się niektórych elementów programowania prawie od zera.

[stn]

Może zapytajmy na forum nVidii czy takie zastosowanie grafy ma sens i czy jest w ogóle możliwe. Tam ludzie bardziej w tym siedzą i może powiedzieli by coś sensownego.   http://forums.nvidia.com/index.php?showforum=62

[sesef]

Wracając do przesyłu danych GPU -> CPU trafiłem wczoraj na taki programik http://www.xtremesystems.org/forums/showthread.php?t=225823 patrząc na wyniki myślałem, że będzie to dużo gorzej to wyglądało ale jednak nie. W przypadku 2 MB liczb wypluwanych na sekundę przez sito daje to ~1 GB liczb po 10 min działania sita (taki zakres byłby wystarczający dla GPU nie za mały żeby zbytnio serwera nie obciążać i nie za duży żeby nie trzeb było dużo wysyłać) Przesłanie tego z powrotem do CPU powinno zająć nie więcej niż 10 sec co jest przyzwoitym wynikiem.

Jakoś w lipcu będę planował zakup Radeona 4770 to wtedy będę mógł zrobić dokładniejsze testy.

[stn]

http://www.primegrid.com/results.php?hostid=113211 Ktoś napisał AP26 na PS3

[Troll81]

??? jak to??

[sesef]

??? jak to??

Można liczyć na PS3, liczy po 6 WU na raz na 1 rdzeniu albo na całości przez jakieś 2,5h (tye trwa policzenie 1 WU ale mozna odpalic wiele na raz)

[Troll81]

powoli konsole zaczynają wchodzić do świata BOINC :D MOże pojawi się AP26 na graficzne :D

[sesef]

powoli konsole zaczynają wchodzić do świata BOINC :D MOże pojawi się AP26 na graficzne :D

Pojawi się jak Pan Jarek wymyśli sito równoległe.

[sesef]

mamy kolejny 11 już AP24, ciężko widzę u jakiegoś liczydłowego B@P za dużo osób liczy AP26 :D

[Jarek Wróblewski]

Nowym rekordzistą (największy znany AP24) jest AF>XTBA Pitheque z zespołu L'Alliance Francophone.

[sesef]

Następny 12 AP24, widać jakoś seriami się pojawiają teraz czas na nowe AP25

[Troll81]

to wrzućcie newsa jeśli to nasz teamowicz :D

[Jarek Wróblewski]

Nie, to nie nasz timowicz  :(

[sesef]

kolejne AP24 :)

[Jarek Wróblewski]

to wrzućcie newsa jeśli to nasz teamowicz :D

A tym razem to nasz timowicz  :) :) :)

Szczere gratulacje, bo z taką liczbą przeliczonych próbek, nowe AP24 należało się mindcowi jak psu buda  :D

Niestety, tym razem to nie jest rekord, po prostu nowy AP24.

Aj... Na forum PrimeGrida jest: 24052 (unable to contact user...email returned)

[sesef]

Kolejny AP24, tym razem szczęśliwcem nie jest nasz timowicz.

[Troll81]

wynik meczu się wyrównuje

[Jarek Wróblewski]

wynik meczu się wyrównuje

No, niestety, statystyki liczby przeliczanych obecnie próbek są nieubłagane  :(
A to w dłuższej perspektywie musi sie przełożyć na wynik meczu  :(

W/g stanu na 1 maja 2009:
1,300,274 próbek przeliczonych przez cały AP26 Search
BOINC@Poland 805,808 = 61.97%

W/g stanu na 9 lipca 2009:
2,632,259 próbek przeliczonych przez cały AP26 Search
BOINC@Poland 1,170,880 = 44.48%

Przyrost od 1 maja do 9 lipca:
1,331,985 próbek przeliczonych przez cały AP26 Search
BOINC@Poland 365,072 = 27.41%

[Troll81]

najwyższy czas żeby AP26 zostało projektem miesiąca :D

[KrzychuP]

najwyższy czas żeby AP26 zostało projektem miesiąca :D

pewnie jeszcze nie w sierpniu, ale na wrzesień czemu nie

[AiDec]

Nie narzekaj Jarku - te statystyki pokazuja Ci ze juz nie tylko B@P jest zainteresowane liczeniem w Twoim projekcie :). A faktem jest ze wystarczy zrobic PrimeGrod projektem miesiaca (stawiam na wrzesien) i podbijemy staty odrobinke :).

[sesef]

w tym miesiącu jest 24 godzinny wyścig w AP26 więc jak się sprężymy to trochę podbijemy.

[sesef]

Kolejny AP24, na razie szczęśliwiec nie został jeszcze podany.

Ehh to już 4 AP24 w przeciągu niecałych 2 tygodni.