Programação Paralela em Arquiteturas Multi-Core/Ambientes de programação e bibliotecas

Introdução

Os microcomputadores pessoais têm, hoje em dia, incorporados a eles o poder de processamento das máquinas de grande porte. Dentre as técnicas de melhoria do poder computacional destas máquinas tem-se as técnicas de pipeline, as de integração de circuitos, o uso de hierarquias de memórias e, mais recentemente, a utilização de múltiplos processadores, trabalhando sobre o mesmo programa ou executando programas de diferentes usuários ao mesmo tempo.

A conversão das aplicações codificadas em linguagens seqüenciais para algum paradigma de processamento concorrente é uma tarefa que, muitas vezes, necessita da intervenção humana. Ao mesmo tempo em que se buscam formas de converter aplicações codificadas usando paradigmas seqüenciais para paradigmas que suportem o conceito de paralelismo, são criados novos paradigmas paralelos de forma que novas aplicações possam automaticamente ser codificadas e executadas em máquinas com mais de um processador.

Existem várias linguagens de programação com suporte para programação paralela que vêm sendo utilizadas em máquinas com mais de um processador. São acrescentadas as linguagens de programação (C, C++ e Fortran) algumas bibliotecas que permitem a execução concorrente de processos e, principalmente, a troca de mensagens (dados) e a sincronização entre os processos em execução no ambiente (PVM, MPL, CPS e etc).

Uma outra biblioteca na qual o capítulo está baseado é a Intel Threading Building Blocks (Intel TBB) que é uma biblioteca C++ que simplifica o uso de threads, fazendo com que o desenvolvedor programe em nível de tarefas e deixando para a biblioteca a preocupação de, por exemplo, tomar decisões como: quantas threads devem-se usar e o tamanho da cache. O TBB se compromete com a independência de compilador, processador e SO.

TBB

Visão geral

O Intel Threading Building Blocks (TBB) oferece um rico e completa abordagem para expressar paralelismo em programas C++. Essa é uma biblioteca que ajuda você a tomar vantagens do desempenho de processadores multi-núcleos sem ter experiência em threads. TBB não é apenas uma biblioteca de substituição de threads, ela representa em alto-nível o paralelismo baseado em tarefas que abstrai detalhes e mecanismos de threads sobre desempenho e escalabilidade.

Porque usar?

Para desenvolvedores o benefícios claros de TBB são:

TBB reduz significativamente o número de linhas requeridas no código para desenvolver aplicações multithreads.
TBB reduz a complexidade de programação para o desenvolvimento de aplicações multithreads (esconde muitos detalhes no gerenciamento de threads).
O gerenciador de tarefas do TBB analisa automaticamente no sistema a execução do software está executando, escolhendo números ótimos de threads, executa o balanceamento de carga espalhando o trabalho entre os demais processadores.
Como resultado, a aplicação com threads utilizando TBB escala automaticamente com uso total da computação dos núcleos disponíveis mesmo que no futuro esse número de núcleos aumente.

Tendo alguma experiência no desenvolvimento multithreads em software C++ (novas aplicações ou conversão de aplicativos legados que operam sistemas com multiprocessadores/ multi-núcleos), pode-se experimentar o TBB e será notada a diferença rapidamente em sua facilidade de uso.

Exemplos de uso

Desenvolvendo aplicações utilizando parallel_for

Suponha que você quer aplicar uma função Foo para cada elemento de um arranjo, e isso é seguro processar cada elemento concorrentemente. Abaixo veremo um código sequencia para fazer isso:

void SerialApplyFoo (float a[], size_t n ){
      for( size_t i=0;i<n; ++i )
         Foo(a[i]);
}

A interação aqui é do tipo size_t, e vai de 0 a n-1. A função template tbb::parallel_for sai da interação no pedaço(chunk), e executa cada pedaço em uma thread separada. O primeiro passo na paralelização desse loop é converter o corpo do loop em uma forma que opere em um pedaço. Essa forma é em uma função STL (STL-style), chamado o corpo, no qual o operator() processa um dos pedaços(chunk). O seguinte codigo declara o coropo. O codigo extra requirido para o TBB é mostrado em azul.

#include "tbb/blocked_range.h"
class ApplyFoo{
     float *const my_a;
public:
     void operator()( const blocked_range<size_t>& r) const{
          float *a = my_a;
          for( size_t i=r.begin(); i!=r.end(); ++i )
                Foo(a[i]);
     }
     ApplyFoo( float a[] ):
          my_a(a)
     {}
};

