BOINC@Poland

Cytat: sknd w 28 Maj 2013, 15:16

Cytat: mariotti w 28 Maj 2013, 13:44
Jest nowa wersja programu. Wersji jest kilka, żeby się nie pogubić, nowa dostała numerek 1. W nowej doszło
nowe polecenie, ale z tego co widzę, raczej będzie to niewypał. Za to stare polecenie zostało zmodyfikowane,
czyli inaczej działa:
threadMemPerft depth max_thread hsize hprobe forget

Wcześniej parametr forget mógł przyjmować duże wartości, od 0 do 2^64-1 i trudno było go dobrać.
Teraz sensowe wartości są (prawdopodobnie) w mniejszym przedziale od 20 do 10000.

Na komputerze e3-1230 v2 3.3ghz warto sprawdzić nową komendę z tak dobranymi parametrami, aby
była taka sama ilość pamięci. Czyli np.:

threadMemPerft 10 259200000 8 200
threadMemPerft 10 259200000 8 150
threadMemPerft 10 259200000 8 100

Pozdrawiam i dzięki.

powinno być 5 parametrów, podałeś 4, zdaje się że zapomniałeś o ilości wątków. Mógłbyś mi podać przykładowe wartości tak żeby zajmowało to powiedzmy 6 giga ramu (mam 8 ) ?

aha, i w tabelce jest mały błąd - obliczenia robiłem na tym samym procku - e3-1230 v2  ;)
postaram się wieczorem zapuścić jeden a może i dwa testy zależy o której dotrę do domu...

Wszystko pomyliłem :)

1) Tabelka już poprawiona.
2) W poleceniach faktycznie zabrakło ilości wątków.

Chciałem porównać z sobą skuteczność różnych algorytmów w podobnych warunkach. Czyli
pozostawiamy taką samą ilość wątków, taką samą ilość układów w ram, no i ten sam procesor :)

Poprzedni algorytm (threadMemPerft2 w wersji 0) miał w RAM 32400000 * 8 = 259200000 układów.
Chciałbym zobaczyć jak on wypada w porównaniu z algorytmem threadMemPerft w wersji 1.
Więc takie przykładowe polecenia.
threadMemPerft 10 6 259200000 8 200
threadMemPerft 10 6 259200000 8 150
threadMemPerft 10 6 259200000 8 100


Wersja perft1 jest pod linkiem:
http://www.boincatpoland.org/smf/przetwarzanie-rozproszone/to-co-bawimy-sie-d/?action=dlattach;attach=1310

Pozdrawiam

Cytat: krzyszp w 28 Maj 2013, 09:17
No to kolejny wynik, zwracam uwagę na zmiany w skrypcie startującym testy (ostatnie 3):

Dzięki :)

Wiążę wyniki z poleceniami tak jak poniżej widać. Czyli wygrało 8 6.

mem=5400000
thr=4
depth=9
threadMemPerft2 $depth $thr $mem 8 1 nodes:2439530234167 time:2110
threadMemPerft2 $depth $thr $mem 8 2 nodes:2439530234167 time:2053
threadMemPerft2 $depth $thr $mem 8 3 nodes:2439530234167 time:2027
threadMemPerft2 $depth $thr $mem 8 4 nodes:2439530234167 time:2004
threadMemPerft2 $depth $thr $mem 8 5 nodes:2439530234167 time:1981
threadMemPerft2 $depth $thr $mem 8 6 nodes:2439530234167 time:1977
threadMemPerft2 $depth $thr $mem 8 7 nodes:2439530234167 time:1986
threadMemPerft $depth $thr 10800000 4 1 nodes:2439530234167 time:5148
threadMemPerft $depth $thr 10800000 4 2 nodes:2439530234167 time:5140
threadMemPerft $depth $thr 10800000 4 3 nodes:2439530234167 time:5138



W tych testach było w pamięci 5400000 * 8 = 43200000 układów
Czyli odpowiednik takich komend:


threadMemPerft 9 4 43200000  8 20
threadMemPerft 9 4 43200000  8 50
threadMemPerft 9 4 43200000  8 80
threadMemPerft 9 4 43200000  8 120
threadMemPerft 9 4 43200000  8 200
threadMemPerft 9 4 43200000  8 300


Wcześniej najlepsza była piątka, więc dajmy też do testów piątkę.

Cały skrypt:

#!/bin/sh
(
echo threadMemPerft 9 4 43200000  8 20
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  8 50
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  8 80
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  8 120
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  8 200
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  8 300
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  5 20
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  5 50
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  5 80
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  5 120
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  5 200
echo quit
) | ./perft1 >> out.txt
(
echo threadMemPerft 9 4 43200000  5 300
echo quit
) | ./perft1 >> out.txt


Jeszcze raz wielkie dzięki za testy :)

Nie mam nowych pomysłów na ulepszenie zarządzania pamięcią, więc teraz spróbuję coś
ulepszyć w zarządzaniu wątkami :)

Pozdrawiam

Cytat: sknd w 28 Maj 2013, 13:19

Cytat: mariotti w 27 Maj 2013, 23:25
Czy mógłbyś sprawdzić jeszcze na tej samej maszynie takie polecenie?
threadMemPerft2 10 6 32400000 8 1

zrobione
threadMemPerft2 10 6 32400000 8 1
nodes:69352859712417 time:13085
jak widac czas gorszy troche

Dzięki. Jak na taką skalę obliczeń, to czas wiele gorszy, takie różnice
mogą zadecydować o tym, czy dożyjemy końca czy nie :D

Aktualna tabelka:

-----------------------------------------------------------------------------------------------------------------
Wersja | Procesor               | polecenie                                 | wynik            | czas   | user
-----------------------------------------------------------------------------------------------------------------
   0   | Phenom II 1050T 2.4GHz | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s |
   0   | Phenom II 1050T 2.4GHz | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s |
   0   | Phenom II 1050T 2.4GHz | threadMemPerft 10 8 250000000 8 0         | 69352859712417ok | 30042s |
   0   | i7 950 @3.07GHz        | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s |
   0   | i7 950 @3.07GHz        | threadMemPerft 10 5 450000000 8 1000000   | 69352859712417ok | 12173s |
   0   | Phenom II 1050T 2.4GHz | threadMemPerft 10 8 250000000 8 10000000  | 69352859712417ok | 17768s |
   0   | i7 950 @3.07GHz        | threadMemPerft 10 5 450000000 8 10000000  | 69352859712417ok | 12092s |
   0   | e3-1230 v2 3.3ghz      | threadMemPerft2 10 6 32400000 8 7         | 69352859712417ok | 11709s | sknd
   0   | i7 950 @3.07GHz        | threadMemPerft2 10 5 56250000 8 1         | 69352859712417ok | 13667s |
   0   | Phenom II 1050T 2.4GHz | threadMemPerft 10 8 250000000 8 50000000  | 69352859712417ok | 17781s |
   0   | e3-1230 v2 3.3ghz      | threadMemPerft2 10 6 32400000 8 1         | 69352859712417ok | 13085s | sknd
   0   | Phenom II 1050T 2.4GHz | threadMemPerft 10 8 250000000 12 10000000 | 69352859712417ok | 18111s |
   1   | Phenom II 1050T 2.4GHz | threadMemPerft 10 8 250000000 8 200       | 69352859712417ok | 25889s |
---------------------------------------------------------------------------------------------------------------


Jest nowa wersja programu. Wersji jest kilka, żeby się nie pogubić, nowa dostała numerek 1. W nowej doszło
nowe polecenie, ale z tego co widzę, raczej będzie to niewypał. Za to stare polecenie zostało zmodyfikowane,
czyli inaczej działa:
threadMemPerft depth max_thread hsize hprobe forget

Wcześniej parametr forget mógł przyjmować duże wartości, od 0 do 2^64-1 i trudno było go dobrać.
Teraz sensowe wartości są (prawdopodobnie) w mniejszym przedziale od 20 do 10000.

Na komputerze e3-1230 v2 3.3ghz warto sprawdzić nową komendę z tak dobranymi parametrami, aby
była taka sama ilość pamięci. Czyli np.:

threadMemPerft 10 259200000 8 200
threadMemPerft 10 259200000 8 150
threadMemPerft 10 259200000 8 100

Pozdrawiam i dzięki.

Są dwa nowe testy.

1) Widać że nowy algorytm raczej działa gorzej (i7)
2) Zwiększanie ostatniego parametru z 10mln do 50mln nie zmieniło czasów (Phenom)

Widocznie to pierwsze podejście do zapamiętywania danych jest lepsze niż mi się wydawało :)
Ale i tak będzie jeszcze podejście trzecie.


