Mudamos!!!

Atualmente estamos no endereço: www.assemblando.wordpress.com

OpenMP – Primeiro contato

Nada como um projeto novo para entusiasmar no aprendizado de tecnologias diferentes. Já fazia algum tempo que eu estava com vontade de começar a trabalhar com programação paralela, mas sem algo concreto para dar o impulso inicial estava complicado.

Relembrando o algorítimo de cálculo do valor de pi com base em uma série de somas:

soma = 0
para cada i, enquanto i < LIMITE:
   soma += 4/(i*4 + 1)
   soma -= 4/(i*4 + 3)
   i += 1
fim para

Resolvi implementar esse pequeno código para testar uma primeira implementação usando o OpenMP. Na minha pesquisa de paralelismo de simulação de dinâmica dos Fluidos (CFD) vou usar a linguagem Fortran, por ser uma linguagem diretamente voltado à cálculos matemáticos. Porém, com uma rápida pesquisa sobre OpenMP, descobri que ela é suportada também pela linguagem C++, uma velha amiga, que eu sempre gostei muito de usar. Pensei então “por que não estudar como usar o OpenMP em ambas?”. Então, na medida do possível, pretendo repetir todos os experimentos e exemplos nas duas linguagens.

Versões do OpenMP para C++ e Fortran

Como discutido no post anterior, a idéia do OpenMP é ser uma API que faz o gerenciamento dos Threads, distribuindo-os entre os núcleos/processadores disponíveis no sistema. Esse gerenciamento faz com que o programador não precise se preocupar com o sincronismo entre os threads, nem com a escalabilidade dos sistema.

Porém, o OpenMP é uma API, ou seja, uma ferramenta. E uma ferramenta só faz o que o programador a instrui fazer. Basicamente fica ao encargo do programador definir quais regiões serão paralelizadas, quais serão executadas de forma serial e quais são as variáveis compartilhadas e privadas de cada thread. O programador faz uso de algumas diretivas que são incluídas no código. Essas diretivas são avaliadas pelo pré-processador do OpenMP, e este faz o trabalho de dividir as tarefas entre os núcleos/processadores.

Tomemos como base a implementação em linguagem C do programa de cálculo do PI:

#include
#define NUM_PASSOS 20000000

int main(){
 double pi = 0;
 int i;

 for(i = 0; i < NUM_PASSOS; i++){
   pi += 4.0 / (4.0*i + 1.0);
   pi -= 4.0 / (4.0*i + 3.0);
 }
 printf("-> %f\n",pi);
return 0;
}

O mesmo exemplo pode ser visto em Fortran aqui

Compilando esse código com o GCC, sem nenhuma flag de otimização e executando o código em um pc com processador intel ia32 com GNU/Linux o programa precisou de quase 1 segundo para executar:

[john@vaio rascunhos]$ time ./a.out
-> 3.141593

real    0m0.906s
user    0m0.870s
sys     0m0.000s

Apenas para efeito de comparação, o código escrito em Fortran, compilado com o compilador ifort da intel, precisou de apenas 0.010s para executar. Um ganho de quase 90% que o Fortran proporciona, mas isso é assunto para um outro post.

O motivo pelo o qual esse código consumiu tanto tempo para ser executado está no número de repetições dentro do laço. A priori, em todo laço existe uma grande possibilidade de paralelizar o processo, dividindo as tarefas internas do laço entre os vário núcleos do meu sistema multiprocessado. Neste exemplo simples, percebam, a complexidade do meu algoritmo é linear, e relativa ao número de iterações. Em caso de complexidades mais críticas (quadrática, por exemplo), a paralelização do código traz benefícios ainda mais evidentes.

Devido a problemas estruturais (minha máquina não é multi-core) realizei o mesmo experimento com o auxílio do meu amigo Maluta em um Mac Mini que rendeu o seguinte resultado (não paralelizado, apenas para servir de base comparativa para o código paralelizado):

$ time ./a
-> 3.141593

real 0m0.686s
user 0m0.634s
sys 0m0.002s

Para paralelizar o código devemos indicar, por meio de diretivas, quais trechos o compilador deve utilizar a API OpenMP para dividir em threads. A primeira diretiva apresentada é a diretiva OMP PARALLEL. Essa diretiva indica qual parte do código vai ser dividida (fork). O final de um trecho paralelo é sinalizado com um OMP END PARALLEL:

