Programowanie współbieżne, Języki programowania, Aplikacje, Gry

Następca OpenCL zapowiedziany!

Czerwiec 19th, 2011 Marcin Borowiec

Pamiętacie mój ostatni wpis o OpenCL? Pisałem w nim, że nie widzę OpenCL jako technologii przyszłości do programowania GPGPU. Przewidywałem także, że pojawi się nowa technologia, która ułatwi sposób tworzenia oprogramowania na GPU i wykorzysta przyszłe układy CPU i GPU. Przewidywania okazały się bardzo trafne i dzisiaj mogę wam powiedzieć jak ta technologia nazywa.

Tak więc po kolei:

I. Jak ta technologia się nazywa?

C++ AMP

II. Kto ją zapowiedział?

Herb Sutter w imieniu firmy Microsoft (w której pracuje) podczas konferencji organizowanej przez firmę AMD.

III. Co to jest C++ AMP?

Jest to otwarta specyfikacja rozszerzeń do języka C++ ver2011 (C++0x powinien zostać oficjalnie zatwierdzony w tym roku) zaproponowana przez Microsoft. Specyfikacja zawiera opis zestawu podzbiorów pełnego C++ i dodatkowej biblioteki z algorytmami i kontenerami. W obecnej chwili Microsoft mówi o jednym podzbiorze języka – podzbiorze pozbawionym m.in części operacji na wskaźnikach zgodnym z wymaganiami DirectCompute (elementu biblioteki DirectX 11). W przyszłej wersji Visual Studio Microsoft dostarczy dwie wersje kompilatora zgodnego z C++ AMP: domyślny pod CPU i w wersji restrict(direct3d) pod GPU. Kod pod CPU będzie wykonywał się natywnie, natomiast kod pod GPU będzie wykonywany poprzez bibliotekę DirectX 11. AMD zamierza stworzyć także swój własny kompilator pod C++ AMP (za pewne rozszerzy, któryś z open source’owych kompilatorów) i udostępni go pod systemy Windows, Linux i inne. Kompilator obsłuży kolejne generacje układów od AMD.

IV. Jak C++ AMP odnosi się do moich „5 punktów” z postu o OpenCL?

1. Ad: Możliwości zapisania programu w języku wysokiego poziomu bez sztucznego podziału: kod po stronie CPU, kod po stronie GPU

Kod tworzy się w języku C++ przy pomocą bibliotek, które znajdują się w specyfikacji C++ AMP. Poszczególne fragmenty kodu mogą zostać oznaczone jako restrict(nazwa_podzbioru). W zależności od poziomu restrykcji taki kod będzie się mógł uruchomić na różnych typach układów. Warto pamiętać, że kolejne generacje GPU będą coraz mniej restrykcyjne i w pewnym momencie mogą obsługiwać język C++ w pełni. Restrict nie mówi na jakim konkretnie układzie program ma działać a jaki zestaw funkcji taki układ musi posiadać. W tej chwili pełny zestaw zadziała tylko na CPU a zestaw direct3d na CPU i GPU (zarówno od AMD jak i Nvidii). Idea restrict jest znacznie szersza i po więcej informacji odsyłam do podlinkowanego wcześniej video z prezentacji C++ AMP. OpenCL zakładał, że GPU jest akceleratorem, który trzeba obsłużyć z poziomu kodu wykonywanego przez CPU (zainicjować, wysłać mu dane, uruchomić program, pobrać dane). C++ AMP zakłada, że posiadamy system z różnymi typami jednostek obliczeniowych i typami podsystemów pamięci (system heterogeniczny) a podział zadań pomiędzy tymi jednostkami, może być realizowany niejawne poprzez platformę C++ AMP. Jest to rozwiązanie bardziej ogólnie i sprawdzi się dużo lepiej przy kolejnych generacjach CPU i GPU.

2. Ad: Jak najniższego kosztu dostosowania obecnego oprogramowania do uruchomienia na GPU.

Programy pisze się w języku C++ więc jest to dużo ułatwienie, gdyż bardzo duża ilość oprogramowania została stworzona w tym języku. Niestety nie możemy oczekiwać, że koszt przeniesienia oprogramowania na C++ AMP będzie zerowy. Aby przenieść takie oprogramowanie czasem potrzebne będzie zastosowanie bardziej ogólnego mechanizmu do rozdzielania zadań czy użycie algorytmu, który lepiej skaluje się po rozdzieleniu na większą ilość wątków. Są to jednak rzeczy, które nie da się ominąć. Najważniejsze jest to, że nie mamy wielu sztucznych ograniczeń, które ma OpenCL.

3. Ad: Wykorzystania potencjału przyszłych układów: Kolejne wersje układów od Nvidii i AMD, rozwiązania Intela z rodziny Knights (Knights Ferry i Knights Corner).

O tym już pisałem w punkcie 1. C++ AMP ma bardziej przyszłościowy model programowania. Inną kwestią pozostaje to jak Nvidia i Intel odniosą się do tej technologii.

4. Ad: Wykorzystania potencjału jaki przyniosą nowe modele sterowników, chodzi tu m.in o WDDM 2.1 (Windows Display Driver Mode), który pojawi się prawdopodobnie w Windows 8.

