IAC7 - Desempenho 4 - Arquiteturas Paralelas

Prévia do material em texto

06/04/2020 1
Requisitos para 
Alto Desempenho
Arquiteturas Paralelas
2
Alto Desempenho
• Arquiteturas Paralelas
• Computadores MIMD
• Computadores SIMD
• Computadores Vetoriais
• Computadores de Fluxo de Dados
3
Arquiteturas Paralelas
 Modelo Básico, máquina de Von Neumann
CPU Memória
Modelo SISD – Single Instruction Stream, Single Data 
Stream
Limitação de velocidade:
• Na execução das instruções
• Na comunicação entre CPU e Memória
4
Arquiteturas Paralelas
A Arquitetura de Harvard - É uma arquitetura onde a leitura de 
instruções e de alguns tipos de operandos pode ser feita ao mesmo 
tempo em que executa instruções. Enquanto uma instrução está 
sendo executada, a seguinte está sendo lida. Esse processo é 
conhecido como pipelining. 
Ref: https://pt.wikipedia.org/wiki/Arquitetura_Harvard
https://pt.wikipedia.org/wiki/Arquitetura_Harvard
5
Arquiteturas Paralelas
Soluções para evitar a limitação de velocidade:
1) Divisão da memória em bancos de memória
Outras limitações: acesso aos bancos de memória
CPU Memória
Memória
Memória
6
Arquiteturas Paralelas
Soluções para evitar a limitação de velocidade:
2) Uso de memória cache (buffer pequeno, rápido)
Outras limitações: Tecnologia de hardware
Cache Memória
Memória
Memória
CPU
7
Arquiteturas Paralelas
Soluções para evitar a limitação de velocidade:
3) Segmentação (pipeline) de instrução
 Fetch (busca) da Instrução,
 Decodificação da Instrução,
 Fetch (busca) dos operandos,
 Execução da Instrução,
 Escrita dos resultados
4) Segmentação (pipeline) de execução
 É possível ainda paralelizar a execução de instruções
8
Arquiteturas Paralelas
Soluções para evitar a limitação de velocidade:
5) Pipelining de dados: Computação Vetorial (instruções para 
tratamento de vetores); Array de processadores, fluxo de dados 
pipelined (fetch e aritmética de vetores); Registradores vetoriais.
P1 P2 P3 Pn
a1
a2
a3
an
b1
b2
b3
bn
c1
c2
c3
cnPrograma:
C <- A + B
ou
do i = 1 to n:
c(i)=a(i)+b(i)
Tempo Sequencial:
n*p unidades
Tempo Vetorial:
1 unidade
A B CMemória
Processadores
+
Instrução soma
9
Arquiteturas Paralelas
Soluções para evitar a limitação de velocidade:
5) Pipelining de dados: Computação Vetorial (instruções para 
tratamento de vetores); Array de processadores, fluxo de dados 
pipelined (fetch e aritmética de vetores); Registradores vetoriais.
P1 P2 P3 Pn
a1
a2
a3
an
b1
b2
b3
bnPrograma:
A <- A+B*C
ou
do i = 1 to n:
a(i)=a(i)+b(i)*c(i)
Tempo Sequencial:
n*p unidades
Tempo Vetorial:
1 unidade
A B Memória
Processadores
+
c1
c2
c3
cn
C
a1
a2
a3
an
*
Instrução soma e multiplica
10
Arquiteturas Paralelas
Soluções para evitar a limitação de velocidade:
Outras alternativas:
CPU´s múltiplas e unidades de memória interconectadas
Número de CPUs Taxa de 
Número de Unidades de Memória Processamento
11
Arquiteturas Paralelas
Modelo SIMD – Single Instruction Stream, 
Multiple Data Stream
Unidade de Controle única despacha instruções para cada 
processador. Execução síncrona da mesma instrução por todos os 
processadores, que executam essa instrução em múltiplos 
conjuntos de dados, simultaneamente. (Ex: ILLIAC IV projetado com 
256 unidades de ponto flutuante de 64 bits e 4 CPUs capazes de processar 
um bilhão de operações por Segundo).
Unidade
de 
Controle
Proc.
Proc.
Proc.
Proc.
REDE
12
Arquiteturas Paralelas
Modelo MIMD – Multiple Instruction Stream, 
Multiple Data Stream
Cada processador pode executar um programa diferente, incluindo 
o sistema operacional. Exemplos: Cosmic Cube (64 processadores 
8086), nCube2 (8192 processadores com 14 conexões por nó). A maioria 
dos computadores paralelos segue o modelo em cubo.
Processador +
Unidade de Controle
Processador +
Unidade de Controle
Processador +
Unidade de Controle
Processador +
Unidade de Controle
REDE
13
Arquiteturas Paralelas
SIMD: Modelo apropriado para PARALELISMO DE DADOS, em 
que o mesmo conjunto de instruções são realizadas sobre um 
grande volume de dados.
MIMD: PARALELISMO DE CONTROLE, execução simultânea 
de diferentes fluxos de instrução.
Caso particular: pipelining (cadeia de dados) fluindo através de 
(sub-)processadores que executam (sub-)instruções diferentes 
14
Arquiteturas Paralelas
SIMD: No modelo SIMD, diferentes processadores NÃO PODEM 
executar instruções diferentes no mesmo ciclo de relógio.
Ex: if C
then A
else B
Assim, programas “data-paralelos” em que uma parte significativa 
dos cálculos estão em instruções condicionais, têm baixo 
desempenho em SIMD.
MIMD: Os processadores são mais complexos, mas podem ser 
genéricos, enquanto que os do modelo SIMD exigem um projeto 
específico. Assim, a economia de escala permite que os 
processadores MIMD sejam mais baratos e mais poderosos do 
que os SIMD. 
15
Interação entre processadores
Organização do espaço de endereçamento (memória):
1) Troca de mensagens (multicomputadores)
 Processadores conectados através de uma rede de 
