Programação Paralela em Arquiteturas Multi-Core/Compiladores paralelizadores

Introdução

A execução simultânea de instruções possibilita ganhos no tempo final de execução e o melhor aproveitamento das potencialidades das arquiteturas em que executam. Em particular, de modo geral, apenas parte do conjunto de instruções de um programa merece atenção quanto à possibilidade de paralelização.

A proposta de exploração do paralelismo implícito procura manter a sintaxe da codificação seqüencial. Nesta primeira proposta o compilador traduz a aplicação escrita em linguagem de alto nível seqüencial para sua forma paralela. Na segunda proposta, exploração da distribuição/paralelismo explícito, as linguagens existentes são ampliadas com construtores específicos para o paralelismo, ou são criadas novas que disponibilizem os mesmos.

O desenvolvimento de programas capazes de realizar execuções em paralelo pode ser obtido de duas maneiras. Uma delas, paralelismo explícito, ocorre quando o paralelismo fica a cargo do programador, que sabe construir programas paralelos e faz uso de linguagens e ferramentas de programação que lhe oferecem suporte. Nessa proposta o programador é responsável por especificar o que pode/deve ser executado em paralelo, exigindo que, além de dominar o algoritmo, o programador conheça as características operacionais da arquitetura paralela. Além disso, nesse caso, o projeto do compilador paralelizador tem sua complexidade reduzida, porém ainda engloba aspectos mais sofisticados que o projeto de compiladores para códigos seqüenciais. Outra forma, paralelismo implícito, faz uso de compiladores que detectam o paralelismo existente em um código seqüencial gerando código paralelo automaticamente. Fica deste modo oculto ao programador o acréscimo de complexidade introduzido pelo paralelismo, mantendo-se a sintaxe da codificação seqüencial, ganhando, porém grande complexidade a tarefa de elaboração do compilador paralelizador.

Compiladores

Um compilador é um programa que, a partir de um código escrito em uma linguagem, o código fonte, cria um programa semanticamente equivalente, porém escrito em outra linguagem, código objeto.

Normalmente, o código fonte é escrito em uma linguagem de programação de alto nível, com grande capacidade de abstração, e o código objeto é escrito em uma linguagem de baixo nível, como uma seqüência de instruções a ser executada por uma determinada arquitetura de hardware. O processo de compilação é composto de análise e síntese. A análise tem como objetivo entender o código fonte e representá-lo em uma estrutura intermediária. A síntese constrói o código objeto a partir desta representação intermediária.

A análise pode ser subdividida ainda em análise léxica, análise sintática e análise semântica. A síntese é mais variada, podendo ser composta pelas etapas de geração de código intermediário, optimização de código e geração de código final (ou código de máquina), e somente esta última etapa é obrigatória.

Classicamente, um compilador traduz um programa de uma linguagem textual facilmente entendida por um ser humano para uma linguagem de máquina, específica para um processador e sistema operacional. Atualmente, porém, são comuns compiladores que geram código para uma máquina virtual que é, depois, interpretada por um interpretador.

Em linguagens de programação híbridas, o compilador tem o papel de converter o código fonte em um código chamado de bytecode, que é uma linguagem de baixo nível. Um exemplo deste comportamento é o do compilador da linguagem Java que, em vez de gerar código da máquina hospedeira (onde se está executando o compilador), gera código chamado Java Bytecode.

Outra parte separada do compilador que muitos usuários vêem como integrada é o linker, cuja função é unir vários programas já compilados de uma forma independente e unificá-los em um programa executável. Isso inclui colocar o programa final em um formato compatível com as necessidades do sistema operacional para carregá-lo em memória e colocá-lo em execução.

Compiladores versus paralelização

As linguagens existentes para programação paralela podem ser divididas em declarativas e imperativas.

Com as declarativas (lógicas e funcionais), obtém-se um paralelismo de granulação fina e que pode ser explorado mais naturalmente por compiladores específicos. As linguagens de fluxo de dados (funcionais) seguem essa característica. Exemplos dessas linguagens são Sisal, Val e Haskiel.

Nas linguagens imperativas, algumas possibilidades estão disponíveis:

Compiladores paralelizadores: geram automaticamente versões paralelas de programas não paralelos. Esses compiladores exigem o mínimo de trabalho de conhecimento extra por parte do usuário, mas o desempenho obtido normalmente é modesto (embora existam aplicações que se adequem bem). Também, nem sempre esses compiladores estão disponíveis, principalmente para sistemas de memória distribuída, além de apresentarem baixa flexibilidade. Normalmente exploram granularidade fina. Como exemplo temos: Oxygen, OSCAR, PARADIGM, SUIF, Parafrase2 e Cray.

Extensões paralelas: são bibliotecas cujo conjunto de instruções, aliado com as primitivas da linguagem hospedeira, permite o desenvolvimento de aplicações paralelas. Possuem como vantagem o fato de não exigirem do usuário o aprendizado de uma nova linguagem. Normalmente apresentam um desempenho melhor quando comparadas com os compiladores paralelizadores. Como exemplo tem-se PVM (Parallel Virtual Machine), MPI (Message Passing Interface, para arquiteturas de memória distribuída) e Parmacs;

