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)
Brunofs (discussão | contribs)
Sem resumo de edição
Linha 127:
1: A = B + C
if(X >= 0) then
2: A = A + 2
end if
3: D = A * 2.1
Linha 136:
<pre>
do I = 2,N
1: A(I) = B(I) + C(I)
2: D(I) = A(I)
end do
</pre>
Linha 145:
<pre>
do I = 2,N
1: A(I) = B(I) + C(I)
2: D(I) = A(I-1)
end do
</pre>
Linha 154:
<pre>
do I = 2,N
1: A(I) = B(I) + C(I)
2: D(I) = A(I+1)
end do
</pre>
 
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 ===
Linha 167 ⟶ 170:
Um exemplo simples de conversão de um laço em uma instrução vetorial pode ser visto a seguir, onde o laço:
 
<pre>
do I = 1,N
A(I) = B(I+2) + C(I+1)
end do
</pre>
 
transforma-se na instrução vetorial:
 
<pre>
A(1:N) = B(3:N+2) + C(2:N+1)
</pre>
 
Para o caso acima, não existe 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.
 
<pre>
do I = 1,N
1: A( do I) = B(I)1,N
21: C(I) = A(I) += B(I)
32: E C(I) = CA(I) +1 B(I)
3: E(I) = C(I+1)
end do
end do
</pre>
 
Observando o código acima, percebe-se uma dependência verdadeira entre a instrução 2 e a 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.
 
<pre>
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)
</pre>
 
Considerando agora o seguinte laço:
 
<pre>
do I = 2,N
1: A( do I) = B(I)2,N
21: C(I) = A(I) += B(I-1)
32: E C(I) = CA(I) + B(I-1)
43: B E(I) = C(I) + 21)
4: B(I) = C(I) + 2
end do
end do
</pre>
 
Percebe-se uma dependência verdadeira entre as intruçõ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. Em situações de dependência mútua como a existente entre as instruções 2 e 4 (depedência verdadeira entre 4 e 2 e antidepedência entre 2 e 4, para este caso) indicam que estas intruçõ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.
 
<pre>
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
</pre>
 
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.
 
<pre>
do I = 1,N
1: A(I) = B(do I) += C(I)1,N
21: ASUM A(I) = ASUMB(I) + AC(I)
2: ASUM = ASUM + A(I)
end do
end do
</pre>
 
O código vetorial gerado para este laço pode ser visto abaixo, onde a função SUM retorna a soma do seu argumento.
 
<pre>
1: A(1:N) = B(1:N) + C(1:N)
2: ASUM = ASUM + SUM(A(1:N))
</pre>
 
A vetorização de operações de redução podem vir a gerar resultados erroneos. 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 sejam desabilitadas 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 a construção de códigos paralelos a serem executados em arquiteturas multiprocessadas. Uma forma de utilizar os multiplos 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 depedências de dados entre as interações são analisadas. Caso as instruções não dependam de dados antigo (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, considera-se o código abaixo.
 
<pre>
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
</pre>
 
Nele é possivel perceber que todas as iterações do laço controlado pela variável I são idependentes 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 outra 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 indenpendetes.
 
<pre>
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
</pre>
 
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á está disponível. Abaixo pode-se ver o código interno do laço com a inclusão da sincronização.
 
<pre>
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 possiblitar 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, ela 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 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, e 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 com threads adicionais.
 
----
----
 
=== Alguns Exemplos de Compiladores Vetorizadores e/ou Paralelizadores ===
 
Nessa seção serão apresentados alguns exemplos de compiladores, falando sobre a arquitetura a qual se destinam, a linguagem tratada bem como 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 [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. 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 é
 
 
 
 
----
 
==== OSCAR ====
 
----
 
==== PARADIGM ====
 
----
 
==== SUIF ====
 
 
 
===== Modelo de paralelização SUIF/CVM =====
 
----
 
=== Vantagens do Uso de Compiladores Paralelizadores/Vetorizadores ===
 
----
----
 
=== Desvantagens do Uso de Compiladores Paralelizadores/Vetorizadores ===
 
----
----
 
=== Conclusão ===
 
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''FALTA FAZER A CONCLUSÃO!!!'''&nbsp;&nbsp;
<tt>Progresso:</tt> [[Image:00%.png]]
</center>
----
 
----
----
=== Referências ===
 
----
[[Imagem:Attention_niels_epting.svg|right|25px]]
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''FALTA COMPLETAR REFERÊNCIAS!!!'''&nbsp;&nbsp;
<tt>Progresso:</tt> [[Image:00%.png]]
</center>
----