TELP: Aplicações Paralelas em Ambientes de Passagem de Mensagens Introdução à Computação Paralela

TELP: Aplicações Paralelas em Ambientes de Passagem de Mensagens

Introdução à Computação Paralela

Conceito de Processamento Paralelo Divisão de uma determinada aplicação, de

forma que esta possa ser executada por vários elementos de processamento, que deverão cooperar entre si (comunicação e sincronismo) (FOSTER et al., 2003),

Ganho de eficiência por meio da quebra da execução seqüencial do fluxo de instruções da máquina de von Neumann (ALMASI & GOTTLIEB, 1994).

Histórico

Em 1920, Vanevar Bush, do MIT (Massachussets Institute of Technology), apresentou um computador analógico que resolvia equações diferenciais em paralelo.

Von Neumann, em seus artigos, por volta de 1940, também sugeriu utilizar paralelismo como forma de se resolver equações diferenciais.

O surgimento do computador ILLIAC IV (supercomputador composto por 64 processadores), projeto iniciado na década de 60 e colocado em operação em 1972, na Universidade de Illinois, foi considerado o marco inicial do processamento paralelo (ROSE & NAVAUX, 2003).

Motivação pelo paralelismo

Basicamente: ganho de desempenho. Especificamente (ALMASI & GOTTLIEB, 1994): Restrições físicas à melhoria de desempenho de

um único processador: velocidade da luz, as leis da Termodinâmica, a dimensão física dos componentes e o custo;

O desenvolvimento tecnológico permitiu a construção de microprocessadores de alto desempenho, que agrupados, possibilitam um ganho significativo de poder computacional.


Microprocessadores de alto desempenho possibilitam uma melhor relação custo/desempenho quando comparadas aos supercomputadores de custo extremamente alto;

Agrupamento de microprocessadores em módulos permite a expansão do sistema através da inclusão de novos módulos;

Maior facilidade em incorporar o conceito de tolerância à falhas devido à redundância de hardware.



Concorrência e Paralelismo

A concorrência existe quando dois ou mais processos iniciaram a sua execução e ainda não foram finalizados, sem que haja uma relação com o número de elementos de processamento utilizados.

Quando existe apenas um elemento de processamento e vários processos estão sendo executados de maneira concorrente existe um pseudo-paralelismo ou paralelismo lógico


Paralelismo lógico: os processos estão

supostamente sendo executados ao mesmo tempo

há apenas o compartilhamento do elemento de processamento entre os processos em execução.

em um determinado instante de tempo, apenas um processo está em execução

e3

e2 e2

e1

e2

e3

e1

t1

t

tempo

processos


Paralelismo físico: Quando se tem mais de

um elemento de processamento e existem processos sendo executados ao mesmo tempo, há um paralelismo físico ou simplesmente paralelismo.

t1

t

tempo

processos

e3

e2

e1

Granulosidade ou granularidade A granulosidade (ou nível de paralelismo)

representa o tamanho das tarefas submetidas aos processadores e pode ser classificada em fina, média e grossa (GRAMA et al., 2003).

Este conceito está intimamente ligado ao tipo de máquina paralela em que o programa será executado.

Granulosidade Fina

Indica que o paralelismo está sendo realizado em nível de operações ou instruções. Geralmente, requer um número maior de comunicação por

parte das unidades de processamento. Desvantagem: alto custo de sincronização. Vantagem: uso de processadores mais simples. Os computadores multiprocessados são mais adequados a

processos paralelos de granulosidade fina,

Granulosidade Média

Indica o paralelismo obtido através da execução de blocos ou sub-rotinas do programa.

Granulosidade Grossa

Relaciona o paralelismo em nível de processos. Geralmente, requer um número menor de

comunicação e sincronismo entre os processadores.

Uso de processadores mais genéricos e complexos do que os destinados à execução de programas de granulosidade fina.

Os multicomputadores executam melhor os processos paralelos com granulosidade de média a grossa (FOSTER, 1995).

Taxa de granulosidade

G = P /C Onde C e P se referem respectivamente aos

tempos de comunicação e processamento local; G alto significa granulosidade grossa, isto é,

muito processamento local e pouca comunicação.

Medidas de Desempenho