Compiladores especiais: permitem a extensão de linguagens seqüenciais com ferramentas para o desenvolvimento de aplicações paralelas, como processos e monitores. Como exemplo pode-se citar Pascal Concorrente (para arquiteturas de memória compartilhada);

Linguagens concorrentes: são linguagens criadas especificamente para esse fim. Apresentam a desvantagem de exigir do usuário o aprendizado de uma nova linguagem de programação, além de possuírem baixa portabilidade. Por outro lado, podem oferecer:
- Flexibilidade;
- Clareza para ativação e coordenação de processos;
- Ferramentas para depuração e detecção de erros;
- Melhor desempenho.

Como exemplos, podem ser citadas as linguagens Occam, Ada, HPF e C*.

Compiladores paralelizadores

Para que seja possível detectar o paralelismo implícito em uma seqüência de instruções, faz-se necessária uma análise das dependências de dados entre as instruções. Esse é um dos maiores desafios para o desenvolvimento de compiladores paralelizadores eficientes.

Se não houver dependências de dados, as instruções podem ser executadas ao mesmo tempo. Caso contrário, conforme o tipo de dependência existente, o compilador poderá realizar otimizações capazes de melhorar o desempenho final do programa, por exemplo, realizando rearranjos nos índices dos loops ou retirando do interior de loops operações que não necessitam estar ali (nesse caso, podendo ser realizadas anteriores ou posteriores ao loop). Os laços de repetição presentes em códigos seqüenciais são potenciais fontes de paralelismo e são foco das análises de compiladores.

A tarefa de paralelização pode ser dividia em três subproblemas:

Identificação de regiões com potencial de paralelismo;
Mapeamento do paralelismo dentro da arquitetura da máquina alvo;
Geração e otimização de código paralelo.

Quando os pontos de paralelismo já foram identificados pelo programador, as tarefas de mapeamento e geração de código necessitam de uma detalhada análise do compilador e de transformações no código.

A eficiência dos programas gerados por esse tipo de compiladores depende diretamente da arquitetura da máquina sobre a qual ele será executado. Existem compiladores para arquiteturas vetoriais que detectam instruções de laços de repetição que podem ser transformadas em instruções vetoriais. Esse tipo de compilador é conhecido como compilador vetorizador. Em arquiteturas vetoriais as operações são executadas em pipeline. Cada CPU (Central Processing Unit) vetorial está associada a um tamanho de vetor específico que indica o número máximo de elementos que podem ser inseridos no pipeline. Um compilador vetorizador identifica instruções de laços de repetição que podem ser convertidas em instruções vetoriais. Quanto maior o número de laços convertidos em instruções vetoriais, maior será o desempenho do programa sobre a arquitetura. Quando se trata de arquiteturas multiprocessadas, os compiladores paralelizadores particionam o conjunto de instruções de um laço entre os processadores da arquitetura para sua execução concorrente. Para os casos em que as arquiteturas suportam, podem vir a ser empregadas tanto técnicas de paralelização quanto vetorização conjuntamente.

Alguns exemplos de compiladores paralelizadores/vetorizadores são o Oxigen, OSCAR e PARADIGM. Esses compiladores geram código paralelo a partir de códigos seqüenciais escritos em Fortran, assim como vários outros compiladores paralelizadores em desenvolvimento. Um outro exemplo é o SUIF que paraleliza códigos seqüenciais Fortran e C. O Parafrase2 é um outro exemplo de compilador paralelizador para a linguagem C.

Análise de dependências

A análise das dependências de dados é fundamental para possibilitar otimizações e detecção de paralelismo implícito em programas seqüenciais. Essa análise oferece as informações necessárias para realizar transformações coerentes capazes de proporcionar melhorias de localização em memória, balanceamento de cargas e escalonamento eficiente. As informações de dependência de dados são essenciais para detectar iterações de laços que podem ser executadas em paralelo por arquiteturas multiprocessadas e vetoriais. As relações de dependências de dados armazenam a ordenação existente entre os estágios de um programa. Essa ordem deve ser preservada em qualquer transformação do compilador para garantir a validade do código que será gerado. As principais classificações de dependências de dados e em que situações elas acontecem serão apresentadas a seguir. Inicialmente considere o seguinte código.

1: A = B + C
2: D = A + 2
3: E = A * 3

No código acima as instruções 1 e 2 não podem ser executadas ao mesmo tempo uma vez que a instrução 2 precisa do valor A computado na instrução 1. Este tipo de dependência é conhecida como dependência verdadeira ou dependência de fluxo ou RAW (Read-After-Write). A instrução 3 também depende da instrução 1, logo a instrução 1 deve ser a primeira a ser executada. Como não existe dependência entre 2 e 3, essas duas instruções podem ser executadas em paralelo.

1: A = B + C
2: B = D / 2

