Biblioteca OpenMP

Depois de estudar um pouco a biblioteca MPI e aprender suas principais funções, decidi investir um tempo na biblioteca OpenMP. Como eu já tinha comentado em outro post, a diferença principal entre as duas é que o MPI usa o paradigma de memória distribuída enquanto no OpenMP a memória é compartilhada.

Dispor de memória compartilhada pode facilitar bastante o trabalho. Um exemplo é a divisão balanceada das iterações entre os processadores e com trabalho totalmente distribuído (no referido post a distribuição era feita através de um processador mestre). Com o MPI chegamos a uma solução com comunicação não-bloqueante, mas que executava um número de iterações maior do que o previsto.

Com o OpenMP podemos manter um pool central de iterações. Conforme cada processador termine de executar seu bloco de iterações, ele adquire exclusividade sobre esse pool, atualiza o número de iterações restantes e libera o recurso.

Fiz a simulação de uma iteração usando a função sleep com tempos aleatórios.

Geração de números aleatórios

Em geral, um requerimento para reproducibilidade de experimentos em que se usam números aleatórios é que toda vez que executamos o código, a sequência gerada seja a mesma. Para isso a biblioteca padrão stdlib oferece a função srand, que recebe como parâmetro uma semente. Se a semente for fixada, a sequência terá essa propriedade.

Quando estamos trabalhando com paralelização de código, uma propriedade desejável é que a união das sequências geradas em paralelo correspondam à sequência que seria gerada sequencialmente. Por exemplo, se com um processo geramos 6 números aleatórios entre 1 e 10, {6, 6, 8, 9, 7, 9}, então essa mesma sequência deveria ser gerada para 2 processos. Poderia ser algo como {6, 8, 7} e {6, 9, 9} (na verdade depende da ordem em que cada processador invocou o gerador – o importante é que a união das sequências seja igual à sequência original).

Com isso, os resultados obtidos serão essencialmente os mesmos entre a versão sequencial e a versão paralela, restando comparar apenas o tempo de execução.

O problema do gerador da biblioteca padrão C é que não temos acesso ao estado do gerador. Assim, não dá para garantir que quando cada processador gerar um número aleatório, o gerador esteja com o mesmo estado em todos os processadores. A biblioteca Boost possui uma implementação de geradores de números aleatórios, com a vantagem de que o gerador é um objeto ao qual temos acesso.

Assim, podemos colocá-lo como variável compartilhada entre os processadores e colocar a geração do número aleatório dentro de uma região crítica do Open MP, que é uma região onde apenas um processador pode executar por vez (quem tentar acessar fica bloqueado até que o processador na região crítica termine). Com isso garantimos que o estado do gerador está sempre atualizado para todos os processadores. Essa abordagem pode ser conferida na seção de código abaixo.

Resultados computacionais

Rodei o código abaixo em uma máquina quad-core e obtive os seguintes tempos de execução (medidos com a função time do linux), em função do número de threads utilizadas:

Tempos de execução

Observamos que a aceleração é quase linear. A terceira coluna da tabela mostra um tempo “normalizado” crescente com o aumento do número de processadores, mas isso se deve ao trecho não paralelizado do código. De forma geral, a economia de tempo foi bastante satisfatória. Porém, trata-se de um exemplo muito simples. Pretendo ainda aplicar essa estratégia em uma implementação mais complexa para ver os ganhos obtidos.

Código

#include <stdio.h>
#include <iostream>
#include <algorithm>

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>
#include <omp.h>

/* A otenção do número aleatório deve ser protegido */
int random(boost::mt19937 &gen, int lb, int ub){
    int val;
    #pragma omp critical
    {
        boost::uniform_int< > dist(lb, ub);
        boost::variate_generator<boost::mt19937&, 
                                 boost::uniform_int<> > r(gen, dist);
        val = r();
    }
    return val;
}
int iteration(boost::mt19937 &gen){
    int rtime = random(gen, 1, 10);
    sleep(rtime);
}
/* A atualização das iterações restantes deve ser 
 * uma area protegida */
bool get_iteration_block(int *iter){
    bool stat;
    #pragma omp critical
    {
        if (*iter <= 0){
            stat = false;
        }
        else {
            *iter = *iter - 1;
            stat = true;
        }
    }
    return stat;
}
int main (){

    boost::mt19937 gen;
    gen.seed(0);

    int iter = 20;  // numero inicial de iteracoes
    #pragma omp parallel shared(iter, gen) num_threads(2) 
    {
        while (get_iteration_block(&iter))
            iteration(gen);         
    }
    return 0;
}

Para compilar código OpenMP no linux podemos usar o gcc com a flag -fopenmp

g++ -fopenmp <arquivo.cpp>

No código acima, o gerador mt19937 é baseado no algoritmo gerador de números pseudo-aleatórios Mersenne Twister.

2 respostas a Biblioteca OpenMP

  1. Por que não tenta OpenCL ou CUDA em GPU? Pra que 4 Cores se você pode ter 512? :p

    Dá uma olhada em nosso seminário: http://wp.me/pEMSX-6w

    e na apresentação: http://gpubrasil.files.wordpress.com/2011/04/introducao-a-computacao-de-alto-desempenho-utilizando-gpu1.pdf

    Abraço Kunigas!


    Thársis

  2. kunigami diz:

    Thársis,

    Estava mesmo pensando em estudar CUDA mais pra frente. Valeu pelos links!

%d bloggers like this: