Introdução ao OpenMP

Processamento Paralelo

Prof. Oberlan RomãoDepartamento de Computação e Eletrônica – DCELCentro Universitário Norte do Espírito Santo – CEUNESUniversidade Federal do Espírito Santo

OpenMP

O que é OpenMP?

• Open Multi-Processing (OpenMP)

• API para paralelismo em computadores com vários processadores(núcleo) de memória compartilhada

• Parte do programa contém um único thread e parte vários threads

• Possui 3 componentes• Diretivas de compilador que podem ser colocadas em programas C/C++

ou Fortran• Biblioteca de tempo de execução para configuração e consulta de

parâmetros paralelos (por exemplo, #threads)• Variáveis de ambiente que definem parâmetros paralelos de tempo de

execução (por exemplo, #threads)

1/37

OpenMP

Objetivos

• Padronizar

• Simplificar

• Facilitar o uso

• Permitir portabilidade

2/37

OpenMP

Modelo de programação

• Threads dinâmicas

• Paralelismo explícito e aninhável

• Diretivas de compilador

• Modelo Fork-Join

3/37

OpenMP

Modelo Fork-Join

• OpenMP usa o modelo fork-join da execução paralela:

• Todos os programas com OpenMP começam como um único processo: o threadmestre, que é executado sequencialmente até que a primeira construção da regiãoparalela seja encontrada

• FORK: o thread mestre cria um grupo de threads paralelos

• As instruções no programa da região paralela são executadas em paralelo pelosthreads do grupo

• JOIN: Quando os threads concluem as instruções da região paralela, eles sãosincronizados e finalizados, deixando apenas o thread mestre

• O número de regiões paralelas e os threads que os compõem são arbitrários4/37

OpenMP

Diretivas

• Uma diretiva é uma linha especial de código com significado especialapenas para determinados compiladores

• Uma diretiva se distingue pela existência de uma sentinela no começo dalinha

• Em C/C++, a sentinela do OpenMP é:

#pragma omp

• O compilador interpreta essas diretivas e gera chamadas de bibliotecapara paralelizar regiões de código

5/37

OpenMP

DiretivasUsadas para:

• Criar regiões paralelas

• Distribuir blocos de código

• Distribuir iterações de laços

• Sincronizar threads

• . . .

Modelo:

#pragma omp directive [clause , ...]

6/37

OpenMP

• #pragma omp parallel• Diretiva paralela mais básica do OpenMP

• O número de threads que executam o bloco de código seguinte édeterminado pelo sistema em tempo de execução

7/37

OpenMP

Regiões paralelas

#pragma omp parallel \private (var1, var2, ...) \shared (var1, var2, ...) \firstprivate(var1, var2, ...) \copyin(var1, var2, ...) \reduction(operator:var1, var2, ...) \if(expression) \default(shared|none) \num_threads(thread_count) \

{...bloco de código...

}

8/37

OpenMP

Regiões paralelas

• Uma região paralela é um bloco de código executado por todos threadssimultaneamente

• Cada thread tem um ID, que é um inteiro de 0 (o thread mestre) até onúmero de threads menos um

• Pode ser determinado pela função omp_get_thread_num()

• Threads podem executar diferentes instruções na região paralela• Normalmente feito usando a ID do thread:

#pragma omp parallel{

myid = omp_get_thread_num ();if (myid == 0)

do_something ();else

do_something_else(myid);}

9/37

OpenMP

Exemplo 1

#include <stdio.h>#include <omp.h>

int main(int argc , char *argv[]){int numThreads = atoi(argv[1]);

#pragma omp parallel num_threads(numThreads)printf("Hello , world .\n");

return 0;}

10/37

OpenMP

Exemplo 2

#include <omp.h>#include <stdio.h>#include <stdlib.h>

int main (int argc , char *argv[]) {#pragma omp parallel{

int nthreads , tid;/* Obtain thread number */tid = omp_get_thread_num ();printf("Hello World from thread = %d\n", tid);

/* Only master thread does this */if (tid == 0) {

nthreads = omp_get_num_threads ();printf("Number of threads = %d\n", nthreads);

}} /* All threads join master thread and disband */return 0;

}11/37

OpenMP

Regiões paralelas: Modos de execução

• “Modo dinâmico” (o padrão)• O número de threads usados em uma região paralela pode variar, sob

