Koszt utrzymania podstawy kodu programowania SIMD

Pytanie:

Konsensus branży oprogramowania jest taki, że czysty i prosty kod ma fundamentalne znaczenie dla długoterminowej żywotności bazy kodu i organizacji, która jest jej właścicielem. Te właściwości prowadzą do niższych kosztów utrzymania i zwiększonego prawdopodobieństwa kontynuacji bazy kodu.

Jednak kod SIMD różni się od ogólnego kodu aplikacji i chciałbym wiedzieć, czy istnieje podobny konsensus w sprawie czystego i prostego kodu, który dotyczy konkretnie kodu SIMD.

Tło mojego pytania.

Piszę dużo kodu SIMD (jedna instrukcja, wiele danych) do różnych zadań przetwarzania i analizy obrazów. Ostatnio musiałem także przenieść niewielką liczbę tych funkcji z jednej architektury (SSE2) na inną (ARM NEON).

Kod został napisany dla oprogramowania owiniętego w folię, dlatego nie może zależeć od zastrzeżonych języków bez nieograniczonych praw do redystrybucji, takich jak MATLAB.

Przykład typowej struktury kodu:

• Używanie typu macierzy OpenCV ( Mat) do zarządzania całą pamięcią, buforem i czasem życia.
• Po sprawdzeniu wielkości (wymiarów) argumentów wejściowych pobierane są wskaźniki do adresu początkowego każdego rzędu pikseli.
• Liczba pikseli i adresy początkowe każdego rzędu pikseli z każdej matrycy wejściowej są przekazywane do niektórych niskopoziomowych funkcji C ++.
• Te niskopoziomowe funkcje C ++ używają wewnętrznych funkcji SIMD (dla architektury Intel i ARM NEON ), ładując i zapisując nieprzetworzone adresy wskaźników.
• Charakterystyka tych niskopoziomowych funkcji C ++:
  • Wyłącznie jednowymiarowe (kolejne w pamięci)
  • Nie zajmuje się przydziałami pamięci.
    (Każda alokacja, w tym tymczasowa, jest obsługiwana przez kod zewnętrzny za pomocą urządzeń OpenCV.)
  • Zakres długości nazw symboli (wewnętrznych, nazw zmiennych itp.) To około 10-20 znaków, co jest dość nadmierne.
    (Brzmi jak techno-bełkot.)
  • Ponowne użycie zmiennych SIMD jest odradzane, ponieważ kompilatory mają problemy z poprawnie parsowanym kodem, który nie jest zapisany w stylu kodowania „pojedynczego przypisania”.
    (Złożyłem kilka raportów o błędach kompilatora).

Jakie aspekty programowania SIMD spowodowałyby, że dyskusja różni się od ogólnej sprawy? Lub dlaczego SIMD jest inny?

Pod względem początkowego kosztu opracowania

• Powszechnie wiadomo, że początkowy koszt opracowania kodu C ++ SIMD o dobrej wydajności wynosi około 10x - 100x (z szerokim marginesem) w porównaniu do swobodnie napisanego kodu C ++.
• Jak zauważono w odpowiedziach na wybór między wydajnością a kodem czytelnym / czystszym? , większość kodu (w tym swobodnie napisany kod i kod SIMD) początkowo nie jest ani czysta, ani szybka .
• Odradza się ewolucyjną poprawę wydajności kodu (zarówno w kodzie skalarnym, jak i SIMD) (ponieważ jest to postrzegane jako rodzaj przeróbki oprogramowania ), a koszty i korzyści nie są śledzone.

Pod względem skłonności
(np . Zasada Pareto, czyli zasada 80-20 )

• Nawet jeśli przetwarzanie obrazu stanowi tylko 20% systemu oprogramowania (zarówno pod względem wielkości kodu, jak i funkcjonalności), przetwarzanie obrazu jest stosunkowo powolne (patrząc jako procent czasu procesora), zajmując ponad 80% czasu.
  • Wynika to z efektu rozmiaru danych: Typowy rozmiar obrazu jest mierzony w megabajtach, podczas gdy typowy rozmiar danych innych niż obraz jest mierzony w kilobajtach.