W przyszłości zarządzanie zadaniami i pamięcią na GPU będzie odbywać się podobnie jak teraz na CPU. C++ AMP świetnie wpisuje się w ten model.

5. Ad: Narzędzi: debuggery, profilery itp które obsługiwać będzie się podobnie do tych, które obecnie używane są dla programów pisanych pod CPU.

Takie narzędzia ma posiadać następna wersja Visual Studio, łącznie z debuggerem kodu na GPU.

 

GPGPU ewoluuje i razem z nim podejście AMD-ATI. Za czasów Radeonów serii HD2xxx, HD3xxx, HD4xxx ATI udostępniało platformą opartą o kompilator Brook++. Ideą Brook++ było wykorzystanie GPU jako prostego procesora strumieniowego. To rozwiązanie przestało się sprawdzać razem z premierą Radeonów serii HD 5xxx (już przy Radeonach HD 4xxx słabo się sprawdzało), które posiadały wiele funkcji, z których nie można było skorzystać za pomocą Brook++. AMD porzuciło wtedy Brook++ i swoją uwagę skupiło na OpenCL. Tylko, że OpenCL też niedługo przestanie się sprawdzać. Prawdopodobnie już od Radeonów serii HD8xxx AMD będzie potrzebować czegoś więcej (C++ AMP) niż OpenCL.

Pozostaje pytanie co zrobi w tej sytuacji Nvidia. Jej CUDA było lepsze od Brook++, OpenCL zdobyło dość dużą popularność ale nie nadszarpnęło zbytnio pozycji platformy CUDA. Nvidia nawet olała implementacje OpenCL w wersji 1.1. Tylko, że teraz przeciwnik jest na prawdę duży. Co innego walczyć z firmą, która przeznacza znacznie mniejsze pieniądze na GPGPU (AMD kiedyś), a co innego walczyć z firmą, której heterogeniczne maszyny (kolejne generacje APU) są obecnie priorytetem nr 1. (AMD dziś) a pomaga jej firma Microsoft.

CPU vs GPU: Architektura cz. 2

Kwiecień 1st, 2011 Marcin Borowiec

W poprzednim poście przedstawiłem różne sposoby zwielokrotniania jednostek obliczeniowych w procesorach. Dzisiaj opisze, z jakich jednostek obliczeniowych składają się popularne układy CPU. Ponieważ nie ma dużych różnic pomiędzy układami AMD i Intela opisze tylko jeden model procesora. Będzie to Intel Core i7-950, procesor ma 4 rdzenie, obsługuje technologię Hyper-threading i posiada obsługę instrukcji SSE w wersji 4.2.

Jako przykład specjalnie wybrałem wersję procesora z Hyper-threading. O tej technologii będę pisał dokładnie w kolejnych częściach. Dzisiaj wspomnę tylko jedną rzecz, która potrzebna jest do zrozumienia tego postu. Hyper-threading powoduje, że jeden rdzeń procesora jest w stanie obsłużyć dwa wątki sprzętowe w jednym momencie. Wątki są w pełni niezależne i z punktu widzenia podziału jednostek obliczeniowych z poprzedniego postu jeden rdzeń zawiera dwie jednostki typu MIMD. Mnożąc to razy ilość rdzeni otrzymujemy mini schemat procesora Intel Core i7-950:

Ten rysunek zakłada, że do operacji wykorzystujemy jedynie podstawowe instrukcje operujące na pojedynczych wartościach (całkowitych lub zmiennoprzecinkowych). Takie instrukcje wystarczają aby napisać dowolny program i pewien podzbiór programów używa tylko tych instrukcji. Opisywany procesor obsługuje także instrukcje SSE. Instrukcje te pozwalają na wykonywanie operacji na grupie spakowanych danych tworząc w ten sposób grupę jednostek typu SIMD. Ilość logicznych jednostek SIMD jest zależna od wielkości danych, na których operujemy. Ponieważ spakowane dane zajmują 128 bit to kombinacje jakie otrzymaliśmy to: 2 x 64 bit (całkowite lub zmiennoprzecinkowe), 4 x 32bit (całkowite lub zmiennoprzecinkowe), 8 x 16 bit (całkowite), 16 x 8 bit (całkowite). Na schemacie może to wyglądać tak:

W ten sposób otrzymujemy drzewo jednostek obliczeniowych. Procesor zawiera 8 jednostek MIMD z czego każda składa się z kilku jednostek SIMD. Oczywiście w danym momencie możemy np. na pierwszej jednostce MIMD korzystać ze zwykłych instrukcji na liczbach skalarnych podczas gdy na drugiej jednostce MIMD będziemy liczyć na wektorze czterech 32 bitowych liczb a na trzecim MIMD będziemy liczyć na wektorze dwóch 64bitowych liczb.

Procesory AMD działają bardzo podobnie. Jedyna różnica to taka, że otrzymujemy SSE w nieco uboższej trzeciej wersji i żaden z modeli produkowanych przez AMD nie posiada technologii Hyper-Threading. Pewną zmianą są natomiast procesory z drugiej generacji Intel Core i7 i Intel Core i5. Posiadają one zestaw nowych instrukcji o nazwie AVX. W stosunku do SSE różnią się przede wszystkim wielkością spakowanej liczby, która teraz wynosi 256bit co zwiększa dwukrotnie ilość logicznych jednostek SIMD dla danej wielkości liczb.