controle do sistema operacional, de uma região paralela para outra• Definir o número de threads apenas define o número máximo de threads

• “Modo estático”• O número de threads é fixado pelo programador;

• As regiões paralelas podem ser aninhadas, mas um compilador podeoptar por “serializar” a região paralela interna, ou seja, executá-la em umúnico thread

• O modo de execução é controlado por• A variável de ambiente OMP_DYNAMIC• A função OMP omp_set_dynamic()

12/37

OpenMP

Cláusulas da diretiva do OpenMP

• shared(var1,var2,...)• Variáveis a serem compartilhadas entre todos os threads (threads

acessam os mesmos locais de memória)

• private(var1,var2,..)• Cada thread tem sua própria cópia das variáveis na execução do código

paralelo.

• firstprivate(var1,var2,...)• Variáveis privadas que são inicializadas quando o código paralelo é

iniciado

• lastprivate(var1,var2,...)• Variáveis privadas que tem seus valores salvos na última iteração

13/37

OpenMP

Cláusulas da diretiva do OpenMP

• if(expression)• Paraleliza o código apenas se a expression for verdadeira.

• default(shared|private|none)• Especifica o escopo padrão para variáveis em código paralelo.

• schedule(type [,chunk])• Controla como as iterações de um loop são distribuídas entre os threads

• reduction(operator|intrinsic:var1,var2...)• Garante que uma operação de redução (por exemplo, uma soma global)

seja executada com segurança

14/37

OpenMP

Escopo de variáveis

• Na programação sequencial, o escopo de uma variável consiste naspartes de um programa em que a variável pode ser usada

• Em OpenMP, o escopo de uma variável se refere ao conjunto de threadsque podem acessar a variável em um bloco paralelo.

• Uma variável que pode ser acessada por todos os threads do grupo temescopo compartilhado (shared)

• Uma variável que só pode ser acessada por um único thread tem escopoprivado (private)

• O escopo padrão para variáveis declaradas antes de um bloco paralelo écompartilhado.

15/37

OpenMP

if(expression)

• Só executa em paralelo se expression for avaliada como verdadeira

• Caso contrário, executa sequencialmente

private(var1,var2,...)

• Nenhuma associação de armazenamento com a variável original

• Todas as referências são para uma variável local

• Os valores são indefinidos no inicio e no fim

shared(var1,var2,...)

• Os dados são acessíveis por todos os threads do grupo

• Todos os threads acessam o mesmo espaço de endereçamento

#pragma omp parallel if (n > 10) shared(n,x,y) private(i){} 16/37

OpenMP

Diretivas para Compartilhamento de Trabalho

• #parallel for

• #parallel sections

• Colocados dentro de regiões paralelas

• Distribui a execução de instruções entre os threads existentes

17/37

OpenMP diretiva: for

#parallel for

#pragma omp parallel shared(a,b) private(j){

#pragma omp forfor (j = 0; j < N; j++)

a[j] = a[j] + b[j];}

• Distribui iterações do loop imediatamente a seguir entre os threads deum grupo

• Por padrão, há uma barreira no final do loop• Os threads aguardam até que tudo esteja concluído e, em seguida,

prosseguem• Use a cláusula nowait para permitir que os threads continuem sem

aguardar

18/37

OpenMP diretiva: for

#parallel for

#pragma omp parallel shared(a,b) private(j){

#pragma omp forfor (j = 0; j < N; j++)

a[j] = a[j] + b[j];}

• Distribui iterações do loop imediatamente a seguir entre os threads deum grupo

• Por padrão, há uma barreira no final do loop• Os threads aguardam até que tudo esteja concluído e, em seguida,

prosseguem• Use a cláusula nowait para permitir que os threads continuem sem

aguardar

18/37

OpenMP diretiva: for

Formas legais para declarações for paralelizáveis

19/37

OpenMP diretiva: for

#parallel for

#pragma omp for [clause [clause]...]for loop

onde cada clause pode ser

• private(var1,var2,...)

• firstprivate(var1,var2,...)

• lastprivate(var1,var2,...)

• reduction(operator: var1,var2,...)

• ordered

• schedule(type [, chunk_size])

• nowait

20/37

OpenMP diretiva: for

firstprivate(var1,var2,...)

• Variáveis são privadas (locais para cada thread), mas são inicializadascom o valor do código sequencial anterior

int myid , c = 98;#pragma omp parallel private(myid) firstprivate(c){

