Nastoletni
Programiści

Logo Nastoletnich Programistów

Boost.SIMD, co tak naprawdę potrafi jeden rdzeń?

Wolny program? Hurr durr, zrób wątki.

Brzmi znajomo? Jeśli program działa wolniej niż się chce inni programiści dają z reguły dwie rady: pierwsza, bardzo dobra – poprawić algorytm, druga, zwykle fatalna – użyć wielu wątków / procesów. Prawda jest taka, że czego by nam nie pchali producenci 12–rdzeniowych procesorów w telefonach wiele wątków ma tyle zalet co wad. Sama synchronizacja pochłania tyle mocy obliczeniowej, że o jednym rdzeniu można zapomnieć (drobna przesada nikogo nie zabiła :P), pełno miejsca na świeżutkie wycieki pamięci czy niezdefiniowane wyścigi po dane, jednym słowem – chaos.

Więc jak żyć?

Użyć jednego rdzenia, ale lepiej. Jak? Tu właśnie do akcji wkracza SIMD (Single Instruction, Multiple Data – z ang. jedna instrukcja, wiele danych). Sztuczka polega na klasycznym przeprowadzeniu jednej operacji jak dodawanie, odejmowanie czy dzielenie, ale zamiast jednego lub kilku operandów używa się całych zestawów danych, dobrze ilustruje to rysunek poniżej. Takie podejście do problemu znane jest od dawna, ale ręcznie wykorzystywane w praktyce dosyć rzadko, na rynku jest tak dużo procesorów, że programista podchodzący poważnie do tego co robi często nie wie czy jego program zostanie w ogóle uruchomiony na x86(_64), jak tu liczyć na konkretne rozszerzenie jak np. SSE4.2, AVX2 albo NEON? Dlatego w przypadku C++ (o nim głównie będzie ten wpis) liczyło się z reguły na kompilator, że zoptymalizuje to tu, to tam. Ale kompilator nie jest wszechwiedzący, dlatego dodatkowe 16 256–bitowych rejestrów w naszym nowiutkim procesorze może zostać niewykorzystane. A co jak co, 256–bitowe rejestry to nie lada zabawka.

Teraz przyszły jednak piękne czasy, kiedy na pytanie „SIMD?” odpowiadamy „Boost.SIMD”, tj. nazwą dość świeżej biblioteki z rodziny boost (swoją drogą polecam jeśli ktoś nie kojarzy), która za nas zajmie się doborem technologii, tyle że w przeciwieństwie do optymalizacji kompilatora możemy dostosować kod do takiego równoległego wykonania. Przykładowo iloczyn skalarny na procesorze wspierającym AVX (nie AVX2, to jest spotykane na zbyt niewielu procesorach żeby o tym pisać) można obliczyć ponad trzykrotnie szybciej – jednym rdzeniem.

Trochę praktyki

Już wiemy co i jak z tym Boost.SIMD i SIMD w ogóle, więc teraz trzeba sprawdzić jak to działa.

Uwaga – Boost.SIMD wymaga do pracy biblioteki boost w wersji 1.60 lub nowszej, inaczej pojawi się błąd związany z boost::enable_if (a może jeszcze jakiś inny).

Biblioteka jest na tyle dobrze zaprojektowana, że do nauczenia się jej obsługi w stopniu pozwalającym na przyśpieszenie wielu algorytmów wystarczy omówić prosty (ale nie za prosty) przykład, wybrałem wcześniej wspomniany produkt skalarny – idealnie pasuje do sytuacji (wydaje mi się, że ten przykład wykorzystano też w jakimś anglojęzycznym kursie, ale nie mogłem go znaleźć).
Na początek warto rozwiązać ten problem bez klawiatury, produkt skalarny można opisać tak: P = a1×b1 + a2×b2 + … + an×bn.

To teraz naiwna implementacja liczenia produktu dla dwóch instancji std::vector (z dowolnym alokatorem).

Poza komentarzami kod chyba nie wymaga dalszych wyjaśnień. Teraz pora na ciekawszą część z wykorzystaniem Boost.SIMD. Na początek kilka linii przygotowujących nas do właściwego wykorzystania biblioteki.

Warto pamiętać, że jeśli zamiast float wykorzystacie double ilość operacji prowadzonych na raz (cardinal) najprawdopodobniej zmaleje dwukrotnie. A wracając do produktu skalarnego, tutaj algorytm jest dalej prosty, ale już mniej oczywisty, najwygodniej opisać go zwykłym zdaniem:

Dzielimy vectory na pary paczek o rozmiarze cardinal, równolegle mnożymy paczki otrzymując nową o tym samym rozmiarze i doliczamy sumę jej elementów do produktu, jeżeli rozmiar vectorów nie jest wielokrotnością cardinal resztę doliczamy liniowo.

Teraz może wydawać się to troszkę zawiłe, ale kilka linii kodu rozwiewa wątpliwości:

Liczby proszę

Prosty teścik wydajności obu rozwiązań:

W moim przypadku (kompilowane z flagą -mavx) liniowe rozwiązanie wykonywało się średnio 4522ms a to używające Boost.SIMD – 1305. Prosta matma mówi że to drugie jest ~3.47 raza szybsze, fajnie, nie? Ps. Nie tłumaczę kodu do testu, bo to głównie standard C++, jedyne o czym warto wspomnieć to alokator bs::allocator<float> – upewnia się że dane w wektorze są odpowiednio wyrównane co bywa niezbędne do sprawnego wykorzystania instrukcji SIMD, jednak nie wpływa w żaden (odczuwalny) sposób na czas wykonania liniowej implementacji.

Podsumowanie

I to by było na tyle. Wydaje się za proste? Mi też, ale ta wiedza wystarczy do wydajnego policzenia niejednego zadania, jeśli będziecie chcieli wiedzieć coś więcej to dokumentacja Boost.SIMD zaprasza. :). Bo nie łudźmy się, kod ode mnie jest szybki, ale nie najszybszy – trochę pracy i na procesorze z AVX powinniście móc osiągnąć co najmniej 6-krotny wzrost wydajności. Cały kod dla zainteresowanych.

koczurekk

Jestem koniem z rogiem na tęczowym tle, lubię C++ i D, bawią mnie optymalizacje Lua, poprawiam kod bez profilera a za debugger służy mi std::cout. Ps. Jestem crossfiterem, weganem i wapuję.

Zobacz wszystkie posty tego autora →

Komentarze

  • Paweł Syska

    Materiał bardzo spoko, na pewno kiedyś to wykorzystam.
    W pierwszym kodzie możesz także przekazać referencje na stały wektor bo go nie modyfikujesz.
    W drugim przykładzie też tak bym zrobił, chociaż nie jestem pewny co do tego, czy boost przypadkiem nie będzie wywoływał niestałej metody std::vector::data().

  • joel falcou

    Hi, Boost.SIMD author here. Cool article 🙂
    I think you can do better by using larger pack to trigger unrolling in the loop. pack is actually 2 pack that get unrolled automatically.

    • I didn’t see that in docs. 😮 But yeah, in my case changing pack_t to pack seems to give ~20% performance boost, so… thanks!