• W ramach kodu przetwarzania obrazu programista SIMD jest przeszkolony do automatycznego rozpoznawania 20% kodu zawierającego punkty aktywne poprzez identyfikację struktury pętli w kodzie C ++. Zatem z perspektywy programisty SIMD 100% „kodu, który ma znaczenie”, stanowi wąskie gardło w wydajności.
• Często w systemie przetwarzania obrazu istnieje wiele punktów aktywnych i zajmują one porównywalne proporcje czasu. Na przykład może być 5 punktów aktywnych, z których każdy zajmuje (20%, 18%, 16%, 14%, 12%) całkowitego czasu. Aby osiągnąć wysoki wzrost wydajności, wszystkie punkty aktywne muszą zostać przepisane w SIMD.
  • Podsumowano to jako zasadę wyskakiwania balonu: balonu nie można dwukrotnie otworzyć.
  • Załóżmy, że są jakieś balony, powiedzmy 5 z nich. Jedynym sposobem na ich zdziesiątkowanie jest rozbicie ich jeden po drugim.
  • Po pęknięciu pierwszego balonu pozostałe 4 balony stanowią teraz wyższy procent całkowitego czasu wykonania.
  • Aby uzyskać dalsze korzyści, należy przebić kolejny balon.
    (Jest to sprzeczne z zasadą optymalizacji 80–20: dobry wynik ekonomiczny można osiągnąć po zerwaniu 20% owoców o najniższym zawieszeniu.)

Pod względem czytelności i konserwacji

• Kod SIMD jest wyraźnie trudny do odczytania.

  • Jest to prawdą, nawet jeśli przestrzega się wszystkich najlepszych praktyk inżynierii oprogramowania, np. Nazewnictwa, enkapsulacji, stałej poprawności (i oczywistych skutków ubocznych), rozkładu funkcji itp.
  • Dotyczy to nawet doświadczonych programistów SIMD.

• Optymalny kod SIMD jest bardzo zniekształcony (patrz uwaga) w porównaniu do równoważnego kodu prototypowego C ++.

  • Istnieje wiele sposobów na przekręcenie kodu SIMD, ale tylko 1 na 10 takich prób osiągnie akceptowalnie szybkie rezultaty.
  • (Oznacza to, że w przypadku przyrostów wydajności 4x-10x w celu uzasadnienia wysokich kosztów rozwoju. W praktyce zaobserwowano jeszcze większe korzyści).

(Uwaga)
Oto główna teza projektu MIT Halide - cytując dosłownie tytuł artykułu:

„Algorytmy oddzielające od harmonogramów dla łatwej optymalizacji potoków przetwarzania obrazu”

Pod względem możliwości zastosowania w przyszłości

• Kod SIMD jest ściśle powiązany z jedną architekturą. Każda nowa architektura (lub każde rozszerzenie rejestrów SIMD) wymaga przepisania.
• W przeciwieństwie do większości programów, każdy fragment kodu SIMD jest zwykle zapisywany w jednym celu, który nigdy się nie zmienia.
  (Z wyjątkiem przenoszenia na inne architektury).
• Niektóre architektury zachowują doskonałą kompatybilność wsteczną (Intel); niektóre spadną przez drobną część (ARM AArch64 zastępując vtblz vtblq), ale jest wystarczający, aby spowodować, że część kodu nie kompilacji.

Pod względem umiejętności i szkolenia

• Nie jest jasne, jakie wymagania wstępne wiedzy są wymagane, aby poprawnie wyszkolić nowego programistę w zakresie pisania i obsługi kodu SIMD.
• Wydaje się, że absolwenci szkół wyższych, którzy nauczyli się programowania SIMD w szkole, gardzą i odrzucają to jako niepraktyczną ścieżkę kariery.
• Odczytywanie-dezasemblacja i profilowanie wydajności na niskim poziomie są wymieniane jako dwie podstawowe umiejętności pisania wysokowydajnego kodu SIMD. Nie jest jednak jasne, jak systematycznie szkolić programistów w zakresie tych dwóch umiejętności.
• Nowoczesna architektura procesora (która znacznie odbiega od tego, czego nauczają podręczniki) sprawia, że ​​szkolenie jest jeszcze trudniejsze.

Pod względem poprawności i kosztów związanych z wadami

• Pojedyncza funkcja przetwarzania SIMD jest na tyle spójna, że ​​można ustalić poprawność poprzez:
  • Stosowanie metod formalnych (za pomocą długopisu i kartki) oraz
  • Weryfikacja wyjściowych zakresów liczb całkowitych (z kodem prototypowym i wykonywana poza czasem wykonywania) .