Note o argumento operator(). A blocked_range<T> é uma classe template provida pela biblioteca. Ela descreve uma iteração de uma dimensão sobre o tipo T. A classe parallel_for trabalha com outros tipos de iteração também. A biblioteca provê blocked_range2d para espaços bidimensionais. Voce pode definir seu próprio espaço como explicado adiante.

Uma instância de ApplyFoo precisa de um campo membro que o lembre de todas as variaveis que foram definidas fora do loop original mas que está sendo usada dentro dele. Usualmente, o construtor para o corpo do objeto irá iniciar esse campo, através de parallel_for que não se importa em como o corpo do objeto foi criado. A função template parallel_for requer que o corpo do objeto tenha uma copia do construtor, do qual é invocado para criar uma copia separada (ou copias_ de cada thread ativa. Isso também invoca um destrutor para destruir essas copias. Em muitos casos, a copia do construtor gerada implicitamente e o destrutor trabalham corretamente. Caso contrario, isso é sempre o caso (como usualmente em C++) que você defina ambos para serem consistentes.

Devido ao fatodo do corpo do objeto ser copiado, seu operator() nao deve modifica-lo. Por outro lado a modificação deve ou não se tornar visivel para a thread que é invocou o parallel_for, dependendo se operator() esta atuando sobre o original ou sobre uma copia. Como lembrança disso, parallel_for requer que o corpo do objeto operator() seja declarado const.

O exemplo operator() carrega my_a em uma variavel local a. Pois não é necessario que tenha duas razões para fazer isso no exemplo:

Style: Faz com que o corpo do laço (loop) se pareça com o original.
Performance: Algumas vezes colocando frequentemente o valor acessado nas variaveis locals ajuda o compilador a otimizar o loop ainda mais, porque as variaveis locais são frequentemente mais faceis para o compilador rastrear.

Uma vez que voce tenha um corpo de loop escrito como um corpo de objeto, invoque a função template parallel_for, como seque:

#include "tbb/parallel_for.h"
void ParallelApplyFoo( float a[], size_t n) {
    parallel_for(blocked_range<size_t>(0,n,IdealGrainSize), ApplyFoo(a) );
}

O blocked_range construido aqui representa a iteração de entrada do espaço de 0 a n-1, do qual o parallel_for divide em subespaços para cada processador. A forma geral para o construtor blocked_range<T>(begin,end,grainsize). O T especifica o valor tipo. O argumento begin e end especifica o espaco de iteração STL-style como o intervalo (begin,end).

Grainsize

O terceiro argumento, grainsize, especifica o número de iterações para um "tamanho razoavel" de pedaços (chunk) a ser tratado pelo processador. Se a iteração tem mais que grainsize iterações, parallel_for se divide em subintervalos separados que são agendados(scheduled) separadamente.

O grainsize habilita você a evitar excessivo overhead paralelo. Um laço paralelo resulta em um custo de overhead para cada subintervalo. Se os subintervalos são muito pequenos, o overhead pode ser excessivo para o trabalho. Pela especificação de um grainsize, você pode limitar o overhead. Efetivamente o Grainsize valerá o menor valor possivel para a paralelização.

A figura acima ilustra o impacto do overhead mostrando o trabalho efetivo como a area cinza dentro do quadrado marrom. Ambos os casos A e B tera a mesma area cinza. O caso A mostrara como é pequeno o grainsize para um alto overhead relativamente. No caso B mostra o quão grande é o grainsize reduzido nessa proporção, no custo da redução do potencial paralelismo.

O overhead como uma fração de trabalho efetivo depende do grainsize, não em numero de grão. Considere essa relação e não em número total de iterações ou número de processadores quando estiver configurando o grainsize.

Uma regra é que as iterações de grainsize em operator() deve ter no mínimo 10.000-100.000 instruções a serem computadas. Na duvida, faça o seguinte:

Defina o maior parametro grainsize possivel. Definindo-o para 10.000 é usualmente uma bom ponto de partida, porque cada iteração do loop normalmente requer um minimo de instruções por iteração.

Execute seu algoritmo em um processador.

Comece reduzindo a metade o parametro grainsize e veja o quanto o algoritmo perde de desempenho quando esse valor diminui.

Um redução de desempenho de 5-10% quando estiver executando com uma única thread é uma boa margem na maioria dos casos. A devolução de definição de um grainsize é de 10.000 e o laço tem 20.000 iterações, o parallel_for distribui o laço entre somente dois processadores, sempre que tive mais disponíveis. Embora, se voce não tiver certeza, é bom "chutar" um valor um pouco mais alto do que mais baixo, porque valores muito baixos atingem o mesmo desempenho do serial.

Largura de Banda

Para um suficientemente simples função Foo, o exemplo pode não mostrar aumento de desempenho (speedup) significativo quando escrito como laço paralelo. A cause disso pode ser largura de banda insuficiente do sistema entre o processador e a memória. Nesse caso, você deve ter que repensar em seu algoritmo para ter um melhor vantagem de cache. Reestruturando melhor utilize os beneficios da cache para o programa paralelo bem como o programa serial.

Usando um Particionador

Uma caracteristica do TBB é suportar particionadores. Um particionado é um objeto que guia a escolher um tamanho para os pedaços. Duas classes de particionadores que você pode escolher são simple_partitioner e auto_partitioner.

Um simple_partitioner implementa um politica padrão. Esse padrão para o parallel_for, parallel_reduce. Um simples particionador tem as seguintes vantagens:

É conceitualmente simples.
Tem garantia que os pedaços (chunks) não são maiores que grainsize iterações, dos quais deixam você assumir um tamanho para o intervalo máximo para o operator(). Isso garante que algumas vezes operator() será habilitado para usar um arranjo de tamanho fixo temporario no lugar de um arranjo temporario dinamico.
Escolhe o melhor para uma máquina específica.

O retorno de um simple_partitioner é que isso requer estimatizar o próprio grainsize e um ótimo grainsize pode ser particular para uma máquina.

O auto_partitioner prover uma alternativa que heuristicamente escolhe o tamanho do pedaço(chunk) quando você não o definir. A heuristica se limita a overheads enquanto ainda prover uma ampla oportunidade de balanceamento de carga.

O código abaixo mostra como usar um auto_partitioner no lugar de um grainsize. Note que o parametro grainsize é omitido quando construir um blocked_range e que um auto_partitioner objeto é passado como um terceiro argumento para o parallel_for.

#include "tbb/parallel_for.h"
void ParallelApplyFoo( float a[], size_t n) {
    parallel_for(blocked_range<size_t>(0,n), ApplyFoo(a), 
                                                                     auto_partitioner() );
}

Como com muitas heuristicas, tem se situações onde auto_partitioner pode não encontrar o valor ótimo e o simple_partitioner deveria produzir o melhor desempenho. Recomendamos usar auto_partitioner ao menos que você tenha tempo para experimentar e melhor o grainsize para as máquinas de interesse.

Desenvolvendo aplicações utilizando parallel_reduce

Um loop pode se reduzir a:

float SerialSumFoo( float a[], size_t n ){
    float sum=0;
    for( size_t i=0; i!=n; ++i )
          sum+= Foo(a[i]);
    return sum;
}

Se a iteração for independente, você pode paralelizar esse loop usando uma classe template chamada parallel_reduce como, por exemplo:

class SumFoo{
       float *my_a;
 public:
       float sum;
       void operator() ( const blocked_range<size_t> &r ){
               float *a = my_a;
               for ( size_t i=r.begin(); i!=r.end(); ++i)
                       sum += Foo(a[i]);
       }
       SumFoo( SumFoo& x, split ) : my_a(x.my_a), sum(0) {}
       void join( const SumFoo& y ) {sum+=y.sum;}
       SumFoo(Float a[]) : my_a(a), sum(0){}
 };

Note a diferença com a classe ApplyFoo. Primeiro, operator() não é const. Isso porque SumFoo::sum deve ser atualizado. Segundo, porque SumFoo tem um splitting constructor e um método join que deve estar presente para parallel_reduce ser executado. O splitting construtor toma como argumento a referencia original do objeto, e o argumento do tipo split, do qual é definido como biblioteca. O argumento split distingue o spliting construtor de sua copia.

Quando a thread que esta sendo executada esta disponível, como decidido pela tarefa agenda (task scheduler), parallel_reduce diminui o trabalho de invocar o construtor splitting de criar a subtarefa do processador. Quando a tarefa se completa, parallel_reduce usa o método join para acumular o resultado da subtarefa. O seguinte grafo mostra a seqüência separa-reduz (split-join):

Grafo da Sequência split-join

Um aro da figura indica a ordem no tempo. Note que o construtor splitting pode executar concorrentemente enquanto o objeto x está sendo usado para a primeira metade da redução. Embora, todas as ações do construtor splitting, que cria y, devam ser feitas por uma thread segura (safe) ao seu respectivo x. Então, se o construtor splitting necessita aumentar a referencia do contador compartilhado, deverá ser usado um incrementador atômico.

float ParallelSumFoo( const float a[], size_t n ) {
   SumFoo sf(a);
   parallel_reduce (blocked_range<size_t> (0,n,IdealGrainSize), sf);
   return sf.sum;
}

Como com parallel_for, você deve prover um razoável grainsize, com um número de iterações o suficiente para no mínimo de 10.000 iterações. Se você não esta certo desse tamanho, o melhor a se fazer é "chutar" um grainsize grande. Você pode também usar um particionador para permitir executar a biblioteca que te guie a uma faixa de intervalo (chunking).

parallel_reduce generaliza qualquer operação associativa. Em geral, o construtor splitting faz duas coisas:

Copia as informações de somente leitura necessária para executar o corpo do loop.
Inicializa as variáveis de redução para identificar os elementos das operações.

O método join deve fazer sua intercalação (merge) correspondente. Você pode fazer mais que uma redução ao mesmo tempo: você pode obter o min e max com um único parallel_reduce.

Desenvolvendo aplicações utilizando parallel_while

Para alguns loops, o fim do espaço de iteração não é conhecido enquanto estiver sendo iterado, ou o coropo do loop pode adicionar mais iterações antes de finalizado. Você pode tratar com ambas as situações usando a classe template tbb::parallel_while.

Uma lista encadeada é um exemplo de um espaço de iteração que não é conhecido enquanto iterado. Em programação paralela, é usual preferir o uso de arranjos dinâmicos no lugar de listas encadeadas porque o acesso aos itens em uma lista encadeada é feito de forma serial. Mas se você esta limitado ao uso de lista encadeada e os itens pode sem seguramente processados em paralelo sendo que o processamento de cada item tome no mínimo de poucos milhares de instruções, você pode usar parallel_while nessa situação onde a forma serial é como se segue:

void SerialApplyFooToList ( Item *root ){
    for( Item* ptr=root; ptr!=NULL; ptr=ptr->next)
       Foo(pointer->data);
}

Se o Foo tomar no mínimo poucos milhares de instruções, você pode obter um parallel speedup por converter o loop a usar parallel_while. Diferente dos templates, descritos anteriormente, parallel_while é uma class, não uma função, e requer dois objetos definidos por usuário. O primeiro objeto define uma stream de itens. O objeto pode ter um método pop_if_present tais que quando bool b=pop_if_present(v) é invocado, o valor do conjunto v na próxima iteração se há um e retorna verdadeiro (true). Se há mais iterações é retornado falso (false). Abaixo, com fonte azul, indicaremos as mudanças no código requerido pelo TBB. Algumas das demais linhas, fonte preta, mostra a parte do código original a princípio, mas que foi alterada na forma para mudar o fluxo(stream).

  class ItemStream {
        Item* my_ptr;
  public:
     bool pop_if_present(Item*& item) {
      if(my_ptr){
              item=my_ptr;
              my_ptr=my_ptr->next;
              return true;
              }else{
              	return false;
              }
      };
   Item( Item* root) : my_ptr(root){}
   }

O segundo objeto define o corpo do loop, e deve definir o operador() const e um tipo membro argument_type. Isso é similar a uma função C++ do cabecalho padrão <functional>, exceto que isso deve ser const.

 class ApplyFoo{ 
 public:
         void operator() (Item* item) const{
          Foo(item->data);
}
          typedef Item* argument_type;
};

Dado uma stream e o corpo da classe, o novo código segue abaixo:

 void ParallelApplyFooToList( Item *root ){
        parallel_while<ApplyFoo> w;
        ItemStream stream;
        ApplyFoo body;
        w.run( stream, body );
}

O método pop_if_present não tem de ser thread safe para um dado fluxo (stream), porque parallel_while nunca o chama concorrentemente para o mesmo stream. Note que essa conveniência faz parallel_while não ser escalavel, porque fetching é serializado. Mas em muitas situações, você ainda pode obter speedup fazendo isso sequencialmente.

Há uma segunda maneira que é o parallel_while que pode ser trabalhado, e assim, torná-lo escalável. O corpo de um parallel_while w - se a referencia dada para w quando isso for construído, pode ser adicionado para mais trabalho chamando w.add(item), onde o item é de um tipo Body::argument_type. Por exemplo, talvez processando um nodo na arvore seja um pré-requisito para processar seus descendentes. Com parallel_while, depois de processar um nodo você pode usar parallel_while::add para adicionar nodos descendentes. A instancia de parallel_while nao termina até que todos os itens tenham sido processados.

Outros ambientes de programação e bibliotecas

PVM:O PVM foi especialmente desenhado para interligar recursos computacionais numa rede, fornecendo ao utilizador uma plataforma paralela para executar aplicações, independentemente da localização, da quantidade ou das diferenças entre os computadores na rede. Em PVM um programa vê um conjunto heterogêneo de computadores, UNIX, de um modo uniforme como se tratasse um único computador paralelo.

MPI:O MPI é uma biblioteca de troca de mensagens utilizada para estabelecer comunicação, via troca de mensagens, entre processadores de sistemas de memória distribuída. A comunicação em MPI é realizada por chamadas explícitas às rotinas de comunicação do MPI, contidas em um programa escrito, pelo usuário, em linguagem C ou FORTRAN.

HPF:O HPF é uma extensão do FORTRAN 77 e 90, especialmente orientado ao paralelismo de dados. Ele oferece dentre outros os seguintes recursos: permite execução paralela com memória distribuída, automaticamente detectada pelo compilador e trabalha em vários tipos de arquiteturas para paralelismo.

PESSL (Parallel Engineering and Scientific Subroutine Library):O PESSL é uma biblioteca de sub-rotinas para cálculo científico que obtém alta performance em processamento numérico em sistemas SP da IBM e cluster IBM RS/6000. O PESSL é a versão paralela do ESSL.

ScaLapack:O ScaLapack é uma biblioteca de sub-rotinas para álgebra linear com alta performance em redes de estações que suportam PVM e/ou MPI. Sendo essencialmente uma extensão do LAPACK, o ScaLAPACK possui rotinas para solução de sistemas de equação linear, problemas de mínimos quadrados e autovalores.

OSLP:O OSLP provê suporte para a utilização das rotinas da biblioteca de otimização OSL em ambiente paralelo.

Conceitos importantes

Paralelismo com memória compartilhada

Enquadram-se os sistemas SMP (Symmetric Multi Processing) que possuem mais de um processador em um mesmo computador.
Todos eles compartilham os recursos de memória e disco existentes, segundo uma política de controle de concorrência adotada pelo sistema operacional.
Esta arquitetura é bem transparente ao usuário, ficando a cargo do sistema operacional a maior parte da complexidade.

Paralelismo com memória distribuída

Enquadram-se os sistemas MPP (Massive Parallel Processing), onde há pouco ou nenhum compartilhamento de recursos entre processadores.
Normalmente, cada nó de um sistema MPP é um computador independente, com memória e discos próprios.
Nestes sistemas, o controle do paralelismo é realizado pela aplicação, que deve coordenar as tarefas e a coerência entre os diversos nós.

Problemas em explorar o paralelismo

Ganho de desempenho em maquinas multicores requerem programação paralela.
É sempre simples escrever códigos paralelos quando existir "for paralelo"
Dois aspectos para programação paralela:
Corretude: Evite condições de corrida e deadlocks.
Desempenho: Uso eficiente de recursos como, por exemplo:
- Threads de Hardware
- Espaço de memória
- Largura de banda da memória

Programação Genérica

Exemplos bem conhecido é o STL (Standard Template Library) do C++.
- Escreve algoritmos o melhor possível da maneira mais geral.
Não força uma estrutura de dados particular para o usuário.
Instância algoritmos para uma situação específica

Conclusões

O aumento de velocidade dos supercomputadores é excepcional e apresenta um ranking mundial. Esse aumento é estendido aos computadores domésticos graças à utilização de múltiplos núcleos e à ligação de PCs em clusters. Esse grandioso poder computacional é ineficaz caso os programadores não possuam a capacidade de produzir programas de forma eficiente. Daí a importância de ambientes e compiladores paralelizadores de fácil utilização para que o desenvolvimento de aplicações não se restrinja a pesquisadores altamente qualificados. Essa realidade ocasiona na existência de chips multicore que, embora sejam o sonho do poder ilimitado de processamento, estão se tornando o pesadelo da programação paralela.

Referências

Intel Threading Building Blocks
Wikilivro do C++
Tudo sobre Programação Genérica