Upload
internet
View
105
Download
1
Embed Size (px)
Citation preview
ARQUITETURA DE COMPUTADORESDEPT. DE CIÊNCIA DA COMPUTAÇÃO - UFMG
Aula19: Desempenho de SSMLarge-Scale MPSincronização
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 P21 Write x12 Read x23 Write x14 Write x25 Read 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
L1
P
L1
P
L2
L1
P
L1
P
L2
Main Mem
L1
P
L1
P
L2
L1
P
L1
P
L2Mem Mem
B1
B2 B2
B1
Hierarquias com Memória Global
Caches primárias: 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
L1
P
L1
P
L2
L1
P
L1
P
L2
Main Mem
B1
B2
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
L1
P
L1
P
L2
L1
P
L1
P
L2Mem Mem
B2
B1
Hierarquias Baseadas em Clusters
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
Cache
P
Cache
P
Rede de Interconexão
Memória Diretório
Bits de presença Dirty
K processadores
Para cada bloco de cache na memória => k bits de presença, 1 dirty-bit
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 ContentsRead miss Cache Dir P,AWrite miss Cache Dir P,AInvalidate Dir R. Caches A
Fetch Dir R. Caches AFetch/Inv. Dir R. Caches A
Data value reply Dir Cache DataData write back R.Cache Dir A,Data
Protocolo (Cache)
Invalid Shared
Exclusive
Send read miss message
CPU read
Invalidade
CPU read hit
CPU read missRead miss
CPU write
Send w
rite m
iss message
Fetch D
ata w
rite-
back
CPU read m
iss
Data writ
e-back, r
ead miss
CPU write missData write-backWrite miss
CPU write hitCPU read hit
Fet
ch in
valid
ade
Dat
a w
rite
-ba
ck
Sen
d w
rite
mis
sC
PU
writ
e
Protocolo (Diretório)
Uncached Shared
Exclusive
Data value replySharers = {P}
Read missRead missData value replySharers += {P}
Write
miss
Invalidate; S
harers
= {P};
data value reply
Read miss
Fetch, d
ata valu
e reply,
Sharers
+= {P}
Write missFetch/InvalidateData value replySharers = {P}
Dat
a w
rite
back
Sh
arer
s =
{}
Dat
a va
lue
rep
lyS
har
ers
= {
P}
Writ
e m
iss
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 R3,R4,R0
LL R2,0(R1)
SC R3,0(R1)
BEQZ R3,try
MOV R4,R2
Implementando fetch-and-increment com load-linked
try: LL R2,0(R1)
DADDUI R3,R2,#1
SC R3,0(R1)
BEQZ 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 R2,0(R1)
BNEZ R2,lockit
DADDUI R2,R0,#1
SC R2,0(R1)
BEQZ R2,lockit