Paralelização de Aplicações com OpenMP

Introdução

O OpenMP é uma norma/API para programação paralela em sistemas de memória partilhada para as linguagens de programação C, C++ e Fortran, desenvolvida e mantida pelo OpenMP Architecture Review Board. Disponibiliza uma alternativa simples e portável a soluções de mais baixo nível como POSIX Threads, e é suportado por vários compiladores como o GCC ou ICC, e deverá chegar em breve ao Clang/LLVM.

O OpenMP distingue-se de outras soluções para suporte a paralelismo em memória partilhada pelo seu nível de abstracção, na medida em que o essencial das suas funcionalidades é obtido através de um conjunto de directivas do compilador que especificam de forma declarativa como é que diferentes partes do código podem ser executadas em paralelo. Adicionalmente, um compilador que não suporte OpenMP pode simplesmente ignorar estas directivas, continuando a aplicação a funcionar correctamente (embora de forma sequencial). Contudo, aplicações mais complexas podem também necessitar de chamadas a funções de mais baixo nível (disponibilizados pela API do OpenMP), e que tornam a compilação da aplicação dependente do OpenMP.

Neste artigo pretende-se mostrar como podem explorar paralelismo em memória partilhada recorrendo a um pequeno conjunto de funcionalidades do OpenMP, de modo a tirarem partido dos processadores com múltiplos núcleos disponíveis na generalidade dos PCs hoje em dia. Utilizar-se-á o C com linguagem de suporte neste artigo. Os programas serão compilados usando o GCC 4.7.2.

Conceitos Básicos

O OpenMP usa threads para obter paralelismo. Todas as threads usam o mesmo espaço de endereçamento de memória, sendo que os dados podem ser partilhados por todas as threads, ou privados de cada thread (cada thread tem uma cópia da variável à qual só ela acede). De notar que o OpenMP utiliza um modelo de memória de consistência relaxada, na medida em que cada threads pode ter uma cópia local temporária (por exemplo, em registos ou cache) cujo valor não necessita de ser constantemente consistente com o valor global visto por todas as outras threads (vários mecanismos são disponibilizados para que o programador possa forçar a consistência de memória em determinados pontos da aplicação).

É usado um modelo fork & join, em que temos inicialmente uma única thread (a master, ou principal), e depois temos pontos da aplicação em que um grupo de threads é criado (fork, no início de uma região paralela), e pontos da aplicação onde as threads são terminadas voltando a haver apenas uma thread (join, no final de uma região paralela), como mostrado na Figura 1. Ou seja, as regiões paralelas identificam os blocos de código onde o trabalho a ser executado é atribuído a várias threads. A norma do OpenMP prevê a possibilidade de termos regiões paralelas aninhadas, em que cada thread de um grupo de threads dá origem a um novo grupo de threads. No entanto, nem todas as implementações suportam regiões paralelas (e neste caso, cada região paralela aninhada será apenas executada por uma thread).

OpenMP: modelo fork & join — Figura 1: modelo *fork & join* do *OpenMP*

O acesso às funcionalidades do OpenMP é feito através de três tipos de mecanismos:

directivas de compilador: permitem criar regiões paralelas, distribuir o trabalho a ser realizado pelas várias threads, controlar o acesso a dados (especificando se são privados ou partilhados, por exemplo), assim como gerir a sincronização entre threads;
funções: permitem definir o número de threads a usar, obter informações sobre quantas threads estão a correr ou qual o identificador da thread em que estamos, determinar se se está numa zona paralela, gerir locks, aceder a funções de tempo (relógio), entre outras coisas;
variáveis de ambiente: permitem também definir o número de threads a usar, controlar o escalonamento, definir o máximo aninhamento de regiões paralelas, etc.

Nas próximas secções veremos como alguns alguns destes mecanismos podem ser usados, sendo dado especial foco às directivas de compilador.

Mecanismos do OpenMP

Nesta secção veremos como podemos usar as funcionalidades do OpenMP. O exemplos disponibilizados podem ser compilados usando a opção de compilação -fopenmp do GCC (caso estejam a usar outro compilador, devem recorrer à documentação do mesmo para determinar como activar as funcionalidades do OpenMP).

Criação de Threads

Na base do OpenMP está a directiva omp parallel. Esta directiva cria uma região paralela, i.e., indica que um determinado bloco de código será executada por várias threads (caso o OpenMP esteja activo). Como exemplo, considere o seguinte código.

int main(void) {
  #pragma omp parallel
  {
    printf("Hello world!\n");
  }
  return 0;
}