...
... trecho serial
...
OMP PARALLEL
...
... trecho paralelizado
...
OMP END PARALLEL
...
... serial novamente

Desta maneira, tudo que está no trecho paralelizado vai ser executado simultaneamente por todos os threads do sistema. Devemos salientar que as diretivas sofrem leves variações do C++ para o Fortran. Essas diferenças serão notadas nos códigos, mas a semântica é a mesma para ambos os casos.

Outra diretiva, senão a mais usada, é a que indica que um loop deve ser paralelizado. A diretiva OMP PARALLEL FOR ou OMP DO são usadas para indicar que um laço deve ser dividido. Como o intuito desse blog não é ser um tutorial de OpenMP ou uma referência formal, mais detalhes sobre a sintaxe de cada diretiva pode ser encontrada no site oficial do projeteo OpenMP.

Paralelizando o laço principal (e único) do meu programa, temos o seguinte código:

#include
#include
#define NUM_PASSOS 20000000
<pre>int main(){
	double pi = 0;
	int i;
	#pragma omp parallel for
	for(i = 0; i < NUM_PASSOS; i++){
		pi += 4.0 / (4.0*i + 1.0);
		pi -= 4.0 / (4.0*i + 3.0);
	}
	printf("-> %f\n",pi);
return 0;
}

O equivalente em Fortran pode ser encontrado aqui.

Para compilar o código usando o GCC e o OpenMP, é necessário usar a flg -fopenmp:

gcc -fopenmp <source> [-o nome]

O resultado da execução deste código foi:

$ time ./b
-> 2.897633

real 0m0.544s
user 0m1.041s
sys 0m0.005s

Bem, o tempo de execução para o código linear foi de o.686s e no paralelo foi de 0.544s, ou seja, um ganho de aproximadamente 20%, porém, o meu resultado foi PI = 2.897633 ????????????? Alguma coisa não funcionou corretamente neste modelo de paralelismo.

A resposta é simples: quando o código foi paralelizada, cada parte da execução foi feita em um núcleo diferente. Assim, ao se fazer o join, as duas partes não são somadas, como deveriam. Em outras palavras, as variáveis Soma nesse caso estão separadas, e não compartilham o mesmo dado. O que devemos fazer nesse caso é forçar a união desses valores ao fim da execução dos threads. Para isso usamos mais uma diretiva, a diretiva REDUCTION:

#include
#include
#define NUM_PASSOS 20000000

int main(){
    double pi = 0;
    int i;
    #pragma omp parallel for reduction (+:pi)
    for(i = 0; i < NUM_PASSOS; i++){
        pi += 4.0 / (4.0*i + 1.0);
        pi -= 4.0 / (4.0*i + 3.0);
    }
    printf("-> %f\n",pi);
    return 0;
}

Novamente, o resultado em Fortran se encontra aqui.

Compilando e executando o código, temos a seguinte saída:

$ time ./a
-> 3.141593

real 0m0.433s
user 0m0.634s
sys 0m0.003s

Agora o nosso resultado confere com o valor de PI e o ganho em desempenho é de aproximadamente 36% comparado com o seu equivalente serial.

Com isso já temos base suficiente para brincar um tanto bom com paralelismo, e testar em outros algoritimos. Vale novamente ressaltar que esse blog não tem o intuito de ser um tutorial de OpenMP, estou apenas mostrandop por onde caminhei, e indicando onde encontrei as referências para estudo.

O que é e como funciona o Paralelismo

Sem delongas, na computação de alto desempenho o tempo é um fator determinante no resultado final de um trabalho. Em um campo onde a complexidade dos algoritmos tende a subir, e o tempo gasto para se executar um algoritmo engrandece junto à sua complexidade, distribuir as tarefas entre vários processadores e vários núcleos é uma maneira de se ganhar um tempo precioso na execução das tarefas.

O princípio básico é extremamente intuitivo: O seu código é dividido em partes que podem ser executadas separadamente, e cada uma dessas partes são enviadas à diferentes núcleos/processadores do seu sistema. Simples assim.