interconexão
 Cada processador tem sua memória local
 Interação por troca de mensagens
 “Memória distribuída”
16
Interação entre processadores
1) Troca de mensagens (múltiplos computadores)
 Processadores conectados através de uma rede de 
interconexão
 Cada processador tem sua memória local
 Interação por troca de mensagens
 “Memória distribuída”
REDE
Proc.
Mem.
Proc.
Mem.
Proc.
Mem.
Proc.
Mem.
17
Interação entre processadores
Organização do espaço de endereçamento (memória):
2) Memória compartilhada (multiprocessadores)
 Todos os processadores têm acesso ao espaço de 
endereçamento (memória), que é compartilhado entre 
eles.
 Processadores são conectados à memória via rede. 
 A banda da rede de interconexão deve ser alta para não 
degradar a performance.
18
Interação entre processadores
2) Memória compartilhada (múltiplos processadores)
 Todos os processadores têm acesso ao espaço de 
endereçamento (memória), que é compartilhado entre eles.
 Em determinado ciclo de relógio, todos os processadores 
podem estar fazendo um acesso à memória compartilhada.
Proc1 Proc2 Proc3 Proc4
Barramento
Memória
19
Interação entre processadores
2a) Memória compartilhada (e memória em cada processador)
 Em certos casos o acesso via rede pode ser muito lento. 
Ex: read ou write [E/S] pode passar por muitos estágios da 
rede (veremos estes estágios adiante).
 A solução é dotar cada processador de uma memória local, que 
pode armazenar o programa em execução e dados locais.
 Os dados globais são armazenados na memória compartilhada.
P1 P2 M2 P3
Rede / Barramento
Memória
M1 M3
20
Interação entre processadores
2b) Memória compartilhada (e cache em cada processador)
 Problemas de coerência de cache.
 Pode ter memória local ou não.
P1 P2 P3
Rede / Barramento
Memória
Cache Cache Cache
21
Interação entre processadores
O problema de coerência de cache.
1) A página W está na memória e no cache da máquina B. 
Estado do cache de B: “limpo”;
2) A lê W, B não reage à leitura de A. O valor vem da 
memória. Estado dos caches de A e B: “limpo”.
3) A escreve em W. Essa escrita invalida a cópia de B 
(estado=“inválida”), atualiza a memória e marca a cópia de 
A como “reservada”.
4) A escreve em W de novo, que está em seu cache. Nenhum 
tráfego no barramento é requerido. O estado do cache de A 
fica “sujo” e o de B permanece “inválido”.
5) C lê W. A fornece a página e invalida sua entrada no cache. 
C agora possui a única entrada válida. O estado do cache 
de A fica “inválido”, de B idem e de C fica “sujo”.
22
Interação entre processadores
2c) Memória compartilhada e memória local acessada por 
todos os processadores (modelo NUMA)
 Suporte de hardware para acesso de leitura e escrita à memória 
