Sistemas de Memória
Cache em
Multiprocessadores
Prof. Dr. Norian Marranghello
Grupo 11
Jarbas de Freitas Peixoto
Anderson Kenji Ono
Tópicos Abordados
•
Introdução
•
Estruturas de Memórias Cache
•
Protocolos de Coerência
•
Protocolos baseados em Software
•
Protocolos baseados em Hardware
•
Protocolos de Diretório
•
Protocolos Snoopy (Protocolos Espiões)
Introdução
Multiprocessadores de Memória Compartilhada
• Memória compartilhada acessada através de um subsistema de
comunicação
P1
P2
P3
Barramento
Memória Compartilhada
Pn
Introdução
Multiprocessadores de Memória Compartilhada
Vantagens:
• Baixo custo de implementação
• Modelo de programação simples (permite fácil desenvolvimento de
software paralelo)
Desvantagens:
• Competição pela utilização de recursos compartilhados
• Aumento da latência média de acesso à memória compartilhada
Estruturas de Memória Cache
Objetivo:
• Minimizar a diferença de velocidade entre a CPU e o sistema de
memória
Funcionamento:
• Princípio da localidade
• Transferência da parte relevante das informações sobre o processo em
execução para a memória cache
Tipos de Memória Cache em
Multiprocessadores
•
Caches Compartilhadas
Reduzem o tempo médio de acesso à memória, mas não conseguem
diminuir a disputa por recursos compartilhados
Caminho de dados compartilhado
P1
Processadores
P2
P3
Pn
Switch
Barramento
Memória Compartilhada
CC
Cache
Compartilhada
Tipos de Memória Cache em
Multiprocessadores
•
Caches Privadas
Satisfazem a maioria de referências à memória localmente, eliminando
a necessidade de acesso a memória compartilhada
P1
P2
P3
Pn
CP
CP
CP
CP
Barramento
Memória Compartilhada
Processadores
Caches Privadas
Problema de Coerência da
Cache
•
Vários processadores com módulos de memória cache individuais
•
Múltiplas cópias do mesmo dado em diferentes caches simultaneamente
•
Processadores habilitados a atualizar suas cópias livremente
Solução:
•
Adotar uma estrutura que permita o gerenciamento das informações
dispersas
Inconsistência de Dados
Causas:
• Compartilhamento de dados que podem ser modificados
• Migração de processos
• Operações de Entrada/Saída
Sistema Coerente
• Todas as leituras por qualquer processador retornam o valor produzido
pela última operação de escrita, independente de qual processador
realizou esta operação
Protocolos de Coerência
•
Métodos que definem o conjunto de operações de acesso a memória
compartilhada, prevenindo inconsistências entre caches
Classes de Protocolos de Coerência em Multiprocessadores
•
Protocolos baseados em Software
•
Protocolos baseados em Hardware
Protocolos Baseados em
Software
• Características
• Vantagens
• Desvantagens
Baseados em Software
• Características
- Soluções estáticas ou preventivas
- Tratamento da coerência
- programador, compilador ou SO;
- soluções em tempo de compilação.
- Coerência
Evitar existência de cópias inconsistentes de dados nos
módulos de memória cache;
Permite a cópia dos dados quando estes não estão sendo
compartilhados.
Baseados em Software
O compilador tem que ser capaz de analisar e identificar, no programa,
cada variável que está sendo compartilhada. E o momento em que se
pode fazer cópias dessas variáveis na cache.
Logo se tem:
Variáveis possíveis de cópia;
Variáveis não possíveis de cópia.
Baseados em Software
Marcação das variáveis e invalidação das cópias:
O programa é dividido em unidades computacionais.
- Apenas leitura por diversos processos:
Nesse caso não há problema pois a informação pode ser
copiada em todos os módulos de memória desejados;
- Apenas leitura por vários processos e leitura/escrita por um único
processo:
Somente o processo de leitura/escrita pode copiar a variável,
mantendo uma politíca de atualização para manter os dados
consistentes;
Baseados em Software
- Leitura/escrita por um único processo:
Como o processo é único o dado pode ser copiado para a
cache;
- Leitura/escrita por diversos processos:
Não é permitido copiar a informação na cache.
Baseados em Software
• Vantagens
- Mais baratos
• Desvantagens
- Esquemas estáticos tornam esses métodos ineficientes
- Hit ratio é reduzido.
Protocolos Baseados em
Hardware
• Características
• Grupos
- Directory Protocols
- Snoopy Protocols
• Vantagens
• Desvantagens
Baseados em Hardware
• Características
- São mais populares e mais freqüentemente utilizados em
multiprocessadores comerciais.
Baseados em Hardware
• Características
- São mais populares e mais freqüentemente utilizados em
multiprocessadores comerciais.
• Grupos
- Directory Protocols (Protocolos de Diretório)
- Snoopy Protocols (Protocolos Espiões)
Baseados em Hardware
Directory Protocols (Protocolos de Diretório)
- Estes protocolos armazenam informações a respeito de
onde as cópias do bloco estão localizadas.
- Nomalmente a coerência é delegada a um Controlador
central.
Obs: Quando ocorre uma requisição dos controladores de cache local,
o controlador central analisa o diretório e fornece os comandos
necessários para transferir dados entre memória e caches ou entre
caches.
Baseados em Hardware
- Protocolos de Diretório
Estrutura do Bloco Replicada
Master Copy
E
P bits
Replicated Block
E V
Replicated Block
E V
Replicated Block
P : Número de processadores
V : Válido ou Inválido
E V
E : Exclusivo ou somente Leitura
Baseados em Hardware
- Protocolos de Diretório
Processador 1 requisita um bloco de dados para escrita:
Bloco
E V
1 1
P1
C1
CCL
P2
C2
P3
CCL
C3
CCL
Barramento
Controladores de Cache Local
Validação
Memória Compartilhada
V
Bloco Principal
0 – Desatualizado
1 – atualizado
0 1 0 0
Exclusividade
E P1 P2 P3
E
0 – Somente leitura
1 – Permisão p/ op. escrita
Baseados em Hardware
- Protocolos de Diretório
Processador 2 requisita o mesmo bloco de dados:
Bloco
E V
1 1
Bloco
E V
0 1
P1
C1
P2
C2
CCL
P3
CCL
C3
CCL
Barramento
Controladores de Cache Local
Memória Compartilhada
Bloco Principal
0 1 1 0
E P1 P2 P3
V
0 – Desatualizado
1 – atualiza
E
0 – Somente leitura
1 – Permisão p/ op. escrita
Baseados em Hardware
- Protocolos de Diretório
Processador 1 realiza uma operação de escrita invalida bloco do Proc 2:
Bloco
E V
1 1
Bloco
E V
0 0
P1
C1
P2
C2
CCL
P3
CCL
C3
CCL
Barramento
Controladores de Cache Local
Memória Compartilhada
Bloco Principal
0 1 1 0
E P1 P2 P3
V
0 – Desatualizado
1 – atualiza
E
0 – Somente leitura
1 – Permisão p/ op. escrita
Baseados em Hardware
- Protocolos de Diretório
Processador 2 busca o bloco atualizado na memória:
Bloco
E V
1 1
Bloco
E V
0 1
P1
C1
P2
C2
CCL
P3
CCL
C3
CCL
Barramento
Controladores de Cache Local
Memória Compartilhada
Bloco Principal
0 1 1 0
E P1 P2 P3
V
0 – Desatualizado
1 – atualiza
E
0 – Somente leitura
1 – Permisão p/ op. escrita
Baseados em Hardware
- Protocolos de Diretório
Processador 1 termina operação de escrita:
Bloco
E V
0 1
Bloco
E V
0 1
P1
C1
P2
C2
CCL
P3
CCL
C3
CCL
Barramento
Controladores de Cache Local
Memória Compartilhada
Bloco Principal
1 1 1 0
E P1 P2 P3
V
0 – Desatualizado
1 – atualiza
E
0 – Somente leitura
1 – Permisão p/ op. escrita
Baseados em Hardware
- Protocolos de Diretório
Processador 3 requisita o bloco para escrita:
Bloco
E V
0 0
P1
C1
CCL
Bloco
E V
0 0
Bloco
E V
1 1
P2
C2
P3
C3
CCL
CCL
Barramento
Controladores de Cache Local
Memória Compartilhada
Bloco Principal
0 1 1 1
E P1 P2 P3
V
0 – Desatualizado
1 – atualiza
E
0 – Somente leitura
1 – Permisão p/ op. escrita
Baseados em Hardware
- Protocolos de Diretórios
Conclusões:
- São Muito efetivos em sistemas de larga escala
que envolvem barramentos múltiplos ou redes de interconexão.
- Não Flexível em caso de expansão (diretórios
grandes)
- Garantir escalabilidade
- O uso de um ponto central e pelo overhead de
comunicação entre vários controladores de cache e o controlador
central torna-se uma desvantagem
Baseados em Hardware
- Protocolos Espiões (Snoopy Protocols)
Utiliza distribuição para tratar coerência.
São baseados nas ações de controladores de cache local e
suas informações de estado local sobre o dado na cache.
Duas políticas de escrita são normalmente aplicadas:
-Write Invalidate
- Write Update
Baseados em Hardware
- Write Invalidate
São protocolos de Invalidação.
Permitem múltiplos leitores mas apenas um escritor de cada
vez.
Cada escrita em um bloco compartilhado deve iniciar com
invalidação de todas as outras cópias do mesmo bloco.
Baseados em Hardware
- Write Invalidate (Invalidação)
Permitem múltiplos leitores mas apenas um escritor de cada
vez.
Cada escrita em um bloco compartilhado deve iniciar com
invalidação de todas as outras cópias do mesmo bloco.
- Write Update (atualização)
A palavra a ser escrita em um bloco compartilhado é
distribuída a todos os outros e caches contendo aquele bloco podem
atualizá-lo
Isso previne um estado de espera, mas aumenta tráfego.
Baseados em Hardware
- Protocolos Espiões
Conclusões:
Devido a ineficiência de performance para todos os tipos de
carqa de trabalho dos dois métodos. Existem protocolos que
combinam as duas políticas.
Eles iniciam com Broadcast de escritas, mas quando uma
longa seqüencia de escritas locais é encontrada ou prevista, o sinal de
invalidação do bloco é enviado.
Estas soluções procuram adaptar os esquemas de coerência
de maneira a melhorar a performance do sistema.