myid=omp_get_thread_num ();printf("T:%d c=%d", myid , c);

}

T:1 c=98T:3 c=98T:2 c=98T:0 c=98

• Cada thread tem uma cópia privada de c, inicializada com o valor 98

21/37

OpenMP diretiva: for

lastprivate(var1,var2,...)

• O valor correspondente à última iteração do loop (no modo serial) ésalvo após a construção paralela

#pragma omp parallel for lastprivate(x){

for(i=1; i<=n; i++){x = sin((float)i );a[i] = exp(x);

}}lastx = x;

• Se x for declarado com private, o valor de lastx é indefinido!

22/37

OpenMP diretiva: for

ordered

• Usado quando parte do loop deve executar em ordem sequencial

#pragma omp parallel for private(myval) ordered{

for(i=1; i<=n; i++){myval = do_lots_of_work(i);#pragma omp ordered{

printf("%d %d\n", i, myval);}

}}

23/37

OpenMP diretiva: for

reduction(operator: var1,var2,...)

for(i = 1; i <= n; i++){sum = sum + a[i];

}

• sum é a variável de redução

• Não pode ser declarada como shared: threads sobrescreveriam o valorde sum

• Não pode ser declarado como private: variáveis privadas não persistemfora da região paralela

• Com a cláusula de redução, o compilador gera código de tal forma queuma condição de corrida é evitada

24/37

OpenMP diretiva: for

reduction(operator: var1,var2,...)

#pragma omp parallel for reduction(+:sum){

for(i=1; i<=n; i++){sum = sum + a[i];

}}

• operator pode ser:

+, *, -, &, ^, |, &&, ||

25/37

Quais loops são paralelizáveis?

Paralelizáveis

• Número de iterações conhecidas na entrada e não altera

• Cada iteração é independente de todas as outras

• Nenhuma dependência de dados

Não paralelizáveis

• Loops condicionais (muitos loops while)

• Iterações dependentes umas das outras

• Dependência de dados

26/37

OpenMP diretiva: section

• Permitem blocos separados de código serem executados em paralelo (ex.diversas subrotinas independentes)

• Não é escalável: o código fonte deve determinar a quantidade deparalelismo disponível

• Barreira implícita no final da construção das seções• Use a cláusula nowait para suprimir isso

#pragma omp sections{

#pragma omp section/* first section */#pragma omp section/* next section */

}

27/37

OpenMP diretiva: section

Exemplo

#include <omp.h>#define N 1000int main () {

int i;double a[N], b[N], c[N],

d[N];/*Some initializations*/for (i = 0; i < N; i++) {

a[i] = i * 1.5;b[i] = i + 22.35;

}

#pragma omp parallel \shared(a,b,c,d) private(i)

{#pragma omp sections nowait{

#pragma omp sectionfor (i=0; i < N; i++)

c[i] = a[i] + b[i];#pragma omp section

for (i=0; i < N; i++)d[i] = a[i] * b[i];

} /*end of sections*/} /*end of parallel section*/return 0;

}

28/37

Diretivas de sincronização

OpenMP: Sincronização

O que é necessário?

• É necessário sincronizar ações em variáveis compartilhadas

• É necessário assegurar a ordenação correta de leituras e escritas.

• É necessário proteger a atualização de variáveis compartilhadas (nãoatômicas por padrão).

29/37

OpenMP: Diretiva single

• Indica que um bloco de código deve ser executado apenas por um thread

• A primeira thread que alcançar a diretiva single irá executar o bloco

• Outros threads deve esperar até que o bloco seja executado• a menos que um nowait seja especificado

• Sintaxe:

#pragma omp single

30/37

OpenMP: Diretiva single

Exemplo

#pragma omp parallel{

#pragma omp forfor( int i=0; i<N; i++ )

a[i] = f0(i);#pragma omp singlex = f1(a);#pragma omp forfor(int i=0; i<N; i++ )

b[i] = x * f2(i);}

31/37

OpenMP: Diretiva master

• Indica que um bloco deve ser executado apenas pelo thread master(thread 0)

• Outros threads pulam o bloco e continuam a execução• Diferente da diretiva single neste aspecto

• Na maior parte das vezes utilizada para I/O

• Sintaxe:

#pragma omp master

32/37

OpenMP: Diretiva master

Exemplo

#pragma omp parallel{

