Stanowisko organizatorów.

Są to fluktuacje sprawdzarki, podejrzewam, że mogą być związane nawet nie tyle z fluktuacją wydajności, co ze sposobem pomiaru.

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.

Nasze eksperymenty pokazywały, że standardowe odchylenie czasu działania to około 5%. W Twoim wypadku to odchylenie wyniosło około 12%, czyli faktycznie niefortunnie dużo, ale jeszcze w granicach akceptowalnej dla nas normy, biorąc pod uwagę, że wzorcówki mieściły się w połowie limitów czasowych.

Zgadzam się, że to przykre, kiedy takie zdarzenie losowe wpływa na wynik. Mimo to mam wrażenie, że sytuacja w której nie jest w pełni deterministyczne, czy rozwiązanie znajdujące się blisko krawędzi limitu czasowego przekroczy go, czy nie, jest wpisana w naturę systemu sprawdzaczek; wraz z rozwojem systemu do sprawdzania zadań rozproszonych będziemy walczyli o redukcję tego wariancji (i w związku z tym redukcję zakresu "blisko", który jest zagrożony taką losowością).