W kolejnym poście przedstawię budowę GPU Nvidi.

CPU vs GPU: Architektura cz. 1

Listopad 17th, 2010 Marcin Borowiec

Tym postem zaczynam serię artykułów, w których porównam architekturę aktualnie dostępnych układów CPU od Intela i AMD, układów GPU firmy NVidia montowanych w kartach GeForce począwszy na serii 8xxx i skończywszy na najnowszej 5xx, układów GPU firmy AMD/ATI montowanych w kartach Radeon począwszy od serii HD 4xxx i skończywszy na serii HD 6xxx, a także układów z serii Knights od Intela.

Ponieważ temat jest bardzo rozległy musiałem go podzielić na kilka części:

  1. Opisanie różnych typów jednostek obliczeniowych pod kątem „niezależności” wykonywania różnych ścieżek programu naraz czy też możliwości wykonywania operacji na wielu różnych porcjach danych w „jednym momencie”.
  2. Porównanie układów pod kątem typów jednostek obliczeniowych  w nich występujących (a raczej hierarchii tych jednostek)
  3. Opisanie sposobów wymiany danych i synchronizacji pomiędzy jednostkami. Opisanie dostępu do pamięci a także rozjaśnienie terminów: superskalarność, dual-issue
  4. Powiązanie informacji wymienionych w pkt3. z konkretnymi układami.
  5. Podanie przykładów algorytmów i sposoby ich implementacji dla różnych układów.

Jakiś czas temu porównałem ze sobą różne układy gpu i cpu pod względem teoretycznej maksymalnej wydajności. W tym i następnym poście postaram się już częściowo odpowiedzieć, które układy potrafią wykorzystać w większym stopniu swoją moc obliczeniową, a które układy będą mieć „puste GFLOPSy”.  Sytuacje można w dużym stopniu porównać do procesorów Pentium 4, które były pokonywane przez dużo wolniejsze (taktowane wolniejszym zegarem) Athlony czy Pentium M (które to później ewoluowały w Core 2 Duo). Wtedy mówiliśmy o „pustych gigahercach”

Najnowsze układy CPU i GPU są układami wielordzeniowymi. Zwykłe procesory w komputerach osobistych mają już po 2,3,4 a nawet 6 rdzeni. Co więcej każdy z tych rdzeni zawiera możliwość wykonania obliczeń na kilku danych jednocześnie, między innymi dzięki instrukcjom SSE. Możliwość wykonania kilka instrukcji w jednym cyklu uzyskano także dzięki superskalarności czy funkcji HyperThreading. Jeszcze bardziej ciekawie wygląda sprawa z układami kart graficznych. W najnowszych modelach mamy dostępne już kilkaset małych rdzeni. Te 6 rdzeni w głównym procesorze komputera nie robi przy tym wrażenia. Oczywiście nie dokonano tutaj jakiegoś cudu, te „procesorki” są po prostu dużo bardziej prymitywne. Aby je porównać posłużę się poniższym rysunkiem:

Te skróty na rysunku to sposoby na zwielokrotnienie jednostek obliczeniowych w procesorach  i oznaczają:

  • SIMD (Single Instruction, Multiple Data) – Najprostsze wprowadzenie dodatkowych jednostek obliczeniowych do procesora. Każda jednostka w jednej grupie SIMD wykonuje tą samą operacje na różnych danych. Najlepszym przykładem SIMD są instrukcje SSE w procesorach z rodziny x86. Jednostki SIMD idealnie nadają się do prostych operacji np przetwarzania obrazu. Przykładowo aby rozjaśnić obraz wystarczy dodać do wartości koloru kolejnych pikseli stały kolor. Zastępując jedną skalarną jednostkę obliczeniową jedną grupą SIMD składającą się z 4 jednostek otrzymamy bardzo niskim kosztem 4-krotne przyspieszenie. Aby zwiększyć użyteczność jednostek SIMD stworzono wariacje podstawowych instrukcji, np w przypadku dodawania mamy dodawanie z nasyceniem i dodawanie z przepełnieniem. Jeśli chcemy rozjaśnić obraz to interesuje nas dodawanie z nasyceniem. Gdy operujemy na jednostkach skalarnych możemy zawsze użyć dodawania z przepełnieniem + osobną instrukcję warunkową ustawiającą kolor biały w przypadku przepełnienia. Jednostki w jednej grupie SIMD nie mają własnego kontekstu wątku co powoduje, że albo wszystkie jednostki wykonają daną instrukcję albo żadna. Przez co jednej instrukcji dodawania  z nasyceniem nie da się zastąpić dodawaniem z przepełnieniem + instrukcja warunkowa(Przypadek gdy musimy ustawić kolor biały tylko dla części danych). Oczywiście nie da się mnożyć podstawowych instrukcji w nieskończoność i w wielu przypadkach gdy mamy dużo ‚ifów” zależnych od konkretnej wartości, na której operujemy SIMD staje się bezużyteczne.
  • VLIW (Very Long Instruction Word) – Rozszerza SIMD o możliwość wykonania różnych instrukcji dla każdej jednostki wchodzącej w skład grupy VLIW. Nadal jednak to cała grupa posiada jeden kontekst wątku. VLIW ma troszkę inne zadanie niż SIMD. SIMD używamy tam gdzie musimy wykonać tą samą sekwencję operacji na zbiorze danych. VLIW ma za zadanie przyspieszyć wykonanie jednego wątku poprzez zrównoleglenie instrukcji, które od siebie nie zależą, np taką sekwencję:
    1) d = a + b;
    2) e = a * c;
    3) f = c + d;
    można wykonać w ten sposób:
    1)d = a + b;          e = a * c;
    2)f = c + d;
    Mówiąc krótko, wyniki operacji pierwszej i drugiej nie zależą od siebie więc instrukcje mogą zostać wykonane jednocześnie.
  • SIMT (Single Instruction, Multiple Thread) – Termin zaproponowany przez NVidię przy okazji premiery pierwszy kart graficznych z obsługą CUDA. SIMT jest rozszerzeniem SIMD poprzez stworzenie kontekstu wątku dla każdego procesora wchodzącego w skład grupy SIMT. Teraz „ify” zależne od wartości ze zbioru danych, na którym operujemy nie są już takie straszne. W czasie wykonywania instrukcji warunkowej procesor w zależności od aktualnie wykonywanej gałęzi (if albo else) i swojego kontekstu wątku wykonuje daną operacje albo zostaje tymczasowo wyłączony. W przypadku pętli każdy z procesorów wyłącza się po wykonaniu swoich iteracji i czeka aż ostatni z grupy SIMT zakończy pętle. Dopiero wtedy cała grupa SIMT kontynuuje obliczenia.
  • SIMF (Single Instruction, Multiple Flow) – Jest to termin wymyślony przeze mnie na potrzeby tego artykułu. SIMF w porównaniu do SIMT pozwala każdemu procesorowi na niezależne wykonanie sekwencji instrukcji (choć ciągle mówimy o tej samej sekwencji instrukcji dla każdego procesora wchodzącego w skład grupy SIMF). Różnica polega na tym, że każdy z procesorów może przetwarzać inną gałąź tej samej sekwencji. Tzn jeden procesor może wykonywać właśnie instrukcje dla spełnionego warunku „if”, inny może w tym czasie wykonywać kod dla else. W przypadku pętli procesor nie czeka na wyjście z pętli innych procesorów.
  • MIMD (Multiple Instruction, Multiple Data) – Oznacza pełną swobodę. Każdy z procesorów może wykonywać całkiem inny kod na całkiem innych danych. Procesor w grupie MIMD to przede wszystkim popularny rdzeń w procesorze komputera (CPU). Granica pomiędzy SIMF a MIMD jest trochę zamazana. Teoretycznie możemy przecież napisać kod w postaci if (warunek()) Funkcja1() else Funkcja2(). Mamy jedną sekwencje instrukcji, która zawiera dwie gałęzie zależne od warunku. W przypadku SIMF każdy procesor niezależnie wykona gałąź odpowiednią dla niego. Więc czym tak na prawdę różni się SIMF od MIMD? Wyjaśnię to dokładnie w kolejnym poście.

Patrząc na powyższy rysunek można powiedzieć, że sposoby znajdujące się po lewej stronie oznaczają niski koszt zwielokrotnienia jednostek obliczeniowych i dużo ograniczeń co do sposobu zrównoleglenia obliczeń. Im bardziej na prawo tym mamy większą swobodę i możliwości lecz koszt wzrasta. Które z rozwiązań jest najlepsze? To zależy od zastosowania. Niski koszt w przypadku SIMD, VLIW powoduje że możemy dodać dużo dodatkowych jednostek jednak gdy okaże się że nasze obliczenia ciężko zrównoleglić, lepszym rozwiązaniem może być np stworzenie 2 procesorów MIMD zamiast np 16 SIMD. Ważna jest jeszcze jedna rzecz. Nikt nie powiedział, że w danym procesorze możemy mieć tylko jedną grupę jednostek obliczeniowych. Można np. stworzyć układ który będzie zawierał grupę MIMD zawierają grupę procesorów SIMT. Właśnie takie drzewiaste rozwiązania stosuje się w procesorach CPU i GPU. Rysunek pokazuje jeszcze jedną rzecz. Mamy dwie drogi w „zrównoleglaniu” programu. Pierwsze ze względu na dane: SIMD -> SIMT -> SIMF -> MIMD gdzie kolejny skrót oznacza coraz bardziej elastyczny przypadek oraz ze względu na kod VLIW -> MIMD gdzie VLIW oznacza wykonywanie różnych operacji w ramach jednego wątku a MIMD wykonywanie różnych zadań w ramach jednego programu.

Ciąg dalszy w następnym poście.

Volatile a publikacja obiektu w C++

Grudzień 5th, 2009 Marcin Borowiec

W jednym z poprzednich wpisów pisałem o problemie publikacji obiektu w programie wielowątkowym. Podałem wtedy bardzo prosty przykład kodu w pseudo asemblerze. Z kolei w  języku C++ publikacja mogła by wyglądać następująco:

