Política de uso de dados

Ao navegar por este site, você concorda com a política de uso de dados.

Política de uso de dados

Ao navegar por este site, você concorda com a política de uso de dados.

| | | |

Computação Paralela com C++

2 Multiprocessamento (MP)2.2 Escalabilidade e eficiência 2.4 Laços e reduções

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

2.3 Condição de corrida

Um condição de corrida (race condition) ocorre quando multiplas threads tentam acessar a mesma variável ao mesmo tempo. Isso pode levar a resultados inesperados, pois o valor da variável pode ser alterado por um thread enquanto outro thread está tentando lê-la ou escrevê-la.

Por exemplo, considere o seguinte código para computar o produto interno entre dois vetores de $n$ elementos randômicos. No código, a tarefa é distribuida para duas threads, em que cada uma computa o produto interno parcial de um pedaço dos vetores. O resultado é acumulado na variável dot. Por fim, o código computa o erro entre o valor computado e o valor esperado. O código é o seguinte.

Código 3: ProdInt_v0.cpp

⬇

1#include <iostream>

2#include <cmath>

3// Matrix computation library

4#include <eigen3/Eigen/Eigen>

5// OpenMP API

6#include <omp.h>

8int main()

10 // ** Variáveis compartilhadas

12 // vetores

13 int n = 100;

14 std::cout << "n = " << n << std::endl;

16 Eigen::VectorXd u =

17 Eigen::VectorXd::Random(n);

18 Eigen::VectorXd v =

19 Eigen::VectorXd::Random(n);

20 Eigen::VectorXd w(n);

22 double dot = 0.0;

24 // região paralela

25 #pragma omp parallel num_threads(2)

26 {

27 // ** Variáveis privadas

29 int nthreads = omp_get_num_threads();

30 int thread_id = omp_get_thread_num();

32 // thread chunk

33 int chunk_size = n / nthreads;

34 int start = thread_id * chunk_size;

35 int end = (thread_id + 1) * chunk_size;

36 if (thread_id == nthreads - 1) {

37 end = n;

38 }

40 for (int i = start; i < end; i++) {

41 dot = dot + u(i) * v(i);

42 }

43 }

45 std::cout << "Erro: " << fabs(dot - u.dot(v)) << std::endl;

47 return 0;

48}

Cada vez que rodamos o código podemos obter um valor de erro diferente. Verifique! Mas, porquê há um erro? A explicação está relacionado ao fato da variável dot ser compartilhada entre os threads. Variáveis declaradas foram de regiões paralelas, são variáveis compartilhadas em as threads. Já variáveis declaradas dentro de regiões paralelas são variáveis privadas, ou seja, cada thread tem sua própria cópia da variável.

O erro ocorre porque há uma condição de corrida na linha 41. A variável dot é compartilhada entre os threads. Na linha 41, enquanto um thread está lendo o valor de dot, outro thread pode estar escrevendo um novo valor. Ou seja, a variável dot não é protegida contra acessos simultâneos. Isso leva a uma condição de corrida, onde o resultado final depende da ordem em que os threads acessam a variável.

2.3.1 Região crítica

Para evitar uma condição de corrida, precisamos proteger as operações de escrita e leitura de variáveis compartilhadas. Podemos fazer isso usando a diretiva omp critical. A diretiva omp critical define uma região crítica, onde apenas um thread pode acessar a variável compartilhada de cada vez.

Uma versão corrigida do Código 3 é dada a seguir. Verifique!

Código 4: ProdInt_v1.cpp

⬇

1#include <iostream>

2#include <cmath>

3// Matrix computation library

4#include <eigen3/Eigen/Eigen>

5// OpenMP API

6#include <omp.h>

8int main()

10 // Variáveis compartilhadas

12 // vetores

13 int n = 100;

14 std::cout << "n = " << n << std::endl;

16 Eigen::VectorXd u =

17 Eigen::VectorXd::Random(n);

18 Eigen::VectorXd v =

19 Eigen::VectorXd::Random(n);

20 Eigen::VectorXd w(n);

22 double dot = 0.0;

24 // região paralela

25 #pragma omp parallel num_threads(2)

26 {

27 int nthreads = omp_get_num_threads();

28 int thread_id = omp_get_thread_num();

30 // thread chunk

31 int chunk_size = n / nthreads;

32 int start = thread_id * chunk_size;

33 int end = (thread_id + 1) * chunk_size;

34 if (thread_id == nthreads - 1) {

35 end = n;

36 }

38 double local_dot = 0.0;

39 for (int i = start; i < end; i++) {

40 local_dot = local_dot + u(i) * v(i);

41 }

43 // região crítica

44 #pragma omp critical

45 {

46 dot = dot + local_dot;

47 }

48 }

50 std::cout << "Error: " << fabs(dot - u.dot(v)) << std::endl;

52 return 0;

53}

2.3.2 Exercícios

E. 2.3.1.

Localize e explique a condição de corrida do seguinte código.

⬇

1double soma = 0.0;

2#pragma omp parrallel

4 soma += omp_get_thread_num();