---------------------------------------------------------------------------------------------------------
Procesor          | polecenie                                 | wynik            | czas   | user
---------------------------------------------------------------------------------------------------------
Phenom II         | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s |
Phenom II         | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s |
Phenom II         | threadMemPerft 10 8 250000000 8 0         | 69352859712417ok | 30042s |
i7 950 @3.07GHz   | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s |
i7 950 @3.07GHz   | threadMemPerft 10 5 450000000 8 1000000   | 69352859712417ok | 12173s |
Phenom II         | threadMemPerft 10 8 250000000 8 10000000  | 69352859712417ok | 17768s |
i7 950 @3.07GHz   | threadMemPerft 10 5 450000000 8 10000000  | 69352859712417ok | 12092s |
e3-1230 v2 3.3ghz | threadMemPerft2 10 6 32400000 8 7         | 69352859712417ok | 11709s | sknd
i7 950 @3.07GHz   | threadMemPerft2 10 5 56250000 8 1         | 69352859712417ok | 13667s |
Phenom II         | threadMemPerft 10 8 250000000 8 50000000  | 69352859712417ok | 17781s |
--------------------------------------------------------------------------------------------------------




Pozdrawiam

Cytat: sknd w 28 Maj 2013, 00:29
sprawdzę, ale to już nie dziś, bo ja jednak jestem z tych, co to im szum kompa przeszkadza przy spaniu  ;)

Rozumiem, bo mnie też kiedyś przeszkadzał. Przyzwyczaiłem się jak sypiałem na biurku w serwerowni :)

Cytat: sknd w 27 Maj 2013, 23:08

Cytat: sknd w 27 Maj 2013, 19:40
zapodałem na próbę na e3-1230 v2 3.3ghz:
threadMemPerft2 10 6 32400000 8 7
niech mieli...

zmielił:
nodes:69352859712417 time:11709

To nowy rekord :) Super, dzięki wielkie.

Uaktualniam tabelkę:

---------------------------------------------------------------------------------------------------------
Procesor          | polecenie                                 | wynik            | czas   | user
---------------------------------------------------------------------------------------------------------
Phenom II         | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s |
Phenom II         | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s |
Phenom II         | threadMemPerft 10 8 250000000 8 0         | 69352859712417ok | 30042s |
i7 950 @3.07GHz   | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s |
i7 950 @3.07GHz   | threadMemPerft 10 5 450000000 8 1000000   | 69352859712417ok | 12173s |
Phenom II         | threadMemPerft 10 8 250000000 8 10000000  | 69352859712417ok | 17768s |
i7 950 @3.07GHz   | threadMemPerft 10 5 450000000 8 10000000  | 69352859712417ok | 12092s |
e3-1230 v2 3.3ghz | threadMemPerft2 10 6 32400000 8 7         | 69352859712417ok | 11709s | sknd
--------------------------------------------------------------------------------------------------------


Czy mógłbyś sprawdzić jeszcze na tej samej maszynie takie polecenie?
threadMemPerft2 10 6 32400000 8 1

Pozdrawiam

Cytat: krzyszp w 27 Maj 2013, 22:37
Ja jednak stawiam na problem z Virtual Box'em - przypominam, że na Q6600 pod Ubuntu, oraz u innych kolegów się nie wywala - ten problem występuje tylko pod VB...

Jeśli się wywala tylko w jednym środowisku, to by dobrze wróżyło - debugowanie może
naprawdę zająć masę czasu i opóźnić start projektu.

Wkrótce wypróbujemy kolejną strategię zarządzania danymi w kliencie, czyli łącznie
sprawdzimy 3 strategie (no, chyba że mi przyjdzie do głowy kolejna). Jeśli program
nie będzie się wywalał, to sprawdzimy go jeszcze na dużej ilości różnych układów.
Jeśli nadal poda dobre wyniki i nie wywali się, to pozostanie optymalizacja. Po
optymalizacji klient będzie gotowy, a właściwie to pozostanie jeszcze przeportowanie
na windowsa.

Potem przyjdzie pora na serwer... Szacuję że serwer będzie musiał podać
100mln zadań i przyjąć tyle samo odpowiedzi. Potem drugie tyle w etapie
weryfikacji - prawdopodobnie jeden klient od razu będzie musiał pobierać
100-1000 zadań żeby nie zajeździć bazy danych na serwerze :) Przypuszczam,
że dla głębokości 14-15 serwer może być wąskim gardłem projektu, dopiero
dla głębokości 16 wąskim gardłem staną się obliczenia na klientach. Istnieje
jeszcze możliwość dostosowania serwera osobno do każdej głębokości...
Możliwości jest sporo :)

Te 100mln to na razie szacunki intuicyjne, za jakiś czas oszacuję
to metodą Monte Carlo. Po szacowaniu MC będziemy wiedzieć bardzo
dokładnie jakie będą wymagania co do serwera i ile obliczeń zajmie
cały projekt.

Małymi kroczkami da się to wydzióbać :)


Pozdrawiam

Cytat: krzyszp w 27 Maj 2013, 20:44
Rozumiem. Po prostu pomyślałem, że chcesz jednym skryptem shella sprawdzić więcej parametrów na tej samej maszynie ;)
No cóż, zobaczymy, czy nie wywali się na mojej maszynie (przypominam, 4GB RAM + trochę roboty w tle).
Próbowałem jeszcze raz odpalić na wirtualce, dając 8 wątków do dyspozycji, niesety, VB się wywala... (Prawdopodobnie mam za mało pamięci, aby to sprawnie obsłużyć i jeszcze pracować na kompie).

Kurcze powinno działać, jak nie działa, to najbardziej sugeruje błąd w moim programie :/

Obecnie mam nadmiernie skomplikowany kod odpowiedzialny za wielowątkowość. Nie dość
że jest skomplikowany, to prawdopodobnie jest wolniejszy niż inny, całkiem prosty algorytm.
Wkrótce zaimplementuję ten prostszy - jak po tym przestanie się wywalać, to sprawa się wyjaśni, a
jak nie, to nie wiem... opracuję kolejne testy i buga w końcu znajdziemy.

Pozdrawiam

Cytat: krzyszp w 27 Maj 2013, 20:05
Ciekawi mnie, że zmieniasz ilość pamięci w przedostatnim poście? Przerobiłem go.sh podając "z palca" 10800000 dla 3 dodatkowych prób...

Ale kto i gdzie zmienia?

Ja mam dwa komputery, jeden mój, a drugi udostępnił mi Rysiu.
Na moim jest mniej ramu, o wpisuję 250mln układów. Na tym od Rysia jest
więcej, to wpisuję 450mln.

Są dwa algorytmy. Był threadMemPerft, a doszedł threadMemPerft2 (dwójka na końcu nazwy).
W drugim algorytmie łączna ilość układów to ilość_paczek * ilosc_układów_w_jednej_paczce.

Przykładowo:
threadMemPerft2 9 4 5400000 8 4
oznacza 5400000 * 8 = 43200000 układów = 1036800000 bajtów ram


threadMemPerft2 9 4 10800000 4 2
oznacza 10800000 * 4 =  43200000 układów = 1036800000 bajtów ram <-- tyle samo


W jednym i  drugim poleceniu jest w pamięci tyle samo układów, ale mocno
zmienia się sposób zarządzania pamięcią. Chodzi o to żeby sprawdzić, czy
lepsza jest większa ilość małych paczek, czy mniejsza większych :D


Parametr ostatni decyduje o zarządzaniu w ramach jednej paczki :)


Pozdrawiam

Doszedł nowy benchmark z phenoma. Wynik poprawny, czas rekordowy jak na ten procesor.
Pomiary czasu są obarczone dużą losowością (algorytm nie jest deterministyczny), ale
raczje już widać, że korzystne wartości dla ostatniego parametru to bardzo duże liczby,
powyżej 1mln.



----------------------------------------------------------------------------------------
Procesor        | polecenie                                 | wynik            | czas
----------------------------------------------------------------------------------------
Phenom II       | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s
Phenom II       | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s
Phenom II       | threadMemPerft 10 8 250000000 8 0         | 69352859712417ok | 30042s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 1000000   | 69352859712417ok | 12173s
Phenom II       | threadMemPerft 10 8 250000000 8 10000000  | 69352859712417ok | 17768s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 10000000  | 69352859712417ok | 12092s
----------------------------------------------------------------------------------------


Pozdrawiam

P.S.
Gdy linux w poleceniu cat /proc/cpuinfo wyświetla że procesor ma 2400MHz, to co to oznacza?
Że w danej chwili procesor ma taką częstotliwość? Czy że w pełnym stresie ma tyle? Mój
Phenom był przetaktowany w dół, bo na pełnej prędkości pobierał nawet 300Wat mocy. Nie
pamiętam już, o ile go spowolniłem. Czy mogę polegać na tych 2400MHz z cpuinfo?

Cytat: sknd w 27 Maj 2013, 19:40
zapodałem na próbę na e3-1230 v2 3.3ghz:
threadMemPerft2 10 6 32400000 8 7
niech mieli...

Dzięki wielkie! To będzie pierwszy głęboki test nowego algorytmu :D
Pozdrawiam

Cytat: Karlik w 27 Maj 2013, 19:33
Tak mi się teraz nasunęło: jak przechowujesz przeliczone hashe? Masz własne drzewo avl lub czerwono-czarne czy korzystasz np. z STLowego?

