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.