É possível fazer essa computação em paralelo?

Resposta 0.

Não há como paralelizar esta computação.

E. 2.3.2.

O seguinte código é paralelamente ineficiente. Proponha uma nova versão mais eficiente.

⬇

1int n = 10;

2Eigen::VectorXd v = Eigen::VectorXd::Random(n);

3double product = 1.0;

4#pragma omp parallel

6 int nthreads = omp_get_num_threads();

7 int thread_id = omp_get_thread_num();

8 for (int i = thread_id; i < n; i+=nthreads) {

9 #pragma omp critical

10 {

11 product *= v(i);

12 }

13 }

14}

Resposta 0.

⬇

1int n = 10;

2Eigen::VectorXd v = Eigen::VectorXd::Random(n);

3double product = 1.0;

4#pragma omp parallel

6 int nthreads = omp_get_num_threads();

7 int thread_id = omp_get_thread_num();

9 double local_product = 1.0;

10 for (int i = thread_id; i < n; i+=nthreads) {

11 local_product *= v(i);

12 }

14 #pragma omp critical

15 {

16 product *= local_product;

17 }

18}

E. 2.3.3.

Desenvolva um método com OpenMP/C++ para computar a norma $l_{2}$ de um vetor arbitrário.

Resposta 0.

⬇

1#include <cmath>

2#include <eigen3/Eigen/Eigen>

3#include <omp.h>

5double norma(Eigen::VectorXd &v)

7 int n = v.size();

8 double norm = 0.0;

9 #pragma omp parallel

10 {

11 int nthreads = omp_get_num_threads();

12 int thread_id = omp_get_thread_num();

13 // thread chunk

14 int chunk_size = n / nthreads;

15 int start = thread_id * chunk_size;

16 int end = (thread_id + 1) * chunk_size;

17 if (thread_id == nthreads - 1) {

18 end = n;

19 }

21 double local_norm = 0.0;

22 for (int i = start; i < end; i++) {

23 local_norm += v(i) * v(i);

24 }

26 // região crítica

27 #pragma omp critical

28 {include <cmath>

29 #include <eigen3/Eigen/Eigen>

30 #include <omp.h>

32 double norma(Eigen::VectorXd &v)

33 {

34 int n = v.size();

35 double norm = 0.0;

36 #pragma omp parallel

37 {

38 int nthreads = omp_get_num_threads();

39 int thread_id = omp_get_thread_num();

40 // thread chunk

41 int chunk_size = n / nthreads;

42 int start = thread_id * chunk_size;

43 int end = (thread_id + 1) * chunk_size;

44 if (thread_id == nthreads - 1) {

45 end = n;

46 }

48 double local_norm = 0.0;

49 for (int i = start; i < end; i++) {

50 local_norm += v(i) * v(i);

51 }

53 // região crítica

54 #pragma omp critical

55 {

56 norm += local_norm;

57 }

58 }

60 return sqrt(norm);

61 }

62 norm += local_norm;

63 }

64 }

66 return sqrt(norm);

67}

E. 2.3.4.

Desenvolva um método com OpenMP/C++ para computar a integral de uma função $y=f(x)$ em um intervalo $[a,b]$ pela regra composta do trapézio com um número arbitrário de subintervalos $n$ .

E. 2.3.5.

Desenvolva um método com OpenMP/C++ para computar a integral de uma função $y=f(x)$ em um intervalo $[a,b]$ pela regra composta de Simpson¹¹endnote: ¹Thomas Simpson, 1710 - 1761, matemático britânico. Fonte: Wikipédia: Thomas Simpson. com um número arbitrário de subintervalos $n$ .

Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Computação Paralela com C++

2 Multiprocessamento (MP)2.2 Escalabilidade e eficiência 2.4 Laços e reduções

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

2.3 Condição de corrida

Código 3: ProdInt_v0.cpp

⬇

1#include <iostream>

2#include <cmath>

3// Matrix computation library

4#include <eigen3/Eigen/Eigen>

5// OpenMP API

6#include <omp.h>

8int main()

10 // ** Variáveis compartilhadas

12 // vetores

13 int n = 100;

14 std::cout << "n = " << n << std::endl;

16 Eigen::VectorXd u =

17 Eigen::VectorXd::Random(n);

18 Eigen::VectorXd v =

19 Eigen::VectorXd::Random(n);

20 Eigen::VectorXd w(n);

22 double dot = 0.0;

24 // região paralela

25 #pragma omp parallel num_threads(2)

26 {

27 // ** Variáveis privadas

29 int nthreads = omp_get_num_threads();

30 int thread_id = omp_get_thread_num();

32 // thread chunk

33 int chunk_size = n / nthreads;

34 int start = thread_id * chunk_size;

35 int end = (thread_id + 1) * chunk_size;

36 if (thread_id == nthreads - 1) {

37 end = n;

38 }

40 for (int i = start; i < end; i++) {

41 dot = dot + u(i) * v(i);

42 }

43 }

45 std::cout << "Erro: " << fabs(dot - u.dot(v)) << std::endl;

