Czy analiza algorytmiczna polegająca na liczeniu flopów jest przestarzała?

Na moich kursach analizy numerycznej nauczyłem się analizować wydajność algorytmów, licząc liczbę wymaganych operacji zmiennoprzecinkowych (klap) w stosunku do wielkości problemu. Na przykład w tekście Trefethen & Bau na temat numerycznej algebry liniowej są nawet trójwymiarowe zdjęcia liczby flopów.

Teraz modne jest stwierdzenie, że „flopy są bezpłatne”, ponieważ opóźnienie pamięci do pobrania czegokolwiek poza pamięcią podręczną jest o wiele większe niż koszt flopa. Ale nadal uczymy studentów, jak liczyć klapy, przynajmniej na kursach analizy numerycznej. Czy zamiast tego powinniśmy ich uczyć liczenia dostępów do pamięci? Czy musimy pisać nowe podręczniki? A może dostęp do pamięci jest zbyt specyficzny dla urządzenia, aby spędzać czas? Jaki będzie długoterminowy trend, jeśli chodzi o to, czy wąskie gardło ma dostęp do klap lub pamięci?

Uwaga: niektóre z poniższych odpowiedzi wydają się odpowiadać na inne pytanie, takie jak „Czy mam obsesyjnie przepisać moją implementację, aby zaoszczędzić kilka flopów lub poprawić wydajność pamięci podręcznej?” Ale pytam bardziej w stylu: „ Czy bardziej przydatne jest oszacowanie złożoności algorytmicznej pod względem operacji arytmetycznych lub dostępu do pamięci ?”

Myślę, że właściwą rzeczą (pierwsze zamówienie) jest przyjrzenie się stosunkowi flopów do bajtów potrzebnych w algorytmie, który nazywam . Niech będzie maksymalną szybkością flopa procesora, a maksymalną przepustowością. Jeśli , wówczas algorytm będzie ograniczony. Jeśli , algorytm jest ograniczony do flopa.F m a x B m a $\beta$$F_{\mathrm{max}}$$B_{\mathrm{max}}$Bmaxβ>Fma$\frac{F_{\mathrm{max}}}{\beta} > B_{\mathrm{max}}$$B_{\mathrm{max}}\beta > F_{\mathrm{max}}$

Myślę, że liczenie dostępu do pamięci jest obowiązkowe, ale powinniśmy również pomyśleć o:

• Ile pamięci lokalnej jest wymagane

• Ile mamy możliwych współbieżności

Następnie możesz zacząć analizować algorytmy dla nowoczesnego sprzętu.