No segundo código apresentado nota-se que a instrução 1 usa o valor de B antes da instrução 2 atribuir um novo valor a B. Isso implica que a instrução 1 deve ser executada antes da instrução 2 para que possa utiliza o valor antigo de B. Esse tipo de dependência é chamada de antidependência ou WAR (Write-After-Read).

1: A = B + C
2: D = A + 2
3: A = E + F

Nesse terceiro exemplo, tanto a instrução 1 quanto a instrução 3 estão atribuindo valor a A. Dependendo da ordem de execução das instruções (3 antes de 1) o valor resultante de A pode ser errado. Assim, a instrução 1 deve ser executada antes de 3. Esse tipo de dependência é conhecida como dependência de saída ou WAW (Write-After-Write).

1: A = B + C
   if(X >= 0) then
2:   A = A + 2
   end if
3: D = A * 2.1

Uma outra situação onde ocorrem dependências é quando ocorrem desvios condicionais em um código. No exemplo acima, o valor de A utilizado pela instrução 3 tanto pode ser o que foi gerado pela instrução 1 ou pela instrução 2, dependendo do valor de X. Este tipo de dependência é conhecida como dependência de controle ou dependência procedural. Considerando as dependências de dados dentro de laços de instruções existe um interesse na dependência entre as instruções e entre os elementos das instruções. Como exemplo tem-se o seguinte código:

   do I = 2,N
1:   A(I) = B(I) + C(I)
2:   D(I) = A(I)
   end do

O exemplo acima mostra uma dependência de dados entre a instrução 2 e a instrução 1. Esta dependência acontece na mesma iteração do laço já que o valor do elemento de A produzido na instrução 1 será utilizado na instrução 2. Observando agora um exemplo similar de laço de repetição.

   do I = 2,N
1:   A(I) = B(I) + C(I)
2:   D(I) = A(I-1)
   end do

Nota-se que a relação de dependência entre a instrução 2 e 1 permanece existindo. Porém, para qualquer iteração I a instrução 2 utilizará o valor do elemento de A produzido na iteração anterior. Um outro exemplo similar também pode ser visto.

   do I = 2,N
1:   A(I) = B(I) + C(I)
2:   D(I) = A(I+1)
   end do

Nesse último exemplo, para cada iteração I, a instrução 2 utiliza um elemento de A que será recarregado na iteração seguinte. Como a instrução 2 utiliza uma valor antigo de A, existe uma relação de antidependência entre 2 e 1.

Vetorização de instruções

Em arquiteturas vetoriais as operações são executadas em pipeline. Cada CPU (Central Processing Unit) vetorial está associada a um tamanho de vetor específico que indica o número máximo de elementos que podem ser inseridos no pipeline. Um compilador vetorizador identifica instruções de laços de repetição que podem ser convertidas em instruções vetoriais. Quanto maior o número de laços convertidos em instruções vetoriais, maior será o desempenho do programa sobre a arquitetura.

De modo geral, o processo que envolve a detecção de laços de repetição que podem ser convertidos em instruções vetoriais é seguido por todos os compiladores vetoriais. O que difere um compilador de outro são as peculiaridade de cada arquitetura vetorial. Por esse motivo, serão apresentadas as técnicas para conversão de laços empregada pela maioria dos compiladores vetoriais.

Um exemplo simples de conversão de um laço em uma instrução vetorial pode ser visto a seguir, onde o laço:

do I = 1,N
  A(I) = B(I+2) + C(I+1)
end do

transforma-se na instrução vetorial:

A(1:N) = B(3:N+2) + C(2:N+1)

Para o caso acima, não existem dependências de dados na instrução, o que simplifica o processo de conversão do laço. Quando existem dependências de dados entre instruções do laço, alguns cuidados devem ser tomados. Abaixo tem-se um exemplo desse tipo.

   do I = 1,N
1:   A(I) = B(I)
2:   C(I) = A(I) + B(I)
3:   E(I) = C(I+1)
   end do

Observando o código acima, percebe-se uma dependência verdadeira entre as instruções 2 e 1. Existe, também, uma antidependência entre 3 e 2, já que a instrução 3 utiliza um valor antigo de C que será atualizado na próxima iteração. Para este caso, a vetorização das instruções pode ser realizada desde que haja uma reordenação onde a instrução 3 passa a preceder a instrução 2. Abaixo tem-se o código resultante.

1: A(1:N) = B(1:N)
3: E(1:N) = C(2:N+1)
2: C(1:N) = A(1:N) + B(1:N)

Considerando agora o seguinte laço:

   do I = 2,N
1:   A(I) = B(I)
2:   C(I) = A(I) + B(I-1)
3:   E(I) = C(I+1)
4:   B(I) = C(I) + 2
   end do

Percebe-se uma dependência verdadeira entre as instruções 2 e 1 e outra entre as instruções 4 e 2. Existem antidependências entre as instruções 3 e 2, 2 e 4 e entre 1 e 4. Situações de dependência mútua como a existente entre as instruções 2 e 4 (dependência verdadeira entre 4 e 2 e antidepedência entre 2 e 4, para este caso) indicam que estas instruções são fortemente conectadas. Nesses casos, as duas instruções envolvidas devem ser mantidas em um laço serial. Já as demais instruções podem ser vetorizadas sem problemas. Veja abaixo como fica o código resultante.

