I
IB109 Návrh a implementace paralelních systémů
Programování v prostředí se sdílenou pamětí
Jiří Barnat
HW model prostředí se sdílenou pamětí
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 2/32
HW platformy
Paralelní systémy se sdílenou pamětí
• Systémy s více procesory
• Systémy s více-jadernými procesory
• Systémy s procesory se zabudovaným SMT o Kombinace
Rizika paralelních výpočtů na soudobých procesorech
o Mnohé optimalizace na úrovni procesoru byly navrženy tak, aby zachovávaly sémantiku sekvenčních programů.
Pozor zejména na
• Přeuspořádání instrukcí
• Odložené zápisy do paměti
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 3/32
Simultání multithreading (SMT)
Princip
9 Procesor využívá prázdné cykly způsobené latencí paměti k vykonávání instrukcí jiného vlákna.
9 Vyžaduje duplikaci jistých částí procesoru (např. registry).
• Vlákna sdílí cache.
Příklad: Intel Pentium 4
• Hyper-Threading Technology (HTT)
• OS s podporou SMP vidí systém se SMT/HTT jako více procesorový systém.
• Až 30% nárůst výkonu, ale vzhledem ke sdílené cache může být rychlost výpočtu jednoho vlákna nižší.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 4/32
Více-jaderné procesory (multicores]
Více plnohodnotných procesorů v jednom chipu. Výhody
• Efektivnější cache koherence na nejnižší úrovni. 9 Nižší náklady pro koncového uživatele.
Nevýhody
o Víc jader emituje větší zbytkové teplo.
• Takt jednoho jádra bývá nižší.
o Automatické dočasné podtaktování/přetaktování.
• Jádra sdílí datovou cestu do paměti.
Realita
• Více-jádrové procesory se SMT.
• Intel Core-i7 (hexa-core se SMT = 12 paralelních jednotek)
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 5/32
Paralelismus v prostředí se sdílenou pamětí
Idealizovaný model
• Na této úrovni se řeší návrh paralelního algoritmu.
• Jednotlivá výpočetní jádra paralelního systému pracují zcela nezávisle.
• Přístupy k datům v paměti jsou bezčasové a vzájemně výlučné.
• Komunikace úloh probíhá atomicky přes sdílené datové struktury.
Realita
• Na této úrovni musí programátor řešit technickou realizaci paralelního algoritmu.
9 Přístup do paměti přes sběrnici je pro CPU příliš pomalý.
• Registry procesoru a cache paměti - rychlé kopie malého množství dat na různých místech datové cesty.
• Problém koherence dat.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 6/32
Paralelní úlohy v kontextu OS - Procesy a vlákna
Procesy
• Skrývají před ostatními procesy své výpočetní prostředky.
• Pro řešení paralelní úlohy je potřeba mezi-procesová komunikace (IPC).
• Sdílené paměťové segmenty, sokety, pojmenované a nepojmenované roury
Vlákna
o Existují v kontextu jednoho procesu.
• V rámci rodičovského procesu sdílí výpočetní prostředky.
• Komunikace probíhá přes sdílené datové struktury.
• Účelem interakce je spíše synchronizace než transport dat.
• Subjekty procedury plánování.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 7/32
Příklad použití vláken v rámci procesu
Vlákno
• Realizuje výpočet, tj sekvenci instrukcí.
• Každý proces je tvořen alespoň jedním vláknem.
• Hlavní vlákno procesu vytváří další vlákna.
Příklad
1 for (i=0; i<n; i++)
2 for (j=0; j<n;
3 m [i] [j] = create_thread(
4 product(getrow(i),getcol(j))
5 )
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 8/32
Procesy versus vlákna
Proces
• Identifikátory procesu a vlastníka
9 Proměnné prostředí, pracovní adresář
• Kód
• Registry, Zásobník, Halda
• Odkazy na otevřené soubory a sdílené knihovny
• Reakce na signály
• Kanály IPC
Vlákna mají privátní
• Zásobník
• Registry
• Frontu signálů
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 9/32
Proces v operačním systému
stuck
text
data
heap
User Address Space
routinel    varl()
	
Locks	
Sockets	
	
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 10/32
Vlákna v rámci procesu
Stack Pointer Prgrm. Counter Registers
	^trtrlt Pňirttŕr
IB	-J L d \_ IX.  ■  Ulli IC 1 Prgrm. Counter Registers
Process ID User ID Group ID	
	
I
IB109 Návrh a implementace paralel
nich systémů: Programování v prostředí se sdílenou pamětí
str. 11/32
Argumenty pro používaní vláken místo procesů
Výkon aplikace
• Vytvoření procesu je výrazně dražší než vytvoření vlákna.
o Změna dat provedená v rámci jednoho vlákna je viditelná v kontextu celého procesu.
• Komunikace mezi vlákny spočívá v předávání reference na data, nikoliv v předávání obsahu.
9 Předávání reference se děje v rámci jednoho procesu, operační systém nemusí řešit skrývání dat a přístupová práva.
Nevýhody
• Vlákna nemají žádné "soukromí". Sdílené globální proměnné.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 12/32
Efektivní využití cache
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 13/32
Cache
Princip cache
• Menší ale rychlejší paměť na pomalé datové cestě.
• Při prvním čtení se okolí čtené informace uloží do cache.
a Při následujícím čtení z okolí původní informace se čte pouze z cache.
Koherence
• Soulad dat uložených v paměti počítače (potažmo v cache).
• Je zajištěno, že existuje právě jedna platná hodnota asociovaná s daným paměťovým místem.
• Z důvodu rychlosti jsou zápisy procesoru do paměti odkládány a sdružovány, bližší specifikace chování procesoru v tomto ohledu je dána paměťovým modelem daného CPU.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 14/32
Cache - související pojmy
Související pojmy
• Cache line - atomický paměťový blok uložený v cache.
• "Hit ratio" - číslo vyjadřující úspěšnost obsloužení požadavků na data daty uloženými v cache.
• "Vylití cache" - procedura aktualizace dat v paměti hodnotami uloženými v cache.
Zásady efektivního použití cache
• Časová lokalita - přístupy v malém časovém intervalu.
• Prostorová lokalita - přístup k datům uložených adresně blízko sebe.
• Zarovnaná alokace paměti (např. memalign (GNU C)).
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 15/32
False sharing - príklad
Specifikace
• Paralelní cache koherentní systém s více procesory.
• Program s několikanásobně vícero vlákny.
• Pole hodnot int pole [nr_of _threads].
o Vlákna počítají výslednou hodnotu typu int a k výpočtu si ukládají mezivýsledek typu int.
Varianty implementace
A) Každé vlákno opakovaně zapisuje do datového pole integerů na pozici určenou jeho ID.
B) Každé vlákno zapisuje do lokální proměnné a před skončením nakopíruje hodnotu do pole na pozici určenou jeho ID.
Otázka
o Která implementace bude pomalejší a proč?
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 16/32
typedef struct {
long long iter;
} thread_private_data_t;
thread_private_data_t v [16] ;
v[1]	v[2]				
my .thread(...) {
v[id] . iter ++;
}
\ Cache /'
t
WRITE
Cache
t
WRITE
CPU 0
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
CPU 1
str. 17/32
typedef struct {
long long iter;
char cache_line_f iller [2000] ; } thread_private_data_t;
thread_private_data_t v [16] ;
v[1]			v[2]		
my .thread(...) {
v[id] . iter ++;
}
\ Cache
\ Cache /
t
WRITE
t
WRITE
CPU 0
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
CPU 1
str. 18/32
typedef struct {
long long iter;
char cache_line_f iller [2000] ; } thread_private_data_t;
thread_private_data_t v [16] ;
v[1]			v[2]		
my .thread(...) {
v[id] . iter ++;
}
\ Cache /'
t
WRITE
\ Cache /
t
WRITE
CPU 0
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
CPU 1
str. 19/32
1 thread 10 threads 16 threads
2000
119 xlO6 iterations (l.OOx) 231 xlO6 iterations (1.94x) 313 xlO6 iterations (2.63x)
—i-r
no padding
linear
1500
o
-I—•
P 1000
CD
O
500 -
0 l_i_i_i_i_i_i_i_l
0 2 4 6 8 10 12 14 16
threads
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 20/32
1 thread 10 threads 16 threads
2000
1500
o
-I—•
o 1000
CD
O
500 -
0
0
119 xlO6 iterations (l.OOx) 1055 xlO6 iterations (8.86x) 1815 xlO6 iterations (15.25x)
—i-r
with padding
no padding
linear
8
threads
10
12
14
16
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 21/32
Přehnaná důvěra v mentální model
POZOR!
• Není garantováno, že všechny informace uložené do explicitně definovaných proměnných budou zapsány do paměti.
• Proměnné mohou být realizovány registrem procesoru. Důsledek
• Posloupnost hodnot uložených do jedné proměnné v rámci jednoho vlákna může být viděna jiným vláknem jen částečně nebo vůbec.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 22/32
Nestále proměnné
Pozorování
• Udržování koherence cache pamětí je nákladné.
• Soudobé překladače nevynucují, aby každá vypočítaná hodnota byla uložena do paměti (nevygenerují instrukci ukládající obsah registru do paměti).
Důsledek
• Modifikace sdílené proměnné provedená v jednom vlákně na daném CPU se nemusí projevit v jiném vlákně na jiném CPU.
Příklad
int i=0;
PO {
Pl {
while ( i==0 );
if (i==0)
}
}
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 23/32
Nestále proměnné
Problém
o Vlákno PO neskončí, neboť nezaznamená změnu proměnné i.
• Může záviset na stupni optimalizace překladu, například
• chyba se neprojeví při překladu pomocí g++ -00
• chyba se projeví při překladu pomocí g++ -02
Řešení
• Je nutné označit proměnnou jako tzv. nestálou proměnnou.
• C,C++: klíčové slovo volatile.
• Překladač zajistí, aby daná proměnná nebyla realizována pouze na úrovni registrů CPU, ale před a po každém použití byla načtena/uložena do paměti.
Příklad
volatile int i=0;
PO { Pl {
while ( i==0 ); if (i==0)
} }
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí str. 24/32
Nestálé proměnné - volatile
Použití klíčového slova
9 Umístěno před nebo za datový typ v definici proměnné.
• Rozlišujeme
o nestálou proměnnou: volatile T a T volatile a
• ukazatel na nestálou proměnnou:
volatile T *a
• nestálý ukazatel na nestálou proměnnou:
volatile T * volatile a
Případy, kdy je nutné použít volatile:
9 Proměnná sdílená mezi souběžnými vlákny/procesy.
• Proměnná zastupující vstup/výstupní port.
9 Proměnná modifikovaná procedurou obsluhující přerušení.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 25/32
Přehnaná důvěra ve volatile
Příklad
volatile int i=0;
Proč {
for (int j=0; j<100000;
i=i+l;
}
main {
run_thread Proč as TI; run_thread Proc as T2; wait_on TI; wait_on T2; print i;
}
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 26/32
Přehnaná důvěra ve volatile - pokračování
Výstup
9 Na systému s jednou výkonnou jednotkou výstup vždy 200000.
• Na paralelních architekturách výstup často menší než 200000.
Zdůvodnění
9 Zápisy hodnot do paměti (do cache) nejsou prováděny v okamžiku zpracování instrukce, ale jsou odkládány a shlukovány.
• Přesný popis toho, jak procesor manipuluje se zápisy do paměti je součástí specifikace procesoru, jedná se o tzv. paměťový model.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 27/32
Přehnaná důvěra v mentální model
POZOR!
• Pořadí zápisů do paměti dle vykonávané posloupnosti instrukcí procesoru nemusí korespondovat se skutečným pořadím zápisu hodnot do paměti.
• Paměťový model procesoru garantuje korektnost pouze pro sekvenční programy.
Důsledek
o Posloupnost přiřazení hodnot různým sdíleným proměnným provedená v jednom vlákně nemusí korespondovat s pořadím změn hodnot těchto proměnných v jiném vlákně.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 28/32
Největšř "skrčka" paralelního programování
Příklad
volatile int i=0;
volatile int * volatile p=0;
PO { Pl {
• • • • • •
while (i==0); p = new int;
(*p)=5; i=l;
• • • • • •
} } Problém
o V okamžiku přístupu na adresu odkazovanou ukazatelem může mít p hodnotu 0.
Pozorování
• Bez nějakého dalšího opěrného bodu na HW úrovni je programování paralelních systémů téměř nemožné.
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
Co je to
9 HW primitivům pro synchronizaci stavu paměti a stavů procesorů v daném místě programu.
• Na soudobých procesorech realizované instrukcí mfence. Přesný popis
Na hardwarové úrovni provede serializaci všech load a store instrukcí, které se vyskytují před instrukcí mfence. Tato serializace zajistí, že efekt všech instrukcí před instrukcí mfence bude globálně viditelný pro všechny instrukce následující za instrukcí mfence.
Realizace
• Není součástí vyšších programovacích jazyků.
o Různé překladače dávají programátorovi jisté možnosti.
• GCC: __sync_synchronize ()
• Intel(R) C++ Compiler: void_mm_mfence(void)
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
HW podpora pro atomické instrukce
Fakta
9 Paměťová bariéra neřeší problém atomických instrukcí jako jsou TEST-AND-SET, COMPARE-AND-SWAP, atd.
• Instrukce výše zmíněného typu jsou však pro účely efektivního paralelního programování velmi vhodné.
Další HW podpora
• Alpha, Mips, PowerPC, ARM: instrukce typu LL/SC
• x86 architektura
• lock - následující (do paměti zapisující) instrukce proběhne atomicky a její efekt bude ihned globálně viditelný
• XCHG - prohodí obsah registru a paměťového místa (obsahuje z definice prefix lock)
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 31/32
Realizace atomických instrukcí na úrovni kódu
Možnost 1: Jazyk symbolických adres
1 int test_and_set (volatile int *s){
2 int r;
3 __asm__ __volatile__(
4 "xchgl °/00, yol \n\t"
5 :  "=r"(r), "m"(*s)
6 :  "0"(1), "m"(*s)
7 :  "memory"); ^— paměťová bariéra
8 return r;}
Možnost 2: Zabudované funkce překladače (GCC > 4.1)
• type __sync_val_compare_and_swap (...)
• type __sync_fetch_and_add (...)
Možnost 3: Součást programovacího jazyka
• C++ rev. 11, Java, ...
IB109 Návrh a implementace paralelních systémů: Programování v prostředí se sdílenou pamětí
str. 32/32