bool gotowe = false;
Object *object = 0;
// ...
object = new Object(a,b,c);
gotowe = true;

Jak już wiemy abyśmy mieli gwarancje że object będzie dostępny jak tylko zmienna gotowe zmieni wartość na true, musimy upewnić się, że zapisy nie zostaną przeniesione przed inne zapisy i odczyty nie zostaną przeniesione za inne odczyty. W przypadku języków C# czy Java coś takiego możemy wymusić za pomocą deklaracji gotowe jako volatile. Niestety albo na szczęście standard C++ nic takiego nie przewiduje. W takim razie co należy zrobić aby uzyskać możliwość publikowania obiektu?

  • Jeśli nasz program będzie uruchamiany wyłącznie na procesorach x86 możemy zadeklarować gotowe jako volatile. To w zupełności wystarczy, gdyż model tej architektury jest stosunkowo mocny (Po szczegóły odsyłam do moich poprzednich wpisów).
  • Jeśli nasz program będziemy kompilować wyłącznie w Visual C++ 2005 lub nowszym, podobnie jak w poprzednich punkcie mamy gwarancje że volatile zadziała. Także dla kompilacji pod IA64. Jest to specjalna właściwość kompilatora Microsoftu.
  • W pozostałych przypadkach musimy albo opakować odwołania do gotowe w sekcję krytyczną albo użyć specjalistycznej biblioteki, z funkcją która wymuszą odpowiednie memory barrier. (Co prowadzi do oszczędności czasu procesora w stosunku do sekcji krytycznej).

Odnosząc się do słówka volatile pozostają jeszcze dwa pytania. Czy w takim razie volatile jest prawie całkiem bezużyteczne? oraz co o volatile mówi przyszły standard C++ 0x? Na te pytania postaram się odpowiedzieć, w któryś z kolejnych postów.

Memory ordering cd.

Wrzesień 21st, 2009 Marcin Borowiec

Miesiąc temu poruszyłem problem „przestawiania operacji odczytu i zapisu” w procesorach z rodziny x86. Dzisiaj postaram się rozszerzyć ten temat na inne architektury. W tym wpisie będę odnosił się przede wszystkim do dokumentu Memory Barriers: a Hardware View for Software Hackers. Najbardziej istotny jest tutaj rozdział 7 i tabela 5 na stronie 16. Znajduje się tam porównanie różnych architektur pod kątem możliwych zamian kolejności operacji odczytu i zapisu. Nie zamierzam tutaj tłumaczyć całego rozdziału, skupię się tylko na kilku ważnych faktach:

  • Istnieją architektury ze zdecydowanie luźniejszym modelem pamięci niż ten w procesorach x86.
  • Niektóre architektury pozwalają na wybranie jednego z kilku możliwych modeli pamięci przez system operacyjny.
  • Niespójność widoku pamięci różnych wątków może wywodzić się nie tylko z istnienia write buffera ale także np z luźniejszego modelu synchronizacji pamięci cache.
  • Wykonanie instrukcji atomowej nie implikuje uzyskania „total order”
  • Do wymuszania zachowania kolejności określonych operacji służą instrukcje typu „memory barrier”. Architektury o luźniejszym modelu oferują przeważnie kilka różnych instrukcji tego typu do uzyskania różnego poziomu spójności widoków pamięci.

Ten kto obejrzał film z poprzedniego wpisu wie, że model pamięci x86 pozwala na bezpieczne publikowanie obiektu. Przez publikację obiektu należy rozumieć sytuację:

mov a, r1;
mov gotowe, 1;

W powyższych przykładach agotowe to zmienne w pamięci, r1 to rejestr procesora. Zakładamy, że obiekt gotowe przed rozpoczęciem wykonywania tego kodu zawierał wartość 0. Zakładamy też, że przypisanie wartości 1 do obiektu gotowe oznacza, że obiekt a zawiera już nową poprawną wartość i ta wartość może być odczytana przez inny wątek. W takim wypadku inny wątek programu może co jakiś czas odczytywać wartość gotowe aż odczyta wartość 1. Wtedy wie że obiekt a zawiera poprawną wartość i może ją odczytać. Niestety takie rozwiązanie nie zadziała np. na procesorach z rodziny Power PC. Dla nich proces publikacji powinien wyglądać tak:

mov a, r1;
lwsync; //memory barrier
mov gotowe, 1;

W następnym poście opiszę jak informacje zawarte w tym wpisie odnoszą się do publikowania obiektów w C++.

Memory ordering w x86

Sierpień 24th, 2009 Marcin Borowiec

We wcześniejszych postach o widoku pamięci wątku i volatile wspomniałem o tym, że istnieje coś takiego jak write buffer. Jego zadaniem jest optymalizować zapis danych obliczonych przez procesor. Bez niego wydajność naszych maszyn byłaby dużo niższa. Niestety jego obecność powoduje zerwanie „sequential consistency”. Przykładowo sekwencja instrukcji:

a = r1; //zapis do pamięci

r2 = b; //odczyt z pamięci

(gdzie a i b to zmienne zlokalizowane w pamięci a r1, r2 to rejestry procesory) może być widziana na zewnątrz jako:

r2 = b;

a = r1;

