English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: [Kol] - rozwiązanie
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!
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ć.
Sugerowałbym, żeby wszystkie TLE przepuścić jeszcze raz przez system, i zrobić tak z 5 razy.
Każde TLE było puszczone przez system 3 razy. Istnieje dość niezaniedbywalny koszt podnoszenia liczby 3.