Códigos de Correção de Erro Memória Cache

Prévia do material em texto

Organização e Arquitetura de Computadores 
Aula 04 
 
Prof. Harlei Miguel de Arruda Leite 
Sumário 
• Códigos de Correção de Erro 
• Memória Cache 
• Homework 
• Referências 
Códigos de Correção de Erro 
• Introdução 
 
– Memórias de computador podem cometer erros de vez em quando devido a 
picos de tensão na linha elétrica, raios cósmicos ou outras causas. Para se 
resguardar contra esses erros, algumas memórias usam códigos de detecção 
de erros ou códigos de correção de erros. 
 
– Quando são usados, bits extras são adicionados a cada palavra de memória 
de modo especial. Quando uma palavra é lida na memória, os bits extras são 
verificados para ver se ocorreu um erro. 
Códigos de Correção de Erro 
• Funcionamento 
 
– O que é um erro? 
 
• Suponha que uma palavra de memória consista em m bits de dados, aos quais 
serão adicionados r bits redundantes, ou de verificação. Seja o comprimento total 
n (isto é, n = m + r). Uma unidade de n bits que contém m dados e r bits de 
verificação costuma ser denominada uma palavra de código de n bits. 
 
• Dada duas palavras de código quaisquer, por exemplo, 10001001 e 10110001, é 
possível determinar quantos bits correspondentes são diferentes. Nesse caso, 3 
bits são diferentes. 
Códigos de Correção de Erro 
• Funcionamento 
 
– O que é um erro? 
 
• Para saber quantos bits são diferentes, basta calcular o ou exclusivo booleano bit 
por bit das duas palavras de código e contar o número de bits 1 no resultado. 
A B Saída 
0 0 0 
0 1 1 
1 0 1 
1 1 0 
Códigos de Correção de Erro 
• Funcionamento 
 
– O que é um erro? 
 
• O número de posições de bit nas quais as duas palavras de código diferem é 
denominado distância de Hamming. 
 
• Sua principal significância é que, se duas palavras de código estiverem separadas 
por uma distância de Hamming d, será preciso d erros de único bit para converter 
uma na outra. 
 
• Por exemplo, as palavras de código 11110001 e 00110000 estão a uma distância 
de Hamming 3 porque é preciso 3 erros de único bit para converter uma na outra. 
 
Códigos de Correção de Erro 
• Exercício: 
 
– Calcule a distância de Hamming das palavras de código abaixo: 
 
– 11100010 e 01000001 
– 00110011 e 11110001 
– 10100101 e 00110110 
Códigos de Correção de Erro 
• Funcionamento 
 
– Se uma leitura de memória aparecer com uma palavra de código inválida, o 
computador sabe que ocorreu um erro de memória. 
 
– A próxima figura é uma representação simples de um código de correção de 
erros para palavras de 4 bits. O diagrama de Venn da figura contém três 
círculos, A, B e C, que juntos formam sete regiões. Como exemplo, vamos 
codificar a palavra de memória de 4 bits 1100 nas regiões AB, ABC, AC, BC, 1 
bit por região (em ordem alfabética). 
Códigos de Correção de Erro 
• Codificação de 1100 
A 
B 
C 
1 1 
0 
0 
Códigos de Correção de Erro 
• Funcionamento 
 
– Em seguida, acrescentamos um bit de paridade a cada uma dessas três 
regiões vazias para produzir paridade par, como mostra a próxima figura. 
 
– No círculo A, temos os quatro números 0, 0, 1 e 1, cuja soma total é 2, um 
número par. 
 
– No círculo B, os números são 1, 1, 0 e 0, cuja soma total é 2, um número par. 
 
– Por fim, no círculo C, temos a mesma coisa. 
 
– Essa figura corresponde a uma palavra de código com 4 bits de dados e 3 bits 
de paridade. 
Códigos de Correção de Erro 
• Codificação de 1100 
 
A 
B 
C 
1 1 
0 
0 
0 
0 
1 
Códigos de Correção de Erro 
• Funcionamento 
 
– Agora, suponha que algo de ruim aconteça com o bit na região AC e ele mude 
de 0 para 1, conforme a próxima figura. Agora, o computador pode ver que 
os círculos A e C tem a paridade errada (ímpar). A única mudança de bit 
individual que pode corrigi-los é restaurar AC para zero, o que corrige o erro. 
Desse modo, o computador pode corrigir automaticamente erros de 
memória em único bit. 
Códigos de Correção de Erro 
• Codificação de 1100 
 
A 
B 
C 
1 1 
1 
0 
0 
0 
1 
Erro 
Códigos de Correção de Erro 
• Código de Hamming 
 
• Considerando o exemplo 0101 
 
• Primeira etapa: Encontrar os locais dos bits de verificação 
M1 M2 M3 M4 
X1 X2 0 X3 1 0 1 
1 2 3 4 5 6 7 
22 21 20 
Códigos de Correção de Erro 
• Código de Hamming 
 
• Segunda etapa: Encontrar os bits de verificações 
 
 
 
 
 
 M1 = 3 = 2+ 1 = X1 + X2 
 M2 = 5 = 4 + 1 = X3 + X1 
 M3 = 6 = 4 + 2 = X3 + X2 
 M4 = 7 = 4 + 2 + 1 = X3 + X2 + X1 
M1 M2 M3 M4 
X1 X2 0 X3 1 0 1 
1 2 3 4 5 6 7 
22 21 20 
Códigos de Correção de Erro 
• Código de Hamming 
 
• Segunda etapa: Encontrar os bits de verificações 
 
 
 
 
 