1: A(2:N) = B(2:N)
3: E(2:N) = C(3:N+1)
   do I = 2,N
2:   C(I) = A(I) + B(I-1)
4:   B(I) = C(I) + 2
   end do

Algumas operações de redução que frequentemente aparecem nos programas também são identificadas pelos compiladores vetorizadores. Um exemplo desse tipo de operação é a soma, conforme pode ser visto no código abaixo.

   do I = 1,N
1:   A(I) = B(I) + C(I)
2:   ASUM = ASUM + A(I)
   end do

O código vetorial gerado para este laço pode ser visto abaixo, onde a função SUM retorna a soma do seu argumento.

1: A(1:N) = B(1:N) + C(1:N)
2: ASUM = ASUM + SUM(A(1:N))

A vetorização de operações de redução pode vir a gerar resultados errôneos. Principalmente quando os dados envolvidos são valores não inteiros. Por exemplo, alguns métodos produzem a soma vetorial através de acumulações parciais e por fim a adição das partes. Como as acumulações serão realizadas em ordens diferentes do laço original, os erros de arredondamento podem ser acumulados diferentemente gerando respostas diferentes. Por esse motivo alguns compiladores vetoriais possibilitam que a vetorização de operações de redução seja desabilitada para garantir que será atingida a mesma resposta tanto no código vetorizado quanto no serial.

Paralelização de instruções

Os compiladores paralelizadores voltam-se à construção de códigos paralelos a serem executados em arquiteturas multiprocessadas. Uma forma de utilizar os múltiplos processadores disponíveis é particionar o conjunto de iterações de um laço distribuindo-os entre os processadores. A qualidade do código gerado é diretamente influenciada pelo balanceamento de cargas dos processadores e pelo tempo em que um processador permanece ocioso devido a sincronizações. O processo de paralelização deve, além de distribuir as iterações entre os processadores, tentar organizar o código a fim de evitar sincronizações ou, no mínimo, diminuir o tempo de espera.

Para a paralelização das instruções de laços de repetição as dependências de dados entre as interações são analisadas. Caso as instruções não dependam de dados antigos (originados em iterações anteriores) elas poderão ser distribuídas entre os processadores disponíveis. Caso tais dependências a valores antigos existam, serão necessárias comunicações entre os processadores. Para exemplificar, considere-se o código abaixo.

   do I = 1,N
     do J = 2,N
1:     A(I,J) = B(I,J) + C(I,J)
2:     C(I,J) = D(I,J) / 2
3:     E(I,J) = A(I,J-1)**2 + E(I,J-1)
     end do
   end do

Nele é possível perceber que todas as iterações do laço controlado pela variável I são independentes umas das outras. Já no laço controlado por J isso não acontece uma vez que na terceira instrução faz-se necessário os valores de A e E das iterações anteriores. Logo, todas as iterações do laço controlado por I podem ser distribuídas entre os processadores.

Caso existam N processadores disponíveis, cada processador poderá executar uma iteração do laço. Caso exista um número inferior de processadores, as iterações poderão ser distribuídas entre os processadores de várias formas. O compilador pode pre-escalonar as iterações entre os P processadores em blocos contínuos onde o primeiro processador recebe as N/P primeiras iterações, o segundo as N/P seguintes e assim por diante. Outra forma possível é o compilador atribuir ao primeiro processador todas as P+1 iterações, ao segundo as P+2 e assim por diante.

Uma alternativa também é possível onde os processadores podem ser auto-escalonados. Nesse caso, cada processador, ao final de toda iteração, entra em uma seção crítica do código para determinar qual será a próxima iteração do laço que ele irá executar. Esse tipo de escalonamento funciona bem quando a carga de trabalho de cada iteração é relativamente grande, mas pode variar entre diferentes iterações devido a códigos condicionais no laço.

Considerando agora um caso onde as iterações não são independentes.

   do I = 2,N
1:   A(I) = B(I) + C(I)
2:   C(I) = D(I) * 2
3:   E(I) = C(I) + A(I-1)
   end do

Como pode ser visto, a terceira instrução depende do valor de A encontrado na iteração anterior, logo as iterações não podem ser executadas independentemente. Para que se obtenha o resultado esperado é necessário que haja uma sincronização capaz de garantir que o valor de A (I-1) já esteja disponível. Abaixo pode-se ver o código interno do laço com a inclusão da sincronização.

1: A(I) = B(I) + C(I)
   signal(I)
2: C(I) = D(I) * 2
   if(I>2) wait(I-1)
3: E(I) = C(I) + A(I-1)

O compilador pode reordenar as instruções para possibilitar a redução de uso de sincronizações. Quanto maior o número de sincronizações necessárias maior será o prejuízo para o desempenho do programa. Nesse ponto vê-se a importância de testes de dependências confiáveis, uma vez que testes mal feitos podem incluir sincronizações desnecessárias influenciando o desempenho final.

