English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Nie. Bo:
(a) HyperThreading oznacza że jeden wątek robiący Receive() spowalnia drugi wątek coś liczący na tym samym rdzeniu. Tym samym temu drugiemu wątkowi czas biegnie nawet do dwóch razy szybciej (do 2x mniej instrukcji na cykl) niż gdyby liczył na nie obciążonej maszynie.
(b) jeśli mamy mniej procków niż instancji to kolejność ich wykonywania jest 'at the mercy of the scheduler'
Wyobraźmy sobie 2 instancje:
(a) LiczCos(1 sekunda) Send(b) Receive(b) Exit()
(b) LiczCos(1 sekunda) Send(a) Receive(a) Exit()
Widać że powinno skończyć po 1 sekundzie (+ trochę czasu na synchronizację).
Wykonajmy to na 1 procesorze. Załóżmy, że scheduler quantum to 10 sekund (z reguły jest bliżej 10ms ale to tylko czyni kontr przykład trudniejszy do skonstruowania).
Scheduler wybiera wątek (b) - bo mu wolno.
Wątek (b) wykonuje się przez 10 sekund albo do czasu wykonania blokującego syscall'a (czyli nigdy bo nie mamy takich).
Przez pierwszą sekundę coś liczymy, Send(a) wsadza coś do jakiegoś bufora gdzieś i praktycznie zajmuje zero czasu. Następnie Receive(a) przez 9 sekund siedzi i bardzo aktywnie wysiaduje jaja na procku.
Skończył się 10s quantum. Scheduler wybiera wątek (a).
Wątek (a) liczy coś przez sekundę, robi Send(b) i Receive(b) w praktycznie zerowym czasie (bo dane już czekają w jakimś buforze) po czym robi Exit().
Scheduler wybiera wątek (b) [bo nie ma wyboru].
Wątek (b) otrzymuje dane i robi Exit()
(a) wykonywało się 1+epsilon sekund.
(b) wykonywało się 10+epsilon sekund.
Jak widać maksimum to 10+epsilon i jest większe od właściwego wyniku 1+epsilon sekund.
Trywialnie przykład rozszerzyć żeby minimum też było złe.
Np.
(a) 2x{ LiczCos(1 sekunda) Send(b) Receive(b) } Exit()
(b) 2x{ LiczCos(1 sekunda) Send(a) Receive(a) } Exit()
Właściwy czas 2+epsilon sekund.
A nam na powyższym schedulerze wyjdzie:
- przez 10 sekund [b] (1 licz1 + 0 send1 + 9 receive1)
- przez 10 sekund [a] (1 licz1 + 0 send1 + 0 receive1 + 1 licz2 + 0 send2 + 8 receive2)
- przez 1 sekund [b] (0 receive1 + 1 licz2 + 0 send2 + 0 receive2 + 0 exit)
- przez 0 sekund [a] (0 receive2 + 0 exit)
czas [a] = 10, [b] = 11, min = 10, max = 11, poprawny = 2
11 i 10.
---
W praktyce scheduling quantum jest dużo mniejszy więc będzie mniej rozbieżne, ale też odpalamy dużo więcej instancji, mamy _dużo_ mniej procków niż instancji, mamy hyperthreading oraz scheduler jest dużo bardziej losowy.
No i jeszcze dochodzą efekty związane z opróżnianiem się cache'u procesora przy każdej zmianie tego który wątek się liczy (plus przenoszenie się wątków z jednego procka na inny i znowu pusty cache).
(a) HyperThreading oznacza że jeden wątek robiący Receive() spowalnia drugi wątek coś liczący na tym samym rdzeniu. Tym samym temu drugiemu wątkowi czas biegnie nawet do dwóch razy szybciej (do 2x mniej instrukcji na cykl) niż gdyby liczył na nie obciążonej maszynie.
(b) jeśli mamy mniej procków niż instancji to kolejność ich wykonywania jest 'at the mercy of the scheduler'
Wyobraźmy sobie 2 instancje:
(a) LiczCos(1 sekunda) Send(b) Receive(b) Exit()
(b) LiczCos(1 sekunda) Send(a) Receive(a) Exit()
Widać że powinno skończyć po 1 sekundzie (+ trochę czasu na synchronizację).
Wykonajmy to na 1 procesorze. Załóżmy, że scheduler quantum to 10 sekund (z reguły jest bliżej 10ms ale to tylko czyni kontr przykład trudniejszy do skonstruowania).
Scheduler wybiera wątek (b) - bo mu wolno.
Wątek (b) wykonuje się przez 10 sekund albo do czasu wykonania blokującego syscall'a (czyli nigdy bo nie mamy takich).
Przez pierwszą sekundę coś liczymy, Send(a) wsadza coś do jakiegoś bufora gdzieś i praktycznie zajmuje zero czasu. Następnie Receive(a) przez 9 sekund siedzi i bardzo aktywnie wysiaduje jaja na procku.
Skończył się 10s quantum. Scheduler wybiera wątek (a).
Wątek (a) liczy coś przez sekundę, robi Send(b) i Receive(b) w praktycznie zerowym czasie (bo dane już czekają w jakimś buforze) po czym robi Exit().
Scheduler wybiera wątek (b) [bo nie ma wyboru].
Wątek (b) otrzymuje dane i robi Exit()
(a) wykonywało się 1+epsilon sekund.
(b) wykonywało się 10+epsilon sekund.
Jak widać maksimum to 10+epsilon i jest większe od właściwego wyniku 1+epsilon sekund.
Trywialnie przykład rozszerzyć żeby minimum też było złe.
Np.
(a) 2x{ LiczCos(1 sekunda) Send(b) Receive(b) } Exit()
(b) 2x{ LiczCos(1 sekunda) Send(a) Receive(a) } Exit()
Właściwy czas 2+epsilon sekund.
A nam na powyższym schedulerze wyjdzie:
- przez 10 sekund [b] (1 licz1 + 0 send1 + 9 receive1)
- przez 10 sekund [a] (1 licz1 + 0 send1 + 0 receive1 + 1 licz2 + 0 send2 + 8 receive2)
- przez 1 sekund [b] (0 receive1 + 1 licz2 + 0 send2 + 0 receive2 + 0 exit)
- przez 0 sekund [a] (0 receive2 + 0 exit)
czas [a] = 10, [b] = 11, min = 10, max = 11, poprawny = 2
11 i 10.
---
W praktyce scheduling quantum jest dużo mniejszy więc będzie mniej rozbieżne, ale też odpalamy dużo więcej instancji, mamy _dużo_ mniej procków niż instancji, mamy hyperthreading oraz scheduler jest dużo bardziej losowy.
No i jeszcze dochodzą efekty związane z opróżnianiem się cache'u procesora przy każdej zmianie tego który wątek się liczy (plus przenoszenie się wątków z jednego procka na inny i znowu pusty cache).
"3. Moim skromnym zdaniem poprawianie tych outów jest równoważne mówieniu Konradowi, co dokładnie ma źle w programie :P" << być może, tak zresztą jak mówienie, jaki się miało czas na danym teście może zdradzać złożoność, a szybkie wrzucenie dużych testów z outami sugerować, że zadanie było łatwe. W ogóle zresztą wrzucanie testów innych niż losowe (tzn. takich, które coś konkretnie sprawdzają) jest podpowiadaniem, na co należy zwrócić uwagę. Skoro jednak jest to tolerowane, to czemu nie wrzucenie poprawnych outów.
Jakiś mały test: http://www.sendspace.com/filegroup/DCqqGaS5dDSEVLQqIIP70A
edit: Testy p. Piotra Godlewskiego potwierdzam
edit: Testy p. Piotra Godlewskiego potwierdzam
Jako osoba w zauważalnej części odpowiedzialna za system sprawdzania zadań rozproszonych spróbuję trochę wyjaśnić, dlaczego czasy działania w tym systemie wykazują się większym poziomem fluktuacji, niż dla sprawdzarki jednomaszynowej. Nasze eksperymenty pokazywały, że typowe odchylenie czasów to jakieś 5%; co biorąc pod uwagę, że wzorcówki mieściły się w połowie limitów czasowych uznaliśmy za OK.
Na "nierozproszonych" zadaniach uzyskuje się większą stabilność czasu działania poprzez liczenie czasu w cyklach procesora, a nie w czasie zegarowym. W ten sposób unika się wpływu zdarzeń "losowych", jak np. działań jądra systemu operacyjnego, na odmierzony czas działania programu. Ta metoda nie jest idealna (bo działania jądra mogą np. spowodować wyrzucenie jakichś danych z cache'u), ale w praktyce dają bardzo stabilne czasy.
W zadaniach rozproszonych trzeba w czasie działania uwzględnić też czas oczekiwania na komunikację (czyli czas zwisania na Receive). Gdybyśmy tego czasu nie uwzględnili, to w teorii byłoby możliwe "zrównoleglenie" każdego rozwiązania nierozproszonego w następujący sposób: Zaczyna liczyć tylko instancja 0. Kiedy jest bliska limitu czasu, pakuje cały stan, przerzuca na instancję 1, i kończy działanie. Instancja 1 zaczyna działać, liczy do limitu czasu, i przerzuca stan na instancję 2, i tak dalej. W ten sposób każda instancja zużywa tylko tyle procesora, ile jej wolno - ale widać gołym okiem, że nie o takie rozwiązania nam chodzi.
Niestety, uwzględnienie czasu oczekiwania na komunikację siłą rzeczy powoduje, że liczymy czas zegarowy, a nie czas procesora. Liczenie czasu procesora nie bardzo ma sens, bo jeśli jedna instancja zostanie spowolniona przez operacje jądra, a druga czeka na jej komunikat, to to spowolnienie i tak się odbije na czasie działania programu - nawet jeśli pierwszej instancji policzymy czas procesora, to drugiej siłą rzeczy będziemy liczyli czas oczekiwania jako czas zegarowy.
Z powodów jak wyżej - działania systemu operacyjnego i programów pomocniczych, a także niestabilność opóźnień sieciowych oraz drobne różnice w momencie startu programów - czas działania programu nie jest tak stabilny jak w wypadku mierzenia czasu przez cykle procesora. Są też różnice związane z tym, na których konkretnie komputerach zadanie zostanie uruchomione (bo topologia sieci powoduje, że nie każde dwa komputery mają tę samą prędkość nawiązywania połączenia). Nie mamy dokładnych pomiarów tego, które z wspomnianych parametrów są najbardziej istotne; ja obstawiałbym że największy wpływ mają działania "w tle" systemu operacyjnego i demonów systemowych.
Dodam tu, że na pojedynczej maszynie było uruchamiane tylko jedno rozwiązanie na raz; nie zauważyliśmy istotnych zależności między obciążeniem systemu a czasem działania rozwiązań.
Mam nadzieję, że system sprawdzania zadań rozproszonych będzie się rozwijał, i będą pojawiały się pomysły na redukcję tej wariancji. Pewnie warto też dodać, że nie zredukujemy jej do zera nigdy - i dla przypadku jednomaszynowego również nie jest ona zredukowana do zera, jak pisałem wyżej - jest możliwe, że na zwykłej sprawdzaczce jedno z dwóch uruchomień tego samego kodu dostanie TLE, a drugie OK. Natomiast jest dla mnie dość oczywiste, że da się ją zredukować bardziej - choć uznaliśmy, że obecne parametry są akceptowalne, to chciałbym jeszcze sporo je poprawić.
Na "nierozproszonych" zadaniach uzyskuje się większą stabilność czasu działania poprzez liczenie czasu w cyklach procesora, a nie w czasie zegarowym. W ten sposób unika się wpływu zdarzeń "losowych", jak np. działań jądra systemu operacyjnego, na odmierzony czas działania programu. Ta metoda nie jest idealna (bo działania jądra mogą np. spowodować wyrzucenie jakichś danych z cache'u), ale w praktyce dają bardzo stabilne czasy.
W zadaniach rozproszonych trzeba w czasie działania uwzględnić też czas oczekiwania na komunikację (czyli czas zwisania na Receive). Gdybyśmy tego czasu nie uwzględnili, to w teorii byłoby możliwe "zrównoleglenie" każdego rozwiązania nierozproszonego w następujący sposób: Zaczyna liczyć tylko instancja 0. Kiedy jest bliska limitu czasu, pakuje cały stan, przerzuca na instancję 1, i kończy działanie. Instancja 1 zaczyna działać, liczy do limitu czasu, i przerzuca stan na instancję 2, i tak dalej. W ten sposób każda instancja zużywa tylko tyle procesora, ile jej wolno - ale widać gołym okiem, że nie o takie rozwiązania nam chodzi.
Niestety, uwzględnienie czasu oczekiwania na komunikację siłą rzeczy powoduje, że liczymy czas zegarowy, a nie czas procesora. Liczenie czasu procesora nie bardzo ma sens, bo jeśli jedna instancja zostanie spowolniona przez operacje jądra, a druga czeka na jej komunikat, to to spowolnienie i tak się odbije na czasie działania programu - nawet jeśli pierwszej instancji policzymy czas procesora, to drugiej siłą rzeczy będziemy liczyli czas oczekiwania jako czas zegarowy.
Z powodów jak wyżej - działania systemu operacyjnego i programów pomocniczych, a także niestabilność opóźnień sieciowych oraz drobne różnice w momencie startu programów - czas działania programu nie jest tak stabilny jak w wypadku mierzenia czasu przez cykle procesora. Są też różnice związane z tym, na których konkretnie komputerach zadanie zostanie uruchomione (bo topologia sieci powoduje, że nie każde dwa komputery mają tę samą prędkość nawiązywania połączenia). Nie mamy dokładnych pomiarów tego, które z wspomnianych parametrów są najbardziej istotne; ja obstawiałbym że największy wpływ mają działania "w tle" systemu operacyjnego i demonów systemowych.
Dodam tu, że na pojedynczej maszynie było uruchamiane tylko jedno rozwiązanie na raz; nie zauważyliśmy istotnych zależności między obciążeniem systemu a czasem działania rozwiązań.
Mam nadzieję, że system sprawdzania zadań rozproszonych będzie się rozwijał, i będą pojawiały się pomysły na redukcję tej wariancji. Pewnie warto też dodać, że nie zredukujemy jej do zera nigdy - i dla przypadku jednomaszynowego również nie jest ona zredukowana do zera, jak pisałem wyżej - jest możliwe, że na zwykłej sprawdzaczce jedno z dwóch uruchomień tego samego kodu dostanie TLE, a drugie OK. Natomiast jest dla mnie dość oczywiste, że da się ją zredukować bardziej - choć uznaliśmy, że obecne parametry są akceptowalne, to chciałbym jeszcze sporo je poprawić.
Mogę prosić o jakieś małe testy?
Pierwsze moje zgłoszenie (dzieliło zawsze na 1000 pasków poziomych i #Instancji pasków pionowych):
1 OK 0.28s/1.00s 20 1/1
2 OK 1.99s/5.00s 18 1/1
3 OK 2.56s/8.00s 12 1/1
4 OK 3.27s/10.00s 20 1/1
5 OK 2.81s/10.00s 48 1/1
6 OK 3.41s/18.00s 20 1/1
7 OK 3.71s/22.00s 25 1/1
8 OK 3.95s/16.00s 50 1/1
9 OK 4.60s/12.00s 100 1/1
10 OK 3.32s/6.00s 100 1/1
Drugie (finalne) zgłoszenie (potencjalnie używało mniejszej liczby instancji niż dostarczonych, i mniejszej liczby pasków):
1 OK 0.15s/1.00s 20 1/1
2 OK 0.57s/5.00s 18 1/1
3 OK 1.12s/8.00s 12 1/1
4 OK 1.22s/10.00s 20 1/1
5 OK 1.47s/10.00s 48 1/1
6 OK 2.48s/18.00s 20 1/1
7 OK 3.30s/22.00s 25 1/1
8 OK 2.51s/16.00s 50 1/1
9 OK 3.55s/12.00s 100 1/1
10 OK 2.40s/6.00s 100 1/1
Gdyby trochę lepiej dofitować funkcję estimated_time(N, M, P, B) to pewnie by się jeszcze trochę dało zejść.
U mnie było:
NoN = NumberOfNodes();
best_runtime_us = 86400 * 1000000LL; // 1 day ~ infinity
for (p = 1; p <= NoN; ++p) {
for (i = 1; i <= 1000; ++i) {
// 12.3ns compute per cell (w praktyce chyba bliżej 5.7ns)
long long runtime_us = n * 123LL * m * (i + 1) / i / p / 10000;
// 0.500ms synchronization overhead (w praktyce chyba bliżej 1.9ms)
runtime_us += i * 500LL;
if (runtime_us < best_runtime_us) {
best_runtime_us = runtime_us;
best_nodes = p;
best_pieces = i;
};
if (i >= 10) i += 1;
if (i >= 100) i += 8;
};
};
NoN = best_nodes;
messages = best_pieces;
if (MyNodeId() >= NoN) return 0;
if (NoN == 1) messages = 1;
// should not happen, but safety first
if (messages > 1000) messages = 1000;
if (messages < 1) messages = 1;
// B ~=~ m / messages
1 OK 0.28s/1.00s 20 1/1
2 OK 1.99s/5.00s 18 1/1
3 OK 2.56s/8.00s 12 1/1
4 OK 3.27s/10.00s 20 1/1
5 OK 2.81s/10.00s 48 1/1
6 OK 3.41s/18.00s 20 1/1
7 OK 3.71s/22.00s 25 1/1
8 OK 3.95s/16.00s 50 1/1
9 OK 4.60s/12.00s 100 1/1
10 OK 3.32s/6.00s 100 1/1
Drugie (finalne) zgłoszenie (potencjalnie używało mniejszej liczby instancji niż dostarczonych, i mniejszej liczby pasków):
1 OK 0.15s/1.00s 20 1/1
2 OK 0.57s/5.00s 18 1/1
3 OK 1.12s/8.00s 12 1/1
4 OK 1.22s/10.00s 20 1/1
5 OK 1.47s/10.00s 48 1/1
6 OK 2.48s/18.00s 20 1/1
7 OK 3.30s/22.00s 25 1/1
8 OK 2.51s/16.00s 50 1/1
9 OK 3.55s/12.00s 100 1/1
10 OK 2.40s/6.00s 100 1/1
Gdyby trochę lepiej dofitować funkcję estimated_time(N, M, P, B) to pewnie by się jeszcze trochę dało zejść.
U mnie było:
NoN = NumberOfNodes();
best_runtime_us = 86400 * 1000000LL; // 1 day ~ infinity
for (p = 1; p <= NoN; ++p) {
for (i = 1; i <= 1000; ++i) {
// 12.3ns compute per cell (w praktyce chyba bliżej 5.7ns)
long long runtime_us = n * 123LL * m * (i + 1) / i / p / 10000;
// 0.500ms synchronization overhead (w praktyce chyba bliżej 1.9ms)
runtime_us += i * 500LL;
if (runtime_us < best_runtime_us) {
best_runtime_us = runtime_us;
best_nodes = p;
best_pieces = i;
};
if (i >= 10) i += 1;
if (i >= 100) i += 8;
};
};
NoN = best_nodes;
messages = best_pieces;
if (MyNodeId() >= NoN) return 0;
if (NoN == 1) messages = 1;
// should not happen, but safety first
if (messages > 1000) messages = 1000;
if (messages < 1) messages = 1;
// B ~=~ m / messages
U mnie:
1 OK 0.23s/1.00s 10 1/1
2 OK 0.92s/1.00s 20 1/1
3 OK 2.79s/10.00s 30 1/1
4 OK 1.70s/4.00s 40 1/1
5 OK 1.61s/3.00s 50 1/1
6 OK 1.10s/2.00s 60 1/1
7 OK 1.13s/2.00s 70 1/1
8 OK 1.96s/4.00s 80 1/1
9 OK 1.36s/3.00s 90 1/1
10 OK 1.81s/2.00s 100 1/1
Jak widać bardzo na styk szczególnie na 2gim i 10tym.
1 OK 0.23s/1.00s 10 1/1
2 OK 0.92s/1.00s 20 1/1
3 OK 2.79s/10.00s 30 1/1
4 OK 1.70s/4.00s 40 1/1
5 OK 1.61s/3.00s 50 1/1
6 OK 1.10s/2.00s 60 1/1
7 OK 1.13s/2.00s 70 1/1
8 OK 1.96s/4.00s 80 1/1
9 OK 1.36s/3.00s 90 1/1
10 OK 1.81s/2.00s 100 1/1
Jak widać bardzo na styk szczególnie na 2gim i 10tym.
http://xkcd.com/1210/
Oba programy miały to samo ziarno, więc oba powinny być tak samo popsute ;)
EDIT: Dostałem odpowiedź od organizatorów w tej kwestii:
http://pastebin.com/8JHsrSmz
Muszę powiedzieć, że wyjaśnienie jest wyczerpujące i, co najważniejsze, zawiera wyjaśnienie przyczyny problemu, a nie tylko przyznanie, że istnieje. Brawa dla ekipy!
Oba programy miały to samo ziarno, więc oba powinny być tak samo popsute ;)
EDIT: Dostałem odpowiedź od organizatorów w tej kwestii:
http://pastebin.com/8JHsrSmz
Muszę powiedzieć, że wyjaśnienie jest wyczerpujące i, co najważniejsze, zawiera wyjaśnienie przyczyny problemu, a nie tylko przyznanie, że istnieje. Brawa dla ekipy!
Nie potwierdzam ani outów Konrada ani Adama :)
Moje: http://students.mimuw.edu.pl/~pg290637/ple.tar.gz
Moje: http://students.mimuw.edu.pl/~pg290637/ple.tar.gz
Potwierdzam wszystkie testy, czasy < 0,6s.
> 3. 5 osób napisało, że nie potwierdza outów Konrada i ani jedna nie wrzuciła swoich outów. Serio?
<te outy były złe>
<te outy były złe>
Dzięki Mateusz i Kamil. Już wiem co przeoczyłem w treści :)
A po co ci zależność między m i k ?
co do twojego testu to masz m=1 i k=1,
a masz dwa przelania:
-1 2
-3 2
i reaguje jedna para:
-2 3
co do twojego testu to masz m=1 i k=1,
a masz dwa przelania:
-1 2
-3 2
i reaguje jedna para:
-2 3
Jakie macie czasy?
Wielkie dzięki, tylko... Hmmm, w wejściu które podałem jest chyba tylko jedno przelanie zawartości. Bo m=1 to czyli liczba kroków, czyli przelewanie zawartości.
Z drugiej strony tak trochę głupio się czuję, bo właśnie wiem, że czegoś nie zauważyłem, ale jednak w specyfikacji nie mogę się doszukać opisanej żadnej zależności między m - liczbą kroków, a k - liczbą substancji reagujących ze sobą. Ogólnie mam wrażenie, że "czegoś tu brakuje", czyli albo czegoś trzeba się domyślić z treści, albo coś jest jasno napisane, ale ja po prostu nie mogę tego zauważyć.
Z drugiej strony tak trochę głupio się czuję, bo właśnie wiem, że czegoś nie zauważyłem, ale jednak w specyfikacji nie mogę się doszukać opisanej żadnej zależności między m - liczbą kroków, a k - liczbą substancji reagujących ze sobą. Ogólnie mam wrażenie, że "czegoś tu brakuje", czyli albo czegoś trzeba się domyślić z treści, albo coś jest jasno napisane, ale ja po prostu nie mogę tego zauważyć.