Aula13

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Aula 13: Multiprocessadores e Clusters – Parte 2
Professor: Leandro Marzulo
Arquiteturas Avançadas de Computadores
Multiprocessadores conectados em um único barramento
Como minimizar a concorrência no acesso ao barramento
Caches
Mecanismos para manter a memória e as caches consistentes entre os diversos processadores, da mesma forma que a consistência é mantida entre a memória e os dispositivos de I/O  simplificar a programação
2
2
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
2
Exemplo
Somatório de 100.000 números em um multiprocessador de barramento único
processadores = 100 
elementos_por_processador = 1000
3
//cada processo P executa:
soma_parcial[P]=0;
for(i=elementos_por_processador*P; i<elementos_por_processador*(p+1);i++)
	soma_parcial[P]+=A[i];
//Redução  somar as somas parcias em um resultado final
half=processadores;
do {
	synch() //esperar que a soma parcial anterior termine
	if((half%2!=0) && (P==0))
		soma_parcial[0]+=soma_parcial[half-1] 
		//quando half é impar o processador 0 acumula o último elemento
	half=half/2;
	if (P<half)
		soma_parcial[P]+=soma_parcial[P+half];
while(half!=1)
3
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
3
Exemplo (10 processadores e 100 números)
4
0 9
10 19
20 29
30 39
40 49
50 59
60 69
7079
80 89
90 99
P0
P1
P2
P3
P4
P5
P6
P7
P8
P9
Vetor A
0
1
2
3
4
5
6
7
8
9
somas_parciais – primeiro loop
P0
P1
P2
P3
P4
0
1
2
3
4
somas_parciais 
segundo loop
primeira iteração 
4
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
4
Exemplo (10 processadores e 100 números)
5
P0
P1
somas_parciais 
segundo loop
segunda iteração 
Half é ímpar!
P0 acumula
somas_parciais[4]
também
P0
0
0
1
0
1
2
3
4
somas_parciais 
segundo loop
terceira iteração 
5
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
5
Problema da cache
Cada processador possui a sua cache
Cópias de dados da memória são mantidas na cache de cada processador
O que acontece quando um processador atualiza um dado na cache?
Outro processador possui uma cópia deste dado
Podemos fazer write-through  muito lento
Precisamos de um protocolo de coerência de cache
6
Processador
Cache
Processador
Cache
Processador
Cache
...
...
Barramento único
Memória
I/O
6
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
6
Snooping
Os controladores de cada cache monitoram (snoop) o barramento para determinar se elas possuem uma cópia do bloco compartilhado.
Múltiplas cópias não são um problema na leitura, mas um processador deve ter acesso exclusivo para escrita. Além disso, um processador deve ter a cópia mais recente quando estiver lendo um valor. Sendo assim, todos os processadores precisam pegar os novos valores depois de uma escrita.
A consequência de uma escrita é atualizar ou invalidas as cópias
Os bits de status da cache são expandidos para suportar protocolos de snooping e usados para monitorar atividades do barramento. 
Em um miss de leitura, todas as caches verificam se possuem uma cópia do bloco requisitado e tomam a ação apropriada, como suprir o dado faltante. 
De forma similar, em uma escrita, todas as caches verificam se possuem uma cópia do dado e invalidam ou atualizam suas cópias.
7
7
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
7
Snooping
Máquinas comerciais usam write-back e invalidação  múltiplos leitores e um escritor.
Influência do tamanho do bloco na coerência – broadcast mais caro para blocos maiores – false sharing
8
Processador
Cache tag and data
...
...
Barramento único
Memória
I/O
Snoop tag
Processador
Cache tag and data
Snoop tag
Processador
Cache tag and data
Snoop tag
8
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
8
Exemplo de protocolo
Estados de um bloco
Shared (read only) – bloco não foi escrito e pode ser compartilhado
Modified (read/write) – Bloco sujo (dirty) – foi escrito e NÃO pode ser compartilhado
Invalid: Bloco não tem um dado válido
Vamos separar em 2 diagramas de estados com estímulos do processador e barramento – na verdade só existe um diagrama.
Blocos que não estão na cache são considerados inválidos
9
9
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
9
Exemplo de protocolo
10
No caso de um miss de leitura, se o bloco lido for substituir um bloco sujo (vítima), deve haver uma escrita do bloco sujo na memória
Caches em outros processadores monitoram o miss de leitura e verificam se possuem uma cópia do bloco no estado modificado, é feito o write-back e o bloco passa ao estado de inválido
O bloco que causou o miss de leitura é lido (já com o valor atualizado pelo outro processador)
10
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
10
Exemplo de protocolo
11
Um hit de escrita para um bloco modificado na resulta em ação nenhuma.
Um hit de escrita para um bloco compartilhado causa o envio de uma mensagem de invalidação para as caches de todos os processadores que tiverem uma cópia deste bloco e torna modificado o bloco na cache do processador que gerou o hit de escrita
11
Morgan Kaufmann Publishers
19 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
11