Oprogramowanie naukowe nie różni się tak bardzo od innych programów, jak wiedzieć, co wymaga strojenia.
Metoda, której używam, to losowe wstrzymywanie . Oto niektóre z przyspieszeń, które dla mnie znalazł:
Jeśli duża część czasu jest poświęcana na funkcje takie jak logi exp, widzę, jakie są argumenty tych funkcji, w zależności od punktów, z których są wywoływane. Często są oni wywoływani wielokrotnie z tym samym argumentem. Jeśli tak, zapamiętywanie powoduje ogromny współczynnik przyspieszenia.
Jeśli korzystam z funkcji BLAS lub LAPACK, może się okazać, że duża część czasu poświęcana jest na procedury kopiowania tablic, mnożenia macierzy, transformacji choleski itp.
Rutynowe kopiowanie tablic nie jest dostępne dla szybkości, jest dla wygody. Może się okazać, że jest to mniej wygodny, ale szybszy sposób na zrobienie tego.
Procedury mnożenia lub odwracania macierzy lub wykonywania transformacji choleskiego zwykle zawierają argumenty znakowe określające opcje, takie jak „U” lub „L” dla trójkąta górnego lub dolnego. Ponownie są one dostępne dla wygody. Odkryłem, że ponieważ moje matryce nie były bardzo duże, procedury spędzały ponad połowę czasu na wzywaniu podprogramu do porównywania znaków w celu rozszyfrowania opcji. Pisanie specjalnych wersji najbardziej kosztownych procedur matematycznych spowodowało ogromne przyspieszenie.
Jeśli mogę po prostu rozwinąć to drugie: procedura mnożenia macierzy DGEMM wywołuje LSAME w celu zdekodowania argumentów znaków. Patrząc na uwzględniające procent czasu (jedyne statystyki, na które warto spojrzeć) profilery uważane za „dobre” mogą pokazywać DGEMM wykorzystujący pewien procent całkowitego czasu, np. 80%, a LSAME wykorzystujący pewien procent całkowitego czasu, np. 50%. Patrząc na te pierwsze, kusiłoby cię, by powiedzieć „dobrze, to musi być mocno zoptymalizowane, więc niewiele mogę na to poradzić”. Patrząc na to drugie, kusiłaby cię odpowiedź: „Hę? O co w tym wszystkim chodzi? To tylko drobna rutyna. Ten profiler musi się mylić!”
To nie jest źle, po prostu nie mówi ci, co musisz wiedzieć. Losowe wstrzymywanie pokazuje, że DGEMM znajduje się na 80% próbek stosu, a LSAME na 50%. (Nie potrzeba dużo próbek, aby to wykryć. 10 to zwykle dużo.) Co więcej, w wielu z tych próbek DGEMM właśnie wywołuje LSAME z kilku różnych linii kodu.
Teraz już wiesz, dlaczego obie procedury zabierają tyle czasu. Wiesz także, skąd w kodzie są wywoływani, aby spędzać cały ten czas. Dlatego używam losowego pauzowania i przeglądam profilowane profile bez względu na to, jak są dobrze wykonane. Bardziej interesują ich pomiary niż informowanie o tym, co się dzieje.
Łatwo jest założyć, że procedury biblioteczne matematyki zostały zoptymalizowane do n-tego stopnia, ale w rzeczywistości zostały zoptymalizowane tak, aby były przydatne do szerokiego zakresu celów. Musisz zobaczyć, co się naprawdę dzieje, a nie to, co łatwo założyć.
DODANO: Aby odpowiedzieć na dwa ostatnie pytania:
Jakie są najważniejsze rzeczy do wypróbowania w pierwszej kolejności?
Pobierz 10–20 próbek stosu i nie podsumowuj ich, zrozum, co każdy z nich mówi. Zrób to pierwszy, ostatni i pomiędzy. (Nie ma „próby”, młody Skywalker.)
Skąd mam wiedzieć, ile wydajności mogę uzyskać?
xβ(s+1,(n−s)+1)sn1/(1−x)n=10s=5x
xx
Jak już wcześniej wspomniałem, możesz powtarzać całą procedurę, aż nie będziesz już w stanie, a złożony współczynnik przyspieszenia może być dość duży.
(s+1)/(n+2)=3/22=13.6%.) Dolna krzywa na poniższym wykresie to jej rozkład:
Zastanów się, czy pobraliśmy aż 40 próbek (więcej niż kiedykolwiek naraz) i zauważyliśmy problem tylko na dwóch z nich. Szacunkowy koszt (tryb) tego problemu wynosi 5%, jak pokazano na wyższej krzywej.
Co to jest „fałszywie pozytywny”? Chodzi o to, że jeśli naprawisz problem, zdajesz sobie sprawę, że zyskujesz tak mniej niż oczekiwano, że żałujesz, że go naprawiłeś. Krzywe pokazują (jeśli problem jest „mały”), że chociaż wzmocnienie może być mniejsze niż ułamek próbek, które go pokazują, to średnio będzie ono większe.
Istnieje znacznie poważniejsze ryzyko - „fałszywie ujemny”. Wtedy pojawia się problem, ale go nie znaleziono. (Przyczynia się to do „uprzedzenia potwierdzającego”, w którym brak dowodów jest zwykle traktowany jako dowód braku).
Za pomocą profilera (dobrego) otrzymujesz znacznie dokładniejszy pomiar (a tym samym mniejsze prawdopodobieństwo fałszywych alarmów), kosztem znacznie mniej dokładnych informacji o tym, co w rzeczywistości jest problemem (a tym samym mniejszą szansą na jego znalezienie i uzyskanie wszelkie zyski). Ogranicza to ogólne przyspieszenie, które można osiągnąć.
Zachęcam użytkowników profilerów do zgłaszania czynników przyspieszenia, które faktycznie uzyskują w praktyce.
Jest jeszcze jedna kwestia do zrobienia. Pytanie Pedro dotyczące fałszywych trafień.
Wspomniał, że może istnieć trudność w przejściu do drobnych problemów w wysoce zoptymalizowanym kodzie. (Dla mnie mały problem to taki, który stanowi 5% lub mniej całkowitego czasu.)
Ponieważ jest całkowicie możliwe zbudowanie programu, który jest całkowicie optymalny, z wyjątkiem 5%, kwestię tę można rozwiązać tylko empirycznie, jak w tej odpowiedzi . Aby uogólnić na podstawie doświadczenia empirycznego, wygląda to tak:
Program, jak napisano, zazwyczaj zawiera kilka możliwości optymalizacji. (Możemy nazwać je „problemami”, ale często są one doskonale dobrym kodem, po prostu zdolnym do znacznej poprawy.) Ten schemat ilustruje sztuczny program zajmujący trochę czasu (powiedzmy 100s) i zawiera problemy A, B, C, ... że po znalezieniu i naprawieniu zaoszczędzisz 30%, 21% itd. oryginalnych setek.
Zauważ, że problem F kosztuje 5% pierwotnego czasu, więc jest „mały” i trudny do znalezienia bez 40 lub więcej próbek.
Jednak pierwsze 10 próbek z łatwością znajduje problem A. ** Gdy problem zostanie rozwiązany, program zajmuje tylko 70s, dla przyspieszenia 100/70 = 1,43x. To nie tylko przyspiesza działanie programu, ale także powiększa, o ten współczynnik, wartości procentowe pozostałych problemów. Na przykład problem B początkowo zajmował 21 s, co stanowiło 21% całości, ale po usunięciu A B bierze 21 z 70, czyli 30%, więc łatwiej jest znaleźć, gdy cały proces się powtarza.
Po pięciokrotnym powtórzeniu procesu czas wykonania wynosi 16,8 s, z czego problem F wynosi 30%, a nie 5%, więc łatwo jest znaleźć 10 próbek.
Więc o to chodzi. Empirycznie, programy zawierają szereg problemów mających rozkład rozmiarów, a każdy znaleziony i naprawiony problem ułatwia znalezienie pozostałych. Aby to osiągnąć, żaden z problemów nie może zostać pominięty, ponieważ jeśli tak, siedzą tam, poświęcając czas, ograniczając całkowite przyspieszenie i nie powiększając pozostałych problemów.
Dlatego bardzo ważne jest, aby znaleźć ukryte problemy .
Jeśli problemy od A do F zostaną znalezione i naprawione, przyspieszenie wynosi 100 / 11,8 = 8,5x. Jeśli jeden z nich zostanie pominięty, na przykład D, wówczas przyspieszenie wynosi tylko 100 / (11,8 + 10,3) = 4,5x.
To cena zapłacona za fałszywe negatywy.
Tak więc, gdy profiler mówi „nie ma tutaj żadnego istotnego problemu” (tj. Dobry koder, jest to praktycznie optymalny kod), być może ma rację, a może nie. ( Fałszywie negatywny .) Nie wiesz na pewno, czy jest więcej problemów do naprawienia, w celu przyspieszenia, chyba że spróbujesz innej metody profilowania i odkryjesz, że są. Z mojego doświadczenia wynika, że metoda profilowania nie wymaga dużej liczby próbek, w skrócie, ale niewielkiej liczby próbek, przy czym każda próbka jest wystarczająco dokładnie rozumiana, aby rozpoznać każdą możliwość optymalizacji.
2/0.3=6.671 - pbinom(1, numberOfSamples, sizeOfProblem)1 - pbinom(1, 20, 0.3) = 0.9923627
xβ(s+1,(n−s)+1)nsy1/(1−x)xyy−1Dystrybucja BetaPrime . Symulowałem to z 2 milionami próbek, dochodząc do tego zachowania:
distribution of speedup
ratio y
s, n 5%-ile 95%-ile mean
2, 2 1.58 59.30 32.36
2, 3 1.33 10.25 4.00
2, 4 1.23 5.28 2.50
2, 5 1.18 3.69 2.00
2,10 1.09 1.89 1.37
2,20 1.04 1.37 1.17
2,40 1.02 1.17 1.08
3, 3 1.90 78.34 42.94
3, 4 1.52 13.10 5.00
3, 5 1.37 6.53 3.00
3,10 1.16 2.29 1.57
3,20 1.07 1.49 1.24
3,40 1.04 1.22 1.11
4, 4 2.22 98.02 52.36
4, 5 1.72 15.95 6.00
4,10 1.25 2.86 1.83
4,20 1.11 1.62 1.31
4,40 1.05 1.26 1.14
5, 5 2.54 117.27 64.29
5,10 1.37 3.69 2.20
5,20 1.15 1.78 1.40
5,40 1.07 1.31 1.17
(n+1)/(n−s)s=ny
Jest to wykres rozkładu współczynników przyspieszenia i ich średnich dla 2 trafień z 5, 4, 3 i 2 próbek. Na przykład, jeśli zostaną pobrane 3 próbki, a 2 z nich to trafienie w problem, a problem ten można usunąć, średni współczynnik przyspieszenia wyniesie 4x. Jeśli 2 trafienia są widoczne tylko w 2 próbkach, średnie przyspieszenie jest niezdefiniowane - koncepcyjnie, ponieważ programy z nieskończonymi pętlami istnieją z niezerowym prawdopodobieństwem!
