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

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?

GPGPU – ciekawe linki

Wrzesień 24th, 2008 Marcin Borowiec

GPGPU (General-purpose computing on graphics processing units czyli wykorzystanie kart graficznych do obliczeń ogólnego przeznaczenia) staje się coraz bardziej popularne. Przyczyniła się do tego mocno nvidia reklamując swoje „cuda”. AMD jest nieco w tyle ale dzielnie tworzy swoje Stream SDK. Ostatnio sam zabrałem się za zgłębianie tajemnic procesorów graficznych i api, które przygotowali ich producenci. Zebrałem przy tej okazji kilka ciekawych linków.

Oczywiście podstawowym źródłem informacji są strony: NVIDIA CUDA i AMD Stream. Na początek polecam AMD Stream SDK User Guide i Building a High Level Language Compiler For GPGPU ? PLDI?08 Tutorial. Dokumentacja od AMD wydaje mi się bardziej przyjazna dla początkującego niż ta od nvidii. Przede wszystkim AMD przedstawia architekturę swoich kart graficznych i na tym oparty jest opis API Stream SDK. Pozwala to lepiej zrozumieć dlaczego programy pod GPU piszę się tak a nie inaczej i jak należy programować żeby uzyskać wysoką wydajność. Z kolei nvidia serwuje nam czysty opis API technologii CUDA. Znajdziemy tam kilka nowych pojęć, które wprowadzono aby uporządkować informację o programowaniu ich GPU. Szkoda tylko że nie opisali jak to się ma do architektury GeForce. Czytając dokumentację od AMD warto wspomóc się opisami: RV770 (1) i RV770 (2) (RV770 to układ znajdujący się na kartach Radeon 4850 i Radeon 4870). Przytoczone wcześniej AMD User Guide wspomina głównie o poprzedniku (układzie RV670 znajdującym się na kartach Radeon 3870). Podstawą do programowania w technologii CUDA jest oczywiście NVIDIA Programming Guide. Jeśli po przeczytaniu zastanawiacie się co to jest do cholery ten „warp” polecam przeczytanie artykułu: NVIDIA’s 1.4 Billion Transistor GPU: GT200 Arrives as the GeForce GTX 280 & 260, szczególnie strony drugiej i czwartej.

Jeśli macie jakieś inne ciekawe linki dotyczące tematu GPGPU dopiszcie je w komentarzach 🙂

Kilka spraw organizacyjnych

Sierpień 8th, 2008 Marcin Borowiec

Po miesiącu prowadzenia nowej wersji strony zebrało się kilkach spraw o których chciałbym napisać. Po pierwsze na stronie ciągle zachodzą zmiany, zmieniam ustawienia, dołączam/aktualizuje pluginy do wordpresa. Może się więc okazać że coś nagle przestanie działać. Jeśli ktoś zauważy że coś nie działa będę wdzięczny za informację o tym (albo tutaj w komentarzu albo na e-maila). Po drugie zachęcam do komentowania, czy to konkretnych postów tematycznych czy samej strony. W tej chwili komentarze są moderowane(na stronie będą wyświetlone po zaakceptowaniu komentarza przeze mnie). Pozwala mi to na ręczny odsiew spamu, z którym nie poradziły sobie automaty. W przyszłości postaram się popracować nad lepszym mechanizmem antyspamowym i wyłączeniem moderacji postów. Natomiast jeśli ktoś z Was napisał komentarz i w ciągu 24h nie pojawił się na stronie proszę o informację o tym. Zapewne będzie to wina niepoprawnej konfiguracji skryptów strony. Po trzecie jeśli macie ciekawe linki, materiały o programowaniu wielowątkowym będzie mi miło jeśli mi je podeślecie. Wiedzy nigdy za wiele 😉

Obecnie zrobiłem sobie krótką przerwę od świata wirtualnego. Na nowe wiadomości zapraszam po 15 sierpnia 🙂

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.

Programowanie wielowątkowych gier w języku C++

Lipiec 7th, 2008 Marcin Borowiec

Dziś dodałem pierwszy artykuł do działu publikacje.