Zapis został przeniesiony za instrukcję odczytu, gdyż procesor optymalizuje wykonanie programu poprzez użycie write buffer. Takie zamiany instrukcji nazywamy „memory ordering”. Optymalizując wielowątkowe programy na niskim poziomie powinniśmy wiedzieć jakie zmiany w kolejności odczytu i zapisu są możliwe na danym procesorze. Musimy także wiedzieć jak wymusić wykonanie instrukcji w określonym porządku tam gdzie jest to wymagane.

Poniżej znajduje się bardzo ciekawy wykład przedstawiony przez pracownika Intela. Tematem jest model pamięci architektury IA-32 uściślony przez Intela w 2008 roku.

Aby zrozumieć model pamięci w x86 trzeba zapamiętać i zrozumieć 8 następujących reguł:

  1. Odczyty nie są przenoszone przed lub za inne odczyty.
  2. Zapisy nie są przenoszone przed lub za inne zapisy.
  3. Zapisy nie są przenoszone przed występuje przed nimi odczyty.
  4. Odczyty mogą być przeniesione przed wcześniejsze zapisy. Nie dotyczy przypadku gdy odczyt i zapis do tyczy tej samej lokacji.
  5. Jeśli w wieloprocesorowym systemie procesor0 zapisze 1 do lokacji x i następnie jeśli procesor1 zobaczy tą wartość i zapisze 1 do lokacji y to jeśli procesor2 zobaczy 1 w lokacji y to zobaczy też 1 w lokacji x. Zakładamy że lokacje x i y zawierały w stanie początkowym wartości 0.
  6. Jeśli w wieloprocesorowym systemie  procesor0 zapisał wartość do lokacji a, procesor1 zapisał wartość do lokacji b to dowolne inne dwa procesory zobaczą te zapisy w tej samej kolejności.
  7. Jeśli w wieloprocesorowym systemie procesor0 wykonał operacje blokowaną (np. xchg czyli zapis i odczyt) na lokacji a i procesor1 wykonał operację blokowaną na lokacji b to dowolne dwa inne procesory zobaczą te operacje w tej samej kolejności.
  8. Zapisy i odczyty nie są przenoszone przed lub za instrukcje blokowane.

Polecam obejrzeć dołączony film. Te zasady są tam dobrze objaśnione. W kolejnych postach opisze jak memory ordering wygląda na innych architekturach i co z tego wszystkiego wynika.

MIT OpenCourseWare

Sierpień 10th, 2009 Marcin Borowiec

Ostatnio trafiłem na stronę bezpłatnych kursów publikowanych przez uczelnię MIT (Massachusetts Institute of Technology). Listę kursów można obejrzeć pod adresem: http://ocw.mit.edu/OcwWeb/web/courses/courses/index.htm. Gorąco polecam przejrzenie tej strony. Jest bardzo dużo różnych tematów, zarówno z dziedziny informatyki jak i innych.

Mnie szczególnie zainteresował kurs Multicore Programming Primer. Jak sama nazwa mówi jest on poświęcony programowaniu systemów wielordzeniowych. W ramach kursu dostępne są slajdy z prezentacji, video z prezentacji, przykładowe kody źródłowe programów czy quizy, które pomogą sprawdzić ile zapamiętaliśmy i zrozumieliśmy. W Multicore Programming Primer opisano m.in.:

  • Postawy związane z programowaniem systemów wielordzeniowych.
  • Procesor Cell (zawarty m.in. w konsoli PlayStation3). Procesor ten jest bardzo ciekawym przykładem, gdyż jego budowa wymusza określony sposób rozdzielania zadań na wątki czy komunikacji między wątkami. Wymaga od programisty zastanowienia się nad rzeczami, nad którym w ogóle nie trzeba zaprzątać sobie głowy pisząc program np pod Core 2 Duo czy Phenoma X4.
  • Języki programowania tworzone z myślą o procesorach wielordzeniowych: Cilk (rozszerzenie C) czy dość nietypowy StreamIt. Osobiście uważam że programowanie wielowątkowe powinno być integralną częścią języka, a nie dodatkiem w postaci zewnętrznych bibliotek (tak jak to jest w C++). Co więcej program jednowątkowy powinien być szczególnym przypadkiem programu wielowątkowego. Obecnie większość programów pisze się dokładnie odwrotnie.
  • Podstawy tworzenia kompilatorów, które automatycznie rozdzielają wykonanie kodu na wiele wątków. Ten temat szczególnie mnie zainteresował.

User Mode Scheduling w Windows 7

Maj 20th, 2009 Marcin Borowiec

Windows 7 w wersji 64bit przynosi dobre wieści dla programistów aplikacji wielowątkowych i użytkowników, którzy chcieliby jak najlepiej wykorzystać swoje wielordzeniowe maszyny. W najnowszym systemie Microsoftu wbudowano mechanizm umożliwiający zarządzanie wątkami po stronie aplikacji. Oznacza to że: 1) przełączanie pomiędzy wątkami będzie szybsze i 2) aplikacja ma wpływ na to co się dzieje podczas przełączania wątków. Dla użytkownika końcowego oznacza to lepszą skalowalność programów na wiele rdzeni i możliwość uzyskania lepszej „płynności” (szczególnie przydatne np. w grach). W tej chwili najłatwiejszym sposobem wykorzystania User Mode Scheduling jest napisanie aplikacji z wykorzystaniem Concurrency runtime dostępnym w Visual Studio 2010 beta. Warto zwrócić uwagę że UMS jest dostępny tylko w 64bitowej wersji Windows 7 i Windows 2008 R2.

