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