Um aliado dos compiladores paralelizadores, em especial em ambientes distribuídos, é o multithreading, técnica utilizada para ocultar a latência de memória e sincronização. Dada uma thread que por algum motivo teve de ser bloqueada, o multithreading reduz os custos de requisições remotas executando outras threads enquanto a thread corrente estiver bloqueada.

O primeiro ganho de desempenho de multithreading é que várias threads podem ser usadas para garantir que o processamento seja realizado enquanto a thread correntemente ativa aguarda por uma requisição remota. Se o nível de multithreading for alto o suficiente, várias threads podem ocultar a latência de todas as requisições remotas que não seja o overhead do sistema operacional local. Além disso, essa proposta separa o paralelismo físico do paralelismo lógico. Especificar o número de threads de uma aplicação independente de qualquer arquitetura em particular possui várias vantagens, dentre as quais:

independência da arquitetura;
facilidade de expressão;
balanceamento implícito de carga;
facilidade de geração de código por compiladores paralelizadores.

Contudo também existem desvantagens com o uso de multithreading, a maioria delas relacionadas ao custo de tratar threads adicionais.

Alguns exemplos de compiladores vetorizadores ou paralelizadores

Aqui serão apresentados alguns exemplos de compiladores, falando sobre a arquitetura a qual se destinam, a linguagem tratada, bem como sobre suas peculiaridades. Tais compiladores são diretamente influenciados pelas características da arquitetura a qual se destina. Para as arquiteturas em que é possível, os compiladores aplicam técnicas de paralelização e vetorização conjuntamente para obter o melhor aproveitamento do hardware disponível. Embora as técnicas tenham sido apresentadas separadamente neste texto, nada impede sua aplicação conjunta quando a arquitetura as suporta.

Oxygen

O Oxygen é um compilador paralelizador que gera código paralelo a partir de códigos em Fortran 77. Para tanto são utilizadas diretivas de compilação que permitem a distribuição de código e dados e suporte a um espaçamento de nomes globais. Os códigos gerados pelo Oxygen são destinados a arquiteturas paralelas com memória distribuída ou supercomputadores. O modelo de máquina assumido pelo Oxygen é um torus bi-dimensional de elementos processadores (PE – Processing Elements). Arquiteturas como Parystec Supercluster SC256, iWarp, o Fujitsu AP1OOO, e simulador K9 implementam este tipo de topologia. A Figura 1 mostra um modelo de máquina torus bi-dimensional onde cada elemento processador comunica-se através de primitivas send e receive.

O Oxygen portou dois tipos de sistemas com memória distribuída: o de comunicação sistólica e o de comunicação por memória, conforme observado na figura. Na comunicação sistólica não há trocas de mensagens. Os dados são transmitidos do enviador para o receptor usando transferências entre as filas de memória ou filas de registradores existentes entre os PEs. Nesse caso, um PE pode se comunicar com seus quatro vizinhos mais próximos. A comunicação por memória, também chamada comunicação por troca de mensagens, acontece entre primitivas send e receive. As mensagens podem ser roteadas não só aos vizinhos mais próximos e sim a todos os PEs presentes no torus. Embora as trocas de mensagens sejam mais confortáveis para programar, o tempo gasto no gerenciamento e na computação do roteamento impõe uma maior latência para a comunicação.

Para o compilador Oxygen, os programas Fortran podem ser decompostos em uma seqüência de blocos, os quais podem executar em paralelo em todos os PEs. Esses blocos podem ser locais ou públicos. Blocos locais podem ou não serem executados em paralelo, mas em qualquer caso sua computação é local sem a necessidade de comunicação. Blocos públicos sempre executam em paralelo e com comunicações porque suas operações são sobre estruturas de dados distribuidamente alocadas pelos PEs.

A Figura 2 mostra o modelo de programa para o Oxygen. A coluna da esquerda mostra a decomposição de um código seqüencial, através de diretivas de compilação, em blocos. A coluna central mostra a estrutura de código gerada pelo Oxygen comum a todos os PEs. Cada bloco público é dividido em um tratador de símbolos e um executor, como mostrado na coluna da direita. O tratador de símbolos é uma seqüência de análises de consistência de dados e fases de roteamento para descobrir quem são os donos das variáveis compartilhadas. O executor é uma seqüência de fases de computação ligadas por pontos de verificação (comunicação). A análise de consistência do tratador de símbolos constrói as estruturas de dados que serão usadas pelo executor. Os pontos de verificação separam os blocos de computação locais dentro do executor fazendo a sincronização dentro do PE e não uma sincronização de toda a máquina. Sempre em que faltarem dados localmente o compilador insere uma primitiva de comunicação para obtê-los.

Para os programas que apresentam laços de repetição, o tratamento de seus índices acontece similarmente ao tratamento de índices de vetores. Ambos os índices são particionados e mapeados usando as mesmas diretivas. O Oxygen possui duas diretivas de mapeamento, ROWWISE e COLWISE, que podem ser usadas nesse caso. Elas tanto podem mapear índices double aninhando laços no torus quanto mapear um único laço em todas as linhas (ou colunas) de PEs. Para o último caso, todos os PEs de uma mesma linha (ou coluna) realizam a computação para um mesmo índice.

