PPA+ +2019 01+ +parte+02

Prévia do material em texto

Programação Paralela
2ª parte
Prof. Jobson Massollar
jobson.silva@uva.br
Programação Paralela2
Taxonomia de Flynn
➢ A forma de classificação de computadores paralelos mais adotada é a
Taxonomia de Flynn, em uso desde 1966.
➢ Essa classificação das arquiteturas computacionais multiprocessadas é
feita a partir de duas dimensões independentes de fluxo de instruções
e fluxo de dados.
➢ Cada uma dessas duas dimensões pode admitir somente dois
estados: único (single) ou múltiplo (multiple).
Fluxo de dados
Único Múltiplo
Fluxo de 
instruções
Único SISD
Single instruction, single data
SIMD
Single instruction, multiple data
Múltiplo MISD
Multiple instruction, single data
MIMD
Multiple instruction, multiple data
Programação Paralela3
Taxonomia de Flynn
➢ SISD – Single Instruction, Single Data
 Computador sequencial típico (um único processador).
 Instrução única: apenas um fluxo de instruções é processado pela CPU
durante cada ciclo de clock.
 Dado único: apenas um fluxo de dados é processado durante cada ciclo
de clock.
UNIVAC 1
IBM 360
Programação Paralela4
Taxonomia de Flynn
➢ SIMD – Single Instruction, Multiple Data
 Representa um tipo de computador paralelo.
 Instrução única: apenas um fluxo de instruções é processado pela CPU
durante cada ciclo de clock.
 Dados múltiplos: cada unidade de processamento pode processar um
dado diferente em um mesmo instante.
 GPUs usam essa arquitetura.
Thinking Machines CM-2
Programação Paralela5
Taxonomia de Flynn
➢ MISD – Multiple Instruction, Single Data
 Representa um tipo de computador paralelo.
 Múltiplas instruções: cada unidade de processamento opera sobre os
dados de modo independente através de diferentes fluxos de instrução.
 Dado único: um único fluxo de dados é fornecido para as múltiplas
unidades de processamento.
 Poucos exemplos reais deste tipo de computador já foram concebidos (se
é que de fato algum já foi).
Programação Paralela6
Taxonomia de Flynn
➢ MIMD – Multiple Instruction, Multiple Data
 Tipo mais comum de computador paralelo.
 Múltiplas instruções: cada processador pode processar um fluxo de
instruções diferente.
 Múltiplos dados: cada processador pode processar diferentes fluxos de
dados.
 A execução pode ser síncrona ou assíncrona.