• Proces weryfikacji jest jednak bardzo kosztowny (poświęca 100% czasu na przegląd kodu i 100% czasu na sprawdzenie modelu prototypu), co trzykrotnie i tak już kosztowne koszty opracowania kodu SIMD.
• Jeśli błąd jakoś prześlizguje się przez ten proces weryfikacji, prawie niemożliwe jest „naprawienie” (poprawienie), z wyjątkiem zastąpienia (przepisania) podejrzewanej wadliwej funkcji.
• Kod SIMD cierpi z powodu tępych defektów w kompilatorze C ++ (optymalizator kodu generującego).
  • Kod SIMD generowany przy użyciu szablonów wyrażeń C ++ również bardzo cierpi na wady kompilatora.

Pod względem przełomowych innowacji

• Wiele rozwiązań zostało zaproponowanych przez środowisko akademickie, ale niewiele z nich ma szerokie zastosowanie komercyjne.

  • MIT Halide
  • Stanford Darkroom
  • NT2 (Numerical Template Toolbox) i powiązany Boost.SIMD

• Wydaje się, że biblioteki o powszechnym zastosowaniu komercyjnym nie obsługują w dużej mierze SIMD.

  • Biblioteki open source wydają się SIMD letnie.
    • Ostatnio obserwuję to z pierwszej ręki po profilowaniu dużej liczby funkcji API OpenCV, począwszy od wersji 2.4.9.
    • Wiele innych bibliotek przetwarzania obrazów, które profilowałem, również nie korzysta z SIMD lub brakuje prawdziwych hotspotów.
  • Biblioteki komercyjne wydają się całkowicie unikać SIMD.
    • W kilku przypadkach widziałem nawet biblioteki przetwarzania obrazu cofające kod zoptymalizowany pod SIMD we wcześniejszej wersji na kod inny niż SIMD w późniejszej wersji, co skutkuje poważnymi regresjami wydajności.
      (Odpowiedź dostawcy jest taka, że ​​konieczne było uniknięcie błędów kompilatora).

Pytanie tego programisty: czy kod o niskim opóźnieniu czasami musi być „brzydki”? jest powiązany i wcześniej napisałem odpowiedź na to pytanie, aby wyjaśnić moje punkty widzenia kilka lat temu.

Jednak odpowiedź ta jest w zasadzie „łagodzeniem” punktu widzenia „przedwczesnej optymalizacji”, tj. Punktu widzenia, który:

• Wszystkie optymalizacje są z definicji przedwczesne (lub krótkoterminowe z natury ), oraz
• Jedyną optymalizacją, która przynosi długoterminowe korzyści, jest prostota.

Ale takie poglądy są kwestionowane w tym artykule ACM .

Wszystko to prowadzi mnie do pytania:
kod SIMD różni się od ogólnego kodu aplikacji i chciałbym wiedzieć, czy istnieje podobny konsensus w branży co do wartości czystego i prostego kodu dla kodu SIMD.

Nie napisałem dużo kodu SIMD dla siebie, ale wiele kodu asemblera kilka dekad temu. AFAIK wykorzystujący funkcje SIMD jest zasadniczo programowaniem asemblera, a całe twoje pytanie można przeformułować, zastępując słowo „SIMD” słowem „asembler”. Na przykład, jak już wspomniałeś, punkty

• opracowanie kodu zajmuje 10x do 100x niż „kod wysokiego poziomu”

• jest związany z konkretną architekturą

• kod nigdy nie jest „czysty” ani łatwy do refaktoryzacji

• potrzebujesz ekspertów do pisania i utrzymywania go

• debugowanie i konserwacja jest trudna, ewoluuje naprawdę ciężko

nie są w żaden sposób „specjalne” dla SIMD - te punkty są prawdziwe w każdym języku asemblera i wszystkie są „konsensusem branżowym”. Wniosek w branży oprogramowania jest prawie taki sam jak w przypadku asemblera:

• nie pisz tego, jeśli nie musisz - używaj języka wysokiego poziomu, gdy tylko jest to możliwe i pozwól kompilatorom wykonać ciężką pracę

• jeśli kompilatory nie są wystarczające, przynajmniej obuduj części „niskiego poziomu” w niektórych bibliotekach, ale unikaj rozprzestrzeniania kodu w całym programie

• ponieważ prawie niemożliwe jest napisanie asemblera lub kodu SIMD „samodokumentującego”, spróbuj to zrównoważyć dużą ilością dokumentacji.

Oczywiście sytuacja różni się od „klasycznego” zestawu lub kodu maszynowego: obecnie współczesne kompilatory zwykle wytwarzają wysokiej jakości kod maszynowy z języka wysokiego poziomu, który jest często lepiej zoptymalizowany niż kod asemblera napisany ręcznie. W przypadku popularnych obecnie architektur SIMD jakość dostępnych kompilatorów jest AFAIK znacznie poniżej tego - i być może nigdy tego nie osiągnie, ponieważ automatyczna wektoryzacja jest nadal tematem badań naukowych. Zobacz na przykład ten artykuł, który opisuje różnice w optymalizacji między kompilatorem a człowiekiem, dając pojęcie, że tworzenie dobrych kompilatorów SIMD może być bardzo trudne.