Nie rozumiem, dlaczego trzeba być „zwycięzcą”; nie jest to gra o sumie zerowej, w której liczy się flop, a dostęp do pamięci musi zagłuszyć drugą. Możesz uczyć ich obu i myślę, że oboje mają swoje zastosowania. W końcu trudno powiedzieć, że twój algorytm z dostępem do pamięci pewnością będzie szybszy niż twój algorytm z dostępem . Wszystko zależy od względnych kosztów różnych części (tego nieznośnego czynnika, który zawsze ignorujemy w tych analizach!).O ( N ) O ( N log N ) O ( N 2$O(N^4)$$O(N)$$O(N \log N)$$O(N^2)$

Z szerszej perspektywy uważam, że analiza wydajności algorytmu powinna być „kompleksowa”. Jeśli uczymy ludzi prawdziwych programistów i użytkowników HPC, muszą oni zrozumieć, jakie są koszty programowania w prawdziwym świecie. Modele analizy abstrakcyjnej, które nie uwzględniają czasu programisty. Powinniśmy myśleć w kategoriach „całkowitego czasu do rozwiązania”, a nie tylko liczby flopów i wydajności algorytmicznej. Nie ma sensu spędzać trzech lub czterech dni programisty na przepisaniu procedury, która pozwoli zaoszczędzić jedną sekundę czasu komputerowego na zadanie, chyba że planujesz przeprowadzić kilka milionów obliczeń. Podobnie, kilkudniowa inwestycja pozwalająca zaoszczędzić godzinę lub dwie godziny obliczeń szybko się zwraca. Ten nowatorski algorytm może być niesamowity,

Jak zauważyli inni, odpowiedź zależy oczywiście od tego, czy wąskim gardłem jest przepustowość procesora czy pamięci. W przypadku wielu algorytmów, które działają na dowolnym zestawie danych o dowolnym rozmiarze, wąskim gardłem jest zwykle przepustowość pamięci, ponieważ zestaw danych nie mieści się w pamięci podręcznej procesora.

Co więcej, Knuth wspomina, że ​​analiza dostępu do pamięci prawdopodobnie wytrzyma próbę czasu, prawdopodobnie dlatego, że jest stosunkowo prosta (nawet biorąc pod uwagę łatwość buforowania) w porównaniu ze złożonością współczesnych potoków procesora i prognozowaniem rozgałęzień.

Knuth używa terminu gigamems w tomie 4A TAOCP podczas analizy BDD. Nie jestem pewien, czy używa go w poprzednich tomach. Wspomniał o tym, jak wytrzymać próbę czasu, podczas corocznego wykładu na temat choinki w 2010 roku.

Co ciekawe, robisz to źle Źle pokazuje, że nawet analizowanie wydajności w oparciu o operacje pamięci nie zawsze jest proste, ponieważ istnieją elementy, takie jak nacisk VM, które wchodzą w grę, jeśli dane nie mieszczą się jednocześnie w fizycznej pamięci RAM.

To, jak określisz koszty algorytmu, zależy od tego, na jakim „poziomie” obliczeń naukowych pracujesz i od (wąskiej lub szerokiej) klasy problemów, które rozważasz.

Jeśli zastanawiasz się nad optymalizacją pamięci podręcznej, jest to wyraźnie bardziej odpowiednie np. Dla implementacji numerycznych pakietów algebry liniowej, takich jak BLAS i podobne biblioteki. Należy to do optymalizacji niskiego poziomu i jest w porządku, jeśli masz ustalony algorytm dla konkretnego problemu i wystarczające ograniczenia na wejściu. Na przykład optymalizacja pamięci podręcznej może być istotna, aby uzyskać szybką implementację sprzężonej iteracji gradientu, jeśli obiecuje się, że macierz będzie wystarczająco rzadka.

Z drugiej strony, im szersza klasa problemów, tym mniej można przewidzieć na podstawie rzeczywistych obliczeń (np. Nie wiesz, jak bardzo rzadkie będą macierze wejściowe implementacji CG). Im szersza klasa maszyn, na których program ma działać, tym mniej można przewidzieć na architekturze pamięci podręcznej.

Ponadto, na wyższym poziomie informatyki naukowej, bardziej odpowiednia może być zmiana struktury problemu. Na przykład, jeśli poświęcasz czas na znalezienie dobrego warunku wstępnego dla liniowego układu równań, ten rodzaj optymalizacji zwykle przewyższa jakąkolwiek optymalizację niskiego poziomu, ponieważ liczba iteracji jest drastycznie zmniejszona.

Podsumowując, optymalizacja pamięci podręcznej jest użyteczna tylko wtedy, gdy nie ma już nic do optymalizacji przez równoległość i redukcję asymptotycznej liczby FLOP.

Myślę, że rozsądnie jest dostosować stanowisko informatyki teoretycznej: w końcu poprawa asymptotycznej złożoności algorytmu ma większy zwrot niż mikrooptymalizacja niektórych istniejących linii kodu. Dlatego zliczanie FLOP jest nadal preferowane.

Zawsze nie chciałem nawet myśleć o liczeniu klap, dostępach do pamięci czy cokolwiek innego. To koncepcja z lat 60. XX wieku, kiedy to, co zrobiłeś, było właściwie dane i tylko od tego, jak to zrobiłaś, zależało od optymalizacji algorytmicznej. Zastanów się nad rozwiązaniem problemu elementu skończonego na jednolitej siatce xyz, stosując albo Gaussowską eliminację iteracji Jacobiego.

Teraz możesz zoptymalizować to do piekła i zaoszczędzić kilka flopów, zyskując 10% czasu działania. Możesz też pomyśleć o wdrożeniu metody wielosieciowej i optymalnego warunku wstępnego bloku, uzyskując współczynnik 10 w czasie wykonywania. Do tego powinniśmy szkolić naszych uczniów - zastanów się, jakie złożone zewnętrzne algorytmy mogą cię zyskać, próbując znaleźć lepszy wewnętrzny algorytm. Twój szef (Keyes) ma te slajdy na temat postępów w obliczeniach MHD, które sprawiają, że ten punkt jest dość oczywisty.

Tak, przestarzałe. Analiza algorytmiczna za pomocą klap lub dowolną inną metodą jest tylko tak użyteczna jak abstrakcyjny model maszyny, biorąc pod uwagę rozmiar problemu. Rzeczywista wydajność zależy zarówno od implementacji, jak i od sprzętu, a wraz z upływem czasu zmniejsza się możliwość zastosowania dowolnego modelu abstrakcyjnego w przypadku tego drugiego do rzeczywistości. Na przykład, w miarę jak równolegle wdrażasz złożony algorytm, taki jak dynamika molekularna, różne aspekty stają się ograniczeniem szybkości na innym sprzęcie, a analiza algorytmiczna nie ma nic wspólnego z obserwacjami. W pewnym sensie jedyną ważną rzeczą jest pomiar wydajności implementacji algorytmu (algorytmów) na danym typie sprzętu.

Czy takie abstrakcje są przydatne jako narzędzie do nauki? Tak, podobnie jak wiele modeli używanych do nauczania, są one użyteczne, o ile są umieszczone obok zrozumienia ograniczeń modelu. Klasyczna mechanika jest w porządku, o ile zdajesz sobie sprawę, że nie będzie działać na skalach o małej odległości lub dużej prędkości ...

Nie odpowiadając na twoje pytanie, ale raczej dodając inną zmienną do rozważenia: należy wziąć pod uwagę cechy języka programowania. Na przykład Python sortużywa algorytmu Timsort , który został zaprojektowany (oprócz innych dobrych właściwości) w celu zminimalizowania liczby porównań, które mogą być potencjalnie wolne dla obiektów Python. Z drugiej strony, porównanie dwóch pływaków w C ++ płonie szybko, ale ich zamiana jest bardziej kosztowna, więc używają innych algorytmów.

Inne przykłady to dynamiczna alokacja pamięci (banalna na liście Pythona, szybka zarówno w środowisku wykonawczym, jak i programistycznym, po prostu .append()), w porównaniu z FORTRAN lub C, gdzie, chociaż jest to możliwe i szybsze, jeśli jest właściwie zaimplementowane, zajmuje znacznie więcej czasu i mózgu. Zobacz Python jest szybszy niż FORTRAN.