Koszt utrzymania podstawy kodu programowania SIMD

14

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.

rwong
źródło
2
Czy masz wymagania dotyczące wydajności? Czy możesz spełnić wymagania dotyczące wydajności bez korzystania z SIMD? Jeśli nie, pytanie jest dyskusyjne.
Charles E. Grant,
4
Jest to zdecydowanie za długo na pytanie, najprawdopodobniej dlatego, że duża jego część jest w rzeczywistości próbą odpowiedzi na pytanie, a nawet długo na odpowiedź (częściowo dlatego, że dotyczy znacznie więcej aspektów niż najbardziej rozsądne odpowiedzi).
3
Lubię mieć czysty / prosty / wolny kod (dla wstępnej weryfikacji koncepcji i późniejszych celów dokumentacji) oprócz zoptymalizowanej alternatywy. Dzięki temu jest łatwy do zrozumienia (ponieważ ludzie mogą po prostu czytać czysty / prosty / wolny kod) i łatwy do zweryfikowania (poprzez porównanie zoptymalizowanej wersji z czystą / prostą / wolną wersją ręcznie i w testach jednostkowych)
Brendan
2
@Brendan Byłem w podobnym projekcie i zastosowałem podejście testowe z prostym / wolnym kodem. Chociaż jest to opcja warta rozważenia, ma również ograniczenia. Po pierwsze, różnica wydajności może okazać się wygórowana: testy przy użyciu niezoptymalizowanego kodu mogą trwać godziny ... dni. Po drugie, w przypadku przetwarzania obrazu może się okazać, że porównanie bit po bicie po prostu nie zadziała, gdy zoptymalizowany kod daje nieco inne wyniki - tak, że należałoby użyć bardziej wyrafinowanego porównania, takiego jak diff średni kwadrat diff
gnat
2
Głosuję za zamknięciem tego pytania jako nie na temat, ponieważ nie jest to problem programowania koncepcyjnego opisany w Centrum pomocy .
durron597

Odpowiedzi:

6

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.

Doktor Brown
źródło
według mojej lektury artykułu z Wikipedii wydaje się, że istnieje ogólna zgoda branży, że kod zoptymalizowany na niskim poziomie jest „uważany za trudny w użyciu ze względu na liczne szczegóły techniczne, o których należy pamiętać”
komentuje
@gnat: tak, absolutnie, ale myślę, że jeśli dodam to do mojej odpowiedzi, powinienem tuzin innych rzeczy już wspomnianych przez OP innymi słowy w jego zbyt długim pytaniu.
Doc Brown,
zgadzam się, analiza w twojej odpowiedzi wygląda wystarczająco dobrze, dodając, że odniesienie niesie ryzyko „przeciążenia”
gnat
4

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.

użytkownik1118321
źródło
Brzmi 🔥🔥! Czy ten produkt, który sprzedajesz lub udostępniasz samodzielnie? (Ponadto, czy „AVC” = AVX?)
Ahmed Fasih
Przepraszam, tak, miałem na myśli AVX (naprawię to.) Obecnie nie sprzedajemy kompilatora jako samodzielnego produktu, choć może się to zdarzyć w przyszłości.
user1118321
Bez żartów, to brzmi naprawdę fajnie. Najbliższą rzeczą, jaką widziałem w ten sposób, był sposób, w jaki kompilator CUDA był w stanie tworzyć programy „szeregowe”, które działają na procesorze w celu debugowania - mieliśmy nadzieję, że uogólni to na sposób pisania kodu wielowątkowego i SIMD, ale Niestety. Następną najbliższą rzeczą, o której mogę pomyśleć, jest OpenCL - czy oceniacie OpenCL i uważacie go za gorszy od kompilatora GLSL dla wszystkich?
Ahmed Fasih
1
Cóż, OpenCL nie istniał, kiedy zaczynaliśmy, nie sądzę. (A jeśli tak, to było całkiem nowe.) Więc tak naprawdę nie doszło do równania.
user1118321
0

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

Legowisko
źródło
według mojej lektury, opcja korzystania z bibliotek zewnętrznych została już zbadana i skierowana przez pytającego: „Biblioteki o powszechnym komercyjnym zastosowaniu nie wydają się być w dużym stopniu obsługiwane przez SIMD ...”
gnat
@gnat Właściwie przeczytałem cały akapit, nie tylko punktory na najwyższym poziomie, a plakat nie wspomina o bibliotekach SIMD ogólnego przeznaczenia, tylko o komputerowych systemach wizyjnych i przetwarzających obrazy. Nie wspominając już o tym, że całkowicie brakuje analizy aplikacji języków wyższego poziomu, pomimo braku znacznika C ++ i specyficzności C ++ odzwierciedlonej w tytule pytania. To prowadzi mnie do przekonania, że ​​chociaż moje pytanie nie będzie uważane za podstawowe, prawdopodobnie przyniesie wartość dodaną, uświadamiając ludziom inne opcje.
Den
1
W moim rozumieniu OP pyta, czy istnieją rozwiązania o szerokim zastosowaniu komercyjnym. Chociaż doceniam twoją wskazówkę (być może mogę użyć biblioteki lib do projektu tutaj), z tego, co widzę, RyuJIT jest daleki od bycia „powszechnie akceptowanym standardem branżowym”.
Dok. Brown
@DocBrown może, ale jego aktualne pytanie jest sformułowane w sposób bardziej ogólny: „... konsensus branży w sprawie wartości czystego i prostego kodu dla kodu SIMD ...”. Wątpię, czy w ogóle istnieje jakikolwiek (oficjalny) konsensus, ale twierdzę, że języki wyższego poziomu mogą zmniejszyć różnicę między „zwykłym” a kodem SIMD, podobnie jak w C ++ zapomnijmy o montażu, a tym samym zmniejszeniu kosztów utrzymania.
Den
-1

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).

ChrisW
źródło
według mojego czytania, to podejście zostało wypróbowane przez pytającego, patrz wzmianki o błędach / defektach kompilatora w pytaniu
gnat
OP nie powiedział, czy wypróbował kompilator Intela , który jest również przedmiotem tego tematu w Programmers.SE . Większość ludzi tego nie próbowała. To nie jest dla wszystkich; ale może pasować do biznesu / pytania PO (lepsza wydajność przy niższych kosztach kodowania / projektowania / konserwacji).
ChrisW,
cóż, co przeczytałem w pytaniu, sugeruje, że pytający wie o kompilatorach dla Intela i innych architektur: „Niektóre architektury zachowują idealną kompatybilność wsteczną (Intel); niektóre nie wystarczają ...”
gnat
„Intel” w tym zdaniu oznacza projektanta Intela, a nie pisarza Intela.
ChrisW,