Ile należy zoptymalizować oprogramowanie naukowe?

13

W przypadku aplikacji wymagających znacznych zasobów obliczeniowych wysoka wydajność może być krytycznym czynnikiem, jeśli chodzi o dostarczanie wyników naukowych lub osiąganie „przełomów” w rozsądnym czasie.

Ile czasu i wysiłku powinni twórcy oprogramowania zainwestować w optymalizację aplikacji? Jakie są zastosowane kluczowe kryteria?

Allan P. Engsig-Karup
źródło
Programy pisane przez naukowców często działają bardzo długo (np. Symulacje). Czas programisty i czas działania komputera mogą być porównywalne. To bardzo różni się od dzisiejszej „zwykłej” pracy programisty. Podobnie jak we wczesnych dniach obliczeń, często warto zainwestować trochę wysiłku (i czasu programisty), aby przyspieszyć symulację i zakończyć ją szybciej oraz szybciej wykonać zadanie.
Szabolcs

Odpowiedzi:

15

W zdecydowanej większości przypadków ulepszenia algorytmów mają większą różnicę niż ulepszenia optymalizacji. Algorytmy są również bardziej przenośne niż optymalizacje niskiego poziomu. Radzę postępować zgodnie z ogólnymi najlepszymi praktykami dotyczącymi układu pamięci w celu ponownego użycia pamięci podręcznej, unikania nadmiernej liczby kopii lub komunikacji, traktowania systemu plików w rozsądny sposób i zapewniania ziarnom zmiennoprzecinkowym wystarczającej ziarnistości do wektoryzacji. Czasami to wystarczy, aby osiągnąć akceptowalnie wysoki ułamek „piku” (dla tej operacji).

Zawsze szkicuj model wydajności dla operacji, które uważasz za ważne (lub które odkrywasz, że są ważne przez profilowanie). Następnie możesz użyć modelu wydajności, aby oszacować, co może zapewnić dobrze dostrojona implementacja. Jeśli uznasz, że przyspieszenie jest tego warte (w stosunku do innych rzeczy, które możesz robić), dokonaj optymalizacji.

Być może najtrudniejszym wyzwaniem jest zaprojektowanie wysokopoziomowych, ważnych (w tym sensie, że wiele kodów będzie zależało od tych wyborów) interfejsów i struktur danych, aby można było później zoptymalizować bez potrzeby zmiany interfejsu API. W przeciwieństwie do konkretnych optymalizacji i ogólnych wytycznych, nie wiem, jak tego nauczać, chyba że poprzez doświadczenie. Pomaga praca z wrażliwym na wydajność oprogramowaniem typu open source. Podobnie jak w przypadku każdej decyzji API, ważne jest, aby zrozumieć przestrzeń problemu.

Jed Brown
źródło
1
Niedawno dostałem współczynnik 10 000 (w przypadku naszych największych zdarzeń) poprawy czasu wykonywania ograniczającego etapu naszej analizy, po prostu zastępując algorytm, który był O (n ^ 2) w czasie i przestrzeni jednym O (n log n ) zarówno. Pamiętaj, że oznaczało to kolejną zależność i dodatkową złożoność, ale czasem warto ...
dmckee --- były moderator kociak
1
Czynniki przyspieszenia (które są w stosunku do czegoś) nie są warte wyraźnego odniesienia do tego, co porównałeś. Jeśli porównasz do złej implementacji opartej na niewłaściwym algorytmie, a następnie zmienisz, to oczywiście nie byłoby nierozsądne oczekiwać dużych względnych korzyści.
Allan P. Engsig-Karup
1
@Allan: Z jednej zmiany wynikało 10 000 razy, ale oczywiście była to źle wybrana implementacja. Poprzedni kod był tak samo dotknięty niepotrzebną przestrzenią, jak i złożonością czasową: wydajność buforowania była ogromna. Ale o to nie chodzi?
dmckee --- były moderator kociąt
8

Jak zdefiniowałbyś „optymalizację”? Istnieje całe spektrum od opracowania lepszych algorytmów lub modeli obliczeniowych po użycie ręcznie dostosowanego asemblera.

Moim zdaniem i doświadczenia, nisko wiszące owoce znajdują się gdzieś pośrodku, np. Wybierają algorytm, który najlepiej pasuje do podstawowej architektury komputera. Algorytm niekoniecznie musi być nowy, a twoje zrozumienie architektury bazowej niekoniecznie musi być bardzo szczegółowe, np

  • Jeśli wiesz, że Twoja architektura obsługuje SIMD, przebuduj obliczenia tak, aby operacje można było zapisać w postaci krótkich wektorów,
  • Jeśli wiesz, że twoja architektura to komputer wielordzeniowy, spróbuj rozbić swoje zadanie obliczeniowe na poszczególne zadania cząstkowe, które nie kolidują ze sobą, i uruchom je równolegle (pomyśl o DAG swoich zadań podrzędnych) ,
  • Jeśli twoja podstawowa architektura ma procesor graficzny, zastanów się, w jaki sposób możesz ponownie sformułować swoje obliczenia jako grupę wątków maszerujących przez dane w jednym kroku,
  • itp...