Przechowywanie układów to kluczowa rzecz dla wydajności (tej liniowej, implementacyjnej).
Jest to bardzo ważne zarówno w tym programie (perft), jak i w docelowym, czyli w szachach
samouczących. Więc nie korzystam z żadnego gotowego rozwiązania - wszystko wyrzeźbiłem
ręcznie sam :D

Generalnie mam ciągłą tablicę układów. Następnie liczę adres w tej tablicy:
adres = hash % (size-probe);
Potem przeszukuję mniej/więcej tak:
for( i=0 ; i<probe ; i++ ) {
  if( tablica[adres+i].key == key )
     return tablica[adres+i].nodes;

Kosz tej operacji to pewnie wczytanie tego kawałka do cache, a czas pętli jest
pewnie pomijalny.

To tak w dużym uproszczeniu, bo opis ze szczegółami zająłby ze 4 strony :D
---------------------------------------------------------------------------------------------------------


W kolejnej wersji będą trzy takie tablice i w każdej inna strategia zarządzania
danymi. Strategia - czyli heurystyczne ocenienie tego, co warto pamiętać, a co
można z pamięci już usunąć.

Z niektórych oszacowań wynika, że dobra strategia zarządzania danymi dla
głębokości 16 może przyspieszyć cały proces nawet milion razy. To by znaczyło
że zadanie da się policzyć w 1 rok na 20-100 nowych komputerach. Oczywiście
mogę się mocno mylić... ale jak się nie mylę, to zaliczymy 3 rekordy pod rząd :D


Pozdrawiam

Jest kolejna wersja programu. Zrobiłem eksperyment z innym algorytmem zarządzającym
pamięcią. Niestety... jak na razie nie widzę wyraźnego przyspieszenia ani spowolnienia, ale
może na większych głębokościach da się dobrać tak parametry aby lepiej działało.

Opis polecenia
Wpisujemy threadMemPerft2 i program wyświetli podpowiedź:

using: threadMemPerft2 depth max_thread cnt_packages pack_size best_size
where:
best_size<pack_size

Znaczenie parametrów:
depth - standardowo głębokość przeszukiwania
max_thread - ilość wątków
cnt_packages - ilość paczek z układami
pack_size - ilość układów w jednej paczce
best_size - ilość układów priorytetowych

Przykłady warte przetestowania dla
głębokości 9, czterech wątków i 1GB ram:

threadMemPerft2 9 4 5400000 8 1
threadMemPerft2 9 4 5400000 8 2
threadMemPerft2 9 4 5400000 8 3
threadMemPerft2 9 4 5400000 8 4
threadMemPerft2 9 4 5400000 8 5
threadMemPerft2 9 4 5400000 8 6
threadMemPerft2 9 4 5400000 8 7

threadMemPerft2 9 4 10800000 4 1
threadMemPerft2 9 4 10800000 4 2
threadMemPerft2 9 4 10800000 4 3

Dla 0.5 GB RAM można trzeci parametr zmniejszyć o połowę.

Pozdrawiam

Cytat: Dario666 w 27 Maj 2013, 14:14
Według mnie optymalną wartością jest 5, bo pierwszy test był wykonywany dla 1, a nie dla 0.  ;D

Racja!

Są kolejne wyniki


----------------------------------------------------------------------------------------
Procesor        | polecenie                                 | wynik            | czas
----------------------------------------------------------------------------------------
Phenom II       | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s
Phenom II       | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s
Phenom II       | threadMemPerft 10 8 250000000 8 0         | 69352859712417ok | 30042s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 1000000   | 69352859712417ok | 12173s
----------------------------------------------------------------------------------------


Niby jest nowy rekord - 12tys sekund. Ciekawy jestem jaka jest losowość tych wyników.
Wątki pracują konkurencyjnie i jeden wątek czasami może zamazać ważne dane dla
drugiego wątku - ale na to też jest pewien sposób, będą kolejne benchmarki :)

Pozdrawiam

Cytat: krzyszp w 27 Maj 2013, 10:11
z Q6600:

Kod [Zaznacz] Rozwiń


threadMemPerft $depth $thr $mem 4 0
nodes:2439530234167 time:5512


Dzięki za kolejny test :D
Czyli optymalna wartość drugiego parametru w tym teście wynosiła 4. Widzę że często najlepszą
wartością jest 4 lub 8. Mam nadzieję że to nie z powodu obciążenia komputera :)
Czy mógłbyś odpalić ten sam skrypt, ale ostatnie zera w komendzie zastąpić np. wartością 10000000 - siedem zer?

Cytat: Dario666
A możesz zdradzić jakie były , a jakie są teraz funkcje skrótu i CRC

Używam kluczy zobrista, ale wcześniej były mniej starannie generowane. Teraz
wygenerowałem całą pulę kluczy kluczy. Każdemu kluczowi dałem wartość 0x555... Czyli
w kluczach jest taka sama ilość zer i jedynek. Potem 10^7 raz zamieniałem z
sobą losowe bity (tzn losowy bit z puli a nie z jednego klucza). Mam dzięki temu
gwarancję idealnego rozkładu równomiernego - właściwie z pewnym małym wyjątkiem,
ale chyba nie ma sensu wdawać się aż w takie szczegóły. Mam pomysł jak zapewnić
aby klucze były jeszcze lepsze, ale to się sprawdzi za jakiś czas.

Funkcja do sprawdzania czy wątki nie psują sobie danych to zwykły xor (czyli tak naprawdę
nie jest to CRC, a tylko pełni taką samą rolę).  Tutaj też jest lepsze rozwiązanie. Zabrzmi to
jak nonsens, ale wartość CRC (tzn jej odpowiednik) może mieć dlugość zero bitów.
Istnieje na to pewien sposób, za jakiś czas będę go też testował i opiszę wyniki.

Dzięki i pozdrawiam

Spiszmy postępy w pracach dotyczących wydajności :)


----------------------------------------------------------------------------------------
Procesor        | polecenie                                 | wynik            | czas
----------------------------------------------------------------------------------------
Phenom II       | threadMemPerft 10 8 250000000 8 1000000   | 69352859710032!  | 63547s
Phenom II       | threadMemPerft 10 8 250000000 1 0         | 69352859712417ok | 41515s
i7 950 @3.07GHz | threadMemPerft 10 5 450000000 8 0         | 69352859712417ok | 21051s
----------------------------------------------------------------------------------------


Tak więc mamy trzeci wynik dla głębokości 10 ruchów i rekordowy czas 21tys sekund.
Zważywszy że ktoś to liczył przez kilkanaście dni, to chyba niezły wynik ;-)
Program się nie wywalił, zakończył się normalnie.

Pozdrawiam

Cytat: Karlik w 26 Maj 2013, 21:43
Ogólnie paradoks urodzin. Nie weryfikowałem obliczeń z wikipedii (nie mam tyle czasu i chęci), ale po podstawieniu do wzoru to żeby prawdopodobieństwo powtórzenia przekroczyło 50% to dla 128-bitowej funkcji skrótu potrzeba 2e+19 układów.

W pamięci komputera mamy jednorazowo małą pulę układów, wynosi ona np. 1E+8.
Nie może być konfliktu w ramach puli, we wszystkich mogą zdarzać się konflikty bez
szkody dla wyniku.
Pozdrawiam

Cytat: krzyszp w 26 Maj 2013, 20:48
Program odpalony za pomocą Twojego skryptu wywala u mnie std:bad_alloc. Po zmniejszeniu przydzielonej pamięci (do 50000000) wystartował, aczkolwiek zakładam znaczne wydłużenie operacji.
Komputer mocno obciążony (akurat wildlife dał próbki), dodatkowo podsystem mocno obciążony operacjami dyskowymi MySQL. Przypominam, że procesor to q6600 na standardowych taktowaniach i Ubuntu64 bit.

Dzięki, zobaczymy czy tym razem obejdzie się bez błędów.
Pozdrawiam

Wcześniej odpaliłem:
threadMemPerft 10 8 250000000 8 1000000
Uzyskałem błędny wynik 69352859710032  w czasie 63547 sekund.


Do programu dodałem (chyba) lepszą funkcję skrótu (nadal 64bity) i
lepszą sumę crc (tą do sprawdzania czy wątki nie zepsuły danych).
Wydałem komendę
threadMemPerft 10 8 250000000 1 0
i uzyskałem tym razem poprawny wynik 69352859712417 w znacznie
szybszym czasie 41515 sekund.

Program u mnie nigdy się nie wywalił, zagadką jest dla mnie, dlaczego
wywala się u Was :/ Myślę że wkrótce się wyjaśni wszystko.

Teraz odpalę takie polecenie:
threadMemPerft 10 8 250000000 8 0
Zobaczymy czy wynik będzie dobry i czy coś przyspieszy

Zachęcam, odpalcie nową wersję u siebie jeszcze raz :)

Pozdrawiam

[edit]
Rozejrzałem się po sieci i widzę że ktoś to zadanie liczył na 4 komputerach w 85h,
ktoś inny w 17 dni. Mój program policzył w 12h, a jest jeszcze przed optymalizacją.

