arq-hp9

Prévia do material em texto

ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 287
9. Multiprocessadores
• Processamento paralelo è um programa sendo executado
por múltiplos processadores simultaneamente.
• Questões básicas para projeto de sistemas multiprocessados:
• Compartilhamento de dados;
• Coordenação entre os processadores;
• Quantidade de processadores;
• Compartilhamento de dados
• Processadores com um único espaço de endereçamento
• Processadores de memória compartilhada.
• UMA – uniform memory access ou SMP – symmetric
multiprocessors
• NUMA – nonuniform memory access
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 288
• Processadores de memória privada.
• Troca de mensagens para comunicação entre
processos è send e receive
• Novo modelo de paralelismo è clusters è computadores
ligados por uma rede.
Categoria Tipo Número de
processadores
Troca de Mensagens 8-256
NUMA 8-256
Modelo de
Comunicação Endereçamento
compartilhado UMA 2-64
Rede 8-256Conexão Física
Bus 2-32
• Programação de multiprocessadores
• Speedup
Exemplo
Suponha que queiramos achar o speedup linear com 100
processadores. Que fração da computação original pode ser
seqüencial ?
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 289
Solução
Tempo de execução após melhora = (tempo de execução
afetado pela melhora / quantidade de melhora) + tempo de
execução não afetado
Tempo de execução após melhora / 100 = (tempo de execução
afetado pela melhora / 100) + tempo de execução não afetado
Tempo de execução não afetado = (Tempo de execução após
melhora / 100) - (tempo de execução afetado pela melhora /
100)
Exemplo
Suponha que queremos fazer duas somas: uma de duas
variáveis escalares e uma de duas matrizes 1000 X 1000. Qual
o speedup para 100 processadores ?
Solução
Se assumirmos que a performance é função do tempo de
adição t, então existe 1 adição não beneficiada pelo
paralelismo e 1.000.000 que são è tempo antes = 1.000.001
Tempo de execução depois melhora = (tempo de execução
afetado pela melhora / quantidade de melhora) + tempo de
execução não afetado
Tempo de execução depois melhora = (1.000.000/100)t + 1t =
1.001t
Speedup = 1.000.001/1.001 = 999
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 290
• Multiprocessadores conectados por um barramento simples
Cache
Processor
Cache
Processor
Cache
Processor
Single bus
Memory I/O
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 291
• Computadores com múltiplos processadores conectados em
um único barramento backplane
Nome #
max.
de
proc
Nome do
proc.
Clock
rate
MHz
Max.
mem/sist
MB
Bandwidth
max/sist
MB/seg
Compaq
Proliant
5000
4 Pentium Pro 200 2.048 540
Digital
AlphaServer
8400
12 Alpha 21164 440 28.672 2.150
HP 9000
K460
4 PA-8000 180 4.096 960
IBM
RS/6000 R40
8 PowerPC
604
112 2.048 1.800
SGI Power
Challenge
36 MIPS
R10000
195 16.384 1.200
Sun
Enterprise
6000
30 UltraSPARC
1
167 30.720 2.600
Exemplo – Programa paralelo em single bus
Suponha que queiramos somar 100.000 números em um
computador com múltiplos processadores ligados em um único
barramento. Vamos assumir que temos 10 processadores.
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 292
Solução
Pn è Processador n
1. Somar ¨áreas de números” em cada processador
sum[Pn] = 0;
for (i = 10000*Pn; i < 10000*(pn+1); i = i + 1;)
sum[Pn] = sum[pn] + A[i] ; /* soma as áreas assinaladas*/
2. Somar as diversas sub-somas è metade dos processadores
somam pares de somas parciais, um quarto somam pares das
novas somas parciais ,etc., etc., etc., etc..
half = 10;
repeat
synch(); /* primitiva de sincronização è espera a soma
parcial ser feita */
if (half%2 != 0 && Pn ==0)
sum[0] = sum[0] + sum[half –1];
half = half/2;
if (Pn < half) sum[Pn] = sum[Pn] + sum[Pn+halh];
until (half ==1);
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 293
• Coerência de cache em multiprocessadores è snooping
• snoop è controlador que monitora o bus para determinar se
existe ou não uma cópia de um bloco compartilhado.
• Manutenção da coerência è problema só na escrita.
• Processador tem que ter acesso exclusivo na escrita.
• Todos os processadores tem que ter a cópia mais recente após
uma escrita.
• Protocolo snooping:
• write-invalidate è uma escrita faz com que todas as cópias
em outras caches tornem-se inválidas até a atualização. O
processador que irá escrever manda um sinal de inválido
no bus e todas as caches checkam para ver se tem uma
cópia, se sim, tornam o bloco que contem a palavra
inválido.
Cache tag
and data
Processor
Single bus
Memory I/O
Snoop
tag
Cache tag
and data
Processor
Snoop
tag
Cache tag
and data
Processor
Snoop
tag
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 294
• write-update (write-broadcast) è o processador que
escreve propaga o novo dado no bus e todas as caches com
cópia são atualizadas.
• Exemplo de protocolo de coerência de cache
Invalid
(not valid
cache block)
Read/Write
(dirty)
Read Only
(clean)
)tihfietadilavnidneS(
(W
rite
ba
ck
dir
ty
blo
ck
to
me
mo
ry)
Processor read miss
Processor write
Processor write miss
Processor
read miss
Processor write
(hit or miss)
Cache state transitions using signals from the processor
Invalid
(not valid
cache block)
Read/Write
(dirty)
Read Only
(clean)Invalidate or
another processor
has a write miss
for this block
(seen on bus)
Another processor has a read
miss or a write miss for
this block (seen on bus);
write back old block
a.
Cache state transitions using signals from the busb.
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 295
• Sincronização usando coerência è lock variables (semáforos)
Succeed?
(= 0?)
Unlocked?
(= 0?)
Load lock
variable
No
Yes
No
Try to lock variable using swap:
read lock variable and then set
variable to locked value (1)
Begin update
of shared data
Finish update
of shared data
Unlock:
set lock variable to 0
Yes
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 296
• Multiprocessadores conectados por uma rede
Exemplo – Programa paralelo troca de mensagens
Suponha que queiramos somar 100.000 números em um
computador com múltiplos processadores ligados em um único
barramento. Vamos assumir que temos 100 processadores.
Solução
sum = 0;
for (i = 0; i < 1000; i = i + 1;)
sum = sum + A[i] ; /* soma arrays locais*/
Network
Cache
Processor
Cache
Processor
Cache
Processor
Memory Memory Memory
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 297
Somar as diversas sub-somas è send (x,y) onde x = processador
Pn e y o valor.
half = 100;
repeat
half = (half+1)/2;
if (Pn >= half && Pn < limit) send (pn – half, sum)
if (Pn < limit/2 -1) sum = sum + receive();
limit = half;
until (half ==1);
• Single address space in a large-scale parallel processor
Directory
Memory
Directory
Memory
Cache Cache
ProcessorProcessor
Network
a.
Directory
Memory
Directory
Memory
Cache Cache
ProcessorProcessor
Network
b.
ARQUITETURA DE COMPUTADORES – RICARDO PANNAIN 298
• Clusters è clusters de N máquinas tem N memórias
independentes e N cópias do SO.
• Topologias de Redes
a. 2D grid or mesh of 16 nodes b. n-cube tree of 8 nodes (8 = 23 so n = 3)
c. Omega network switch box
A
B
C
D
P0
P1
P2
P3
P4
P5
P6
P7
a. Crossbar b. Omega network
P0
P1
P2
P3
P4
P5
P6
P7