Como exemplo tem-se o código abaixo.

LOOP SPLIT ROWWISE
do 10 i=1,n
LOOP SPLIT COLWISE
do 20 j=1,m
...
20 continue
10 continue

No exemplo acima, os dois laços foram alinhado no torus. O laço mais externo foi mapeado entre os PEs de uma mesma coluna do torus pela diretiva ROWWISE considerando que n é igual ao número de PEs presentes numa coluna do torus. Através da COLWISE, o laço interno foi mapeado entre todos os PEs de uma mesma coluna, novamente considerando m igual ao número de PEs de uma coluna do torus.

OSCAR

O compilador OSCAR (Optimally SCheduled Advanced multiprocessoR) é o compilador para o CMP (Chip Multiprocessor). Este compilador trabalha com a linguagem de programação Fortran. O compilador OSCAR explora, automaticamente, o paralelismo multi-grão sobre a arquitetura CMP. O paralelismo multi-grão significa o uso hierárquico do paralelismo de tarefas de grão grande entre laços, sub-rotinas e blocos básicos.

Primeiramente o compilador decompõe o código do programa Fortran em tarefas de granularidade grossa (Macro Tarefas). Depois, o compilador analisa o fluxo de controle dentro das tarefas com um grafo acíclico chamado MFG (MacroFlow-Graph). O próximo passo em busca do máximo paralelismo entre as Macro Tarefas é a análise das condições iniciais necessárias para a execução de cada uma das Macro Tarefas. Todas as condições iniciais passam a ser representadas pelo compilador através de um grafo acíclico chamado MTG (MacroTask-Graph). Por fim, uma Macro Tarefa é associada a um grupo de processadores virtualmente definido pelo compilador em tempo de execução através de rotinas de escalonamento dinâmico.

Uma Macro Tarefa pode ser decomposta em tarefas de grão pequeno desde que o MTG não apresente desvios condicionais ou outras incertezas na execução. As tarefas de grão fino serão executadas em paralelo pelos processadores dentro de um grupo de processadores. O compilador analisa as dependências e gera um grafo de tarefas que representa a dependência de dados entre as tarefas de granularidade fina. Então, o compilador associa estaticamente as tarefas aos processadores desde que somente existam dependências entre as tarefas de grão fino.

Depois de escalonar, o compilador gera código de máquina para cada processador. Ele insere instruções para associar as tarefas ao processador e instruções para transferência e sincronização nas fases pré-definidas no escalonamento estático. As informações conhecidas pelo escalonamento estático também permitem que o compilador possa otimizar os códigos gerados.

A Figura 3 apresenta um exemplo simples de uma arquitetura OSCAR CMP. A arquitetura consiste de múltiplos elementos processadores (PE - Processor Elements) e interconexões de rede. Uma memória central compartilhada (CSM - Centralized Shared Memory) também está presente. Cada PE possui um única CPU, uma memória de programa local (LPM - Local Program Memory), uma memória de dados local (LDM - Local Data Memory), uma memória distribuída compartilhada (DSM - Distributed Shared Memory) com duas portas e uma unidade de transferência de dados (DTU - Data Transfer Unit).

A seguir, alguns números para ilustrar o desempenho do compilador paralalelizador OSCAR. Esse, gerando programas paralizados com OpenMP a partir de código seqüencial Fortran, obtém programas com desempenho 5.7 vezes melhor, na média de programas como SPEC CFP95 tomcatv, swim, su2cor, hydro2d, mgrid, applu and turb3d, comparado com o compilador fortran IBM XL em um máquina servidora SMP IBM pSeries 690 com 24 processadores.

PARADIGM

O compilador PARADIGM (PARAllelizing compiler for DIstributed memory General-purpose Multicomputers) destina-se a paralelizar e otimizar programas seqüenciais para execução eficiente em multicomputadores com memória distribuída. O PARADIGM aceita códigos seqüenciais Fortran 77 o HPF (High Performance Fortran) e produz uma versão paralela com passagem de mensagem.

A Figura 4 mostra a estrutura do compilador PARADIGM. Inicialmente é realizada uma análise do programa através do uso do Parafrase-2. O Parafrase divide o programa seqüencial em representações intermediárias analisando o código e gerando grafos de fluxos e dependências. Para a computação regular, o compilador determina automaticamente a distribuição de dados entre os componentes do multicomputador, sempre buscando a melhor distribuição. De acordo com a distribuição dos dados, o compilador divide a computação em processos e gera comunicações inter-processos para requerer dados não locais.

Nos casos de computação irregular, dependências de dados só são conhecidas em tempo de execução. Para esses casos o PARADIGM combina um flexível ambiente de execução irregular e uma análise em tempo de compilação. O compilador também pode fazer uso de threads para tornar as comunicações assíncronas e assim melhor aproveitar os ciclos computacionais. Além disso, as comunicações podem ocorrer através de um conjunto de bibliotecas de comunicação suportadas pelo compilador, entre elas MPI e PVM.

