Programação Paralela em Arquiteturas Multi-Core/Compiladores paralelizadores: diferenças entre revisões

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.

 

==== OSCAR ====

 

O compilador '''OSCAR''' é o compilador para o ''OSCAR (Optimally SCheduled Advanced multiprocessoR) 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.

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.

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.

 

===== 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:

 

=== Desvantagens do uso de compiladores paralelizadores-vetorizadores ===

 

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

* '''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:

 

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.

 

=== Referências ===