Jak już opisałeś w swoim pytaniu, istnieją również problemy z jakością w przypadku najnowocześniejszych bibliotek. Więc IMHO najlepiej możemy mieć nadzieję, że w następnych latach jakość kompilatorów i bibliotek wzrośnie, być może sprzęt SIMD będzie musiał się zmienić, aby stać się bardziej „przyjazny dla kompilatora”, być może specjalistyczne języki programowania ułatwiające wektoryzację (np. Halide, który wspomniano dwa razy) stanie się bardziej popularny (czy nie była to już siła Fortran?). Według Wikipedii , SIMD stało się „produktem masowym” około 15 do 20 lat temu (a Halide ma mniej niż 3 lata, kiedy poprawnie interpretuję dokumenty). Porównaj to z kompilatorami czasu dla „klasycznego” języka asemblera potrzebnego do dojrzałości. Zgodnie z tym artykułem z Wikipediiminęło prawie 30 lat (od ~ 1970 do końca lat 90.), zanim kompilatory przekroczyły wydajność ludzkich ekspertów (w tworzeniu nierównoległego kodu maszynowego). Być może będziemy musieli poczekać 10–15 lat, aż to samo stanie się z kompilatorami obsługującymi SIMD.

Moja organizacja zajęła się właśnie tym problemem. Nasze produkty znajdują się w przestrzeni wideo, ale większość pisanego przez nas kodu to przetwarzanie obrazów, które działałoby również w przypadku zdjęć.

„Rozwiązaliśmy” (a może „uporaliśmy się”) z tym problemem, pisząc własny kompilator. To nie jest tak szalone, jak się początkowo wydaje. Ma ograniczony zestaw danych wejściowych. Wiemy, że cały kod działa na obrazach, głównie na obrazach RGBA. Ustawiliśmy pewne ograniczenia, na przykład bufory wejściowe i wyjściowe nigdy nie mogą się nakładać, więc nie ma aliasingu wskaźnika. Rzeczy takie jak te.

Następnie piszemy nasz kod w języku OpenGL Shading Language (glsl). Zostaje skompilowany do kodu skalarnego, SSE, SSE2, SSE3, AVX, Neon i oczywiście rzeczywistego glsl. Kiedy potrzebujemy obsługiwać nową platformę, aktualizujemy kompilator, aby wyświetlał kod wyjściowy dla tej platformy.

Wykonujemy także kafelkowanie obrazów, aby poprawić spójność pamięci podręcznej i tym podobne. Ale utrzymując przetwarzanie obrazu w małym jądrze i używając glsl (który nawet nie obsługuje wskaźników), znacznie zmniejszamy złożoność kompilacji kodu.

To podejście nie jest dla wszystkich i ma swoje własne problemy (na przykład musisz zapewnić poprawność kompilatora). Ale działało to dla nas całkiem dobrze.

Wydaje się, że nie powoduje to nadmiernych kosztów utrzymania, jeśli rozważasz użycie języka wyższego poziomu:

Vector<float> values = GetValues();
Vector<float> increment = GetIncrement();

// Perform addition as a vector operation:
List<float> result = (values + increment).ToList();

vs

List<float> values = GetValues();
List<float> increment = GetIncrement();

// Perform addition as a monadic sequence operation:
List<float> result = values.Zip(increment, (v, i) => v + i).ToList();

Oczywiście będziesz musiał zmierzyć się z ograniczeniami biblioteki, ale sam nie utrzymasz jej. Może być dobra równowaga między kosztami utrzymania a wydajnością.

http://blogs.msdn.com/b/dotnet/archive/2014/04/07/the-jit-finally-proposed-jit-and-simd-are-getting-married.aspx

http://blogs.msdn.com/b/dotnet/archive/2014/05/13/update-to-simd-support.aspx

W przeszłości zajmowałem się programowaniem asemblera, a nie programowaniem SIMD.

Czy zastanawiasz się nad użyciem kompilatora obsługującego SIMD, takiego jak Intel? Czy przewodnik po wektoryzacji za pomocą kompilatorów Intel® C ++ jest interesujący?

Kilka z twoich komentarzy, takich jak „popping balon” sugeruje użycie kompilatora (aby uzyskać korzyści, jeśli nie masz jednego punktu aktywnego).