Caso execute este código (compilado com a opção do OpenMP activa), deverá ver a mensagem Hello world! aparecer no ecrã tantas vezes quanto o número de núcleos do CPU da sua máquina. Tendo em conta que não há sincronização entre as threads, é possível que o texto impresso pelas várias threads apareça misturado.

Aquilo que é executado em paralelo é delimitado pelo bloco que se segue à directiva omp parallel. Por exemplo, no seguinte código, temos mensagens que são impressas por todas as threads, e mensagens que são impressas apenas pela thread principal.

int main(void) {
  #pragma omp parallel
  {
    printf("Hello world!\n"); // todas as threads
    printf("All threads.\n"); // todas as threads
  }
  printf("Only master.\n"); // apenas thread principal
  return 0;
}

De notar que a mensagem Only master., que apenas é impressa pela thread principal, deverá ser sempre a última mensagem a ser mostrada, na medida em há uma barreira implícita no final do bloco paralelo (a generalidade dos construtores têm barreiras implícitas no final, sendo que alguns mecanismos suportam a opção nowait para evitar estas barreiras; consulte a documentação para mais detalhes), i.e., a thread principal não avança enquanto ainda houver threads a executar a região paralela.

Existem diversas formas de controlar explicitamente o número de threads que são criadas por uma região paralela. Por exemplo, podem simplesmente acrescentar a opção num_threads(3) no final do omp parallel (ficando com #pragma omp parallel num_threads(3)) para indicar que querem 3 threads.

Distribuição de Trabalho

O exemplo anterior não é particularmente útil na maior parte dos casos, na medida em que todas as threads executam o mesmo trabalho de forma redundante. Em exemplos reais, normalmente o que queremos é que cada thread execute uma parte diferente do trabalho. O OpenMP disponibiliza diversos mecanismos para tal.

Uma forma simples de distribuir trabalho é indicar que diferentes partes da região paralela podem ser executadas em paralelo, mas cada parte só deverá ser executada por uma thread. Para obter este comportamento podemos usar a directiva omp sections. Considere o seguinte bloco de código.

#pragma omp parallel
{
  #pragma omp sections
  {
    #pragma omp section
    {
      task11();  // apenas uma thread
      task12();  // apenas uma thread
    }
    #pragma omp section
    task2();  // apenas uma thread
    #pragma omp section
    task3();  // apenas uma thread
  }
  taskAll();  // todas as threads
}

Neste bloco de código teremos uma thread a executar task11 e task12, outra thread a executar task2, outra thread a executar task3, e todas as threads a executar taskAll (visto que esta função já se encontra fora do bloco omp sections). Ou seja, a directiva omp sections define um conjunto de blocos de código em que cada um deles deve ser executado por apenas uma thread. Cada um dos blocos desse conjunto é identificado pela directiva omp section. Se houver mais blocos do que threads, uma mesma thread irá executar mais do que uma secção (realça-se, contudo, que a divisão de trabalho entre as threads nem sempre é equilibrada, podendo uma thread ficar com a maioria das tarefas). No final do bloco omp sections existe mais uma vez uma barreira implícita aplicada a todas as threads.

Uma outra forma muito útil de distribuir trabalho entre threads é dividindo as iterações de um ciclo for. Para tal temos a directiva omp for, usada no próximo exemplo.

double nums[SIZE];
// ...
// inicializar nums
// ...
#pragma omp parallel for
for(int i = 0; i < SIZE; i++) {
  nums[i] = sqrt(nums[i]);
}

Este código computa a raiz quadrada dos elementos de um array. As iterações não têm dependências, pelo que podemos ter as várias iterações a serem executados em paralelo. É precisamente isso que a directiva omp for está a fazer. De referir que estamos a juntar as directivas omp parallel e omp for numa só, na medida em que ambas se aplicam ao mesmo bloco de código.

Mas nem sempre as iterações do ciclo são completamente independentes, o que pode requerer a utilização de funcionalidades mais complexas do OpenMP. Por exemplo, suponhamos que se pretende somar todos os elementos de um array. Tal pode ser feito de forma sequencial com o seguinte código.

double sum = 0;
double nums[SIZE];
// ...
// inicializar nums
// ...
for(int i = 0; i < SIZE; i++) {
  sum += nums[i];
}

Todas as iterações escrevem na variável sum, pelo que no caso de executarmos várias iterações em paralelo, teremos um race condition, que pode levar a resultados incorrectos. Existem várias maneiras de contornar este problema, nomeadamente através da utilização de diferentes variáveis para cada thread, como veremos mais adiante. Contudo, o OpenMP disponibiliza um mecanismo de alto nível para este tipo de situações, em que é feita uma operação de redução de um array (i.e., os elementos do array são agrupados num só elemento, neste caso, a soma de todos os elementos). O mecanismo em causa é o reduction(<op>:<var>). Este mecanismo torna a variável <var> privada a cada thread dentro da região paralela (na generalidade dos casos, variáveis declaradas fora do bloco são partilhadas por omissão), e no final realiza uma junção de todas as cópias privadas da variável aplicando a operação <op>. Para o nosso caso, queremos que a variável sum seja privada a cada thread, e queremos que no final todas as cópias privadas sejam somadas. Assim, a versão paralela pode ser obtida como exemplificado no seguinte código.

double sum = 0;
double nums[SIZE];
// ...
// inicializar nums
// ...
#pragma omp parallel for reduction(+:sum)
for(int i = 0; i < SIZE; i++) {
  sum += nums[i];
}

Existem formas mais rudimentares de distribuir o trabalho por threads, usando a API do OpenMP. Pegando no exemplo anterior, a sua versão paralela pode ser também obtida através do código que se segue.

// variável que irá a
double sum = 0;
double nums[SIZE];
// ...
// inicializar nums
// ...
// criação de uma região paralela
#pragma omp parallel
{
  // declarada dentro da região paralela, logo privada à thread
  double sumt = 0;
  // obter o id desta thread
  int id = omp_get_thread_num();
  // obter o número de threads
  int nthreads = omp_get_num_threads();
  for(int i = id; i < 100; i += nthreads) {
    sumt += nums[i];
  }
  // região crítica; apenas uma thread a executa em cada momento
  #pragma omp critical
  sum += sumt;
}

Neste exemplo temos novamente todas as threads a executar a região paralela. Aqui a distribuição do trabalho é feita recorrendo à API do OpenMP. Obtendo o identificador de cada thread, e o número de threads a serem executados, podemos usar as estruturas condicionais para que cada thread execute trabalho diferente. No caso, for(int i = id; i < 100; i += nthreads) faz com que a thread id some os valores dos índices i tal que i % nthreads == id (sendo nthreads o número de threads a executar). Desta forma, temos as várias posições do array divididas, de forma cíclica, por todas as threads. A variável sumt está declarada dentro da região paralela, pelo que a mesma é local a cada thread. No final, todas as threads adicionam a sua soma à variável sum, que contém a soma total. Mais uma vez é necessário cuidado com as race conditions, visto que todas as threads escrevem na variável sum. A directiva omp critical é usada para evitar problemas. Esta garante que apenas uma thread está a executar aquele bloco da região paralela num determinado momento. De notar também que o acesso às funções da API do OpenMP requer a utilização do header omp.h.

Penso que todos os leitores irão concordar que a utilização do omp for e do reduction permite um código muito mais simples, e é a versão que se recomenda que seja utilizada. Por norma, apenas se recomenda fazer este tipo de divisão de trabalho manual quando não é possível fazê-lo usando apenas as directivas do compilador (o que pode ocorrer em casos mais complexos).

Sincronização de Threads

No exemplo anterior já vimos como podemos sincronizar a execução de threads através do omp critical. Existem mais alguns mecanismos que podem ser usados para sincronização:

omp atomic: é uma versão mais básica (mas também mais eficiente) do omp critical, que permite tornar as actualizações de variáveis atómicas (no exemplo anterior seria mais eficiente utilizar o omp atomic do que o omp critical);
omp master: indica que um bloco de código só será executado pela thread principal (de referir que, ao contrário da generalidade dos mecanismos do OpenMP, não existe uma barreira implícita no final destes blocos);
omp barrier: permite definir barreiras explícitas, onde as threads de uma região bloqueiam até que todas elas tenham atingido aquele ponto de execução;
omp flush: é usado para garantir que todas as threads têm uma visão consistente da memória naquele ponto (como indicado anteriormente, o OpenMP usa um modelo de memória de consistência relaxada);
omp ordered: permite definir que um determinado bloco dentro de um ciclo que está a correr em paralelo deverá ser executado na mesma ordem em que seria executado se estivesse a correr de forma sequencial.

Adicionalmente, podemos ainda sincronizar a execução de threads através das funções de gestão de locks disponibilizados pela API do OpenMP, que incluem o omp_init_lock (inicialização de um lock), omp_set_lock (adquire um lock, esperando até que tal seja possível), omp_unset_lock (liberta um lock), omp_test_lock (tenta adquirir um lock, mas não bloqueia caso não seja possível), e omp_destroy_lock (destrói o lock). Por exemplo, o omp critical usado no exemplo anterior podia ser substituído pela utilização de locks, como mostrado no próximo exemplo.

double sum = 0;
double nums[SIZE];
// ...
// inicializar nums
// ...
omp_lock_t sumlock;
omp_init_lock(&sumlock);
#pragma omp parallel
{
  // declarada dentro da região paralela, logo privada à thread
  double sumt = 0;
  // obter o id desta thread
  int id = omp_get_thread_num();
  // obter o número de threads
  int nthreads = omp_get_num_threads();
  for(int i = id; i < SIZE; i += nthreads) {
    sumt += nums[i];
  }
  omp_set_lock(&sumlock);
  sum += sumt;
  omp_unset_lock(&sumlock);
}
omp_destroy_lock(&sumlock);

Mais uma vez, sempre que possível, aconselha-se a utilização dos mecanismos abstractos disponibilizadas OpenMP (critical, atomic, barrier, etc.) em vez da utilização das funções de mais baixo nível disponibilizados pela API.

Para terminar, convém referir que os mecanismos de sincronização devem ser evitados, pois os mesmos implicam overheads, muitas vezes ao ponto impedirem que a paralelização produza qualquer ganho de desempenho. Em geral é recomendável que se tente reorganizar o algoritmo de modo a evitar a necessidade destes mecanismos.

Tarefas Paralelas

Uma outra forma de definir blocos de código que podem ser executados em paralelo (por uma thread cada) é usando a directiva omp task. Esta directiva permite definir tarefas cuja a execução pode ser feita de forma assíncrona. A directiva de sincronização omp taskwait deve depois ser usada para bloquear a execução da aplicação até que a tarefa tenha sido concluída (quando necessário). Por exemplo, o seguinte código implementa o cálculo de um número de Fibonacci em paralelo.

int fibonacci(int n) {
  int fib1, fib2, result;
  if(n == 0 || n == 1) {
    result = n;
  }
  else {
    // cria uma tarefa assíncrona
    #pragma omp task shared(fib1)
    fib1 = fibonacci(n - 1);
    // cria uma tarefa assíncrona
    #pragma omp task shared(fib2)
    fib2 = fibonacci(n - 2);
    // espera pelas tarefas assíncronas lançadas
    #pragma omp taskwait
    result = fib1 + fib2;
  }
  return result;
}

Neste código é indicado que as chamadas recursivas à função fibonacci podem ser executadas de forma assíncrona. Antes de precisarmos de utilizar o resultados dessas chamadas recursivas, utilizamos o omp taskwait para esperarmos pela conclusão das tarefas.

Neste exemplo podemos também ver mais uma vez a utilização de mecanismos de controlo de escopo/partilha (já anteriormente tínhamos visto que o reduction podiam ser usado para tornar variáveis privadas às threads). Ao contrário da generalidade dos construtores, no omp task as variáveis declaradas anteriormente são privadas à task por omissão. Assim, se precisarmos de aceder ao seu valor mais tarde, como no caso das variáveis fib1 e fib2, é necessário tornar as variáveis partilhadas. Tal é feito através das opções shared(fib1) e shared(fib2).

Conclusão

Neste artigo procurou-se mostrar como podem paralelizar aplicações de forma simples usando o OpenMP. Contudo, este disponibiliza apenas uma introdução ao tema, sendo que as funcionalidades do OpenMP vão muito para além das aqui abordadas, nomeadamente no que diz respeito ao escalonamento de tarefas, ou às formas de controlo de escopo/partilha de variáveis. Sugere-se ao leitor interessado que consulte a lista de referências disponibilizada no final caso deseje aprofundar os seus conhecimentos.

Neste artigo também não houve grande preocupação com o desempenho da aplicação. Tirar partido da paralelização requer cuidados adicionais no que diz respeito à performance, nomeadamente para se fazer um bom uso da hierarquia de memória (por exemplo, para se evitarem problemas de false sharing), para se conseguir um bom balanceamento de carga, ou para evitar overheads excessivos com sincronização (como referido anteriormente).

Apesar do OpenMP ser destinado a sistemas memória partilhada, pode ser usado em conjunto com soluções de memória distribuída (como o MPI). Para além das linguagens suportadas oficialmente (C, C++ e Fortran), existem solução similares para outras linguagens como o Java, por exemplo.

Referências

Website do OpenMP: http://www.openmp.org/
Especificação do OpenMP: http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf
Tutorial de OpenMP: https://computing.llnl.gov/tutorials/openMP/
Tutorial prático de OpenMP: http://openmp.org/mp-documents/omp-hands-on-SC08.pdf

Revista PROGRAMAR