Cytat: Karlik w 26 Maj 2013, 15:44
Zauważ, że jak na razie mówisz, że tak robią programy szachowe i może to być racja, nawet do głębokości tych 9 czy nawet 13 ruchów tak funkcja skrótu może wystarczyć (chociaż ciężko to zwryfikować).

Wszystko się zgadza, ale żeby nasze wyniki były poważnie traktowane, to też musimy się zabezpieczyć
przed osobami, które złośliwie podeślą błędne wyniki. Więc można raz policzyć na funkcji 128
bitowej i drugi raz na zupełnie (naprawdę zupełnie) innej funkcji też o długości 128 bitów. Jeśli
wynik będzie błędny, to jest skrajnie mało prawdopodobne, że błąd na dwóch zupełnie różnych
funkcjach skrótu będzie taki sam. Z tą techniką (chyba) upieczemy pięć pieczeni na jednym ogniu:
1) szybkie porównywanie
2) oszczędność pamięci
3) zabezpieczenie przed nieuczciwymi osobami
4) błąd ram, błąd transferu sieci
5) jest już gotowy program, nie trzeba nic dopisywać.

Cytat: Karlik w 26 Maj 2013, 15:44
Jednak nawet sam wspomniałeś o tym, że to jest drzewo i liczba węzłów rośnie wykładniczo i to bardzo szybko.
Nawet jeśli na każdym kolejnym poziomie będzie 20 razy więcej węzłów to samo zapisanie tego wymaga o 5 bitów więcej, nie wspominając w ogóle o prawdopodobieństwie.

Jak poprawnie oszacować to prawdopodobieństwo...

Przypuśćmy że na depth=16  jest 1E+19 różnych układów, czyli 2^63.
Użyjemy 128 bitów. Czyli jeden układ przypada na 2^65 wartości
funkcji skrótu... niestety w tej chwili nie wiem jak dalej pójść tą drogą, może
ktoś dokończy?

Może inaczej: W komputerze jest zapamiętanych około 10^8 = 2^27 układów. Funkcja
skrótu ma 2^128 wartości. Czyli na jeden wpis w pamięci przypada 2^101 wartości
funkcji skrótu. Czyli prawdopodobieństwo kolizji wynosi 1 / 2^101. Prawdopodobieństwo
braku kolizji to 1 - 1 / 2^101. Chcemy znać prawdopodobieństwo braku kolizji w 2^65
prób. Czyli mamy ( 1 - 1 / 2^101 ) ^ ( 2^65 )
Wolfram twierdzi, że to dziesięć dziewiątek po przecinku.
http://www.wolframalpha.com/input/?i=%281+-+1+%2F+2^101%29^%282^65%29

Do tego każde obliczenia przeprowadzimy dwa razy na zupełnie innych funkcjach skrótu.

Proszę prześledź moje rachunki, może się gdzieś pomyliłem. Ale jak nie znajdziesz
błędu, to znaczy, że tak właśnie zrobimy i każdy będzie nas traktował poważnie.

Cytat: Karlik w 26 Maj 2013, 15:44
Tak więc do 12 poziomu spokojnie może Ci wystarczyć 64 bity na samo zapisanie numeru układu, a gdzie tu mówić o jakimkolwiek porównywaniu? Poza tym komputer do grania nie potrzebuje wiedzy pewnej, jak przeoczy któreś ustawienie to praktycznie nic się nie dzieje, co najwyżej lekko mu spadnie możliwość wygranej, Ty bierzesz się za coś co ma być wiedzą pewną/naukową, tutaj naprawdę każda pojedyncza wartość ma znaczenie jeśli chcesz być brany poważnie (albo inaczej: żeby wyniki ciężko było podważyć).

Jest jeszcze jeden powód z którego będą nas traktowali poważnie. Jeśli 128 bitów okaże się
za mało, to szybko będą wychodziły różne wyniki dla tych samych układów przy użyciu różnych
funkcji skrótu. Od razu wyjdzie że 128 bitów to za mało i zwiększymy do 196 lub 256.

Cytat: Karlik w 26 Maj 2013, 15:44
Do samych obliczeń spokojnie możesz mieć równolegle obie wersje. Zauważ, że w tej chwili bierzesz pod uwagę konieczność wydłużania funkcji hashującej w nieskończoność, więc chyba prościej zapamiętywać cały układ.

Oj nie w nieskończoność. Jeśli dobrze oszacowałem, to 128 bitów da prawdopodobieństwo 99.99999999%, że
wynik będzie poprawny. A my policzymy każdy układ na dwóch różnych funkcjach skrótu.

Cytat: Karlik w 26 Maj 2013, 15:44
Co do ostatniego to jak dla mnie zupełnie bezsensowne sprawdzenie. Żeby było 50 ruchów to musiałbyś mieć drzewko
na głębokość 50, jak na razie widzę rozważamy max. 20 ruchów do przodu.

Tak, ale mój program docelowo jest stworzony do innego zadania niż test perft. Test perft to
coś co robię tylko przy okazji, więc musi mieć zaimplementowaną (właściwie to już ma) regułę
50 ruchów. Oczywiście po ostatnich optymalizacjach zakomentuję regułę 50 posunięć i potrójne
powtórzenie. Ale struktury danych nie napiszę od nowa, tak żeby nie uwzględniała tej reguły -
po prostu nie mam na to tyle czasu.

Cytat: Karlik w 26 Maj 2013, 15:44
Poza tym ja to proponuję jako sposób zapisu układu na potrzeby porównań (już do samego drzewka
zamiast hasha - w samym hashu też przecież nie sprawdzasz położenia króla ani nic podobnego), i tak
musisz docelowo tę zmianę wprowadzić w funkcji skrótu (zrobić dwa xory przykładowo), tutaj masz
nawet łatwiej, bo tylko robisz proste przypisanie albo nowej wartości pola do figury
(lub dwóch przy biciu lub roszadzie) albo nowej figury do dwóch pól. Uwzględnienie promocji figury w
wersji black/white to może być po prostu najstarszy bit.

Zgadza się, można wprowadzić dodatkową reprezentacje specjalnie na potrzeby hash i powinno działać
szybko. Jednak wersja z xor-ową funkcją skrótu jest już gotowa - nic nie muszę robić, ewentualnie
zwiększę jej długość. Program będzie szybciej gotowy.

Cytat
Lecz to już 32 bajty i nie wiem czy nie lepiej byłoby zakodować każdą figuę (jest ich przecież tylko 6) na 3 bitach i pamiętać 64 pola po 3 bity, co daje tylko 24 bajty.Nie do końca, masz 12 figur (musisz osobno traktować białe i czarne), więc masz 4 bity na pole, czyli łącznie 32 bajty ;)

Czyli o 16 bajtów więcej niż klucz 128 bitowy ;)
16 bajtów to  niby mało... ale widzę że program działa
wyraźnie szybciej z każdym, nawet małym zwiększeniem
pamięci. A weryfikować i tak i tak trzeba.

Pozdrawiam

Cytat: Szopler w 26 Maj 2013, 14:44
U mnie program po kilkunastu godzinach się zakończył... przedwcześnie

Czyli program ma jakiś dziwny błąd, który uaktywnia się dopiero przy
głębokości 10 ruchów i to tylko na niektórych komputerach :/
Cóż, najwyraźniej czeka mnie żmudny proces debugowania.

Moja kolejna prośba odnośnie testów jest kilka postów wyżej:
http://www.boincatpoland.org/smf/przetwarzanie-rozproszone/to-co-bawimy-sie-d/msg225243/#msg225243

Jakby nie chciało Ci się czytać całego posta, to prośba zaczyna
się tam od słów: "Jakby ktoś chciał pomóc" :D

Pozdrawiam i dziękuję.

P.S.
Oczywiście testujemy tylko najnowszej wersji :)

Cytat: Szopler w 26 Maj 2013, 14:44
U mnie program po kilkunastu godzinach się zakończył... przedwcześnie

Czyli program ma jakiś dziwny błąd, który uaktywnia się dopiero przy
głębokości 10 ruchów i to tylko na niektórych komputerach :/
Cóż, najwyraźniej czeka mnie żmudny proces debugowania.

Moja kolejna prośba odnośnie testów jest kilka postów wyżej:
http://www.boincatpoland.org/smf/przetwarzanie-rozproszone/to-co-bawimy-sie-d/msg225243/#msg225243

Jakby nie chciało Ci się czytać całego posta, to prośba zaczyna
się tam od słów: "Jakby ktoś chciał pomóc" :D

Pozdrawiam i dziękuję.

Cytat: Dario666 w 26 Maj 2013, 12:43
Chodziło mi o to, żeby można było wykorzystać w przyszłości uzyskane wyniki do obliczeń na większą głębokość, a nie liczyć znowu od początku.

Teraz rozumiem. Myślałem nad tym kiedyś przez pewien czas i szukałem jakieś metody/algorytmu. Nawet znalazłem taką możliwość, ale
doszedłem do wniosku, że to się nie opłaci. Wątpię aby to było możliwe, ale jakby ktoś mi podsunął taki algorytm, to oczywiście spróbujemy.

Cytat: Dario666 w 26 Maj 2013, 12:43
Druga sprawa dotyczy hashy. NIe wiem czy spotkałeś się kiedyś z "paradoxem urodzin"...

Tak, znam termin paradoksu dnia urodzin. Pomimo tego paradoksu do tej pory nigdy nie spotkałem się z
taką sytuacją, aby klucze 64-bitowe nie zadziałały w zastosowaniach jedno-komputerowych. Nawet przy
liczeniu przez 2 tygodnie na 6 rdzeniach równolegle.

Cytat: Dario666 w 26 Maj 2013, 12:43
Po krótce chodzi o to, że prawdopodobieństwo znalezienia 2 osób urodzonych tego samego dnia wśród grupy 366 osób jest równe 100%.

Przy założeniu że do grupy trafiły losowe osoby :)

Cytat: Dario666 w 26 Maj 2013, 12:43
Wydawałoby się, że aby uzyskać prawdopodobieństwo równe 50% potrzeba grupy 183 osób. Nic bardziej błędnego. Do tego wystarczy grupa jedynie 23 osób!

No tak, ale ilość różnych wartości funkcji skrótu też rośnie wykładniczo z każdym bitem.

Może spróbujesz oszacować teoretyczną ilość bitów?
Klient musi przeszukać na głębokość powiedzmy 9 ruchów. Powiedzmy że
unikalnych węzłów jest 28*28*16^7 (wszystkich jest 210453397504). Klient może w RAM
przechować około 200mln kluczy. Ja bym to oszacował jako paradoks dnia
urodzin dla roku który ma 2^64 albo 2^128 dni, dla grupy która ma 200 mln
osób a potem w grupie jedna osoba zmienia się 28*28*16^7 razy.
Uzyskamy prawdopodobieństwo błędnego wyniku dla jednego klienta.

Cytat: Dario666 w 26 Maj 2013, 12:43
Ten problem wykorzystywany jest do oszacowania ile można wykonać hashy kluczem o określonej długości, aby wystąpiła kolizja (ten sam hash). Przyjmuje się, że prawdopodobieństo 10^-15 jest najwyższym jakie można zaakceptować, aby być pewnym, że kolizja nie wystąpi - notabene na tym bazują funkcje korekcji błędów dysków HDD, CD i DVD. Przy funkcji mieszającej 64-bitowej wystarczy wyznaczyć tylko 190 hashy, aby przekroczyć to prawdopodobieństwo!!! Przy funkcji 128-bitowej jest to 820*10⁹, a przy 256-bitowej to 15*10³⁰. Dlatego właśnie teraz do podpisu elektronicznego stosuje się hashe conajmniej 256-bitowe.

Programy szachowe (wszystkie) działają na funkcji 64bitowej.  Mój program też podaje wyniki dla głębokości 9
(powiedzmy że to 28*28*16^7 unikalnych węzłów) przy funkcji 64 bitowej.

Cytat: Dario666 w 26 Maj 2013, 12:43
Myślę, że powinieneś zastanowić się na zastosowaniem hashy 256-bitowych, żeby nikt nie podważył wyniku obliczeń.

Na pewno wezmę to pod uwagę. W poście powyżej już opisałem dokładnie jak zbadamy sprawę. Wyniki
obliczeń i tak będziemy musieli zweryfikować. Więc można dać każde zadanie do liczenia na dwóch
różnych funkcjach 128 bitowych. Jeśli wyniki będą różne, to się policzy na  trzeciej funkcji skrótu. Jeśli
nadal będą różne, to się zastosuje funkcje 192 bitowe.

Cytat: Dario666 w 26 Maj 2013, 12:43
Lecz to już 32 bajty i nie wiem czy nie lepiej byłoby zakodować każdą figuę (jest ich przecież tylko 6) na 3 bitach i pamiętać 64 pola po 3 bity, co daje tylko 24 bajty. Porówanie takiej struktury wymaga w SIMD tylko kilku instrukcji maszynowych.

Instrukcji SIMD nie ma na każdej maszynie i mogą być różnice pomiędzy AMD i Intelem. Zamiana mojej szachownicy na
liniowe dane to dość skomplikowana procedura. Mniej/więcej coś takiego:

i=0;
for( j=2 ; j<10 ; j++ )
for( k=3 ; k<11 ; k++ )
lin[i++] = board[j*10+k];
lin[i++] = czy_jest_przyzwolenie_na_bicie_w_przelocie;
for( j=0 ; j<4 ; j++ )
lin[i++] = przyzwolenia_roszad[ idx[j] ];
lin[i++] = która_strona_ma_ruch

Czyli do każdego węzła dojdzie 70 pętli. Jak dane skompresujemy, to jeszcze
dojdą operację bitowe and i or. Spowolni to całość z 10-30 razy.

Istnieje jeszcze inne rozwiązanie... można trzymać dwie reprezentacje
(a właściwie trzy, bo drugą wyspecjalizowaną trzymam już w celu przyspieszenia
testów szacha) jednocześnie i aktualizować ją po każdym ruchu...

Tak czy inaczej, na pewno starannie podejdę do sprawy zapamiętywania
danych częściowych - nie możemy ryzykować błędnych wyników.

Pozdrawiam

Cytat: Rysiu w 26 Maj 2013, 10:31
Ja widzę dość zaawansowany problem z funkcją skrótu. Przecież nawet dając hash o długości 128 bitów lub więcej i tak masz teoretyczną szansę, że coś się powtórzy. Prawdopodobieństwo tego być może jest skrajnie niskie ale jednak jest.
Do takiego zliczania potrzebna jest aplikacja zwracająca zawsze w 100% poprawny wynik.

Z tego co wiem, wszyscy liczą takie zadania na funkcji skrótu. Ale skoro mnie uczulacie, to:

Po pierwsze przebadamy sprawę. Dam 40 bitów, potem 41, 42 itd. Zobaczymy jaka długość
wystarcza do jakiej głębokości. Z tego co pamiętam, 56bitów do jedno-komputerowych
zastosowań wystarczało w zupełności, ale sprawdzimy to porządnie jeszcze raz.

Po drugie zawsze może znaleźć się ktoś nieuczciwy i podesłać nam błędny wynik, więc
obliczenia trzeba weryfikować. Więc z każdym podzadaniem będziemy wysyłać inną
funkcję skrótu. Wydaje się skrajnie mało prawdopodobne, żeby na dwóch-trzech błędnych
funkcjach skrótu uzyskać dwa-trzy razy takie same wyniki.


------------------------------------------------------------------------------------------------------------------------------
Sprawdzam wpływ parametrów probe i forget na szybkość obliczeń.
Wyniki na laptopie i3:

threadMemPerft 9 4 200000000 1 0 nodes:2439530234167 time:3264
threadMemPerft 9 4 200000000 2 0 nodes:2439530234167 time:2789
threadMemPerft 9 4 200000000 3 0 nodes:2439530234167 time:2647
threadMemPerft 9 4 200000000 4 0 nodes:2439530234167 time:2598
threadMemPerft 9 4 200000000 5 0 nodes:2439530234167 time:2575
threadMemPerft 9 4 200000000 6 0 nodes:2439530234167 time:2566
threadMemPerft 9 4 200000000 7 0 nodes:2439530234167 time:2564
threadMemPerft 9 4 200000000 8 0 nodes:2439530234167 time:2564


Widzę że kombinując z tymi parametrami można uzyskać spory zysk.
Na innych platformach sprzętowych może być inny koszt odstępu do
pamięci, więc ciekawy jestem czy będzie powtarzalność wyników.

Jakby ktoś chciał pomóc, to przesyłam przykładowy skrypt. Parametry:
mem  - pamięć
thr     -  ilość wątków
depth - głębokość przeszukiwania
Jak je ustawiać, chyba już wiadomo, jak nie, to pytajcie.

Natomiast dwa ostatnie parametry (probe i forget) trzeba
wpisać w każdym poleceniu inne. Najlepiej gdy jeden
z tych dwóch parametrów wpisujemy na stałe, a drugi
zmieniamy z jakimś skokiem.

Parametr drugi od końca ma sensowne wartości w przedziale
od 1 do około 20-30. Przyjmuje tylko wartości całkowite.
Parametr drugi może przyjmować dowolne wartości
całkowite z przedziału od 0 aż do 2^64-1.

Można np. parametr pierwszy wpisać na stałe, może równać się
powiedzmy 4, a pod parametr drugi można podstawić jakieś
mocno rozrzucone liczby.

Np.

4 0
4 1
4 5
4 25
4 125
4 625
4 10000
4 100000
4 1000000
4 10000000

Można zrobić odwrotnie, można drugi parametr pozostawić stały, a zmieniać
tylko pierwszy, np. tak:

1 1000000
2 1000000
3 1000000
4 1000000
5 1000000
6 1000000
7 1000000
8 1000000


Poniżej kod którego ja użyłem. Wyniki trafią do pliku out.txt


#!/bin/sh
mem=200000000
thr=4
depth=9