Speed up: medida utilizada para determinar o aumento de velocidade obtido durante a execução de um programa (código paralelo) em p processadores, em relação à execução desse programa (código seqüencial) em um único processador. Sp = T1 / Tp Onde T1 é o tempo de execução em um

processador e Tp é o tempo de execução em p processadores.


Speed up: caso ideal é quando Sp = p, isto é, o ganho de speed up tende a p, indicando que a velocidade de processamento é diretamente proporcional ao número de processadores.

Dificuldades para a obtenção do caso ideal são: sobrecarga da comunicação entre processadores, partes do código executável estritamente seqüencial (que

não podem ser paralelizadas) nível de paralelismo utilizado (devido à granulosidade ser

inadequada ao tipo de arquitetura utilizada).


Speed up: Eventualmente Sp > p (superlinear) ocorre quando o tempo de execução de um programa seqüencial é bem superior ao tempo gasto pelo seu correspondente paralelo para solucionar um determinado problema.

Fatores: limitações de hardware da máquina que executou o

programa seqüencial má formulação do algoritmo seqüencial, deteriorando o

tempo total de sua execução.


Eficiência (Ep): trata da relação entre o Speed up e o número de processadores. Ep = Sp / p [0,1] A eficiência fornece o “quanto” os processadores

estão sendo utilizados. O caso ideal é obtido quando Ep =1, indicando uma eficiência de 100%.


Lei de Amdahl (AMDAHL, 1967) o Speed up sofre limitações devido aos trecho(s)

não paralelizável(is) de um programa : Sp ≤ 1 / (T<f> + T<1–f> /p)

f é a fração inerentemente seqüencial de um programa. (1-f) é a parte paralelizável de um programa. p é o número de processadores, sendo p > 1.

Uma estimativa de ganho ideal: I = Ts / (T<f> + T<1–f> /p)


Toda solução paralela, em um dado momento, possui um ponto de saturação onde o speed up não apresenta mais ganhos significativos e a eficiência cai.

O programa paralelo não atende mais de maneira satisfatória à escalabilidade da máquina paralela.

Tanto o speed up e quanto a eficiência continuam a cair com o incremento de p.

Arquiteturas Paralelas

Classificação de Flynn O processo computacional deve ser visto como

um fluxo de instruções executando sobre um fluxo de dados (FOSTER et al., 2003).

A classificação de Flynn acomoda as arquiteturas em quatro classes de máquinas: SISD, SIMD, MISD e MIMD.


SISD - Single Instruction Stream / Single Data Stream Fluxo único de instruções / Fluxo único de dados:

corresponde ao tradicional modelo de Von Neumann (apenas um processador).

Um processador executa seqüencialmente um conjunto de instruções sobre um conjunto de dados


SISD

UC UP M

FI

FI = Fluxo de Instruções UC = Unidade de Controle UP = Unidade de Processamento M = Memória


SIMD - Single Instruction Stream / Multiple Data Stream Fluxo único de instruções / Fluxo múltiplo de

dados: envolve múltiplos processadores executando simultaneamente a mesma instrução em diversos conjuntos de dados.

Exemplos: as máquinas paralelas com processadores Array como CM-2 e MasPar (ROSE & NAVAUX, 2003).


SIMD

UP

UP

UP

M

M

M

FI

Memória

FI = Fluxo de Instruções UC = Unidade de Controle UP = Unidade de Processamento M = Memória

… …

UC


MISD - Multiple Instruction Stream / Single Data Stream Fluxo múltiplo de instruções / Fluxo único de

dados: envolve múltiplos processadores executando diferentes instruções em um único conjunto de dados.

Nenhuma arquitetura é classificada como MISD, mas alguns autores consideram o pipeline como um representante dessa categoria.


MISD

UP = Unidade de Processamento FD = Fluxo de Dados M = Memória UC = Unidade de Controle FI = Fluxo de Instruções

M

M

M

FI

FI

FI

UC

UC

UC

FI

FI

FI

UP

UP

UP

FD

FD

... ...


Pipeline: Implementa um paralelismo temporal,

caracterizado quando existe a execução de eventos sobrepostos no tempo.

A tarefa que será executada é dividida em sub-tarefas, cada uma destas sendo executada por um estágio de hardware especializado que trabalha de maneira concorrente com os demais estágios envolvidos na computação (PATTERSON & HENNESSY, 2000).


