Zliczanie FLOP dla funkcji bibliotecznych

Oceniając liczbę FLOP w prostej funkcji, często można po prostu zejść w dół wyrażenia zestawiając podstawowe operatory arytmetyczne. Jednak w przypadku wyrażeń matematycznych obejmujących parzysty podział nie można tego zrobić i można oczekiwać, że będzie można porównać z liczbą FLOP z funkcji z tylko dodatkami i mnożeniami. Sytuacja jest jeszcze gorsza, gdy operacja jest implementowana w bibliotece. Dlatego konieczne jest pewne rozsądne pojęcie o wykonywaniu funkcji specjalnych.

Przez funkcje specjalne rozumiemy takie rzeczy jak:

• exp ()
• sqrt ()
• sin / cos / tan ()

które są zwykle dostarczane przez biblioteki systemowe.

Określenie ich złożoności jest jeszcze bardziej skomplikowane przez fakt, że wiele z nich jest adaptacyjnych i ma złożoność zależną od nakładów. Na przykład stabilne numerycznie implementacje exp () często adaptacyjnie skalują i używają odnośników. Moje pierwsze wrażenie tutaj jest takie, że najlepsze, co można zrobić w tym przypadku, to ustalić średnie zachowanie funkcji.

Cała ta dyskusja jest oczywiście wysoce zależna od architektury. W tej dyskusji możemy ograniczyć się do tradycyjnych architektur ogólnego przeznaczenia i wykluczyć te ze specjalnymi jednostkami funkcyjnymi (GPU, itp.)

Można znaleźć dość proste próby ujednolicenia ich dla poszczególnych architektur ze względu na porównanie systemu z systemem, ale nie jest to dopuszczalne, jeśli dba się o wydajność metody i metody. Jakie metodologie określania złożoności FLOP tych funkcji uważa się za dopuszczalne? Czy są jakieś poważne pułapki?

Wygląda na to, że chcesz sposobu, aby ocenić, jak twój kod jest związany z FPU lub jak efektywnie używasz FPU, zamiast liczyć liczbę flopów zgodnie z tą samą anachroniczną definicją „flop”. Innymi słowy, potrzebujesz metryki, która osiąga ten sam szczyt, jeśli każda jednostka zmiennoprzecinkowa pracuje z pełną wydajnością w każdym cyklu. Spójrzmy na Intel Sandy Bridge, aby zobaczyć, jak może się to potrząsnąć.

Obsługiwane sprzętowo operacje zmiennoprzecinkowe

Ten układ obsługuje instrukcje AVX , więc rejestry mają długość 32 bajtów (mieszcząc 4 podwójne). Architektura superskalarna pozwala na nakładanie się instrukcji, przy czym większość instrukcji arytmetycznych zajmuje kilka cykli, nawet jeśli nowa instrukcja może zacząć od następnego cyklu. Te semantyki są zwykle skracane przez zapisanie opóźnienia / odwrotnej przepustowości, wartość 5/2 oznaczałaby, że wykonanie instrukcji zajmuje 5 cykli, ale możesz rozpocząć nową instrukcję co drugi cykl (zakładając, że operandy są dostępne, więc nie ma danych zależność i nie czekanie na pamięć).

Istnieją trzy zmiennoprzecinkowe jednostki arytmetyczne na rdzeń, ale trzecia nie jest istotna w naszej dyskusji, nazwiemy odpowiednie dwie jednostki A i M, ponieważ ich podstawowymi funkcjami są dodawanie i mnożenie. Przykładowe instrukcje (patrz tabele Agner Fog )

• vaddpd: dodatek zapakowany, jednostka zajmująca A na 1 cykl, opóźnienie / odwrotność wynosi 3/1
• vmulpd: mnożenie upakowane, jednostka M, 5/1
• vmaxpd: pakowane wybierz maksimum parami, jednostka A, 3/1
• vdivpd: dzielenie upakowane, jednostka M (i część A), od 21/20 do 45/44 w zależności od danych wejściowych
• vsqrtpd: upakowany pierwiastek kwadratowy, niektóre A i M, 21/21 do 43/43 w zależności od danych wejściowych
• vrsqrtps: upakowany pierwiastek odwrotny o niskiej dokładności dla pojedynczej precyzji wprowadzania (8 floats)