(
echo threadMemPerft $depth $thr $mem 1 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 2 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 3 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 4 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 5 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 6 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 7 0
echo quit
) | ./perft >> out.txt


(
echo threadMemPerft $depth $thr $mem 8 0
echo quit
) | ./perft >> out.txt


------------------------------------------------------------------------------------------------------------------------------

W załączniku najnowsza wersja programu.

Cytat: Dario666 w 26 Maj 2013, 01:19
Ciekawe jak chcesz zoptymalizować obliczenia z 1160 sekund do średnio 15 sekund, czyli przyspieszyć go 77 razy. To chyba zbytni optymizm.

Otóż obecnie mój program wykonuje tyle ruchów ile... jakby to zgrabnie napisać... no tyle ile jest do wykonania w
danym poddrzewie - w programie szachowym tak właśnie trzeba. Ale w procedurze perft na jedną głębokość przed
liściem, czyli tam gdzie jest najwięcej obliczeń, nie trzeba wykonać ani jednego ruchu - wystarczy zliczyć ile ruchów
jest tam dozwolonych i zrobić return ilość_ruchów; - może się mylę, ale szacuję to na przyspieszenie
rzędu 20-40 razy. Do tego dochodzi zarządzanie pamięcią, po tej optymalizacji na ostatnim poziomie, może program tak
mocno przyspieszyć, że nie będzie sensu zapamiętywanie przedostatniego poziomu w wynikach częściowych - a więc
pamięć zostanie wolna dla większych głębokości - a podanie wyniku bez obliczeń na większych głębokościach
daje większe przyspieszenie niż podanie go na głębokościach mniejszych. Do tego mój program ma parametry
probe i forget - na razie nie wiem jakie są ich optymalne wartości. Do tego można ruchy na jednym poziomie wykonać
nie jeden raz, ale dwa razy. Po co dwa razy wykonywać to samo? Ano po to, żeby sprawdzić dla których ruchów jest
zapamiętany wynik i je od razu podać, bo jak się wykona najpierw inne, to zapamiętany wynik może zostać zamazany....

Niby takie sobie proste przeszukiwanie drzewa gry... ale technik jest dużo i każda może coś przyspieszyć.  Jak mi tylko czas
pozwoli to myślę że jest realne przyspieszenie nawet do 200 razy. No i czasy do szacowań wziąłem z laptopa i3 - a to nie
jest zbyt mocny komputer :)


> Znalazłem na stronach szachowych dość obszery wywód z szacowaniem ilości możliwych rozstawień figur i wynik brzmiał 10⁴⁰.
> Patrząc na to, że funkcja haszująca 160-bitowa ma 1,46*10⁴⁸ różnych wyników, to może się okazać zbyt mało i kolega Karlik może
> mieć rację, że hasze będą się powtarzać dla rózych ustawień.
Niewykluczone że ma rację. Do tej pory nigdy się nie spotkałem z taką sytuacją, aby klucz 64bitowy był za krótki. Być może przy obliczeniach
rozproszonych będzie potrzebny klucz 128 bitowy, a może jeszcze większy - na razie tego nie wiem. Natomiast jestem pewny, że mogę
długość klucza zwiększać aż wystarczy.


> Zasadnicze pytanie jest takie: po co to w ogóle mamy liczyć? Dla samego przeliczenia?
Nie rozumiem. To czyli co? W ogóle całe zadanie? Byłem zachęcany/ponaglany żeby zrobić
jakiś projekt do obliczeń rozproszonych.  Na szybko nic lepszego nie mogę zaoferować niż
to zadanie - więc głównie po to.

Taki projekt jest w jakimś małym stopniu prestiżowy, od dawna pasjonaci szachów zastanawiają
się ile jest możliwych układów. Nie da się odpowiedzieć na to pytanie w ogóle, ale można podać
ile jest układów do określonej głębokości. Wielu ludzi liczyło to do 12 ruchów i się chwaliło że
się udało. Nikt dzięki temu projektowi zdrowszy lub bogatszy nie będzie, ale szczęśliwszy może tak :)


> Jakie jest cel
Np. taki może być cel:
Podać dokładnie jaką wartość zwraca funkcja perft dla głębokości do 16 ruchów włącznie.
Podać bardzo dobre oszacowania funkcji perft do 24 ruchów włącznie.

> i jakie dane chcemy zgromadzić, aby można je było wykorzystać do dalszych badań.
Danych raczej nie chcemy gromadzić. Chcemy znać rozwiązanie i chcemy dojść do
niego w najszybszym czasie.


> Według mnie metoda z haszami nie jest trafiona, bo nie możemy z niej odczytać jakie jest rzeczywiste ustawienie figur na szachownicy.
Nie potrzeba odczytywać rzeczywistego układu, przynajmniej teraz program działa i nie odczytuje tego.

Pozdrawiam

Cytat: krzyszp w 25 Maj 2013, 22:22
Za to u mnie po prawie dobie wyskoczyło "Killed"...  :(
Zakładam, że to z powodu braku wolnej pamięci (serwer wszedł mi ostro na swap'a).
Edit:
Spróbowałem odpalić na Virtualbox'ie skrytp, ale niestety wysypał się z komunikatem (z VB) "Guru meditation" ;)

Masakra, czyli program cały czas jest niestabilny. Jutro zapodam nową wersję.
Dzięki i pozdrawiam.

> Akurat dowolną strukturę można spokojnie w ten sposób porównywać ;]
Nie chodzi o to że nie można, tylko oto, że dane sekwencyjne porównuje się szybciej.



> Nie wiem jak masz to do innych operacji przedstawione, ale jak dla mnie to może być coś typu:
> struct plansza{
> unsigned char white[16];
> unsigned char black[16];
> ;[/code]
> Gdzie spokojnie możesz zapisać na starszych 4 bitach X, na młodszych Y, same zera dają pionek poza planszą.
Nie chodzi o to że nie można spokojnie trzymać :) Chodzi o to, że na reprezentacji planszy trzeba wykonywać
wiele różnych operacji. Jeśli strukturę dopasujemy do jednej operacji, to będzie gorzej dopasowana do drugiej.
Poza tym ta wersja którą teraz robię, docelowo ma efektywnie działać na szachach samouczących, a nie
na teście perft. Test perft to takie zadanie epizodyczne przy okazji :)


> Wtedy masz 32 bajty, które swobodnie możesz porównać przez memcmp.
Ale np. testowanie szacha i znajdowanie ruchów trwa wolniej niż na strukturze którą
mam obecnie - tu przyspieszysz, a tam zwolni.


> Jedyny ew. mankament to pionki, które musiałbyś osobno sprawdzać, bo są traktowane indywidualnie. Inne podejście może być takie:
> struct plansza{
> unsigned char field[4][8];
> };
> wtedy masz w jednym bajcie dwa pola (możesz je traktować liniowo) - wtedy reprezentujesz sobie najstarszy bit zapisu jako
> kolor, pozostałe 3 jako rodzaj figury (król, królowa, goniec, koń, wieża, pion) - jedna wartość niewykorzystana.
> Wtedy masz bardzo wygodne porównywanie przez memcmp.
No tak, ale jak efektywnie na tym wykonywać wszystkie pozostałe operacje? Operacji jest sporo: sprawdzanie
czy jest szach, sprawdzanie czy ruch jest legalny (po ruchu nie może być szacha), sprawdzanie czy nie próbuje
się bić króla, wyszukiwanie gdzie stoi król, zliczenie ile jest w sumie figur, posortowanie ruchów począwszy
od bić, sprawdzenie czy pozycja na planszy nie powtórzyła się trzy razy, sprawdzenie czy jest remis po wykonaniu
50 ruchów bez bicia, promocji i roszady...


> To masz wersje 32 bajtowe. Z mniejszych, gdzie ma się pełną informację na pewno wykonalna jest 28 bajtowa jeszcze.
Pewnie da się jeszcze mniejszą zrobić niż 28 bajtów, ale to się nie opłaci.


> Wydaje mi się, że koszt operowania na tak przygotowanej planszy jest mniejszy niż liczenie funkcji skrótu.
Mam specjalną funkcję skrótu, jej koszt jej obliczenia to... nie wiem ile... może 1% wykonania całego programu.
Używam kluczy zobrosta, można je obliczać "przyrostowo".


> W sumie to takie gdybanie, bo jak się nie widzi kodu to ciężko cokolwiek doradzić.
A jak się widzi kod, to można jedną rzecz przyspieszyć, a 10 innych spowolni :D



> To teraz tak, hash ma 20 bajtów z tego co zrozumiałem.
Hash ma 8 bajtów. Dodatkowo jest 8 bajtów na ilość węzłów i był 1
bajt na crc. Teraz mam 8 bajtów na crc. Czyli jeden wpis to w
nowej wersji 24 bajty.


