Aula19: Desempenho de SSM
Large-Scale MP
Sincronização
ARQUITETURA DE COMPUTADORES
DEPT. DE CIÊNCIA DA COMPUTAÇÃO - UFMG
Coerência de Caches
 Classificação de MR
em 3 C’s
 O que pode
acontecer em uma
cache coerente?
 Sharing miss
 False sharing
Time
P1
1
Write x1
2
3
Write x1
4
5
Read x2
P2
Read x2
Write x2
Extendendo Coerência de Caches para
Memórias Compartilhadas Distribuídas
 Ao contrário de memórias compartilhadas
centralizadas, não possuímos neste caso um
recurso centralizado que vê todas as transações
(bus)
 Não há meio de broadcast
 Não há maneira de serializar transações
 barramento funciona como meio de garantir serialização das
operações
 Técnicas
 Extender protocolos do tipo snoopy
 Protocolos baseados em diretórios
Snoopy Hierárquico
Maneira mais simples: hierarquia de
barramentos, coerência snoopy a cada
nível
Duas possibilidades
P
P
P
P
P
P
P
P
L1
L1
L1
L1
L1
L1
L1
L1
B1
B1
L2
L2
B2
Mem
B2
Main Mem
L2
L2
Mem
Hierarquias com Memória
Global
 Caches primárias:
P
P
P
P
L1
L1
L1
L1
B1
L2
L2
B2
Main Mem
 Alta performance (SRAM)
 B1 segue protocolo snoopy
básico
 Caches secundárias:
 Muito maiores que L1
(precisam manter
propriedade de inclusão)
 L2 funciona como filtro p/
B1 e L1
 L2 pode ser baseada em
tecnologia DRAM
Hierarquias com Memória
Global
Vantagens:
Misses na memória principal requerem
tráfego único para a raiz da hierarquia
Utilização de dados compartilhados não é
uma questão importante
Desvantagens:
Misses para dados locais também trafegam
na hierarquia
Memória em barramento global deve ser
intercalada para aumentar BW
Hierarquias Baseadas em
Clusters
P
P
P
P
L1
L1
L1
L1
B1
Mem
L2
L2
Mem
B2
 Memória principal é distribuída entre clusters
 Alocação de dados locais pode reduzir tráfego em barramento
global
 Reduz latência (acessos locais mais rápidos)
 Exemplos: Encore Gigamax
 L2 pode ser substituída por uma chave roteadora
baseada em tags com coerência
Resumo de Hierarquias
Vantagens:
Conceitualmente simples de se construir
(aplica-se snoopy recursivamente)
Pode-se reduzir hardware necessário ao se
combinar as funcionalidades
Desvantagens:
Gargalo de comunicação na direção da raiz
Latências podem ser grandes na direção da
raiz
Protocolos de Coerência
Baseados em Diretórios
 Protocolos do tipo snoopy não escalam bem
porque dependem de algum meio de broadcast
 Snoop hierarquico faz raiz se tornar um gargalo
 Mecanismos baseados em diretório escalam
bem
 Evitam broadcasts
 Mantém informação de todas as caches que possuem cópia
do bloco
 Utilizam mensagens ponto-a-ponto para manter coerência
Protocolo Baseado em
Diretório
P
P
Cache
Cache
 K processadores
 Para cada bloco de cache
na memória => k bits de
presença, 1 dirty-bit
Rede de Interconexão
Memória
Bits de presença
Diretório
Dirty
 Para cada bloco na cache
 Invalid
 Exclusive
 Shared
Estados
Shared: um ou mais processadores
possuem o bloco cached, e o bloco na
memória é atualizado
Invalid ou Uncached: nenhum
processador possui uma cópia do bloco
Exclusivo: um único processador possui
uma cópia do bloco
Protocolo Baseado em
Diretório
Message
Source Destination
Read miss
Cache
Dir
Write miss
Cache
Dir
Invalidate
Dir
R. Caches
Fetch
Dir
R. Caches
Fetch/Inv.
Dir
R. Caches
Data value reply
Dir
Cache
Data write back R.Cache
Dir
Contents
P,A
P,A
A
A
A
Data
A,Data
Protocolo (Cache)
Invalidade
Invalid
CPU read
CPU read hit
Read miss
Exclusive
CPU write hit
CPU read hit
Shared
CPU read miss
Send write miss
CPU write
Data write-back
Fetch invalidade
Send read miss message
CPU write miss
Data write-back
Write miss
Protocolo (Diretório)
Read miss
Data value reply
Sharers = {P}
Data value reply
Sharers = {P}
Write miss
Sharers = {}
Data write back
Uncached
Exclusive
Write miss
Fetch/Invalidate
Data value reply
Sharers = {P}
Shared
Read miss
Data value reply
Sharers += {P}
Organização de Diretórios
 Implementação dos diretórios na memória
(como o apresentado anteriormente)
 Apresenta problemas de escalabilidade
 Pode apresentar problemas de BW
 Implementação dos diretórios na cache (SCI)
 Listas encadeadas (simples ou duplo)
 Mantém em cada cache “link” do próximo
processador compartilhando bloco
 SCI utiliza listas duplamente encadeadas
 Precisamos agora da mensagem “desconectar da
lista” e “conectar à lista” (a última equivalente a um
MISS)
Sincronização
SSM: sequência de instruções capazes de
recuperar ou alterar valores atomicamente
LSM: latência pode adicionar problemas
de desempenho
Primitivas de Hardware
Atomic exchange
Test-and-set
Fetch-and-increment
Load-linked
Load-linked
try:
OR
LL
SC
BEQZ
MOV
R3,R4,R0
R2,0(R1)
R3,0(R1)
R3,try
R4,R2
Implementando fetch-andincrement com load-linked
try:
LL
DADDUI
SC
BEQZ
R2,0(R1)
R3,R2,#1
R3,0(R1)
R3,try
Implementando Locks com
Coerência de Cache
DADDU R2,R0,#1
lockit:
EXCH R2,0(R1)
BNEZ R2,lockit
lockit:
LD
R2,0(R1)
BNEZ R2,lockit
DADDUI R2,R0,#1
EXCH R2,0(R1)
BNEZ R2,lockit
Implementando Locks com
Coerência de Cache
lockit:
LL
BNEZ
DADDUI
SC
BEQZ
R2,0(R1)
R2,lockit
R2,R0,#1
R2,0(R1)
R2,lockit