Uma vez que a inclusão da comunicação fica a cargo do compilador, este procura evitar comunicações redundantes, ou seja, evita o envio repetitivo de uma mesma mensagem. Para as situações onde elementos contíguos de um vetor são necessários, por exemplo, em laços de repetição, o compilador vetoriza a mensagem enviando todos os dados. Na mesma linha, quando um enviador e um receptor necessitam trocar um grande número de mensagens, o compilador agrega as mensagens em uma mensagem maior. Todas essas otimizações na troca de mensagens buscam diminuir a sobrecarga de comunicação que pode vir a comprometer o desempenho do programa paralelo.

Para os casos em que existem dependências entre iterações de laços e estas iterações possuem granularidade grossa, o PARADIGM possibilita sua execução em pipeline. Um exemplo é mostrado na Figura 5. Nela, pode ser vista a representação seqüencial onde cada iteração depende da iteração anterior e realizam grande quantidade de processamento. A Figura 5 (b) mostra uma possível execução em pipeline com granularidade fina e na Figura 5 (c) com granularidade grossa.

Além de preocupar-se com o paralelismo de dados, o PARADIGM também preocupa-se com o paralelismo funcional. O compilador mapeia em grafo MDG (Macro Dataflow Graph) tanto o paralelismo funcional quanto o de dados. Para determinar a melhor estratégia de execução para um determinado programa, é aplicada ao MDG uma aproximação de alocação e escalonamento. A alocação determina o número de processos usados em cada nó enquanto o escalonamento monta um esquema de execução para os nós alocados em um multicomputador específico. Os algoritmos empregados pelo PARADIGM para a alocação e o escalonamento são baseados em fórmulas matemáticas para determinar o custo de processamento e redistribuição de dados. O processo de escalonamento e alocação carece de um tempo de processamento para a sua determinação e, geralmente, este tempo é pequeno.

SUIF

O Compilador SUIF (Stanford University Intermediate Format), desenvolvido por Stanford Compiler Group, é uma infra-estrutura projetada para suportar colaborações de pesquisas em otimizações e compiladores paralelos.

O objetivo principal do projeto do compilador SUIF foi desenvolver um sistema extensível que suporte uma grande variedade de tópicos de pesquisa incluindo paralelização, linguagens com orientação a objeto, otimizações escalares e otimizações de máquinas específicas.

O compilador SUIF traduz programas seqüenciais em códigos paralelos com intuito de compartilhar espaços de endereços das máquinas. O compilador gera um programa simples de múltiplos dados (SPMD – Single Program Multiple-Data), programa que contém chamadas para bibliotecas em tempo de execução. Atualmente, existem versões de bibliotecas para máquinas SGI e multiprocessadores Stanford DASH e também versões para monoprocessadores que são usados para debugar e testar.

O paralelizador SUIF é capaz de suportar inúmeros projetos de pesquisa. Um deles é um projeto que desenvolveu um compilador que otimiza o programa para compartilhar espaços de endereços das máquinas. O compilador para máquina escalar inclui análise para encontrar dados e decompor cálculos para minimizar a comunicação preservando o paralelismo. Também otimiza custos de redundância na sincronização e reestrutura vetores para aumentar a performance da hierarquia de memória.

O SUIF também incorpora técnicas de análise de paralelização interprocedural. Isso inclui análise de fluxo de dados escalares e análise de dependência, assim como vetores privados e redução de identificação.

O objetivo principal do projeto da infra-estrutura do SUIF é suportar o desenvolvimento independente de módulos de compiladores diferentes que interagem uns com os outros. O compilador é composto de uma série de etapas centradas em uma mesma representação comum conhecida como SUIF. A primeira etapa traduz os recursos dos programas em uma representação SUIF, o compilador analisa ou transforma um programa SUIF em um outro otimizado, e finalmente, a última etapa traduz a representação do SUIF em código objeto. Cada etapa é um programa separado que se comunica com as outras etapas via arquivos binários SUIF. Esse design permite compiladores de etapas diferentes sejam desenvolvidos independentemente e podem ser facilmente encontradas, substituídas ou rearranjadas.

A arquitetura do compilador consiste em quatro camadas de software. No coração do sistema está a definição de um programa de formato intermediário que é implementado como uma classe C++. A representação do programa constitui-se de simples operações como aquelas encontradas em arquiteturas RISC, assim como também construídas em alto nível de captura de informação úteis para transformar estruturas de loop e cálculos de vetores de índices de matriz. A representação também inclui o tipo de informação com detalhes suficientes para suportar análise interprocedural, assim como também a tradução de SUIF para FORTRAN e C. A segunda camada do software é um SET de rotinas do KERNEL e ferramentas definidas como representações de programa. Nisso inclui rotinas que lêem e escrevem em arquivos binários SUIF utilizados para imprimir informações binárias no formato texto e tradutores de mais baixo nível para aquelas mais baixas ainda.

As bibliotecas também incluem ferramentas e rotinas matemáticas utilizadas para paralelismo. Essas ferramentas facilitam a criação de novas camadas SUIF e representam a terceira camada da arquitetura do compilador. Finalmente a última camada consiste de simples scripts que compõe de fim-a-fim sistemas de compilação através de uma seleção de uma série de transformadores de programa.