Como todo computólogo já está cansado de saber, a teoria pode até ser simples, mas na prática as coisas são um pouco diferente. Como o intuito desse blog é ser direto, vamos explicar por exemplos. Tomamos o código abaixo que tem como função calcular o valor de Π (pi). Esse cálculo pode ser feito baseado em uma série dada por :

Assim sendo, o algoritmo que resulta na soma pode ser descrito por:

soma = 0
para cada i, enquanto i < LIMITE:
   soma += 4/(i*4 + 1)
   soma -= 4/(i*4 + 3)
   i += 1
fim para

Ao final da sequência, a variável soma compreende o valor de pi.

Dentro desse loop, que deve ser repetido diversas vezes, são executadas duas principais funções, que geram a soma total do valor de pi. Imaginemos agora que fosse possível dividir essas duas somas, cada um para um núcleo de um processador:

Processador 1:
soma1 = 0
para cada i, enquanto i < LIMITE:
   soma1 += 4/(i*4 + 1)
   i += 1
fim para


Processador 2:
soma2 = 0
para cada i, enquanto i < LIMITE:
   soma2 -= 4/(i*4 + 3)
   i += 1
fim para

E ao final de ambos os processamentos, os valores das duas variáveis são adicionados, resultando em um único valor:

soma = soma1 + soma2

Com isso nosso algoritmo de soma foi dividido em dois, e cada um direcionado para um núcleo independente. Isso faz com que as duas somas de cada loop ocorram “simultâneamente”, ou seja, em paralelo. Com isso, o ganho hipotético em tempo de execução do nosso algoritmo paralelizado é de cerca de 2x.

Esse técnica de dividir e reagrupar (fork & join) é a base de como o OpenMP trabalha para paralelizar os códigos.

A filosofia de se utilizar fork/join consiste em um thread principal, que dispara as threads que vão trabalhar em paralelo. Ao final do trabalho dessas threads em paralelo, o fluxo é reunido (join) o processamento continua de forma serial. No nosso exemplo do cálculo do Pi, essa sequência poderia ser enxergada da forma:

thread principal-> dispara os dois loops em threads diferentes para o cálculo das somas[1,2]
fork-> cada thread calcula sua soma, simultaneamente
join-> os valores das somas são somados, resultando no valor final do meu cálculo

Para este exemplo simples, não fica muito complicado para o programador escrever duas rotinas de soma dentro de loops e disparar a execução dos threads, aguardar o resultado das somas e uní-los. Porém, temos alguns pequenos problemas:

• O código não é maleável em relação a quantidade de núcleos/processadores a serem utilizados.
• O programador deve se encarregar de resolver todos os problemas como concorrência, deadlock, join, etc.
• Não há como saber quantos núcleos eu tenho disponível.
• O código não fica transparente ao programador.
• Com o aumento do código, a manutenção da paralelismo torna-se impraticável.

Como visto, usar threads diretamente resolve o problema, mas está longe de ser uma solução prática e escalável para paralelismo de códigos.

Para resolver esse problema, são empregadas APIs para paralelizar o código. Essas APIs nada mais fazem do que resolver para o programador quais trechos serão divididos, em quantos threads serão divididos e encarregar de enviá-los para seus respectivos núcleos/processadores. A API OpenMP é uma das soluções para se trabalhar com paralelismo de código, e foi a minha escolha para uma primeira abordagem com o assunto.

No próximo tópico começarei a falar sobre o OpenMP, como instalar, qual versão usar e alguns exemplos de códigos.

Usando o Open MP

Resolvi criar um blog para acompanhar a minha evolução no estudo da tecnologia OpenMP para paralelização de aplicações que requerem alta demanda de processamento.

A referência a ser utilizada paara este trabalho, num primeiro instante, é a publicação

Using OpenMP: Portable Shared Memory Parallel Programming

Barbara Chapman

Gabriel Jost

Ruud van der Pas

O leitor desse blog não deve esperar muitos formalismos na forma com o qual o assunto vai ser abordado. Na verdade o intuito dessa pulicação é manter um registro do progresso no estudo do OpenMP e, claro, manter registro pra pesquisas rápidas futuras.

Sobre a frequência de atualização, pretendo atualizar o blog a cada passo significativo que for dado no meu estudo, respeitando o tempo hábil para conclusão das tarefas acadêmicas correlatas. Em suma, devo escrever aqui uma vêz por semana.

Então, vamos estudar!