47 return 0;

48}

2.3.1 Região crítica

Uma versão corrigida do Código 3 é dada a seguir. Verifique!

Código 4: ProdInt_v1.cpp

⬇

1#include <iostream>

2#include <cmath>

3// Matrix computation library

4#include <eigen3/Eigen/Eigen>

5// OpenMP API

6#include <omp.h>

8int main()

10 // Variáveis compartilhadas

12 // vetores

13 int n = 100;

14 std::cout << "n = " << n << std::endl;

16 Eigen::VectorXd u =

17 Eigen::VectorXd::Random(n);

18 Eigen::VectorXd v =

19 Eigen::VectorXd::Random(n);

20 Eigen::VectorXd w(n);

22 double dot = 0.0;

24 // região paralela

25 #pragma omp parallel num_threads(2)

26 {

27 int nthreads = omp_get_num_threads();

28 int thread_id = omp_get_thread_num();

30 // thread chunk

31 int chunk_size = n / nthreads;

32 int start = thread_id * chunk_size;

33 int end = (thread_id + 1) * chunk_size;

34 if (thread_id == nthreads - 1) {

35 end = n;

36 }

38 double local_dot = 0.0;

39 for (int i = start; i < end; i++) {

40 local_dot = local_dot + u(i) * v(i);

41 }

43 // região crítica

44 #pragma omp critical

45 {

46 dot = dot + local_dot;

47 }

48 }

50 std::cout << "Error: " << fabs(dot - u.dot(v)) << std::endl;

52 return 0;

53}

2.3.2 Exercícios

E. 2.3.1.

Localize e explique a condição de corrida do seguinte código.

⬇

1double soma = 0.0;

2#pragma omp parrallel

4 soma += omp_get_thread_num();

É possível fazer essa computação em paralelo?

Resposta 0.

Não há como paralelizar esta computação.

E. 2.3.2.

O seguinte código é paralelamente ineficiente. Proponha uma nova versão mais eficiente.

⬇

1int n = 10;

2Eigen::VectorXd v = Eigen::VectorXd::Random(n);

3double product = 1.0;

4#pragma omp parallel

6 int nthreads = omp_get_num_threads();

7 int thread_id = omp_get_thread_num();

8 for (int i = thread_id; i < n; i+=nthreads) {

9 #pragma omp critical

10 {

11 product *= v(i);

12 }

13 }

14}

Resposta 0.

⬇

1int n = 10;

2Eigen::VectorXd v = Eigen::VectorXd::Random(n);

3double product = 1.0;

4#pragma omp parallel

6 int nthreads = omp_get_num_threads();

7 int thread_id = omp_get_thread_num();

9 double local_product = 1.0;

10 for (int i = thread_id; i < n; i+=nthreads) {

11 local_product *= v(i);

12 }

14 #pragma omp critical

15 {

16 product *= local_product;

17 }

18}

E. 2.3.3.

Desenvolva um método com OpenMP/C++ para computar a norma $l_{2}$ de um vetor arbitrário.

Resposta 0.

⬇

1#include <cmath>

2#include <eigen3/Eigen/Eigen>

3#include <omp.h>

5double norma(Eigen::VectorXd &v)

7 int n = v.size();

8 double norm = 0.0;

9 #pragma omp parallel

10 {

11 int nthreads = omp_get_num_threads();

12 int thread_id = omp_get_thread_num();

13 // thread chunk

14 int chunk_size = n / nthreads;

15 int start = thread_id * chunk_size;

16 int end = (thread_id + 1) * chunk_size;

17 if (thread_id == nthreads - 1) {

18 end = n;

19 }

21 double local_norm = 0.0;

22 for (int i = start; i < end; i++) {

23 local_norm += v(i) * v(i);

24 }

26 // região crítica

27 #pragma omp critical

28 {include <cmath>

29 #include <eigen3/Eigen/Eigen>

30 #include <omp.h>

32 double norma(Eigen::VectorXd &v)

33 {

34 int n = v.size();

35 double norm = 0.0;

36 #pragma omp parallel

37 {

38 int nthreads = omp_get_num_threads();

39 int thread_id = omp_get_thread_num();

40 // thread chunk

41 int chunk_size = n / nthreads;

42 int start = thread_id * chunk_size;

43 int end = (thread_id + 1) * chunk_size;

44 if (thread_id == nthreads - 1) {

45 end = n;

46 }

48 double local_norm = 0.0;

49 for (int i = start; i < end; i++) {

50 local_norm += v(i) * v(i);

51 }

53 // região crítica

54 #pragma omp critical

55 {

56 norm += local_norm;

57 }

58 }

60 return sqrt(norm);

61 }

62 norm += local_norm;

63 }

64 }

66 return sqrt(norm);

67}

E. 2.3.4.

Desenvolva um método com OpenMP/C++ para computar a integral de uma função $y=f(x)$ em um intervalo $[a,b]$ pela regra composta do trapézio com um número arbitrário de subintervalos $n$ .

E. 2.3.5.

Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Pedro H A Konzen

| | | |