Pipeline:


MIMD - Multiple Instruction Stream / Multiple Data Stream Fluxo múltiplo de instruções / Fluxo múltiplo de dados:

envolve múltiplos processadores executando diferentes instruções em diferentes conjuntos de dados,

A interação entre os processadores é feita pela memória. Cada processador executa o seu próprio programa sobre

seus próprios dados de forma assíncrona. O princípio MIMD é bastante genérico, daí cabe ainda uma

subdivisão, de acordo com o tipo de acesso à memória.


MIMD

UP = Unidade de Processamento

FD = Fluxo de Dados M = Memória UC = Unidade de Controle FI = Fluxo de Instruções

UC

UC

UC

UP

UP

UP

FI

FI

FI

FD

FD

FD

M

M

M

FI

FI

FI

... ... ... ...


MIMD: Máquinas com memória compartilhada são

conhecidas como multiprocessadores ou sistemas fortemente acoplados,

Máquinas que possuem memória não compartilhada (distribuída) são ditas multicomputadores ou sistemas fracamente acoplados.

Compartilhamento de Memória Multiprocessadores

Acesso Uniforme à Memória (UMA - Uniform Memory Access): a memória é centralizada e encontra-se à mesma distância de todos os processadores. A latência de acesso à memória é igual para

todos os processadores do sistema.

Compartilhamento de Memória UMA:

Rede de Interconexão

Memória

P P P P P P P P

Compartilhamento de Memória Multiprocessadores

Acesso Não Uniforme à Memória (NUMA - Non-Uniform Memory Access): a memória é organizada em módulos que são associados, de um para um, aos processadores. O espaço de endereçamento é único e cada processador

pode endereçar toda a memória do sistema. A latência de acesso à memória depende se o endereço,

gerado por um processador, encontra-se no módulo de memória diretamente ligado a ele ou não.

Um processador deve utilizar a rede de interconexão para acessar informações mantidas em outros módulos de memória.

Compartilhamento de Memória NUMA:

P P P P P P P P


M M M M M M M M

espaço de endereçamento

Compartilhamento de Memória Multiprocessadores NUMA:

Acesso Não Uniforme à Memória Sem Consistência de Cache NCC-NUMA – Non-Cache-Coherent Non-Uniform Memory

Access Acesso Não Uniforme à Memória Com Consistência

de Cache CC-NUMA – Cache-Coherent Non-Uniform Memory

Access Acesso Não Uniforme à Memória Com Consistência

de Cache em Software SC-NUMA – Software-Coherent Non-Uniform Memory

Access DSM (Distributed Shared Memory)

Compartilhamento de Memória Multiprocessadores NUMA: Arquiteturas de Memória Somente com Cache

COMA - Cache-only Memory Architecture Todas as memórias locais são estruturadas como memória

cache e são chamadas de COMA caches. As COMA caches têm muito mais capacidade que uma

cache tradicional. A memória principal é composta pelas COMA caches,

sendo que as gerências de caches e de memória ficam a cargo de um hardware de suporte, implementado somente nesse tipo de máquina.

Essa complexidade faz com que essa estrutura seja mais cara de implementar que demais máquinas NUMA.

Compartilhamento de Memória COMA

P P P P P P P P


M M M M M M M M

Compartilhamento de Memória Multicomputadores

Sem Acesso a Variáveis Remotas NORMA - Non-Remote Memory Access Cada processador possui sua própria memória local, à qual

apenas ele tem acesso direto. As memórias dos outros processadores são consideradas

remotas e possuem espaços de endereçamento distintos. Como não é possível o uso de variáveis compartilhadas

nesse ambiente, a comunicação com outros processos é realizada através de troca de mensagens via rede de interconexão.

A diferença básica entre as máquinas NORMA e as demais (UMA, NUMA e COMA) é que na primeira há uma replicação de toda a arquitetura convencional (processador, memória e I/O) para formar uma máquina paralela, e não apenas do componente processador como nos multiprocessadores.

Compartilhamento de Memória NORMA


P

M M M M M M M M

P P P P P P P

Compartilhamento de Memória

Documents

TELP: Aplicações Paralelas em Ambientes de Passagem de Mensagens Introdução à Computação Paralela