Precyzyjna semantyka tego, co może się pokrywać vdivpdi vsqrtpdjest najwyraźniej subtelna i AFAIK, nigdzie nie udokumentowana. W większości zastosowań myślę, że istnieje niewielka możliwość nakładania się, chociaż sformułowanie w instrukcji sugeruje, że wiele wątków może zaoferować więcej możliwości nakładania się w tej instrukcji. Możemy uderzyć w szczytowe klapy, jeśli zaczniemy a vaddpdi vmulpdw każdym cyklu, w sumie 8 klapek na cykl. Gęsta matryca-macierz ( dgemm) może zbliżyć się do tego piku.

Licząc klapy dla specjalnych instrukcji, spojrzałbym na to, ile FPU jest zajęte. Załóżmy dla argumentu, że w twoim zakresie danych wejściowych vdivpdzajęło średnio 24 cykle, w pełni zajmując jednostkę M, ale dodawanie mogło (jeśli było dostępne) być wykonywane jednocześnie dla połowy cykli. FPU jest w stanie wykonać 24 spakowanych mnożników i 24 spakowanych dodatków podczas tych cykli (idealnie przeplecione vaddpdi vmulpd), ale przy vdivpdnajlepszym, co możemy zrobić, to 12 dodatkowych spakowanych dodatków. Jeśli przypuszczamy, że najlepszym możliwym sposobem podziału jest użycie sprzętu (rozsądne), możemy liczyć vdivpdjako 36 spakowanych „klap”, co oznacza, że ​​powinniśmy liczyć każdy podział skalarny jako 36 „klap”.

Dzięki odwrotnemu pierwiastkowi kwadratowemu czasami można pokonać sprzęt, szczególnie jeśli pełna dokładność nie jest potrzebna lub gdy zakres danych wejściowych jest wąski. Jak wspomniano powyżej, vrsqrtpsinstrukcja jest bardzo tania, więc (jeśli z pojedynczą precyzją) możesz wykonać jedną, vrsqrtpsa następnie jedną lub dwie iteracje Newtona, aby wyczyścić. Te iteracje Newtona są słuszne

y *= (3 - x*y*y)*0.5;

Jeśli trzeba wykonać wiele z tych operacji, może to być znacznie szybsze niż naiwna ocena y = 1/sqrt(x). Przed udostępnieniem sprzętowego przybliżonego pierwiastka kwadratowego niektóre wrażliwe na wydajność kody wykorzystywały niesławne operacje na liczbach całkowitych w celu znalezienia wstępnego odgadnięcia iteracji Newtona.

Dostarczone przez bibliotekę funkcje matematyczne

Możemy zastosować podobną heurystykę do funkcji matematycznych udostępnianych przez bibliotekę. Możesz profilować, aby określić liczbę instrukcji SSE, ale jak już omówiliśmy, to nie jest cała historia, a program, który spędza cały czas na ocenie funkcji specjalnych, może nie wydawać się zbliżać do szczytu, co może być prawdą, ale nie przydaje się, aby powiedzieć, że cały czas spędzasz poza kontrolą FPU.

Sugeruję użycie dobrej biblioteki matematyki wektorowej jako podstawy (np. VML Intela, część MKL). Zmierz liczbę cykli dla każdego połączenia i pomnóż przez szczytowe osiągalne klapy przez tę liczbę cykli. Jeśli więc upakowana wykładnicza wartość trwa 50 cykli, policz ją jako 100 klap razy szerokość rejestru. Niestety, biblioteki matematyki wektorowej są czasami trudne do wywołania i nie mają wszystkich specjalnych funkcji, więc możesz skończyć na matematyce skalarnej, w którym to przypadku policzysz naszą hipotetyczną wykładniczą skalarną jako 100 flopów (nawet jeśli prawdopodobnie nadal zajmuje 50 cykli, więc otrzymasz tylko 25% „szczytu”, jeśli cały czas poświęcasz na ocenę tych wykładniczych).