> Możesz spróbować jakoś ponumerować układy po prostu. Masz maksymalnie zajęte 32 pola z 64, to masz 64 po 32 = 1,8e+18 układów zajętych pól.
> Masz 13 rodzajów figur (6*2+1 -> jedynka, bo może pole być puste). Więc masz 13^32 *  1,8e+18, z tego logarytm dwójkowy wychodzi ~179, więc
> musisz poświęcić co najmniej 23 bajty na każdy układ. Można teoretycznie zbić jeszcze to trochę, bo król może występować tylko raz, królowa tylko raz,
> więc zamiast 13^32 wyjdzie jakieś 13*12*11*10 (króle i królowe), dalej *9*9*8*8 (gońce), *7*7*6*6 (konie), *5*5*4*4 (wieże), *3^8 * 2^8 (pionki) * 2^30 (bo każdy
> może występować lub nie z wyjątkiem króli), wtedy masz te swoje upragnione 20 bajtów (158 bitów). W rzeczywistej grze liczba układów jeszcze jest mniejsza, bo
> niektóre sytuacje nigdy nie zajdą, ale liczenie tego to... Tak więc teoretycznie te 20 bajtów może Ci wystarczyć, ale nie zdziwiłbym się, gdyby Twoja funkcja skrótu
> dawała tę samą wartość dla dwóch różnych układów (zrobienie takiej idealnej nie jest wbrew pozorom takie proste).
Najprościej i najefektywniej z wszystkich znanych mi sposób działają klucze zobrista. Używam 64bitowej funkcji skrótu, to kolosalna ilość 2^64 różnych
wartości, ale być może okaże się za mało. Mój program właśnie dał złą wartość - może to z powodu zbyt krótkiej funkcji skrótu. Jeśli okaże się za mało, to dam 128 bitów.
Wpis w hash-table z rozmiaru 24bajtów zwiększy się do 32 bajtów - czyli da się zapamiętać o 25% układów mniej - to poważny mankament, bo pamięć jest ważna, ale być
może nie ma innego wyjścia. Natomiast z powodu dłuższych kluczy zobrista program nie spowolni prawdopodobnie nawet o 1% - to naprawdę efektywna metoda.

Pozdrawiam serdecznie

Cytat: Szopler w 25 Maj 2013, 19:59

Kod [Zaznacz] Rozwiń

nie można uruchomić pliku binarnego
1. chmod +x ./perft poszło
2. apt-get install ia32-lib-i386 poszło
3. apt-get libboost-thread-dev poszło
4. ściągnięcie preft + lib w wersji wymaganej poszło
i dalej nie działa :/ (debian 7 no gui)

Program na razie nie będzie działał na linuxie 32 bitowym.
Pozdrawiam

Cytat: Dario666 w 25 Maj 2013, 13:45
Teraz widać dlaczego nikt nie policzył do 16  ;D.
Ostatnia kolumna jest prostym założeniem, wynikającym z podanych przez was wyników, że w trybie z pamięcią obliczenia są wykonywane 40 razy szybciej (patrząc na 1 wątek)
Przy "13" jeszcze idzie policzyć w realnym czasie, ale już "14" to niezła orka.
Przyjmijmy, że wydajność jednego rdzenia to średnio 6000 MIPSów, więc by przeliczyć "14" trzeba wykonać około 1700 kwintylionów FLOPów (licząc jednostki jak amerykanie). To jest, tak dla porównania, około 2 miliardów kredytów w PrimeGrid'zie. Cały zespół B@P ma mniej więcej tyle, a pewnie lwia część tego to projekty liczone na GPU.

Przychodzi mi do głowy tylko jedyny sensowny sposób na dokładnie oszacowanie czasu
dla algorytmu z pamięcią.

Najpierw trzeba policzyć na jakąś głębokość i zapamiętać wszystkie układy. Potem układy
powtarzające się trzeba wyrzucić, a z każdym układem zapamiętać ilość jego wystąpień. W
ten sposób otrzymamy ilość różnych układów. Różne układy mogłyby leżeć w bazie
na jakimś serwerze. Klient może pytać o układ, wykonywać dla niego obliczenia i odsyłać
wynik z powrotem na serwer. Czyli łączny czas obliczeń będzie wynosił A*N, gdzie
A to średni czas liczenia jednego układu, a N to ilość różnych układów.


Sensowna głębokość dla klienta jest w granicach 8-10. Przy głębokości 8, mogą zapchać
serwer. Przy głębokości 10 na serwerze będzie mało układów, a więc gorzej zadziała algorytm
odrzucania powtarzających się. Powiedzmy że klient będzie liczył na głębokość 9. Czyli
serwer musi sam przeszukać na głębokość 5 aby łącznie uzyskać 14.  Drzewko ma 4865609  liści
przy głębokości 5 ruchów. Widzieliśmy że na głębokość 9 da się policzyć w 1160s. Powiedzmy
że program po zoptymalizowaniu policzy na głębokość 9 w 10-20sekund (kurcze, 20 sekund
nadal może zapchać serwer). Czyli 4865609*10-20s=15-30 lat - całkiem szybko, a do tego
wiele układów będzie się powtarzało.


Nie wiem ile układów będzie się powtarzało, myślę że bardzo dużo odpadnie. Strzelam że
zostanie tylko 10% układów. Czyli 10% * 4865609 * 10-20s = 1.5 - 3 lat - Na boinc to bułka
z masłem.


Jeśli przyjmiemy podstawę potęgi równą 25, to by znaczyło, że z tymi technikami w nie więcej
niż 3tys lat dojdziemy do głębokości 16 ruchów.


Obawa pozostaje jedna, czy naprawdę pozostanie tylko 10% układów po odrzuceniu powtórzeń?

To oszacowanie na pewno jest znacznie bardziej optymistyczne niż Twoje 10 738 920 lat :D

Pozdrawiam

Cytat: Karlik w 25 Maj 2013, 17:07
Jesteś pewien, że zapamiętywanie funkcji skrótu zamiast całego układu tak istotne?

Na pewno jest istotne. Jak bardzo istotne, to nie sprawdzałem. Możliwe że to
przyspiesza nawet 2-3 razy. Na pewno da się w ten sposób zapamiętać dwa
razy więcej układów, a to istotnie przyspiesza.

Cytat: Karlik w 25 Maj 2013, 17:07
O ile dobrze liczę to całą planszę można zapisać na 24-32 bajtach (w zależności od tego jak zakodujemy planszę).

w 32 bajtach na pewno można, w 20tu może też by się dało. Ale takie zapamiętanie to
nie byłoby szybkie memcpy i potem porównanie przez memcmp. Jak się zrobi planszę
jako liniowe 64/32 bajty, to z kolei wolno działają inne operacje :)

Cytat: Karlik w 25 Maj 2013, 17:07
Nie znam algorytmu, więc ciężko mi mówić jaki to miałoby wpływ na wydajność (bo może kodowanie/dekodowanie tego by było zbyt czasochłonne).

Mnie też jest trudno powiedzieć, myślę że z tą techniką działa 2-3 razy szybciej.

Pozdrawiam

Cytat: Rysiu w 25 Maj 2013, 15:13
Ja liczę do 10 na Core i7 950 i 24 GB RAM. Program zaalokował ponad 22 GB pamięci.
Głębokość 8 obliczył w 106 sekund. Całkiem niezły wynik mi się wydaje. Wszystkie dotychczasowe wyniki zgadzają się z tymi w bazie oeis.org.
Obliczył właśnie do głębokości 9. Trwało to 1160 sekund. Wynik zgodny z oeis.org.

Zbadamy za jakiś czas jaki wpływ mają dwa ostatnie parametry. U mnie na i3 (laptop) takie
mam wyniki dla depth=8:
./perft
threadMemPerft 8 4 220000000 4 0
nodes:84998978956 time:260
threaMemPerft 8 4 220000000 4 1
unknown command: threamemperft
threadMemPerft 8 4 220000000 4 1
nodes:84998978956 time:277
threadMemPerft 8 4 220000000 4 1000
nodes:84998978956 time:275
threadMemPerft 8 4 220000000 4 1000000
nodes:84998978956 time:247
threadMemPerft 8 4 220000000 8 0
nodes:84998978956 time:246
threadMemPerft 8 4 220000000 8 1000000
nodes:84998978956 time:250
threadMemPerft 8 4 220000000 12 0
nodes:84998978956 time:268
threadMemPerft 8 4 220000000 12 1000000
quit

Najlepszy wynik 246 sekund, najgorszy 277 - czyli trochę można zyskać. Dla
większych głębokości zysk może być znacznie większy.

Pozdrawiam

Cytat: Dario666 w 25 Maj 2013, 13:45
Ostatnia kolumna jest prostym założeniem, wynikającym z podanych przez was wyników, że w trybie z pamięcią obliczenia są wykonywane 40 razy szybciej (patrząc na 1 wątek)

Wyedtyowałem ten post, bo w świetle nowych wyników nie miał on najmniejszego sensu.
Całkiem przyzwoita funkcja aproksymująca to:
time = 400 * A ^ (depth-2)
Dla algorytmu bez pamięci A wynosi prawdopodobnie 25
Dla algorytmu z pamięcią A wynosi prawdopodobnie 11
Gdy pamięci jest mało, to A przyjmuje wartość z przedziału 11-25.
Pozdrawiam

Cytat: Argento w 25 Maj 2013, 13:24