IBM POWERS
ADM OPTERON
Programação Paralela7
Motivação
➢ É usual a classificação das arquiteturas MIMD como
multiprocessadores e multicomputadores:
Programação Paralela8
Multiprocessadores
➢ Essa arquitetura é caracterizada por vários processadores
compartilhando uma única memória.
➢ Os múltiplos processadores executam de forma independente e estão
ligados a uma memória global central por meio de um barramento ou
de uma comutadora (switch).
➢ Qualquer alteração sobre uma posição de memória realizada por
determinado processador é igualmente visível por todos os demais
processadores.
Barramento Comutadora
Programação Paralela9
Multiprocessadores
➢ As arquiteturas de multiprocessadores são conhecidas como
fortemente acoplada, uma vez que processadores e memória estão
fortemente interligados através de seu sistema local de interconexão.
➢ A escalabilidade em uma arquitetura multiprocessada varia de alguns
até centenas de processadores.
➢ De certa forma, o elemento diferencial dessa arquitetura está no fato
da não existir nenhum tipo de comunicação direta entre os
processadores.
➢ Os processadores podem trocar dados através de instruções de
acesso à memória (operações de carregamento e armazenamento),
pois todos os processadores compartilham o mesmo espaço global de
memória.
Programação Paralela10
Multiprocessadores
➢ As arquiteturas multiprocessadas podem ser classificadas de acordo
com a forma de acesso à memória:
1. UMA (Uniform Memory Access)
2. NUMA (Non-uniform Memory Access)
Programação Paralela11
Multiprocessadores - UMA
➢ Todos os processadores são idênticos.
➢ Todos os processadores acessam a memória com a mesma latência,
ou seja, com o mesmo tempo de acesso.
➢ Os processadores podem ou não ter memória cache.
➢ Um único SO controla todos os processadores.
➢ Caso os processadores usem memória cache adota-se a CC-UMA
(Cache Coherent Uniform Memory Access):
✓ Coerência de cache é implementada por hardware (write
invalidate protocol).
Programação Paralela12
Multiprocessadores - UMA
➢ Como funciona a CC-UMA?
✓ Ao ler um valor da memória o processador faz uma cópia desse
valor na sua cache.
✓ Antes de se escrever um valor na memória, todas as cópias
existentes nas caches dos outros processadores são invalidadas.
✓ Quando outros processadores tentam ler o valor invalidado,
acontece um cache miss, o que os obriga a atualizar o valor da
cache a partir da memória.
Programação Paralela13
Multiprocessadores - UMA
➢ Como funciona a CC-UMA?
✓ Exemplo:
Programação Paralela14
Multiprocessadores - SMP
➢ Atualmente, as arquiteturas UMA são adotadas em máquinas com
multiprocessadores simétricos (Symmetric MultiProcessor - SMP).
➢ A arquitetura SMP é conhecida como uma arquitetura de
compartilhamento total, pois os diversos processadores compartilham,
além da memória, todos os dispositivos de E/S.
➢ Os processadores são considerados simétricos porque todos eles têm
os mesmos custos (tempos) para acesso à memória e aos dispositivos
de E/S.
Programação Paralela15
Multiprocessadores - SMP
➢ Configuração clássica de uma arquitetura SMP:
➢ Um fator particular dessa configuração é não possuir múltiplas
memórias e nem tão pouco múltiplos sistemas de E/S, mas apenas
múltiplos processadores.
Programação Paralela16
Multiprocessadores - NUMA
➢ A arquitetura NUMA consiste de diversos processadores e suas
respectivas memórias locais (denominados nós NUMA)
interconectados por links.
➢ A memória local de um processador é compartilhada com os demais
processadores, ou seja, do ponto de vista lógico existe um único
espaço global de endereçamento.
➢ Os processadores têm tempos de acesso diferentes a diferentes áreas
da memória.
Memória CPU
Memória CPU
MemóriaCPU
MemóriaCPU
Programação Paralela17
Multiprocessadores - NUMA
➢ Uma configuração bastante comum em arquiteturas NUMA adota dois
ou mais SMPs como nós.
➢ Cada SMP pode acessar diretamente a memória dos demais.
SMP
CPU CPU
Memória
CPU CPU
CPU CPU
Memória
CPU CPU
Memória
CPU CPU
CPU CPU
Memória
CPU CPU
CPU CPU
Programação Paralela18
Multiprocessadores - NUMA
➢ Caso os processadores usem memória cache adota-se a CC-NUMA
(Cache Coherent Non-uniform Memory Access):
✓ Coerência de cache é implementada por hardware (directory-
based protocol).
Programação Paralela19
Multiprocessadores - NUMA
➢ Como funciona a CC-NUMA?
✓ Associado a cada processador existe um diretório com
informações sobre o estado dos seus blocos de memória.
✓ Cada bloco pode estar em um dos seguintes estados:
▪ Uncached: não está na cache de nenhum processador.
▪ Shared: encontra-se na cache de um ou mais processadores e
a cópia em memória está correta.
▪ Exclusive: encontra-se apenas na cache de um processador e
a cópia em memória está obsoleta.
✓ Além do estado também é registrada qual ou quais CPUs possuem
uma cópia daquele bloco de memória.
Programação Paralela20
Multiprocessadores - NUMA
➢ Como funciona a CC-NUMA?
✓ Exemplo 1:
O valor de X não está na 
cache de nenhum
processador: U000
Cada um dos zeros 
representa um processador.Caches
Memórias
Diretórios
Programação Paralela21
Multiprocessadores - NUMA
➢ Como funciona a CC-NUMA?
✓ Exemplo 2:
O valor de X está na 
cache dos processadores 
1 e 3 e o valor de 
memória é válido: S101
Caches
MemóriasDiretórios
Programação Paralela22
Multiprocessadores - NUMA
➢ Como funciona a CC-NUMA?
✓ Exemplo 3:
O valor de X está 
somente na cache do 
processador 3 e o valor de 
memória é inválido: E001
Caches
Memórias
Diretórios
Programação Paralela23
Multiprocessadores - NUMA
➢ Como funciona a CC-NUMA?
✓ Exemplo:
X não está na cache de 
nenhum processador.
CPU3 envia um read miss 
para CPU1, esta atualiza o 
diretório para shared com 
o bit da CPU3 ligado e o 
valor de X é transferido 
para a cache da CPU3.
CPU1 não possui X em 
cache, o bit da CPU1 no 
diretório é ligado e o valor 
de X é transferido para a 
cache da CPU1.
Programação Paralela24
Multiprocessadores - NUMA
➢ Como funciona a CC-NUMA?
✓ Exemplo:
CPU3 envia um write miss 
para CPU1, esta invalida a 
cópia em cache e atualiza o 
diretório para exclusive da 
CPU3.
CPU2 envia um read miss 
para CPU1, esta pede à 
CPU3 o valor de X, atualiza 
a memória e o diretório e 
envia o valor de X para a 
cache da CPU2.
CPU1 gera um write miss
para invalidar as caches da 
CPU2 e CP3 e atualiza o 
diretório para exclusive da 
CPU1.
Programação Paralela25
Multiprocessadores - NUMA
➢ Como funciona a CC-NUMA?
✓ Exemplo:
CPU3 envia um write miss 
para a CPU1, esta atualiza 
a memória com o valor de 
seu cache e transfere-o 
para a cache da CPU3.
CPU3 envia o valor de X 
para a CPU1 e esta atualiza 
a memória e o diretório.
Programação Paralela26
Multiprocessadores
➢ Vantagens:
✓ A comunicação entre os processos é bastante eficiente, pois os
dados não precisam se movimentar fisicamente.
✓ Espaço de endereçamento global proporciona uma visão mais
simples da memória durante a programação.
➢ Desvantagens:
✓ Primitivas de sincronização são necessárias para acesso às regiões
compartilhadas:
▪ Em algumas linguagens isso fica a cargo do programador.
▪ Linguagens mais recentes abstraem alguns detalhes do programador.
✓ Pouco escalável, pois o aumento do número de processadores
aumenta a contenção no acesso à memória (UMA escala para
algumas dezenas de processadores e NUMA pode chegar a
centenas de processadores).
Programação Paralela27
➢ Conjunto de processadores interligados por uma rede (Ethernet,
Infiniband), onde cada um possui sua própria memória local.
➢ Cada processador opera de modo independente, uma vez que possui
sua própria memória, que não é compartilhada com os demais
processadores.
➢ Como não existe memória compartilhada, não existe o conceito de
coerência de cache.
➢ É de responsabilidade do programador definir explicitamente a
comunicação entre dois processadores, quando há a necessidade de
um acessar os dados de outro.
Multicomputadores
Memória CPU
Memória CPU
MemóriaCPU
MemóriaCPU
rede
Programação Paralela28
Multicomputadores
➢ Vantagens:
✓ Altamente escalável, permitindo a construção de MPPs (Massively Parallel
Computers - Computadores Massivamente Paralelos) com milhares de
processadores.
✓ Cada processador acessa a própria memória sem interferência dos demais
e sem o overhead de manter a coerência de cache.
✓ Pode utilizar processadores e redes já existentes.
➢ Desvantagens:
✓ A programação demanda que os problemas a serem resolvidos tenham
uma natureza paralela (pode ser difícil mapear estruturas de dados
baseadas em memória global para a memória distribuída).
✓ O programador torna-se responsável por muitos dos detalhes associados
à comunicação entre os processadores.
✓ É necessária a distribuição da carga entre os processadores, seja de
maneira automática ou manual.
✓ OS tempos de acesso à memória não são uniformes.
Programação Paralela29
Arquiteturas Híbridas
➢ Os maiores e mais rápidos computadores da atualidade combinam os
conceitos de multiprocessador e multicomputador, ou seja, memória
compartilhada e processamento distribuído:
✓ Cada nó do multicomputador é formado por um multiprocessador
que adota CPUs ou CPUs+GPUs (Graphics Processing Units -
Unidades de Processamento Gráfico).
➢ A complexidade da programação nesse tipo de arquitetura aumenta
consideravelmente.
rede
Memória
CPU CPU
CPU CPU
CPU CPU
Memória
CPU CPU
CPU CPU
Memória
CPU CPU
Memória
CPU CPU
CPU CPU
rede
Memória
GPU CPU
GPU CPU
CPU GPU
Memória
CPU CPU
CPU GPU
Memória
CPU GPU
Memória
GPU CPU
GPU CPU
Programação Paralela30
Outras Arquiteturas - Cluster
➢ Primeiro vislumbre: década de 1960 (IBM)
✓ Interconexão de mainframes para aumentar o processamento e
reduzir custos.
➢ Convergência tecnológica na década de 1980:
✓ Processadores de alto desempenho.
✓ Redes de alta velocidade.
✓ Padronização de ferramentas para computação
paralela/distribuída.
➢ Um cluster pode ser entendido como uma agregação local de
computadores que trabalham de forma dedicada ou não.
➢ Voltados para aplicações que requeiram alto desempenho ou alta
disponibilidade.
➢ Podem ser formados por nós homogêneos ou heterogêneos.
Programação Paralela31
Outras Arquiteturas - Grid
➢ Computação em Grade ou Grid Computing
✓ Agregam ambientes computacionais geograficamente dispersos.
✓ Modelo de memória distribuída.
✓ Utilizam a rede pública como meio de troca de mensagens.
✓ Altamente abstrata e escalável.
✓ O grupo de computadores que forma o grid atua como um
supercomputador virtual para fornecer acesso escalável e contínuo
a recursos de computação que estão distribuídos geograficamente
e os apresenta como um recurso único e unificado para executar
softwares de larga escala, como a análise de grandes conjuntos
de dados (mineração de dados, sequenciamento de DNA, etc.).
Programação Paralela32
Outras Arquiteturas - Cloud
➢ Computação em Nuvem ou Cloud Computing
✓ Arquitetura que visa o fornecimento de recursos computacionais
sob demanda (Computing as an Utility ou Computing as a Service)
✓ Também é altamente abstrata e escalável.
✓ A computação em nuvem é um tipo de computação baseada na
internet na qual um software não acessa os recursos diretamente.
Ao invés disso, ele acessa um enorme pool de recursos
compartilhados, o que permite o acesso sob demanda à esses
recursos.
✓ Favorece a ideia do "pague somente pelo que vai usar".