Modelo de paralelização SUIF/CVM

A programação para máquinas que utilizam troca de mensagens (arquitetura distribuída) pode ser realizada a partir de construções explícitas (grande esforço de programação) ou por compiladores paralelizadores (aplicabilidade limitada, pois não conseguem gerar código otimizado para determinados tipos de aplicações). Uma forma de eliminar estas restrições é combinar um compilador paralelizador para memória compartilhada com um sistema DSM implementado em nível de software.

A proposta de Keleher e Tseng combina o compilador paralelizador SUIF e o software DSM CVM (Coherent Virtual Machine – Máquina Virtual Coerente). O SUIF paraleliza automaticamente aplicações seqüenciais, além de fornecer uma análise sofisticada do código. O programa é compilado para executar em CVM, o qual abstrai os detalhes da arquitetura distribuída que requer troca de mensagens (Figura 6).

As inovações do sistema incluem técnicas de compilação que:

Combinam mensagens de dados da aplicação e de sincronização com a invocação de tarefas paralelas;
Emprega rotinas para avaliação de operações reduzidas;
Seleciona um protocolo de atualização híbrido que envia dados antecipadamente (flushing) realizando atualizações nas barreiras. Atualizações antecipadas (flushing updates) eliminam várias falhas de memória não locais, aumentando assim o desempenho.

Para complementar a proposta de Keleher e Tseng, Han et al propôs algoritmos para eliminação de sincronização de barreira a partir da análise de compilação. As técnicas de compilação para reduzir o overhead de sincronização e desbalanceamento de carga foram implementados com os objetivos de:

Realizar uma análise de comunicação através de análise de subscrição local (local subscript);
Explorar consistência de liberação preguiçosa para eliminar barreiras guardando apenas anti-dependência;
Substituir barreiras (que envolvem todos os processadores) por operações de sincronização que envolvam apenas os mais próximos.

O suporte de compilação para o CVM permite que aplicações seqüenciais sejam portadas para arquiteturas distribuídas com o auxílio de um compilador paralelizador em um ambiente de execução baseado em memória compartilhada distribuída.

Vantagens do uso de compiladores paralelizadores-vetorizadores

Algumas vantagens podem ser listadas dado o uso de compiladores paralelizadores/vetorizadores:

Aproveitamento dos milhões de linhas de código já desenvolvido;
Simplifica o desenvolvimento de soluções paralelas;
Não são necessárias novas metodologias de programação;
Mais fácil desenvolver código seqüencial do que paralelo por parte do programador;
Diminuindo o trabalho do programador, em conseqüência, diminui a possibilidade de inserção de erros por esse no desenvolvimento dos programas.

Desvantagens do uso de compiladores paralelizadores-vetorizadores

Algumas desvantagens podem ser listadas dado o uso de compiladores paralelizadores/vetorizadores:

O código seqüencial pode estar escrito de tal forma que impeça uma paralelização eficiente;
Alta relação que deve existir entre o compilador e a arquitetura;
De modo geral, apenas parte do conjunto de instruções de um programa merece atenção quanto à possibilidade de paralelização;
Os ganhos obtidos com estes compiladores são ainda pouco satisfatórios: para obter bons speedups deve-se ter a ajuda de especialistas, além do nível de automatização. A sutileza pela qual o programador procura é a razão pela qual o compilador não pode fazer a paralelização por ele.

Abaixo segue uma comparação feita entre a execução de alguns códigos paralelizados via compiladores paralelizados e a execução de uma versão paralelizada manualmente. Além disso, utilizaram-se como bases de código seqüenciais os benchmarks NAS SP e BT, largamente utilizadas para comparações de desempenho entre versões paralelas de códigos seqüenciais.

As quatro versões de código paralelo são:

NAS SP & BT Fortran 77 MPI , implementada manualmente pela NASA Ames Research Laboratory
NAS SP & BT (multiparticionado) compilado com dHPF sobre os códigos seqüenciais
NAS SP & BT (2D block) compilado com dHPF sobre os códigos seqüenciais
NAS SP & BT (1D block, transpose) compilado com Portland Group’s pgHPF sobre seus códigos HPF

Para cada paralelização ρ, a métrica de eficiência é calculada como:

{\frac {T_{s}}{P\times T_{p}(P,\rho )}}

Onde, t_s é o tempo de execução da versão original seqüencial implementada pelo grupo NAS da NASA Ames Research Laboratory; P é o número de processadores e t_{p(P, ρ)} é o tempo de execução paralela utilizando P processadores e a paralelização ρ.

Os gráficos mostram que a eficiência de paralelização MDI por codificação manual baseada na distribuição de dados multiparticionados é excelente, rendendo um média de eficiência na paralelização de 1.20 para SP classe ‘A’, 0.94 para SP classe ’B’, 0.97 para BT classe ’A’ e 1.02 para BT classe ’B’. Assim, as versões codificadas possuem speedup quase linear.