„Programowanie wielowątkowych gier w języku C++” zawiera m.in:

  • Podstawy teoretyczne dotyczące synchronizacji wątków
  • Opis jednych z wielu metod synchronizacji wątków w języku C++
  • Zwrócenie uwagi na często pojawiające się błędy w programowaniu w języku C++ (volatile, itp …).
  • Przedstawienie modelu pamięci programowania aplikacji w C++  (niezbędne do zrozumienia zasad pisania poprawnych programów)
  • Krótki zarys OpenMP
  • Uwagi dla programistów gier

Bezpośredni link do artykułu: pwgwjcpp

Co z Paper Ball?

Lipiec 6th, 2008 Marcin Borowiec

Na wstępie chciałem podziękować wszystkim osobom, które aktywnie wspierały mnie przy tworzeniu dotychczasowych wersji Paper Ball (począwszy od betatesterów, poprzez osoby, które kupiły wersję pro, po osoby, które wyraziły opinie o grze). Dzięki! Dla wszystkich zainteresowanych Paper Ball mam trzy wiadomości.

Po pierwsze: Począwszy od dzisiaj Paper Ball 2004Pro staje się w całości darmowe. Na stronie w tej chwili dostępna jest tylko wersja Pro. Użytkownicy wersji podstawowej mogą ją odinstalować i na jej miejsce zainstalować nową wersję. Paper Ball 2004Pro to 6 poziomów trudności i tryb sieciowy.

Po drugie: Nie wykluczam udostępnienia kodu źródłowego gry. Wymaga to jednak przygotowania kilku rzeczy, na które potrzebuje czasu. Jeśli jednak będą zainteresowani postaram się ten czas znaleźć.

Po trzecie: Niestety nie jestem w stanie dokończyć rozpoczętej już w 2003 roku nowej znacznie rozbudowanej wersji gry. Założenia były nie adekwatne do czasu, którym dysponowałem. Chciałbym jednak żeby powstała nowa wersja o podobnej funkcjonalności jak 2004Pro + to co najbardziej wam w niej brakowało:

  • możliwość cofania ruchów
  • nowy znacznie inteligentniejszy algorytm gracza komputerowego z implementacja w pełni wykorzystującą obecne procesory wielordzeniowe
  • wersja na Smartphone i Palmtopy

Może jest ktoś kto mógłby pomóc taką grę zrobić? Chodzi mi głównie o GUI i tryb sieciowy. Ja mógłbym napisać nowy algorytm AI. Niestety kod z wersji 2004 nie nadaje się do rozwijania więc gra będzie musiała być napisana od 0.

Czas na Web 2.0

Lipiec 5th, 2008 Marcin Borowiec

Witam wszystkich czytelników po dość długiej przerwie w aktualizacjach. Mam nadzieje że zmiany (te które już się pojawiły i te które dopiero się pojawią) zrekompensują długi okres oczekiwania. Z braku czasu na tworzenie skryptów i modernizacje layoutu  zdecydowałem się użyć gotowy system zarządzania treścią (CMS). Ułatwi mi to znacznie aktualizowanie strony, a to powinno spowodować że kolejne wpisy na stronie będą przybywać dużo dużo szybciej. Wszystkie newsy i wpisy z księgi gości zostały przeniesione ze starej strony. Była to dobra okazja do usunięcia spamu 😉

Nowa strona to nie tylko nowy CMS ale i zmiana formy dotychczasowej „zwyczajnej strony domowej” na bloga. Na blogu będą pojawiać się newsy dotyczące moich nowych produktów jak i krótkie artykuły techniczne dotyczące głównie programowania aplikacji wielowątkowych. Chociaż nie wykluczam poszerzenia tematu blogu. Pojawia się także nowy dział publikacje. Znajdą się tam artykuły mojego autorstwa, zarówno te adresowane bezpośrednio do czytelników blogu jak i wersje elektroniczne materiałów drukowanych. Jak przystało na stronę Web 2.0 udostępnia ona możliwość komentowania praktycznie wszystkiego co zostało na stronie umieszczone jak i śledzenia zawartości przez czytniki RSS do czego oczywiście zachęcam.