M1 = 3 = 2+ 1 = X1 + X2 
M2 = 5 = 4 + 1 = X3 + X1 
M3 = 6 = 4 + 2 = X3 + X2 
M4 = 7 = 4 + 2 + 1 = X3 + X2 + X1 
 
 
M1 M2 M3 M4 
X1 X2 0 X3 1 0 1 
1 2 3 4 5 6 7 
22 21 20 
X1= M1M2M4 
 0  1 
 1  1 = 0 
Códigos de Correção de Erro 
• Código de Hamming 
 
• Segunda etapa: Encontrar os bits de verificações 
 
 
 
 
 
 
M1 = 3 = 2+ 1 = X1 + X2 
M2 = 5 = 4 + 1 = X3 + X1 
M3 = 6 = 4 + 2 = X3 + X2 
M4 = 7 = 4 + 2 + 1 = X3 + X2 + X1 
M1 M2 M3 M4 
0 X2 0 X3 1 0 1 
1 2 3 4 5 6 7 
22 21 20 
X2= M1M3M4 
 0  0 
 0  1 = 1 
Códigos de Correção de Erro 
• Código de Hamming 
 
• Segunda etapa: Encontrar os bits de verificações 
 
 
 
 
 
M1 = 3 = 2+ 1 = X1 + X2 
M2 = 5 = 4 + 1 = X3 + X1 
M3 = 6 = 4 + 2 = X3 + X2 
M4 = 7 = 4 + 2 + 1 = X3 + X2 + X1 
 
 
M1 M2 M3 M4 
0 1 0 X3 1 0 1 
1 2 3 4 5 6 7 
22 21 20 
X3= M2M3M4 
 1  0 
 1  1 = 0 
Códigos de Correção de Erro 
• Código de Hamming 
 
• Segunda etapa: Encontrar os bits de verificações 
 
 
 
 
 
X1= M1M2M4 
X2= M1M3M4 
X3= M2M3M4 
 
 
X1 X2 M1 X3 M2 M3 M4 
0 1 0 0 1 0 1 
1 2 3 4 5 6 7 
22 21 20 
Códigos de Correção de Erro 
• Código de Hamming 
 
• Verificação 
 
 
 
 
 
X1= M1M2M4 
X2= M1M3M4 
X3= M2M3M4 
 
 
X1 X2 M1 X3 M2 M3 M4 
0 1 0 0 1 0 1 
1 2 3 4 5 6 7 
22 21 20 
P1 = 0 0 1 1 0 
P2 = 1 0 0 1 0 
P3 = 0 1 0 1 0 
= 0 é código correto 
Se o número de bits "1" da mensagem for 
impar adiciona-se um "1" no final da 
mensagem 
 
Se o número de bits "1" da mensagem for 
par é adicionado um "0" no final da 
mensagem 
Códigos de Correção de Erro 
• Código de Hamming 
 
• Verificação 
 
 
 
 
 
X1= M1M2M4 
X2= M1M3M4 
X3= M2M3M4 
 
 
X1 X2 M1 X3 M2 M3 M4 
0 1 0 0 1 1 1 
1 2 3 4 5 6 7 
22 21 20 
P1 = 0 0 1 1 0 
P2 = 1 0 1 1 1 
P3 = 0 1 1 1 1 
= 1 é código incorreto 
Erro 
110(2)=6(10) 
Códigos de Correção de Erro 
• Exercício 
 
– Fazer um exemplo de sua escolha 
Memória Cache 
• Introdução 
 
– Historicamente, as CPUs sempre foram mais rápidas do que as memórias. 
Com o passar dos anos, está diferença tem aumentado significativamente. 
Com memórias lentas, a CPU perde ciclos esperando operações de 
leitura/escrita. 
 
– Uma forma de evitar este problema é usando cache. A ideia básica de uma 
cache é simples: as palavras de memória usadas com mais frequência são 
mantidas na cache. Quando a CPU precisa de uma palavra, ela examina em 
primeiro lugar a cache. Somente se a palavra não estiver ali é que ela recorre 
a memória principal. 
 
– Se uma fração substancial das palavrasestiver na cache, o tempo médio de 
acesso pode ser muito resolvido. 
Memória Cache 
• Curiosidade 
 
– Os engenheiros sabem como construir memórias tão rápidas quanto as 
CPUs, mas para que executem a toda velocidade, elas têm de estar 
localizadas no chip da CPU (porque passar pelo barramento para alcançar a 
memória é uma operação muito lenta). Instalar uma memória grande no 
chip da CPU faz com que esta fique maior e, portanto, mais cara. Ainda que o 
custo não fosse uma questão a considerar, há limites de tamanho para um 
chip de CPU. 
Memória Cache 
• Introdução 
 
– Os programas não acessam a memória de forma totalmente aleatória. Se 
uma dada referência à memória for para o endereço A, é provável que a 
próxima estará na vizinhança de A. Exemplo: é provável que um programa de 
manipulação de matrizes fará muitas referências à mesma matriz antes de 
passar para outra coisa qualquer. 
 
– O princípio da localidade forma a base de todos os sistemas de cache. A ideia 
é que, quando uma palavra for referenciada, ela e algumas de suas vizinhas 
sejam trazidas da memória lenta para a cache, de modo que, na próxima vez 
em que ela for usada, ela possa ser acessada rapidamente. 
Memória Cache 
• Localização da memória cache 
Homework 
• Implementação 
 
– Implementar o código de Hamming 
 
• Leitura 
 
– Capítulo 2 (2.1 e 2.2) 
Referências 
• Tanenbaum, A. S.; Austin, T. Organização Estruturada de 
Computadores. 6ª Edição, Editora Pearson, 2013.