dos outros processadores.
 Acessoremoto emulado por troca de mensagens explícitas.
 Ex: TC-2000 (até 504 processadores), KSR-1 (até 1088 
processadores), Stanford Dash (protótipo com 64 processadores Risc, 
escalável para alguns milhares de processadores).
P1 +
cache
M2
Rede / Barramento
Memória
M1 M3
P2 +
cache
P3 +
cache
23
Interação entre processadores
Há muito tempo, os arquitetos de computadores têm buscado o Eldorado 
do projeto de computadores: criar computadores poderosos 
simplesmente conectando muitos computadores menores existentes. 
Essa visão dourada é a origem dos multiprocessadores. 
O cliente pede tantos processadores quantos seu orçamento permitir e 
recebe uma quantidade correspondente de desempenho. 
Portanto, os multiprocessadores podem ser escaláveis: o hardware e o 
software são projetados para serem vendidos com um número variável 
de processadores. Como o software é escalável, alguns 
multiprocessadores podem suportar operar mesmo com a ocorrência de 
quebras no hardware; ou seja, se um único processador falhar em um 
multiprocessador com n processadores, o sistema fornece serviço 
continuado com n–1 processadores. 
Finalmente, os multiprocessadores possuem o desempenho absoluto 
mais alto – mais rápido do que o uniprocessador mais rápido que existe.
24
Interação entre processadores
O microprocessador é hoje o processador mais econômico.
É consenso que se você não pode tratar um workload em um 
microprocessador, então, um multiprocessador ou um cluster 
composto de muitos microprocessadores é mais econômico do que 
construir um processador de alto desempenho por meio de uma 
tecnologia exótica. 
Há muitas aplicações científicas em que é extremamente difícil fazer 
progresso com um único microprocessador: 
 previsão de tempo, 
 cruzamento de proteínas,
 pesquisa de inteligência extraterrestre, entre outras.
25
Interação entre processadores
A Figura mostra uma representação dos primeiros 500 tipos de 
supercomputadores em uma década, evidenciando que a indústria da computação 
de alto desempenho depende dos multiprocessadores e dos clusters.
26
Clusters
Existem muitas aplicações – como bancos de dados, servidores de 
arquivos, servidores Web, simulações e multiprogramação / 
processamento – apropriadas para serem executadas em máquinas 
conectadas mais livremente do que as máquinas NUMA com 
coerência de cache.
Essas aplicações em geral precisam ser altamente disponíveis, 
exigindo algum tipo de tolerância a falhas e capacidade de 
reparação. 
Tais aplicações – além da semelhança dos nós de multiprocessador 
com os computadores desktop e o surgimento de redes locais de alta 
largura de banda baseadas em switches – são o motivo por que o 
processamento de grande escala use clusters de computadores de 
uso geral facilmente encontrados no mercado. 
27
Clusters
Uma desvantagem dos clusters tem sido a de que o custo de 
administrar um cluster de n máquinas é aproximadamente igual ao 
custo de administrar n máquinas independentes, enquanto o custo de 
administrar um multiprocessador de espaço de endereçamento 
compartilhado com n processadores é aproximadamente igual ao de 
administrar uma única máquina. 
Outro ponto negativo é que os clusters normalmente são conectados 
usando o barramento de E/S do computador, enquanto os 
multiprocessadores em geral são conectados no barramento de 
memória do computador. O barramento de memória possui largura 
de banda mais alta, permitindo que os multiprocessadores levem o 
link de rede a uma velocidade mais alta e tenham menos conflitos 
com o tráfego de E/S nas aplicações de E/S intensa.
28
Granularidade dos processadores
Um computador paralelo pode ser composto por:
 Um pequeno número de processadores poderosos (grão robusto 
ou course-grain) 
 Têm maior custo.
 Aplicações com baixo nível de concorrência, não podem usar um 
grande número de processadores. 
 Um grande número de processadores simples (grão fino ou fine-
grain)
 Aplicações apropriadas para um nível elevado de concorrência.
