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
Brunofs (discussão | contribs)
Sem resumo de edição
Brunofs (discussão | contribs)
Sem resumo de edição
Linha 444:
----
 
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 450:
==== 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.
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''Esta secção se encontra em construção''' &nbsp;&nbsp; -&nbsp;&nbsp;
Previsão de Conclusão: ''14/12''<br>
<tt>Progresso:</tt> <br>
'''FALTA REVISAR: CONTEÚDO E FORMATAÇÃO'''
</center>
----
 
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 (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 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 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 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 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 ''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 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 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.
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.
 
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 SUFSUIF 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.
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 =====
Linha 490 ⟶ 475:
Previsão de Conclusão: ''14/12''<br>
<tt>Progresso:</tt> <br>
'''FALTA REVISAR: CONTEÚDO E FORMATAÇÃO'''<br>
'''FALTA INSERIR IMAGEM 06'''
</center>
----
 
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 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
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''').
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).
 
----
Linha 515 ⟶ 491:
----
 
As inovações do sistema incluem técnicas de compilação que: (i) combinam
 
* 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
paralelas;
atualizações nas barreiras. Atualizações antecipadas (flushing updates) eliminam
* 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. [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:
 
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 barreirasguardando apenas anti-dependência;
* 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 barreirasguardandobarreiras 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.
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.
 
----