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 95:
[[Imagem:Attention_niels_epting.svg|left|25px]]
<center>
'''FALTAINSERIR FALARAQUI SOBRE=> HISTÓRIA DOS COMPILADORES PARALELIZADORES!!!'''
</center>
----
Linha 103:
 
=== Análise de Dependências ===
 
----
[[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> '''FALTA REVISAR: CONTEÚDO E FORMATAÇÃO'''.
</center>
----
 
A análise das dependências de dados é fundamental para possibilitar otimizações e detecção de paralelismo implicito em programas sequênciais. 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 vetorias. 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.
Linha 122 ⟶ 112:
</pre>
 
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.
 
<pre>
Linha 129 ⟶ 119:
</pre>
 
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)'''.
 
<pre>
Linha 137 ⟶ 127:
</pre>
 
Nesse terceiro exemplo, tanto a instrução 1 quanto a instrução 3 estão atribuíndo 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)'''.
 
<pre>
Linha 147 ⟶ 137:
</pre>
 
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:
 
<pre>
Linha 181 ⟶ 171:
=== 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 indida o número máximo de elementos que podem ser iseridos 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.
----
[[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> '''FALTA REVISAR: CONTEÚDO E FORMATAÇÃO'''.
</center>
----
 
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 indida o número máximo de elementos que podem ser iseridos 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:
 
Linha 207 ⟶ 189:
</pre>
 
Para o caso acima, não existeexistem 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>
Linha 217 ⟶ 199:
</pre>
 
Observando o código acima, percebe-se uma dependência verdadeira entre aas instruçãoinstruções 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>
Linha 236 ⟶ 218:
</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çõesSituaçõ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çõesinstruçõ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>
Linha 270 ⟶ 252:
=== 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.
----
[[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> '''FALTA REVISAR: CONTEÚDO E FORMATAÇÃO'''.
</center>
----
 
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, consideraconsidere-se o código abaixo.
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>
Linha 294 ⟶ 266:
</pre>
 
Nele é possivel perceber que todas as iterações do laço controlado pela variável I são idependentesindependentes 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.
 
Linha 307 ⟶ 282:
</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áesteja disponível. Abaixo pode-se ver o código interno do laço com a inclusão da sincronização.
 
<pre>
Linha 319 ⟶ 294:
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”'''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, elao ''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, e facilidade de geração de código por compiladores paralelizadores. :
 
* independência da arquitetura;
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.
* 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 com threads adicionais.
 
----