29
Redes de Interconexão
As redes de Interconexão entre processadores e memórias 
podem ser estáticas ou dinâmicas.
As redes estáticas são usadas tipicamente para organizações por 
troca de mensagens.
As redes dinâmicas estabelecem caminhos entre processadores e 
memórias, tipicamente para organizações de memória compartilhada.
Ex:
Na figura é mostrada uma rede com topologia em anel. 
Os nós processador/memória são mostrados como um quadrado preto. 
Como alguns nós não estão diretamente conectados, algumas 
mensagens precisarão saltar por nós intermediários até chegarem 
no destino final.
30
Redes de Interconexão
Critérios de custo e desempenho:
 Diâmetro – distância entre dois processadores 
quaisquer da rede
 Distância – caminho mais curto em termos de 
número de arestas
 Distância – Tempo de comunicação
 Grau dos nós – número de nós mais próximos. Deve 
ser reduzido para viabilizar a construção e deve ser 
constante, para favorecer a escalabilidade.
31
Redes de Interconexão Dinâmicas
Constituídas de P processadores e M endereços de memória.
Conectividade total: O (MxP) elementos de chaveamento.
Se M crescer muito, o número de elementos de chaveamento pode 
tornar a rede inviável. Esse problema pode ser resolvido organizando 
a memória em bancos.
Se um processador acessar um endereço em um determinado banco, 
os demais endereços do banco não poderão ser acessados. Ficarão 
bloqueados.
32
Redes de Interconexão
Topologias de rede que aparecem nos processadores paralelos 
comerciais:
Os círculos representam chaves e os quadrados representam nós processador-
memória. A topologia booleana de n-cubo é uma interconexão de n dimensões 
com 2^n nós, exigindo n links por chave (mais um para o processador) e, portanto, 
n nós vizinhos mais próximos. Essas topologias freqüentemente são 
suplementadas com arcos extras para melhorar o desempenho e a confiabilidade.
33
Redes Multi-estágios
Uma alternativa para colocar um processador em cada nó em 
uma rede é deixar apenas a chave em alguns desses nós. 
As chaves são menores que os nós processador-memória-
chave e, portanto, podem ser agrupadas mais densamente, 
diminuindo, assim, a distância e aumentando o desempenho. 
Essas redes são chamadas de redes multi-estágio para refletir 
as múltiplas etapas que uma mensagem precisa percorrer. 
As redes multi-estágio são tão numerosas quanto as redes de 
estágio único.
As mais importantes são: Crossbar e rede Omega.
34
Redes Multi-estágios
Uma rede Crossbar permite que qualquer nó se comunique com qualquer 
outro nó em uma passagem pela rede. 
Uma rede Omega usa menos chaves do que a rede crossbar, mas pode ocorrer 
contenção entre mensagens, dependendo do padrão de comunicação. 
Por exemplo, a rede Omega na Figura não pode enviar uma mensagem de P0 
para P6 ao mesmo tempo em que envia uma mensagem de P1 para P7.
35
Conclusão
O sonho de construir computadores apenas agregando processadores 
existe desde os primeiros dias da computação. No entanto, o progresso 
na construção e no uso de processadores paralelos eficientes tem sido 
lento.
No entanto, o progresso nos últimos anos nos dá razões para sermos 
otimistas quanto ao futuro do processamento paralelo e dos 
multiprocessadores.
Atualmente é amplamente aceito que a maneira mais eficaz de construir 
um computador que ofereça mais desempenho do que o obtido com um 
microprocessador de chip único é construindo um multiprocessador ou 
um cluster que potencialize as significativas vantagens de custo-
desempenho dos microprocessadores produzidos em massa.
Os multiprocessadores e clusters são altamente eficazes para workloads 
multiprogramados, que normalmente são o uso dominante de grandes 
servidores, bem como para servidores de arquivos ou servidores Web, 
que são um tipo restrito de workload paralelo.
36
Conclusão
Cabe ressaltar que o sistema operacionalnecessário para executar 
workloads multiprogramados é comum.
Outra área de aplicação importante, que possui um mercado muito 
maior, são os sistemas de bancos de dados e processamento de 
transação de grande escala. Esse domínio de aplicação também tem 
um grande paralelismo natural disponível por meio de processamento 
paralelo de requisições independentes.
O uso de processamento paralelo em domínios como a computação 
científica e de engenharia é usual. Esse domínio de aplicação possui 
uma necessidade quase ilimitada de mais computação. Ele também 
possui muitas aplicações com uma grande quantidade de paralelismo 
natural. Entretanto, programar processadores paralelos até para 
essas aplicações continua sendo um desafio.
Perguntas?