Zainteresowanym polecam linki: Concurrency Runtime and Windows 7, Dave Probert: Inside Windows 7 – User Mode Scheduler (UMS). Niestety dokumentacja do UMS dostępna na MSDN jest ciągle bardzo uboga (ma zostać skończona przed premierą Windows 7). Gdy pojawi się więcej informacji, wróce do tego tematu na blogu.

Mam przy okazji pytanie dla osób preferujących systemy spod znaku pingwina. Czy istnieje podobny mechanizm dla linuksa?

Volatile a operacje atomowe w C++

Lipiec 29th, 2008 Marcin Borowiec

O volatile pisałem już w „programowaniu wielowątkowych gier w języku C++”. Niestety opis, który tam przedstawiłem jest dość pobieżny. Postanowiłem więc powrócić do tego tematu i opisać volatile dokładniej.

Tłumacząc z angielskiego volatile to „zmienny, niestabilny”. volatile w C++ jest kwalifikatorem typu a jego działanie jest określone w standardzie C++ jako: „volatile is a hint to the implementation to avoid aggressive optimization involving the object because the value of the object might be changed by means undetectable by an implementation.” Co oznacza mniej więcej że kompilator powinien zrezygnować z optymalizacji i przy każdym odwołaniu do tej zmiennej wczytać nową wartość z komórki pamięci.

Tylko czy to wystarcza aby zmienne volatile mogły służyć do synchronizacji wątków?

W tym poście opisze kwestie wykorzystania volatile do uzyskania operacji atomowych (A raczej tego że volatile z operacjami atomowymi nie ma nic wspólnego).  W kolejnych wpisach przedstawię inne próby wykorzystania volatile do synchronizacji wątków.

Interesują nas operacje atomowe na liczbach całkowitych, o rozmiarze nie większym niż rejestry ogólnego przeznaczenia. Operacja atomowa to operacja, która zostaje wykonywana nieprzerwalnie dla każdego wątku, procesu. Wyobraźmy sobie dwa wątki które inkrementują zmienną a:

int a = 0;
Wątek1: a++;         Wątek2: a++;

Przy stanie początkowym a wynoszącym 0 nie mamy żadnej pewności że po wykonaniu tych operacji a będzie miało wartość 2. Odwołując się do poprzedniego postu o widoku pamięci dla wątku przyczyną tego mogą być m.in optymalizacje kompilatora. Kompilator nie ma pojęcia że inny wątek też chce modyfikować tą samą zmienną. W efekcie każdy wątek może operować na lokalnej kopii zmiennej:

A co będzie jeśli zmienną a zadeklarujemy jako volatile?

Visual C++ 2005 w trybie Release z wyłączonymi optymalizacjami (-O0) instrukcję a++ przetworzył na 3 instrukcje x86 (załadowanie wartości do rejestru, inkrementacja na rejestrze, zapis do pamięci). Skoro procesor operuje na rejestrze to dalej każdy z wątków posiada własny niezsynchronizowany widok pamięci. Jak widać volatile nie wystarcza do uzyskania poprawnych operacji atomowych (Przykładowy możliwy przebieg programu przedstawiłem w „Programowanie wielowątkowych gier w języku C++”). Na szczęście coraz więcej programistów zdaje sobie z tego sprawę. Do niedawna panowała dość duża dezinformacja, która powstała głównie przez to że dla domyślnych ustawień komplacji (np Visual C++, Release -O2) instrukcja a++; była kompilowana do pojedynczej instrukcji add operującej bezpośrednio na pamięci. Na jednordzeniowych komputerach taki program wykonywał się zawsze poprawnie co mogło sprawiać wrażenie że takie konstrukcję są poprawne. Należy jednak pamiętać że

  • Kompilator może posłużyć się pomocniczym rejestrem do wykonania operacji. Opis volatile mówi tylko o każdorazowym pobraniu wartości z pamięci przy odwołaniu do zmiennej. Nie zabrania tymczasowego użycia rejestru.
  • Nawet jeśli kompilator wygeneruje instrukcję „add na pamięci” to na systemie wielordzeniowym dalej to nie jest poprawna instrukcja atomowa. Instrukcje a++; mogą być wykonane przez każdy z wątków równocześnie. Dodatkowo wynik operacji trafia najpierw do „write buffer” skąd nie jest widoczny dla innych wątków. Ze względu na wydajność procesory nie rozwiązują tych dwóch problemów automatycznie. Konieczne jest wykonanie maszynowej instrukcji „lock”, która nie jest dodawana przez żaden z kompilatorów.

Do tematu volatile i operacji atomowych powróce jeszcze w przyszłości.

Widok wątku na pamięć

Lipiec 15th, 2008 Marcin Borowiec

Na wstępie zachęcam do przeczytania artykułu, o którym pisałem w poprzednim poście. Osobom nie zorientowanym w temacie programowania wielowątkowego znacząco ułatwi zrozumienie tego co będę chciał poniżej przedstawić.

