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.3 Condição de corrida 2.5 Sincronização

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

2.4 Laços e reduções

2.4.1 Laços for

OpenMP permite paralelizar laços de forma simples e eficiente. A diretiva omp for pode ser usada para dividir o trabalho entre os threads disponíveis. Por exemplo, consideremos o seguinte código que implementa um método para a multiplicação de uma matriz $A$ $m\times n$ por um vetor de $n$ elementos.

Código 5: matVet.hpp

⬇

1Eigen::VectorXd matVet(Eigen::MatrixXd &a, Eigen::VectorXd &x)

3 int m = a.rows();

4 int n = a.cols();

6 Eigen::VectorXd y(m);

8 // Multiplicação de matriz por vetor

9 #pragma omp parallel for

10 for (int i = 0; i < m; i++)

11 {

12 y(i) = 0.0;

13 for (int j = 0; j < n; j++)

14 {

15 y(i) += a(i,j) * x(j);

16 }

17 }

19 return y;

20}

Na linha 9 do código, a diretiva omp parallel for indica que o laço for deve ser paralelizado. O compilador divide o laço entre os threads disponíveis. Cada thread computa uma parte dos produtos internos entre as linhas da matriz e o vetor.

Divisão do laço

A distribuição do laço entre as threads pode ser feita de diferentes formas e é definida pela cláusula schedule(type,[n]), que aceita as seguintes opções:

•

static, [n]: o laço é dividido em pedaços iguais de n itens sequênciais. Todos os pedaços são distribuídos de forma sequêncial entre os threads. Ou seja, o primeiro pedaço vai para o primeiro thread, o segundo pedaço vai para o segundo thread e assim por diante. Quando todos os threads tiverem recebido um pedaço, o processo recomeça com o primeiro thread. O padrão é n = ceiling(num_of_iterations/num_of_threads).
•

dynamic, [n]: o laço é dividido em pedaços de n itens sequênciais. Cada thread recebe um pedaço até que todos os pedaços sejam distribuídos. No entanto, a distribuição dos pedaços entre os threads é feita de forma dinâmica, ou seja, cada thread pode pegar um novo pedaço assim que terminar o anterior. O padrão é n = 1.
•

guided, [n]: o laço é dividido em pedaços de n itens sequênciais. Cada thread recebe um pedaço até que todos os pedaços sejam distribuídos. No entanto, a distribuição dos pedaços entre os threads é feita de forma guiada, ou seja, cada thread pode pegar um novo pedaço assim que terminar o anterior. No entanto, o tamanho do próximo pedaço a ser pego diminui a cada iteração. Por padrão, o primeiro pedaço tem tamanho n = ceiling(num_of_iterations/num_of_threads) e os próximos têm camanho ceiling(num_of_iterations_left/num_of_threads).
•

auto: a divisão entre as threads é delegada ao compilar e ao sistema.

2.4.2 Reduções

Uma redução é uma operação que combina os resultados de várias threads em um único resultado. Por exemplo, a soma dos elementos de um vetor é uma operação de redução. A diretiva omp reduction pode ser usada para especificar uma operação de redução em um laço.

Por exemplo, o seguinte código implementa um método para computar o produto interno entre dois vetores de $n$ elementos.

Código 6: prodInt.hpp

⬇

1double dot(Eigen::VectorXd &a, Eigen::VectorXd &b)

3 double result = 0.0;

4 int n = a.size();

6 // Multiplicação de vetor por vetor

7 #pragma omp parallel for reduction(+:result)

8 for (int i = 0; i < n; i++)

9 {

10 result += a(i) * b(i);

11 }

13 return result;

14}

Na linha 9 do código, a diretiva omp parallel for reduction(+:result) indica que o laço for deve ser paralelizado e que a variável result deve ser reduzida. A operação de redução é especificada entre parênteses. Neste caso, a operação de redução é a soma. A variável result é inicializada em cada thread e, ao final do laço, os resultados parciais são somados para obter o resultado final. Reduções com as operações *, /, - também são suportadas.

2.4.3 Exercícios

E. 2.4.1.

Teste a eficiência do Código 5 para diferentes tamanhos de matrizes. O que ocorre quando $m$ aumenta? E quando $n$ aumenta?

E. 2.4.2.

Teste a eficiência do Código LABEL:cap_mp:cod:matVec para diferentes tipos de distribuição de laços pela cláusula schedule. Qual é a mais eficiente em seu computador? Porquê?

E. 2.4.3.

Desenvolva um método com OpenMP/C++ para computar a multiplicação matriz-vetor por colunas. Use a diretiva omp parallel for para paralelizar o laço mais aproriado. Teste diferentes distribuições de iterações com a cláusula schedule e compare os resultados.

E. 2.4.4.

Desenvolva um método com OpenMP/C++ para computar a multiplicação matriz-matriz:

a)

por linhas;
b)

por colunas.

Em cada caso, use a diretiva omp parallel for para paralelizar o laço mais aproriado. Teste diferentes distribuições de iterações com a cláusula schedule e compare os resultados.

E. 2.4.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 do trapézio com um número arbitrário de subintervalos $n$ . Use a diretiva omp parallel for para paralelizar o laço de redução.

E. 2.4.6.

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$ . Use a diretiva omp parallel for para paralelizar os laços de redução.

E. 2.4.7.

Desenvolva um método com OpenMP/C++ para computar o produtório

P=\prod_{i=1}^{n}f(i)

(2.3)

para um função de termos $f$ arbitária. Aplique para computar o fatorial de um número inteiro $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.