Cytatwydać komendę chmod 500 perft

Zapomniałem... :bad:
A teraz sytuacja jak u RAD-Poland, czyli żadnej reakcji na ./perft. Tak z paramterami jak i bez...

Instrukcja i przykłady w moim drugim poście tego wątku :)
Uruchamiamy program i potem wpisujemy komendy.

-------------------------------------------------------------------------------------------------------------------------
Jeśli możesz obliczenia zostawić na dłuży czas ( rzędu 20-60h - zależnie od
szybkości komputera ) to teraz najbardziej potrzebny jest jeden określony
test. A mianowicie trzeba wpisać taki skrypt:

#!/bin/sh
(
echo threadMemPerft 1  5 100000000 4 0
echo threadMemPerft 2  5 100000000 4 0
echo threadMemPerft 3  5 100000000 4 0
echo threadMemPerft 4  5 100000000 4 0
echo threadMemPerft 5  5 100000000 4 0
echo threadMemPerft 6  5 100000000 4 0
echo threadMemPerft 7  5 100000000 4 0
echo threadMemPerft 8  5 100000000 4 0
echo threadMemPerft 9  5 100000000 4 0
echo threadMemPerft 10 5 100000000 4 0
echo quit
) | ./perft >> out.txt

Skrypt można nazwać go.sh. Skryptowi też nadajemy:

chmod 500 go.sh

i uruchamiamy
./go.sh

Potem wynik będą w pliku out.txt


--------------------------------------------------------------------------------------------------------------
Tuning

Jeśli komputer ma 6 rdzeni, to warto jako drugi parametr podać
liczbę 8 (zamiast 5).

Jeśli komputer ma 1GB wolnej pamięci to jak trzeci parametr podajemy
liczbę 50000000 (50 milionów).

Jeśli komputer ma 2GB wolnej pamięci to jak trzeci parametr podajemy
liczbę 100000000 (100 milionów).

Jeśli komputer ma 4GB wolnej pamięci to jak trzeci parametr podajemy
liczbę 200000000 (200 milionów).


---------------------------------------------------------------------------------------------------
PS.

Na moim komputerze program podał wynik z małym błędem. Muszę znaleźć
przyczynę. Potencjalnie są...  cztery przyczyny:
1) błąd sprzętu - wczoraj rano komputer włączył się i nie widział jednej kości ram, musiałem
    wyjąć kości i włożyć na nowo.
2) zwyczajny błąd w kodzie
3) zbyt mała losowość funkcji skrótu (w celu przyspieszenia zapamiętuję tylko funkcję  skrótu a nie cały układ)
4) za słaba CRC - nie używam blokad na dostęp do pamięci, gdyż to bardzo spowalnia. zamiast
   blokad używam crc - jeśli jeden wątek popsuje dane drugiemu wątkowi, to crc powinna się nie zgadzać.

Wyniki na Waszych komputerach trochę pomogą mi ustalić co jest przyczyną błędu. Jeśli wszędzie
będzie dobry wynik, a u mnie zły to będzie wskazywało że mój komputer się rozwalił. Jeśli wszędzie
będą inne wyniki, to będzie wskazywało że mam za słabą funkcję skrótu albo za słaby crc. Jeśli wszędzie
będą takie same (ale błędne) wyniki, to prawdopodobnie mam błąd w kodzie.

Pozdrawiam

Cytat: Argento w 25 Maj 2013, 11:54
A ja po ./perft otrzymuję komunikat <i>command not found</i>...  :o

Trzeba zrobić dwie rzeczy:
1) zmienić katalog bieżący na ten do którego się przekopiowało program
2) wydać komendę chmod 500 perft
potem powinno działać.

Pozdrawiam

Cytat: krzyszp w 24 Maj 2013, 21:43
Ok, odpaliłem jeszcze raz...

Ciekawy jestem jaki masz wynik i czy program się już zakończył :)
U mnie się zakończył, ale podał błędny wynik :)

Poprawny wynik dla głębokości 10 to 69352859712417
U mnie jest: 69352859710032 i czas 63547 sekund.

Program ma dwie heurystyki, czyli coś co zwykle działa, ale nie gwarantuje
poprawnego wyniku. Muszę sprawdzić czy błędny wynik jest zwyczajnie z
powodu błędu w programie, czy te heurystyki zbyt szybko zawiodły.

Jeśli u Ciebie będzie inny wynik niż u mnie, to mamy prawie pewność, że
heurystyki nie zadziałały. Będę musiał je jakoś "wzmocnić".

Pozdrawiam

Cytat: krzyszp w 24 Maj 2013, 21:43
Ok, odpaliłem jeszcze raz...

Jedyny sposób na zapisywanie to dodatkowy skrypt, np. taki:

#!/bin/sh
(
echo threadMemPerft 1  5 100000000 4 0
echo threadMemPerft 2  5 100000000 4 0
echo threadMemPerft 3  5 100000000 4 0
echo threadMemPerft 4  5 100000000 4 0
echo threadMemPerft 5  5 100000000 4 0
echo threadMemPerft 6  5 100000000 4 0
echo threadMemPerft 7  5 100000000 4 0
echo threadMemPerft 8  5 100000000 4 0
echo threadMemPerft 9  5 100000000 4 0
echo threadMemPerft 10 5 100000000 4 0
echo quit
) | ./perft >> out.txt

Cytat: krzyszp w 24 Maj 2013, 21:10
Czyli generalnie, walka toczy się o "14"???

O ile się nie mylę, to tak. Wdziałem z wielu źródeł wyniki dla depth=12. Z raptem dwóch
źródeł dla depth=13. Dla 14 nie widziałem, ale nie powiedziane, że widziałem wszystko :)

Cytat: krzyszp w 24 Maj 2013, 21:10
Bo jeśli tak, i jeżeli możesz zrównoleglić aplikację, to BOINC aż się prosi o to :)

Spróbujemy. Jeśli rzucać się na BOINC, to wersja z pamięcią i od razu można
na kilka głębokości, np. na wszystkie od 10 do 20. Pytanie dlaczego rzucać się na
głębokości powyżej 16, jeśli to wymaga tak ogromnej mocy obliczeniowej? Odpowiedź
jest taka, że poza dokładnym obliczeniem, robi się także oszacowania. Zanim policzymy
dokładnie dla depth>15, to będziemy mieli policzone częściowo,  np. 0.1% całości.  Wtedy
można to co już policzone wymnożyć razy 1000 i podawać z dania na dzień dokładniejsze
oszacowania. Dla mniejszych głębokości (może dla depth<=16) w końcu się uzyska dokładny
wynik, a dla większych oszacowania też będą cieszyły. Koncepcyjnie jest to proste, w
realizacji... no cóż... wymaga dużo czasu.


Projekt jest prosty i zabawowy, ale w środowisku szachowym może wywoływać emocje :)

Cytat: krzyszp w 24 Maj 2013, 21:10
Odpaliłem  threadMemPerft 10 5 100000000 4 0, zobaczymy, jaki będzie czas...

Ja odpaliłem na Phenom II 6 rdzeni:
threadMemPerft 10 8 250000000 8 1000000
Porównamy jutro(?) wyniki :D

Pozdrawiam

Cytat: Rysiu w 24 Maj 2013, 20:38
@Mariotti te 100 milionów lat to jakoś oszacowałeś czy z głowy?

Jeśli komputer Q6600 jest dwa razy szybszy od mojego i współczynnik rozgałęzienia
wynosi 30 to 73mln lat. Jeśli Q6600 jest tak samo szybki jak mój i w.r. wynosi 25 to
28mln lat.

Moze 50mln jest dokładniejszym oszacowaniem niż 100mln :)

Natomiast wersja z pamięcią (mogę się bardzo mylić, tutaj szacowanie jest dużo trudniejsze)
w jakieś 500-1000 lat by dała radę, czyli rok na 1tys maszyn. Z tego co pobieżnie
zdążyłem się zorientować, obecny rekord wynosi 13, czyli 16 by przełamało tę barierę aż o 3 poziomy!

Pozdrawiam

Cytat: krzyszp w 24 Maj 2013, 20:23
Odpaliłem to na serwerze z Q6600, więc mam 4 fizyczne rdzenie, a że komp nigdy nie wyłączany/resetowany - to niech pracuje :) (chyba, że ma to rok potrwać...)

Raczej 100 milionów lat :)

Odpal na głębokość 10 wersję z pamięcią :) Wersja z pamięcią baaardzo przyspiesza, może 100-1000 razy.
Właśnie u siebie sprawdzam ile będzie się to liczyło.

Składnia polecenia:
threadMemPerft depth max_thread mem_size mem_probe forget

Przykład dla 2GB ram i 5-ciu wątków (5 wątków działa szybciej niż 4, nawet gdy są 4 rdzenie)
threadMemPerft 10 5 100000000 4 0

Przykład dla 1GB ram:
threadMemPerft 10 5 50000000 4 0

To powinno się policzyć w jakieś... nie wiem... 12-72h, strzelam że w 20h się policzy.

Pozdrawiam