Que tal aprender um pouco sobre programação paralela?

O desafio deste mês é sobre um framework de programação paralela chamado OpenMP.

Mas o que é programação paralela? E como funciona o OpenMP?

PROGRAMAÇÃO PARALELA

Ao invés de aumentar a frequência da CPU, os sistemas computacionais tem evoluído no sentido de utilizar mais de um processador no mesmo sistema para melhorar sua performance. Hoje por exemplo é comum os SoCs (System-on-Chip) utilizados em sistemas embarcados possuirem múltiplos núcleos (cores) de CPU.

E não adianta nada ter oito núcleos de CPU se a sua aplicação tem uma única linha de execução. Torna-se então necessário utilizar eficientemente os múltiplos núcleos de processamento existentes para melhorar a eficiência e a performance do sistema.

Existem diversas formas de paralelizar a execução de uma aplicação.

Uma delas é dividindo a aplicação em múltiplos processos. Neste caso, é necessário utilizar um mecanismo eficiente de comunicação entre os processos (memória compartilhada, mensagens, sockets, etc.) de forma que não tenhamos sobrecarga na comunicação entre os processos, e consequentemente prejudicando o paralelismo da aplicação.

Outra forma de paralelizar o processamento é dividindo a aplicação em múltiplas threads. Neste caso, é muito mais fácil implementar a comunicação entre as threads já que elas compartilham o espaço de endereçamento de memória. Um seja, uma variável global pode ser acessada diretamente pelas múltiplas threads da aplicação. Aqui o desafio está em implementar eficientemente e corretamente o acesso aos dados compartilhados entre as threads, por exemplo protegendo as seções críticas de acesso concorrente.

Agora, é claro que o desenvolvedor tem todo o trabalho de decidir o que e como paralelizar, implementar corretamente as threads e gerenciar a comunicação e a concorrência entre elas.

E se pudéssemos indicar ao compilador quais trechos do código podem ser paralelizados, e deixássemos que ele fizesse isso por nós? É exatamente esse o papel do OpenMP!

OPENMP

O OpenMP (Open Multi Processing) é um framework genérico de programação paralela suportado por diversos compiladores, incluindo o GCC.

Na prática, é uma API de programação paralela para escrever aplicações multithread, com suporte às linguagens C, C++ e Fortran. Através de diretivas de compilação e algumas rotinas de biblioteca, o desenvolvedor indica ao compilador o quê e como paralelizar!

Por exemplo, veja abaixo um programa de multiplicação de matrizes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <stdio.h>
#include <stdlib.h>
 
#define ORDER 1024
#define AVAL 3.0
#define BVAL 5.0
#define TOL  0.001
 
int main(int argc, char **argv)
{
    int Ndim, Pdim, Mdim;   /* A[N][P], B[P][M], C[N][M] */
    double *A, *B, *C, tmp;
    int i, j, k;
 
    Ndim = Pdim = Mdim = ORDER;
 
    A = (double *) malloc(Ndim * Pdim * sizeof(double));
    B = (double *) malloc(Pdim * Mdim * sizeof(double));
    C = (double *) malloc(Ndim * Mdim * sizeof(double));
 
    /* initialize A[N][P] = AVAL */
    for (i = 0; i < Ndim; i++)
        for (j = 0; j < Pdim; j++)
            *(A+(i*Ndim+j)) = AVAL;
 
    /* initialize B[P][M] = BVAL */
    for (i = 0; i < Pdim; i++)
        for (j = 0; j < Mdim; j++)
            *(B+(i*Pdim+j)) = BVAL;
 
    /* initialize C[N][M] = 0.0 */
    for (i = 0; i < Ndim; i++)
        for (j = 0; j < Mdim; j++)
            *(C+(i*Ndim+j)) = 0.0;
 
    /* multiply the matrices */
    for (i = 0; i < Ndim; i++){
        for (j = 0; j < Mdim; j++){
            tmp = 0.0;
            for(k = 0; k < Pdim; k++){
                /* C(i,j) = sum(A(i,k) * B(k,j)) */
                tmp += (*(A+(i*Ndim+k))) * (*(B+(k*Pdim+j)));
            }
            *(C+(i*Ndim+j)) = tmp;
        }
    }
 
    printf("Done!\n");
    return 0;
}

Este programa leva em torno de 14 segundos para rodar na minha máquina (Intel Core i7 com 8 núcleos de CPU):

$ gcc matrix.c -o matrix
$ time ./matrix
Done!
 
real 0m14.296s
user 0m14.270s
sys 0m0.012s

Colocando uma única diretiva de compilação do OpenMP (linha 36) nós paralelizamos a execução do loop que faz o cálculo das matrizes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <stdio.h>
#include <stdlib.h>
#define ORDER 1024
#define AVAL 3.0
#define BVAL 5.0
#define TOL  0.001
 