Jak wspomnieli inni, można liczyć cykle i sprzętowe liczniki zdarzeń za pomocą PAPI lub różnych interfejsów. W celu prostego liczenia cykli można bezpośrednio odczytywać licznik cykli, korzystając z rdtscinstrukcji z fragmentem zestawu wbudowanego.

Można je liczyć na prawdziwych systemach za pomocą interfejsu PAPI , który zapewnia dostęp do liczników sprzętowych i prostych programów testowych. Mój ulubiony interfejs / opakowanie PAPI to IPM (Integrated Performance Monitor), ale istnieją inne rozwiązania ( na przykład TAU ). Powinno to dać dość stabilne porównanie między metodami.

Odpowiem na to pytanie, tak jakbyś pytał:

„Jak analitycznie porównać lub przewidzieć wydajność algorytmów, które w dużym stopniu opierają się na funkcjach specjalnych, zamiast tradycyjnych liczników FLOP z wielokrotnym dodawaniem i przenoszeniem, które pochodzą z numerycznej algebry liniowej”

Zgadzam się z twoją pierwszą przesłanką, że wydajność wielu funkcji specjalnych jest zależna od architektury i że chociaż zwykle możesz traktować każdą z tych funkcji jako mający stały koszt, wielkość stałej będzie się różnić, nawet między dwoma procesorami tego samego firma, ale o różnych architekturach (patrz tabela czasowa instrukcji Agner Fog ).

Nie zgadzam się jednak, że porównanie powinno koncentrować się na kosztach poszczególnych operacji zmiennoprzecinkowych. Myślę, że zliczanie FLOP jest w pewnym stopniu przydatne, ale istnieje kilka znacznie ważniejszych czynników, które mogą sprawić, że koszt funkcji specjalnych będzie mniej istotny przy porównywaniu dwóch potencjalnych algorytmów, i należy je najpierw dokładnie zbadać przed przejściem do porównania operacje zmiennoprzecinkowe:

1. Skalowalność - algorytmy obejmujące zadania, które można skutecznie wdrożyć na architekturach równoległych, zdominują naukową arenę obliczeniową w dającej się przewidzieć przyszłości. Algorytm o lepszej „skalowalności”, czy to poprzez niższą komunikację, mniejszą potrzebę synchronizacji, czy lepszy naturalny bilans obciążenia, może wykorzystywać wolniejsze funkcje specjalne, a zatem być wolniejszy dla niewielkiej liczby procesów, ale ostatecznie dogoni liczbę procesorów jest zwiększona.

2. Tymczasowa lokalizacja odniesienia - czy algorytm ponownie wykorzystuje dane między zadaniami, pozwalając procesorowi uniknąć niepotrzebnego ruchu pamięci? Każdy poziom hierarchii pamięci, przez który przechodzi algorytm, dodaje inny rząd wielkości (mniej więcej) do każdego dostępu do pamięci. W rezultacie algorytm o dużej gęstości operacji specjalnych będzie prawdopodobnie znacznie szybszy niż algorytm o równoważnej liczbie prostych operacji funkcyjnych w większym obszarze pamięci.

3. Ślad pamięci - jest to ściśle związane z poprzednimi punktami, ale w miarę jak komputery rosną i rosną, ilość pamięci na rdzeń faktycznie maleje. Małe rozmiary pamięci mają dwie zalety. Po pierwsze, niewielka ilość danych programu prawdopodobnie będzie mogła zmieścić się całkowicie w pamięci podręcznej procesora. Po drugie, w przypadku bardzo dużych problemów algorytm o mniejszej powierzchni pamięci może zmieścić się w pamięci procesora, umożliwiając rozwiązanie problemów, które w innym przypadku wykraczałyby poza możliwości komputera.

Po co męczyć się liczeniem klap? Wystarczy policzyć cykle dla każdej operacji, a uzyskasz coś uniwersalnego.