1/37 Open MP Pokročilejší techniky OpenMP Vláknové programování část V Lukáš Hejmánek, Petr Holub {xhejtman,hopet}@ics.muni.cz Laboratoř pokročilých síťových technologií PV192 2014–04–08 2/37 Open MP Pokročilejší techniky OpenMP Přehled přednášky Open MP Pokročilejší techniky OpenMP 3/37 Open MP Pokročilejší techniky OpenMP Open MP • Standard pro programování se sdílenou pamětí • Podpora v programovacích jazycích Fortran (od r. 1997), C, C++ (od r.1998) • Současná verze 3.0 je z roku 2008 pro Fotran i C/C++ • Podporováno řadou překladačů vč. gcc a Intel cc • Podpora paralelního programování pomocí • Soustavy direktiv pro překladač • Knihovních procedur • Proměnných prostředí 4/37 Open MP Pokročilejší techniky OpenMP Programovací model OpenMP • Explicitní paralelismus • Fork/join model • Vnořený (nested) paralelismus není vždy dostupný 5/37 Open MP Pokročilejší techniky OpenMP Překlad • gcc -g -o foo foo.c -fopenmp -D_REENTRANT • Aplikace je slinkována s knihovnami libgomp a libpthread. 6/37 Open MP Pokročilejší techniky OpenMP Open MP příkazy • Přehled syntaxe • Parallel • Loop • Sections • Task (Open MP 3.0+) • Synchronization • Reduction 7/37 Open MP Pokročilejší techniky OpenMP Přehled syntaxe • Základní formát #pragma omp jméno-pˇríkazu [klauzule] nový_ˇrádek • Všechny příkazy končí novým řádkem • Používá konstrukci pragma (pragma = věc) • Rozlišuje malá/velká písmena • Příkazy mají stejná pravidla jako C/C++ • Delší příkazy lze napsat na více řádků pomocí escape znaku \ 8/37 Open MP Pokročilejší techniky OpenMP Parallel • Blok kódu prováděn několika vlákny • Syntaxe: 1 #pragma omp parallel 2 { 3 /* parallel section */ 4 } 9/37 Open MP Pokročilejší techniky OpenMP Parallel – příklad 1 #include 2 #include 3 4 int main (int argc, char *argv[]) { 5 printf("Hello world from threads:\n"); 6 #pragma omp parallel 7 { 8 int tid = omp_get_thread_num(); 9 printf("<%d>\n", tid); 10 } 11 printf("I am sequential now\n"); 12 return 0; 13 } • Výstup: Hello world from threads: <1> <0> I am sequential now 10/37 Open MP Pokročilejší techniky OpenMP Klauzule if, private, shared • if (výraz) • omp příkaz bude proveden paralelně, pokud je výraz vyhodnocen jako pravdivý, jinak je blok proveden sekvenčně • private(list) • Úložiště objektu není asociováno s původní lokací • Všechny reference jsou k lokálnímu objektu • Nemá definovanou hodnotu při vstupu a výstupu • shared(list) • Data jsou přístupná ze všech vláken v týmu • Všechna data jsou pro vlákna na stejných lokacích • Přístup k datům není synchronizován! 11/37 Open MP Pokročilejší techniky OpenMP Loop • Iterace smyčky budou prováděny paralelně • Na konci smyčky je implicitní barriéra, není-li řečeno jinak (nowait) • Syntaxe: 1 #pragma omp for nowait 2 { 3 /* for loop */ 4 } 12/37 Open MP Pokročilejší techniky OpenMP Které smyčky jsou paralelizovatelné? Paralelizovatelné • Počet iterací je znám předem a nemění se • Iterátory (C++) (platí pro Open MP 3.0 a novější) • Každá iterace nezávisí na žádné ostatní • Nezávislost dat Neparalelizovatelné • Podmíněné smyčky (často while smyčky) • Iterátory (C++) (neplatí pro Open MP 3.0 a novější) • Závislé iterace • Závislá data 13/37 Open MP Pokročilejší techniky OpenMP 1 /* Gaussian Elimination (no pivoting): 2 x = A\b */ 3 for (int i = 0; i < N-1; i++) { 4 #pragma omp parallel for shared (A,b,i,N) 5 for (int j = i; j < N; j++) { 6 double ratio = A[j][i]/A[i][i]; 7 for (int k = i; k < N; k++) { 8 A[j][k] -= (ratio*A[i][k]); 9 b[j] -= (ratio*b[i]); 10 } 11 } 12 } Poznámka: lze kombinovat parallel a for do jednoho pragma příkazu 14/37 Open MP Pokročilejší techniky OpenMP Lze paralelizovat? • Vnější smyčka (i) • N-1 iterací • Iterace závisí na ostatních (hodnoty spočítané v kroku i-1 jsou použity v kroku i) • Vnitřní smyčka (j) • N-i iterací (konstanta pro konkrétní i) • Iterace mohou být provedeny v libovolném pořadí • Nejvnitřnější smyčka (k) • N-i iterací (konstanta pro konkrétní i) • Iterace mohou být provedeny v libovolném pořadí 15/37 Open MP Pokročilejší techniky OpenMP Section(s) • Neiterativní spolupráce • Rozdělení bloků programu mezi vlákna • Syntaxe: 1 #pragma omp sections 2 { 3 #pragma omp section 4 /* first section */ 5 #pragma omp section 6 /* next section */ 7 } 16/37 Open MP Pokročilejší techniky OpenMP Section(s) příklad 1 #include 2 #define N 1000 3 int main () { 4 int i; 5 double a[N], b[N], c[N], d[N]; 6 /* Some initializations */ 7 for (i=0; i < N; i++) { 8 a[i] = i * 1.5; 9 b[i] = i + 22.35; 10 } 11 #pragma omp parallel shared(a,b,c,d) private(i) 12 { 13 #pragma omp sections 14 { 15 #pragma omp section 16 for (i=0; i < N; i++) 17 c[i] = a[i] + b[i]; 18 #pragma omp section 19 for (i=0; i < N; i++) 20 d[i] = a[i] * b[i]; 21 } /* end of sections */ 22 } /* end of parallel section */ 23 return 0; 24 } 17/37 Open MP Pokročilejší techniky OpenMP Task – Open MP 3.0+ • Koncepce spuštění bloku kódu na „pozadí“ • Některé kusy kódu jdou špatně paralelizovat, např.: 1 while(my_pointer) { 2 (void) do_independent_work (my_pointer); 3 my_pointer = my_pointer->next ; 4 } // End of while loop • do_indipendent_work by mohlo běžet v pozadí • Pro starší OpenMP – napřed spočítat počet iterací, pak převést while na for • Koncepce tasku: • Smyčka běží v jediném vlákně (kvůli procházení seznamu) • do_independent_work se pustí do pozadí • Syntaxe: #pragma omp task 18/37 Open MP Pokročilejší techniky OpenMP Task – příklad 1 my_pointer = listhead; 2 #pragma omp parallel 3 { 4 #pragma omp single nowait 5 { 6 while(my_pointer) { 7 #pragma omp task firstprivate(my_pointer) 8 { 9 (void) do_independent_work (my_pointer); 10 } 11 my_pointer = my_pointer->next ; 12 } 13 } // End of single - no implied barrier (nowait) 14 } // End of parallel region - implied barrier 19/37 Open MP Pokročilejší techniky OpenMP Task • Čekání na potomky (vytvořené tasky) #pragma omp taskwait • Task má nepatrně vyšší režii než for 20/37 Open MP Pokročilejší techniky OpenMP Task – příklad 1 my_pointer = listhead; 2 #pragma omp parallel 3 { 4 #pragma omp single nowait 5 { 6 while(my_pointer) { 7 #pragma omp task firstprivate(my_pointer) 8 { 9 (void) do_independent_work (my_pointer); 10 } 11 my_pointer = my_pointer->next ; 12 } 13 } // End of single - no implied barrier (nowait) 14 #pragma omp taskwait 15 } // End of parallel region - implied barrier 21/37 Open MP Pokročilejší techniky OpenMP Synchronizace • Kritickým sekcím se nevyhneme ani v OpenMP • Závislosti v běhu programu (některé sekce musí být hotové dřív jak jiné) • Některé kusy nemohou být prováděny paralelně • Synchronizační primitiva • Critical, Atomic • Barrier • Single • Ordered, Flush 22/37 Open MP Pokročilejší techniky OpenMP Critical • Critical • Specifikuje sekci v programu, kterou může vykonávat nejvýše jedno vlákno (je jedno které) • Všechna vlákna postupně sekcí projdou • V podstatě označuje kritickou sekci • Syntaxe: #pragma omp ciritcal [jméno] • jméno je globální identifikátor, kritické sekce stejného jména jsou považovány za identické, tj. žádné bloky stejného jména nepoběží paralelně 23/37 Open MP Pokročilejší techniky OpenMP Atomic • Specifikuje sekci v programu, kterou může vykonávat nejvýše jedno vlákno (je jedno které) • Lehká forma synchronizace, synchronizované jsou pouze čtení a zápisy • Využívá lock instrukce na x86/x86_64 architektuře • Syntaxe: #pragma omp atomic 1 #pragma omp atomic 2 a[indx[i]] += b[i]; • Výraz musí být „atomizovatelný“ jinak je ohlášena chyba • Typicky: x++, x += 2 • Jde přeložit: *a += *a + 1 ale nefunguje korektně! 24/37 Open MP Pokročilejší techniky OpenMP Single, Master • Podobně jako Critical, Single specifikuje sekci, kterou může provádět pouze jedno vlákno • Narozdíl od Critical, je tato sekce provedena pouze jednou • Vhodné pro thread-unsafe sekce, např. I/O • Syntaxe: #pragma omp single • Master je stejné jako Single, sekci provede vždy „master“ vlákno • Syntaxe: #pragma omp master 25/37 Open MP Pokročilejší techniky OpenMP Barrier • Klasická bariéra, synchronizuje všechna vlákna na bariéře • Syntaxe: #pragma omp barrier • Posloupnost paralelních sekci a bariér musí být stejná pro všechna vlákna • Příkazy single a master nemají implicitní bariéru na vstupu a výstupu! 26/37 Open MP Pokročilejší techniky OpenMP Ordered • Ordered • Blok bude vykonán ve stejném pořadí, jako by byl vykonán, kdyby běžel jen v jednom vlákně • Může způsobovat serializaci • Syntaxe: #pragma omp ordered 1 #pragma omp parallel for ordered private(i) shared(n,a) 2 for (i=0; i 2 #include 3 int main() 4 { 5 int n = 9, i, a, b[n]; 6 for (i=0; i 2 #include 3 int main() 4 { 5 int i, n = 25, sumLocal; 6 int sum = 0, a[n]; 7 int ref =(n-1)*n/2; 8 for (i=0; i 2 #include 3 int main() 4 { 5 int i, n = 25; 6 int sum = 0, a[n]; 7 int ref = (n-1)*n/2; 8 for (i=0; i