int main(int argc, char **argv)
{
    int Ndim, Pdim, Mdim;   /* A[N][P], B[P][M], C[N][M] */
    double *A, *B, *C, tmp;
    int i, j, k;
 
    Ndim = Pdim = Mdim = ORDER;
 
    A = (double *) malloc(Ndim * Pdim * sizeof(double));
    B = (double *) malloc(Pdim * Mdim * sizeof(double));
    C = (double *) malloc(Ndim * Mdim * sizeof(double));
 
    /* initialize A[N][P] = AVAL */
    for (i = 0; i < Ndim; i++)
        for (j = 0; j < Pdim; j++)
            *(A+(i*Ndim+j)) = AVAL;
 
    /* initialize B[P][M] = BVAL */
    for (i = 0; i < Pdim; i++)
        for (j = 0; j < Mdim; j++)
            *(B+(i*Pdim+j)) = BVAL;
 
    /* initialize C[N][M] = 0.0 */
    for (i = 0; i < Ndim; i++)
        for (j = 0; j < Mdim; j++)
            *(C+(i*Ndim+j)) = 0.0;
 
    /* multiply the matrices */
    #pragma omp parallel for private(tmp, i, j, k) shared(Ndim, Mdim, Pdim)
    for (i = 0; i < Ndim; i++){
        for (j = 0; j < Mdim; j++){
            tmp = 0.0;
            for(k = 0;k < Pdim; k++){
                /* C(i,j) = sum(A(i,k) * B(k,j)) */
                tmp += (*(A+(i*Ndim+k))) * (*(B+(k*Pdim+j)));
            }
            *(C+(i*Ndim+j)) = tmp;
        }
    }
 
    printf("Done!\n");
    return 0;
}

E o tempo de execução da aplicação cai para 2,1 segundos! Fantástico!

$ gcc matrixmp.c -o matrixmp -fopenmp
$ time ./matrixmp
Done!
 
real 0m2.168s
user 0m16.448s
sys 0m0.012s

AGORA O DESAFIO

O código a seguir utiliza a aproximação do matemático francês François Viète para calcular o número Pi:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main(int argc, char **argv) 
{
	unsigned long int n;
	double r, pi = 1;
	int i, j;
 
        if (argc != 2) {
		printf("Usage: <calc_pi> <number of iterations>\n");
		exit (1);
	}
 
	n = strtol(argv[1], NULL, 10);
	if (!n) {
		printf("ERROR: Invalid number of iterations!\n");
		exit (2);
	}
 
	for (i = 0; i < n; i++) {
 
		r = 2;
		for (j = i; j ; j--)
			r = 2 + sqrt(r);
		r = sqrt(r);
 
		pi *= (r / 2);
	}  
 
	pi = 2 / pi;
 
	printf("Aproximated value of PI = %1.16f\n", pi);
 
	return 0;
}

Executando a aplicação com 8.000 iterações em uma Raspberry Pi 3, o tempo total de processamento é de aproximadamente 10,64 segundos:

# time pi 8000
Aproximated value of PI = 3.1415926535897940
real 0m 10.64s
user 0m 10.64s
sys 0m 0.00s

Seu objetivo é utilizar o OpenMP para paralelizar a execução da aplicação e diminuir o tempo total de processamento. Existem algoritmos mais eficientes que o utilizado neste exercício, mas neste desafio não será permitido alterar o algoritmo em si. A idéia é realmente utilizar apenas as rotinas e diretivas de compilação do OpenMP para paralelizar o processamento da aplicação.

Os testes serão feitos em uma Raspberry Pi 3 com um sistema customizado criado pelo Buildroot, e a aplicação será executada com 8000 iterações, conforme exemplo acima.

Atualização 1: Se você não tiver uma Raspberry Pi 3 não tem problema. Você pode desenvolver e testar no seu PC mesmo, desde que ele seja multicore e de que a aplicação fique portável para que depois eu possa compilar e testar na Raspberry Pi 3.

Todas as respostas que, de alguma forma, paralelizarem o código com o OpenMP levarão os 5 pontos. Aqueles que conseguirem paralelizar e levar o menor tempo de execução levarão os 10 pontos e o concorrerão ao prêmio, que neste desafio será uma Beaglebone White!

Envie sua solução do desafio para o e-mail contato@sergioprado.org. Aceitarei submissões até o dia 24/02 e o resultado será divulgado até o dia 03/03.

Qualquer problema ou dúvida é só escrever nos comentários desta publicação.

E aí, vai topar este desafio? Instancie uma thread e comece a estudar! :)

Um abraço,

Sergio Prado