Aby zrozumieć co oznacza „widok pamięci wątku” warto przeanalizować krótki program w języku C++:

int a;
// --- instrukcje ---
a += 2;
a += 3;

Zakładamy:

  • a jest zmienną, dla której została zaalokowana komórka w pamięci komputera
  • wartość tej komórki przed wykonaniem instrukcji (3) wynosi 0 (tzn że wartość a wynosi 0)
  • tylko jeden wątek wykonuje kod przedstawiony powyżej, żaden inny wątek nie modyfikuje a
  • rozpatrujemy program napisany w języku C++, skompilowany i uruchomiony na popularnych procesorach rodziny x86 (Athlon 64, Core 2, Pentium itp …)

Należy się zastanowić kiedy wynik instrukcji (3) zostanie zapisany do komórki pamięci komputera i dlaczego należy się tym przejmować. Są ku temu 4 powody:

  1. Kompilator zoptymalizował kod i postanowił połączyć intrukcje (3) i (4) w jedną instrukcję a+=5; Z punktu widzenia programu w języku C++ jest to równoznaczne. W efekcie, do pamięci może nigdy nie zostać zapisana wartość 2, pojawi się dopiero wartość 5.
  2. Kompilator postanowił zapisać wartość sumy z instrukcji (3) do rejestru procesora. Pozwoli to na zoptymalizowanie wykonania kolejnych instrukcji na zmiennej a. W końcu zapis i odczyt z rejestru jest znacznie szybszy niż odwołania do pamięci. W przedstawionym przypadku zapis do pamięci może się odbyć po wykonaniu instrukcji (3) i (4) jako skopiowanie wyniku z rejestru procesora do pamięci. Podobnie jak w pkt 1. w komórce pamięci może nastąpić zmiana bezpośrednio z wartości 0 na 5.
  3. „Kompilator wysyła” do pamięci wynik wykonania instrukcji (3) czy to poprzez instrukcję add operującą bezpośrednio na pamięci czy to poprzez sekwencję instrukcji add na rejestrze i move czyli przeniesienia wartości z rejestru do pamięci. Problem w tym że te operacje w rzeczywistości nie powodują bezpośredniego zapisu do pamięci komputera. Procesor także posiada mechanizmy, które mają zwiększyć szybkość wykonywania programów. W rzeczywistości nowa wartość trafia najpierw do „write buffer” gdzie czeka na przesłanie dalej, podczas gdy procesor zajmuje się już wykonaniem kolejnych instrukcji. Write buffer to bardzo mały bufor pamięci. Jak tylko jest możliwość przesłania danych do cache procesora opuszczają one write buffer.
  4. Pamięć procesora jest przeważnie znacznie wolniejsza niż sam procesor a samo przesłanie danych wiąże się z dość dużymi opóźnieniami. Z tego powodu procesor został wyposażony w zintegrowaną pamięć zwaną pamięcią cache. Ostatnio używane dane są buforowane w tej pamięci przez co znacznie skraca się ponowny czas dostępu do nich. Również z powodu optymalizacji nowe dane najpierw zostają zapisane do pamięci cache, a dopiero gdy jest taka potrzebna trafiają do pamięci RAM komputera. Na szczęście nie musimy się martwić jak to dokładnie działa. Synchronizacja pamięci cache odbywa się w całości na poziomie sprzętowym, według protokołów MESI i MOESI (w zależności od procesora). Jeśli procesor potrzebuje dane, które znajdują się w pamięci cache innego procesora to zostaną przesłane do tego pierwszego bez żadnej programowej ingerencji.

O ile o optymalizacjach kompilatora i istnieniu pamięci cache procesora wiedzą chyba prawie wszyscy programiści o tyle niewiele osób zdaje sobie sprawę z istnienia „write bruffera”. Mam takie wrażenie przeglądając kody źródłowe niektórych programów i czytając artykuły o programowaniu wielowątkowym w C++. Zwracam szczególną uwagę na to że pamięć cache to co innego niż write buffer, to pierwsze jest synchronizowane sprzętowo, to drugie jest synchronizowane programowo.

Wracając do tytułu posta. Każdy z wątków wykonywanych w ramach jednego procesu może inaczej widzieć w danym momencie pamięć komputera. Różnice wychodzą właśnie z tymczasowych wartości, które znajdują się w rejestrach czy write bufferze. Należy oczywiście zwrócić uwagę na fakt że stan pamięci cache nie wpływa na widok wątku. Jak już wcześniej napisałem synchronizacja pamięci cache odbywa się w całości sprzętowo niewidocznie dla programisty.

Dopóki korzystamy z funkcji pokroju EnterCryticalSection, InterlockedIncrement nie musimy w ogóle zdawać sobie sprawy z tego o czym tutaj napisałem. Jeśli jednak chcemy zrozumieć jak te funkcje działają, chcemy napisać podobne funkcje albo po prostu chcemy nasz program zoptymalizować warto rozumieć te mechanizmy. W następnych postach będę wielokrotnie odwoływał się do tego artykułu, żeby wyjaśnić kiedy pewne optymalizacje są poprawne a kiedy nie i dlaczego.