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.
Motivação pelo paralelismo



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.
Motivação pelo paralelismo
Motivação pelo paralelismo
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
Concorrência e Paralelismo

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
processos
e3
e3
e2 e2
e2
e1
e1
t
t1
tempo
Concorrência e Paralelismo
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.
e3
e2
e1
t
t1
tempo
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.
Medidas de Desempenho


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).
Medidas de Desempenho


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.
Medidas de Desempenho

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%.
Medidas de Desempenho

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)
Medidas de Desempenho



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.
Arquiteturas Paralelas

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
Arquiteturas Paralelas

SISD
FI
UC
UP
M
= Fluxo de Instruções
= Unidade de Controle
= Unidade de Processamento
= Memória
FI
UC
UP
M
Arquiteturas Paralelas

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).
Arquiteturas Paralelas

FI
SIMD
UC
FI
UC
UP
M
= Fluxo de Instruções
= Unidade de Controle
= Unidade de Processamento
= Memória
UP
M
UP
M
…
…
UP
M
Memória
Arquiteturas Paralelas

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.
Arquiteturas Paralelas

FD
MISD
FI
M
FI
UP
FD
M
UC
FI
= Unidade de Processamento
= Fluxo de Dados
= Memória
= Unidade de Controle
= Fluxo de Instruções
UC
M
UC
...
...
FI
M
UC
FD
FI
UP
FI
UP
FI
UP
Arquiteturas Paralelas

Pipeline:


Implementa um paralelismo temporal,
caracterizado quando existe a execução de
eventos sobrepostos no tempo.
A tarefa que será executada é dividida em subtarefas, 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).
Arquiteturas Paralelas

Pipeline:
Arquiteturas Paralelas

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.
Arquiteturas Paralelas

MIMD
UC
FI
UC
FI
...
UP
= Unidade de
Processamento
FD = Fluxo de Dados
M = Memória
UC = Unidade de Controle
FI = Fluxo de Instruções
UC
UP
UP
FD
FD
...
FI
UP
FD
M
FI
M
FI
...
...
M
FI
Arquiteturas Paralelas

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:
P
P
P
P
P
Rede de Interconexão
Memória
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:
espaço de endereçamento
M
M
M
M
M
M
M
M
P
P
P
P
P
P
P
P
Rede de Interconexão
Compartilhamento de Memória

Multiprocessadores NUMA:
 Acesso Não Uniforme à Memória Sem Consistência
de Cache


Acesso Não Uniforme à Memória Com Consistência
de Cache


NCC-NUMA – Non-Cache-Coherent Non-Uniform Memory
Access
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
M
M
M
P
P
P
M
P
M
M
M
M
P
P
P
P
Rede de Interconexão
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
P
M
M
P
M
P
P
P
P
P
M
M
M
M
M
Rede de Interconexão
Compartilhamento de Memória