Prawidłowe statystyki dotyczące raportowania wyników przyspieszenia

Powiedzmy, że mam powolne i szybkie wersje niektórych kodów i chcę zgłosić liczbę przyspieszeń porównującą oba. Uruchamiam wolną wersję razy i szybką wersję razy, generując czasy i . Najprostszy sposób wytwarzania a przyspieszenie jest średnio środki: $n$ $m$ $(s_1, \ldots, s_n)$ $(f_1, \ldots, f_m)$ Nie uwzględnia to jednak wartości odstających.

\frac{\bar{s}}{\bar{f}} = \frac{m \sum_{i < n} s_{i}}{n \sum_{j < m} f_{j}}

$\frac{\bar{s}}{\bar{f}} = \frac{m \sum_{i<n} s_i}{n \sum_{j<m} f_j}$

Pytanie : Jakiej statystyki najlepiej użyć do zgłaszania liczb przyspieszenia?

statistics publications

— Geoffrey Irving
źródło

Jak duże jest odchylenie standardowe w porównaniu ze średnią? Cokolwiek zrobisz, powinieneś zgłosić to, co zrobiłeś i prawdopodobnie umieścić paski błędów, jeśli są duże. Jeśli są naprawdę duże, powinieneś zbadać źródło. Większość kodu komputerowego powinna działać dość deterministycznie w czasie, chyba że w samym programie znajduje się losowy komponent lub jeśli udostępniasz zasoby komputerowe innym osobom (może to być sieć lub dysk, a nie tylko węzły klastra). Jeśli problemem jest rywalizacja o zasoby dyskowe, możesz rozważyć raportowanie wydajności przy wyłączonym We / Wy (dość powszechne) - pamiętaj o tym.

— Bill Barth

W przypadku Edisona (superkomputera Cray) mam 2% różnicy między dwiema próbkami. Na moim laptopie widzę odchylenie standardowe 6-8% mierzone w 10 próbkach. Oba są tylko dla jądra obliczeniowego, bez we / wy.

— Geoffrey Irving

Aby wyjaśnić, dlaczego wspominam o wartościach odstających, jeśli wariancje są już wystarczająco niskie: jest to wystarczająco podstawowa wielkość statystyczna, że chciałbym znać idealny sposób na zgłoszenie tego, nawet w przypadku tego nieprzystosowanego rozwiązania są w porządku.

— Geoffrey Irving

Pytanie brzmi: co próbujesz przekazać, a formuła najlepiej się komunikuje? Nie sądzę, że kiedykolwiek widziałem artykuł opisujący zmienność przyspieszania między biegami, chyba że przyczyna była najważniejsza. Biorąc pod uwagę, że zakładamy liniową zależność między czasem działania a liczbą procesorów / zadań / wątków, prawdopodobnie dobrze jest użyć współczynnika średnich, ale następnie pasek błędu, który przy stosunku wartości maksymalnych do minimalnych i minimalnych do maksymalnych jeśli uważasz, że pokazanie zasięgu jest ważne. Powinieneś również spojrzeć na opcje skalowania częstotliwości i przypinania zadań, aby zmniejszyć zmienność. :)

— Bill Barth

Eliminowanie IO może być trudne. Pomiędzy optymalizacjami kompilatora a sztuczkami „Copy On Write” mogą istnieć naprawdę nieoczywiste powiązania w dół. Zwykle podążam za prototypem d1 = loadData (); d2 = kopia (d1); r1 = algo (d2); r2 = algo (d1) i uwzględniaj tylko czas drugiego uruchomienia.

— meawoppl

Odpowiedzi:

Oprócz wszystkiego, co Bill Barth powiedział już powyżej, pozwól mi wspomnieć, że ludzie często zgłaszają najszybszy z kilku przebiegów. Uzasadnieniem jest fakt, że rzeczywisty czas działania to idealny czas działania plus dowolna liczba spowolnień wynikających z innych uruchomionych procesów, opóźnień systemu operacyjnego, opóźnień sieci itp. Ponieważ są to szumy, którymi nie jesteśmy zainteresowani, korzystanie z najszybszego czasu działania najbliżej tego, który naprawdę chcemy wiedzieć.

— Wolfgang Bangerth
źródło

Niestety ta zasada nie pomaga przy zgłaszaniu przyspieszenia między dwoma algorytmami.

— Geoffrey Irving

@GeoffreyIrving, dlaczego nie? Oba algorytmy mają teoretyczną oczekiwaną wydajność w stosunku do wielkości problemu (lub liczby procesorów lub innych parametrów niestatystycznych) z ignorowanymi terminami niskiego rzędu i niezależnymi od parametrów. Wykorzystanie najszybszego czasu (i zauważenie tego faktu) pomaga po prostu zignorować te dodatkowe warunki. Co wydaje się dobrą strategią. O ile nie powiesz nam inaczej, wygląda na to, że próbujesz dowiedzieć się, jak najskuteczniej przekazać różnicę między algorytmami, a sugestia Wolfganga jest konwencjonalna i oczekiwana, aby najlepiej przekazać tę informację.

— Bill Barth

Ups, tak, masz rację. Z radością wycofuję moje oświadczenie.

— Geoffrey Irving

(+1) Pytanie poboczne: Uznaję twój punkt widzenia na temat niesymetrycznego rozkładu hałasu itp. Powiedzmy jednak, że wykonuję implementację A, a implementacja B i porównuję je i po rozsądnej liczbie uruchomień 25-ty kwantyl oraz mediana i średnia są około 4,5 razy szybsze w A niż B, podczas gdy 0% kwantyla wynosi około 3 razy. Porównując implementację A do B, pomimo że: yes A is theoretically only ~3x fasterczy przyspieszenie ~ 3x nie jest reprezentatywne dla przyspieszenia, jakiego można się spodziewać przy zastosowaniu implementacji A zamiast B? (

— Nawiasem mówiąc,

@ usεr11852: Wszystko zależy od używanego systemu. Jeśli twoja mediana lub 25-ty kwantyl są tak daleko od siebie, że zniekształcają statystyki w sposób, w jaki tu hipotezujesz, prawdopodobnie jesteś w systemie, który ma dużo hałasu. Na przykład mogą być używane przez innych w tym samym czasie itp. To może nie być reprezentatywne dla systemów, które inni mają do swoich powtórnych eksperymentów, i brzmiałoby to dla mnie, jakbyś przeceniał swoje wyniki w tym przypadku. Tak więc nadal sugeruję zgłaszanie najlepszych przebiegów. Cokolwiek robisz, powinieneś raportować w gazecie, jakich statystyk używasz.

— Wolfgang Bangerth,

Sugeruję użycie mediany do oszacowania statystycznego. W przeciwieństwie do średniej, mediana nie jest zniekształcona przez wartości odstające.

— Jan
źródło

W przypadku danych, w których wszystkie szumy są dodatnie (tj. Z niesymetrycznym rozkładem szumów), mediana jest równie zła, jak w przypadku innych statystyk. W przypadku czasów pracy tak jest rzeczywiście, patrz moja odpowiedź powyżej.

— Wolfgang Bangerth

Jeśli odchylenie standardowe nie jest nieistotne, można użyć dwóch wykresów pudełkowych obok siebie, skonstruowanych zgodnie z czasem jednego z algorytmów. Z pewnością nie są one standardem w analizie numerycznej, ale świetnie sobie radzą z wyświetlaniem tego rodzaju informacji.

— Federico Poloni
źródło