#pragma omp forfor( int i=0; i<100; i++ )

a[i] = f0(i);#pragma omp masterx = f1(a);

}

33/37

OpenMP: Diretiva barrier

• Suponha que rodamos cada um desses dois loops em paralelo sobre i:

for (i=0; i < N; i++) a[i] = b[i] + c[i];

for (i=0; i < N; i++) d[i] = a[i] + b[i];

• Isso pode nos dar uma resposta errada (um dia). Por quê?

34/37

OpenMP: Diretiva barrier

• Suponha que rodamos cada um desses dois loops em paralelo sobre i:

for (i=0; i < N; i++) a[i] = b[i] + c[i];

for (i=0; i < N; i++) d[i] = a[i] + b[i];

• Isso pode nos dar uma resposta errada (um dia). Por quê?

34/37

OpenMP: Diretiva barrier

• Precisamos ter atualizado todos os a[] primeiro, antes de usar a[]

for (i=0; i < N; i++) a[i] = b[i] + c[i];

for (i=0; i < N; i++) d[i] = a[i] + b[i];

espera!barreira

• Todos os threads aguardam no ponto de barreira e só continuam quandotodos os threads o atingirem

35/37

OpenMP: Diretiva barrier

• Nenhuma thread pode prosseguir além da barreira até que todas asoutras threads chegarem até ela

• Note que há uma barreira implícita no final das diretivas for, sectionse single

• Sintaxe:

#pragma omp barrier

36/37

OpenMP: Diretiva barrier

Quando usar barreiras?

• Quando os dados são atualizados de forma assíncrona e a integridadedos dados está em risco

• Exemplo:• Entre partes do código que lê e grava a mesma seção da memória

• Infelizmente, barreiras tendem a ser “caras” computacionalmente

• Portanto, use-as com cuidado.

37/37

OpenMP: Diretiva nowait

• A cláusula nowait pode ser usada para suprimir as barreiras implícitasno final das diretivas for, sections e single

• Sintaxe:

#pragma omp for nowaitfor loop

• Igualmente para sections e single

38/37

OpenMP: Diretiva nowait

Exemplo: dois laços sem dependência

#pragma omp parallel{

#pragma omp for nowaitfor(int i=0; i<100; i++ )

a[i] = f(i);#pragma omp for nowaitfor(int i=0; i<100; i++ )

b[i] = sqrt(i)*2.0;}

39/37

OpenMP: Diretiva nowait

• Use com extremo cuidado

• É muito fácil remover uma barreira que é necessária

• Isso resulta no pior tipo de erro: comportamento não-determinístico daaplicação (às vezes o resultado é correto, às vezes não)

40/37

OpenMP: Diretiva critical

Região critica

• Se sum é uma variável compartilhada, este loop não pode ser executadoem paralelo

for (i=0; i < N; i++){ ... sum += a[i]; ...}

• Podemos usar uma região crítica para isso:

for (i=0; i < N; i++){ ... sum += a[i]; ...}

um de cada vez pode prosseguir

41/37

OpenMP: Diretiva critical

Região critica

• Útil para evitar uma condição de corrida ou para executar I/O

• Todos os threads executam o código, mas apenas um de cada vez

• Sintaxe:

#pragma omp critical

42/37

OpenMP: Diretiva atomic

Região critica

• Usada para proteger uma atualização única em uma variávelcompartilhada

• Uma forma leve e especial de uma seção crítica

• Aplica-se apenas a uma única sentença

• Sintaxe:

#pragma omp atomicstatement

Onde statement deve ter uma das seguintes forma:• x op = expr, x++, ++x, x– ou –x

e op pode ser: +, -, *, /, &, ˆ, «, »

• Alternativa ao uso da cláusula reduction (aplica-se aos mesmos tiposde expressões).

43/37

OpenMP: critical ou atomic

• Como regra simples, use a diretiva atomic sempre que possível: máximode otimização

• Se não for possível use a diretiva critical

44/37

Dúvidas?

44/37

Referências

• OpenMPhttp://www.openmp.org/

• OpenMPhttps://computing.llnl.gov/tutorials/openMP

• What is OpenMP?https://www.dartmouth.edu/~rc/classes/intro_openmp/

• Programação paralela e distribuída – OpenMPhttp://www.dcc.ufrj.br/~gabriel/progpar/OpenMP.pdf

45/37