Wszystkie powyższe funkcje, np. SIMD, równoległość i GPU, są dostępne bez wiedzy na niskim poziomie, ale naprawdę oferują przewagę w algorytmach, które mogą je łatwo wykorzystać.

Pedro
źródło
4

Zgadzam się ze wszystkimi dotychczasowymi odpowiedziami ... Chciałbym poruszyć jeszcze jeden przeoczony aspekt optymalizacji kodu: oczekiwanie jakości.

Problem optymalizacji kodu pojawia się zwykle, gdy użytkownik próbuje rozwiązać coraz większe problemy, a kod jest niewystarczający, aby zaspokoić potrzeby / oczekiwania użytkownika. Ilość czasu, którą należy zainwestować w optymalizację kodu, zależy od zapotrzebowania na spełnienie tych oczekiwań. Z pewnością warto zainwestować dużo czasu, jeśli istnieje krytyczna potrzeba przewagi konkurencyjnej (np. Ukończenie i opublikowanie swoich badań na gorący temat przed innymi).

Oczywiście, ile czasu należy zainwestować, zależy od tego, jak szybko go potrzebujesz i jak przenośny ma być kod. Często te dwie potrzeby są ze sobą w konflikcie i przed rozpoczęciem optymalizacji musisz zdecydować, które z nich jest ważniejsze. Im bardziej jest to przenośne, tym bardziej musisz polegać na zmianach projektowych kodu na wysokim poziomie (algorytm / struktura danych). Im szybciej chcesz, aby kod działał, należy go dostroić za pomocą optymalizacji niskiego poziomu specyficznych dla konkretnej maszyny (np. Optymalizacji kodu / kompilatora / środowiska wykonawczego).

Paweł
źródło
4

Będziesz musiał dokonać (kosztowej) analizy spędzenia tak wielu osobomierzy (a te są zawsze mityczne :-)) na przyspieszenie realizacji. Musisz dowiedzieć się, ile razy to oprogramowanie będzie używane i przez ile osób, abyś mógł oszacować zysk.

Zasadą jest, jak zawsze, słynna zasada 80/20. W pewnym momencie po prostu już się nie sumuje, aby spędzać coraz więcej czasu na zdobywaniu kilku procent (lub mniej) czasu pracy. Ale będziesz musiał przeanalizować.

I szczerze zgadzam się z powyższymi plakatami: upewnij się, że twój interfejs API jest dobrze przemyślany, aby nie wymagał wielu zmian i upewnij się, że kod jest przenośny i łatwy w utrzymaniu (pomyśl o ponownej analizie napisanego przez ciebie algorytmu i drobiazgowości zoptymalizowany dziesięć lat temu). I upewnij się, że korzystasz z dobrej praktyki programowania i standardowych bibliotek. Szanse są rozsądne, ktoś już pomyślał o najbardziej wydajnym algorytmie dla Twojej aplikacji.

Cytując Donalda Knutha: „przedwczesna optymalizacja jest źródłem wszelkiego zła”. Profiluj więc swój kod, ale nie za wcześnie.

GertVdE
źródło
Czy masz na myśli zasadę Pareto (80/20)? Jeśli tak, czy masz na myśli, że powinniśmy skoncentrować działania optymalizacyjne na 20% kodu, który powoduje 80% spowolnienia? A może masz na myśli, że jeśli możesz spodziewać się tylko 20% przyspieszenia, to po prostu nie warto go optymalizować?
Paweł
Nie, użyłem tego tylko jako zasady, nie do końca 80/20. W pewnym momencie poświęcisz tyle wysiłku na zdobycie zaledwie kilku procent, że nie jest to już warte wysiłku.
GertVdE,
3

Kilka dodatkowych porad:

  1. Przed optymalizacją działającego programu upewnij się, że masz dobry zestaw przypadków testowych, które pomagają zachować integralność kodu. Nie ma sensu szybciej uzyskiwać błędnych wyników.
  2. Jeśli Twoja optymalizacja sprawia, że ​​kod jest mniej czytelny, zachowaj oryginalną wersję, przynajmniej w formie komentarza, ale lepiej jako alternatywną wersję do wyboru w czasie kompilacji i w czasie wykonywania. Twoje potrzeby związane z optymalizacją mogą się zmieniać w miarę ewolucji twoich problemów i maszyn, a oryginalny kod może być lepszym punktem wyjścia do optymalizacji za pięć lat.
  3. Jeśli Twoja zoptymalizowana wersja ma minimalny wpływ, ale sprawia, że ​​kod jest mniej czytelny, mniej uniwersalny lub mniej stabilny, wróć do pierwotnej wersji. Tracisz więcej niż zyskujesz.
Khinsen
źródło