Programação Paralela em Arquiteturas Multi-Core/Compiladores paralelizadores: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição |
Sem resumo de edição |
||
Linha 301:
==== Oxygen ====
O Oxygen [6] é 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
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
Linha 311 ⟶ 310:
</center>
----
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õem 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 sequencial, 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 sequê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 sequê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.
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''' INSERIR IMAGEM 02 ''''
</center>
----
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, ou então, 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 [3, 4] é 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. O paralelismo de laços entre suas iterações e o paralelismo de tarefas de grão pequeno próximas entre instruções dentro de blocos básicos.
Primeiramente o compilador decompõem o código do programa Fortran em tarefas de granularidade grossa (Macro Tarefas). Depois, o compilador analiza o fluxo de controle dentro das tarefas 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 pelo 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 exista 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 escalomamento 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).
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''' INSERIR IMAGEM 03 ''''
</center>
----
A seguir, alguns números para ilustrar o desempenho do compilador paralalelizador OSCAR. Esse, gerando programas paralizados com OpenMP a partir de código sequencial Fortran, obtem 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 sequenciais 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.
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''' INSERIR IMAGEM 04 ''''
</center>
----
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 sequencial em representações intermediárias analizando 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 requerir 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 mensagem 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 sequencial 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.
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''' INSERIR IMAGEM 05 ''''
</center>
----
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, é aplicado 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 carecem de um tempo de processamento para a sua determinação e, geralmente, este tempo é pequeno.
----
Linha 324 ⟶ 391:
==== 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 SUF 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.
Focando no design de cada uma dessas camadas, o sistema foi desenvolvido com o intuito de que possa tanto se sustentar como crescer e desenvolver um novo algoritmo compilado. O sistema é um paralelismo básico inclui FORTRAN e também C, um paralelismo dependente de dados, paralelismo de loop intraprocedural e ao final, uma parte que traduz SUIF devolta para FORTRAN e C.
O compilador inclui novos algoritmos de análises de ponteiros de álias para encontrar procedimentos paralelos para otimizar sua localidade. Todos esses algoritmos tem sido prototipados no sistema de compilação SUIF. Também suporta orientação linguagens de programação orientada ao objeto paralelismo e análise de ponteiros interprocedurais, otimização e análise escalar e, finalmente, geração de código e sincronização de instruções para microprocessador populares.
===== 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 [KEL 97] combina o compilador paralelizador SUIF [HAL 95] e o
software DSM CVM (Coherent Virtual Machine – Máquina Virtual Coerente) [KEL
96]. 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 2.2).
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''' INSERIR IMAGEM 06 ''''
</center>
----
As inovações do sistema incluem técnicas de compilação que: (i) combinam
mensagens de dados da aplicação e de sincronização com a invocação de tarefas
paralelas; (ii) emprega rotinas para avaliação de operações reduzidas; (iii) 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. [HAN 97] e
[HAN 98] propuseram 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 barreirasguardando 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 ===
* 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
----
Linha 336 ⟶ 466:
=== Desvantagens do 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üências os benchmarks NAS SP e BT, largamente utilizadas para comparações de desempenho entre geradores de código paralelo.
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ódigo HPF
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''' INSERIR IMAGEM 07 ''''
</center>
----
Para cada paralelização ρ, a métrica de eficiência é calculada como
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''' INSERIR FÓRMULA ''''
</center>
----
Onde, ts é 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 tp(P, ρ) é o tempo de execução paralela utilizando P processadores e a paralelização ρ.
Os gráficos mostram que a eficiência 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 for BT classe ’A’ and 1.02 for BT classe ’B’. Assim, as versões codificadas possuem speedup quase linear.
----
Linha 364 ⟶ 530:
</center>
----
[http://www.inf.ufrgs.br/procpar/disc/cmp134/trabs/T1/051/mccera/compiladores.pdf Compiladores Paralelizadores / Vetorizadores]
| |||