Codigos de Hamming - Detecção e Correção de Erros

1 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Prof Misael Morais moraiscguolcombr 20151 A vontade de vencer é importante mas a vontade de se preparar é vital httpsitesgooglecomsitemoraiscg PARTE 4 Prof Misael Morais moraiscguolcombr A vontade de vencer é importante mas a vontade de se preparar é vital httpsitesgooglecomsitemoraiscg Parte 5 A experiência é resultado da prática 2 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg 3 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Tipos de erro Falhas graves Defeito permanente Erros moderados não permanente Aleatório não destrutivo Causados por problema de alimentação presença de partículas alfas Lógica de deteção e correção de erro código Hamming 3 4 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg 1 Qual carta foi virada A ideia de Hamming 2Coloco uma fileira extra Richard W Hamming 19151998 5 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mudou uma carta Qual Isto é uma algoritmo real de detecção e correção de erro PARIDADE EM BLOCOS 6 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Sabese qual linha errada mas não qual carta PARIDADE SIMPLES 7 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Distância de Hamming É o número de bits diferentes entre duas cadeias Ex Sem erros distância 0 Um erro distância 1 Dois erros distância 2 8 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Código de correção de erro Sendo 2K 1 M K 9 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Código de correção de erro de Hamming Exemplo 10 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg 11 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Posição do bit 12 11 10 9 8 7 6 5 4 3 2 1 Nr da posição 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001 Bit de dados D8 D7 D6 D5 D4 D3 D2 D1 Bit de verificação C8 C4 C2 C1 C1 D1 D2 D4 D5 D7 C2 D1 D3 D4 D6 D7 C4 D2 D3 D4 D8 C8 D5 D6 D7 D8 12 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg 13 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Memória Em sistema digital é um conjunto de células ou dispositivos capaz de armazenar informações binária Conceito Unidade básica de armazenamento Bit Binary digIT 14 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Hierarquias de memória no Computador Hierarquia de memória de cinco níveis Interna Externa Custo acesso Custo acesso Maior capacidade Menor capacidade 15 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Classificação de Memória Quanto sua localização Memória Interna Memória Externa 16 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Principal de acesso mais rápido mas de capacidade mais restrita Armazena informações temporariamente durante um processamento realizado pela UCP Secundária de acesso mais lento mas de capacidade bem maior Armazena grande conjunto de dados que a memória principal não suporta Memória Interna Categoria 17 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Memória Externa Disco magnético Óptica CDROM CDWritable WORM CDRW DVD Fita magnética Categoria 18 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Características fundamentais das memórias Localização Processador Interna e Externa Organização Palavras Unidades endereçáveis Unidade de transferência veja capacidade Palavra e unidades endereçáveis Capacidade Tamanho da palavra e número de palavras Transferência Palavra interna largura do barramento e Bloco normalmente externa Método de acesso Seqüencial Direto Aleatório e Associativo Desempenho terminologia principais parâmetros Tempo de acesso latência tempo de ciclo taxa de transferência Tecnologia Semicondutor magnética ótica magnéticaótica Características físicas Volátil nãovolátil apagável nãoapagável 19 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg OrganizaçãoCapacidadePalavra Tamanho da Palavra quantidade de bits lidos ou escritos paralela ou simultaneamente Ex palavra de 8 bits 16 bits 64 bits Capacidade numero total de bits ou de palavras que a memória pode armazenar Número total de palavras X tamanho da palavra 16K X 8 16K Bytes 16 x 1024 x 8 bits 16384 palavras de 8 bits 31072 bits Organização disposição ou arranjo com que a memória é constituída EX 16K X8 8K X 16 mesma capacidade organizações diferentes Densidade capacidade de armazenamento de bits no mesmo espaço Endereço Conjunto de bits que identificam a posição de memória onde está armazenada uma palavra Escrita operação de colocação de uma palavra conteúdo em uma posição endereço especificado substituindo a anterior Leitura operação de recuperação da informação armazenada conteúdo de uma determinada posição endereço 20 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg OrganizaçãoCapacidadePalavra Memórias com Endereçamento Explícito A palavra lida ou escrita na memória é associada a um numero inteiro de 0 a N1 o endereço Se m é linhas de dados entradasaída e K número de linhas de endereço então a memória terá cada palavra com m bits e 2K palavras ou endereços e arranjo N x m onde N 2K Memórias com Endereçamento Implícito a palavra a ser lida ou escrita é implicitamente especificada 21 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização em detalhes Um chip de 16 Mbits pode ser organizado como 1M de palavras de 16 bits Um sistema de um bit por chip tem 16 lotes de chip de 1 Mbit com bit 1 de cada chip no chip 1 e assim por diante Um chip de 16 Mbits pode ser organizado como um array de 2048 x 2048 x 4 bits Reduz número de pinos de endereço Multiplexa endereço de linha e endereço de coluna 11 pinos para endereçar 2112048 Aumentar um pino dobra o intervalo de valores de modo que a capacidade multiplica por 4 21 22 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização 22 Dois modos de organizar um chip de memória de 4 Mbits 23 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização 2 23 CS 24 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização 4 24 É o arranjo físico dos bits para formar palavras Três maneiras de organizar uma memória de 96 bits 25 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Ordenação na organização 25 a Memória big endian b Memória little endian ordem que os dados serão interpretados Os bytes são guardados por ordem decrescente do seu peso numérico em endereços sucessivos da memória extremidade maior primeiro ou bigendian Os bytes são guardados por ordem crescente do seu peso numérico em endereços sucessivos da memória extremidade menor primeiro ou littleendian Dado Dado 26 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização em módulos 1 26 Arranjos de 256Kbytes Endereços Dados 27 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização em módulos 2 27 28 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Métodos de acesso Seqüencial Começa no início e lê em ordem Tempo de acesso depende da localização dos dados e local anterior Por exemplo fita Direto Blocos individuais possuem endereço exclusivo Acesso saltando para vizinhança mais busca sequencial Tempo de acesso depende da localização e local anterior Por exemplo disco 29 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Hierarquia de memória Registradores Na CPU Memória interna ou principal Pode incluir um ou mais níveis de cache RAM Memória externa Armazenamento de apoio 30 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Desempenho memória Tempo de acesso TA Tempo entre apresentar o endereço e obter os dados válidos Tempo de ciclo de memória TN Tempo que pode ser exigido para a memória se recuperar antes do próximo acesso Tempo de ciclo é acesso recuperação Taxa de transferência R Taxa em que os dados podem ser movidos TNTAnR 31 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Tipos Físicos Tecnologias Semicondutor RAM ROM Magnético Disco e fita Óptico CD e DVD Outros Estática Dinâmica 32 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Tipos de memória de semicondutor Tipo Categoria Apagamento Escrita Volatilidade RAM Leitura e escrita Elétrico Elétrico Volátil ROM Apenas Leitura Não possível Máscara Nãovolátil PROM Elétrico EPROM Luz UV Flash Elétrico EEPROM Elétrico 33 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Tipos de memória RAM 1 RAM Dinâmica DRAM Esta é uma memória baseada na tecnologia de capacitores e requer a atualização periódica do conteúdo de cada célula do chip consumindo assim pequenas quantidades de energia no entanto possui um acesso lento aos dados Uma importante vantagem é a grande capacidade de armazenamento oferecida por este tipo de tecnologia RAM Estática SRAM É uma memória baseada na tecnologia de transistores e não requer atualização dos dados Consome mais energia o que gera mais calor comparandose com a memória dinâmica sendo significativamente mais rápida É frequentemente usada em computadores rápidos Possui uma capacidade de armazenamento bem menor que a memória dinâmica Requerem energia para reter a informação armazenada 34 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Tipos de memória RAM 2 Vantagens Desvantagens RAM Dinâmica Barata Baixo Consumo Alta Densidade Necessita de Atualização Lenta RAM Estática Rápida Não necessita de atualização Mais cara Consome Mais Energia Baixa Densidade 35 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Memória DRAM Bits armazenados com carga em capacitores As cargas vazam Precisa de renovação mesmo se alimentada Construção mais simples Menor por bit Mais barata Precisa de circuitos de refresh Mais lenta Memória principal Dispositivo basicamente analógico Nível de carga determina o valor 35 36 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Características físicas Deterioração Volatilidade externa nãovolátil é chamada memória secundária ou auxiliar Apagável Consumo de energia 37 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Refreshing DRAM Circuito de refresh incluído no chip Desabilita chip Conta por linhas Lê e escreve de volta Leva tempo Atrasa o desempenho aparente 37 38 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Operação memória DRAM Linha de endereço ativa quando bit é lido ou escrito Chave de transistor fechada corrente flui Escrita Voltagem na linha de bit Alta para 1 baixa para 0 Depois sinaliza linha de endereço Transfere carga ao capacitor Leitura Linha de endereço selecionada Transistor liga Carga do capacitor alimentada por linha de bit para amplificador comparar Compara com valor de referência para determinar 0 ou 1 Carga do capacitor deve ser restaurada 38 39 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg DRAM 16Mb 4M x 4 Esquema 40 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg SRAM versus DRAM Ambas voláteis É preciso energia para preservar os dados Célula dinâmica Mais simples de construir menor Mais densa Mais barata Precisa de refresh Maiores unidades de memória Estática Mais rápida Cache 41 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Read Only Memory ROM Armazenamento permanente Não volátil Microprogramação Subrotinas de biblioteca Programas do sistema BIOS Tabelas de função 41 42 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Tipos de ROM Gravada durante a fabricação Muito cara para pequenas quantidades Programável uma vez PROM Precisa de equipamento especial para programar Lida na maioria das vezes Erasable Programmable EPROM Apagada por UV Electrically Erasable EEPROM Leva muito mais tempo para escrever que para ler Memória flash Apaga memória inteira eletricamente 42 43 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Barramento da unidade de memória Memória formada por N palavras de um mesmo tamanho Cada palavra possui um único endereço 01N1 Uma palavra pode ser lida ou escrita na memória Recebe e envia sinais de dados Recebe sinais de endereços Recebe sinais de controle Ler read Escreve write Temporização timming 43 44 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Barramento da unidade de memória 44 Memória N palavras Dados Dados Endereço Leitura Escrita 0 N1 Contrl 45 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Decodificação de endereço 1 45 Localização de EPROM RAM e Porta ES em nosso espaço de endereço de 64 KB 46 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Decodificação de endereço 2 46 Decodificação de endereço completo com ES mapeado na memória ES 47 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Decodificação de endereço 3 47 Decodificação parcial de endereço com ES mapeado na memória 48 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Principio de operação da memória Resumo Selecionar o endereço Selecionar uma operação de leitura ou escrita Fornecer os dados para serem escritos Manter os dados de saída vindo da memória Habilitar e desabilitar a memória 48 Memória 32x4 A4 A3 A2 A1 A0 D3 D2 D1 D0 Entrada de endereço Entradasaída de dados MSB LSB MSB LSB RW CS ou ME Comando de leituraescrita Habilitação de memória 49 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Ciclos de Memória a Leitura b Escrita twc intervalo de duração do ciclo de escrita tas tempo para estabilização do barramento de endereços antes de habilitar a RAM tah intervalo necessário para que o barramento de endereços permaneça estável tw tempo de escrita onde CS e W R ficam em BAIXO tds tempo que os dados devem ser mantidos na entrada antes da desabilitação de CS e W R tdh tempo que os dados devem ser mantidos na entrada depois da desabilitação de CS e W R trc intervalo de duração do ciclo de leitura tacc tempo de acesso à RAM tco tempo que a saída da RAM leva para sair de alta impedância e ter um dado válido tod tempo decorrido entre a desabilitação da RAM e o instante que as saídas da RAM vão para alta impedância 50 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Empacotamento 1 50 CL tRCD tRP tRAS CMD Clock máximo Capacidade Taxa de transferencia em MBs Memória da Corsair 51 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Empacotamento 2 51 52 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg SDR DIM DDR DDR2 DDR3 Empacotamento 3 Transmite 2 dados por ciclo de clock Transmite 4 dados por ciclo de clock Transmite 8 dados por ciclo de clock DDRDouble Data Rate 53 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Gerenciamento de memória por segmentação no processador da Intel Segmento uma área de memória Offset um endereço dentro do segmento Endereço lógico endereço efetivo Endereço físico 53 54 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg 55 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Memória Cache CPU Registradores Cache Interna Memória principal Cache Pequena quantidade de memória rápida Fica entre a memória principal normal e a CPU Pode estar localizada no chip da CPU ou módulo Externa Dispositivo de massa O cache localizase logicamente entre a CPU e a memória principal Fisicamente há vários locais onde ela pode ser colocada 56 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Memória cache e principal 57 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Operação da cache visão geral CPU requisita conteúdo do local de memória Verifica se os dados estão em cache Se estiverem apanha da cache rápido Se não lê bloco solicitado da memória principal para a cache Depois entrega da cache à CPU Cache inclui tags para identificar qual bloco da memória principal está em cada slot da cache 58 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Lógica de funcionamento 59 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Então você quer velocidade É possível montar um computador que usa apenas RAM estática veja adiante Este seria muito rápido Este não precisaria de cache Como você pode manter o cache em cache Isso sairia muito caro 60 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Resumo Memória Cache Idéia básica manter no Cache as palavras mais usadas pelo processador Se a maior parte dos acessos for satisfeita pelo Cache o tempo médio de acesso será próximo do tempo de acesso ao Cache que é pequeno 61 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Resumo Memória cache Princípios fundamentais Memória pequena e rápida Situada entre a CPU e memória principal Pode está montada na CPU ou fora 62 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Outros conceitos Memória Cache Falha de acesso à Cache Quando uma palavra procurada não estiver no Cache a linha correspondente é trazida da memória principal Cache unificada instruções e dados usam a mesma Cache Mais simples de projetar Caches divididas arquitetura Harvard utiliza uma Cache para instruções e uma Cache para dados Permite paralelizar a busca dedados e instruções em processadores pipeline Como as instruções não são modificadas o Cache de instruções não precisa ser atualizado na memória principal Estrutura da Cache em níveis Cache Primária dentro do chip Cache Secundária fora do chip mas no mesmo invólucro Cache Terciária totalmente dissociada da CPU 63 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Arquitetura de cache harvard Processador Cache de instruções Cache de dados Memória principal 64 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Cache lógica e física 65 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Taxa de acertos h onde k é número de referências a uma determinada palavra Tempo médio de acesso t Onde m tempo de acesso à memória principal c tempo de acesso à Cache h Taxa de acertos a memória cache Está na cache hits Não está na cache miss Memória Cache h k1k t ch 1 hcm 66 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Tempo médio de acesso t a uma posição de memória é dada por Onde m tempo de acesso à memória principal c tempo de acesso à Cache h Taxa de acertos a memória cache Está na cache hits Não está na cache miss Memória Cache t ch 1 hcm 67 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Entendendo Projeto de cache Endereçando Tamanho Função de mapeamento Algoritmo de substituição Política de escrita Tamanho de bloco Número de caches 68 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Considerações a memória cache Onde fica a cache Entre processador e unidade de gerenciamento de memória virtual Entre MMU e memória principal Cache lógica cache virtual armazena dados usando endereço virtual Processador acessa cache diretamente não através da cache física Acesso à cache mais rápido antes da tradução de endereço da MMU Endereços virtuais usam o mesmo espaço de endereços para diferentes aplicações Deve esvaziar cache a cada troca de contexto Cache física armazena dados usando endereços físicos da memória principal 69 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Elementos do análise de memórias cache Tamanho Função de mapeamento Direto Associativo Associativo por conjunto Algoritmo de substituição FIFO aleatório menos usado Política de escrita Quantidade de memórias cache 70 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Tamanho Custo Quanto mais cache mais caro Velocidade Mais cache é mais rápido até certo ponto Comprimento da linha é o tamanho do bloco 71 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento direto 72 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento direto Cada bloco de memória principal mapeado apenas para uma linha de cache Ou seja se um bloco está na cache ele deve estar em um local específico 73 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Direto 74 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Direto 75 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Direto 76 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Direto 77 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Direto 78 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Direto Exemplo de uma cache com 1024 210 linhas com palavra de 32 bits 79 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Direto Passos 80 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Mapeamento Direto 81 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Mapeamento Direto Como fica o conteúdo da cache depois desta sequencia de acessos à memória Assumir cache inicialmente vazia 0000 0010 0110 0000 1000 0000 82 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Cont 83 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Cont 84 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Cont 85 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Cont 86 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Cont 87 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Cont 88 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exercício Mapeamento Direto 89 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplos Resposta 90 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Direto Transferência Transferência de Blocos linha com capacidade maior entre níveis de memória Exemplo Memória de 32 bits de endereço e dados de 8 bits 4Giga Byte e cache de 1024 linhas de 32 Bytes 91 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 92 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 0 0 0 0 93 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 0 0 0 0 94 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 0 0 0 0 95 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 0 0 0 0 96 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 0 97 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 98 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 0 99 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 0 100 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exercício Mapeamento Direto CACHE MAMÓRIA PRINCIPAL 0 101 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exercício Resposta CACHE MAMÓRIA PRINCIPAL 0 102 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Dever de Casa 103 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Conclusões e Questões 104 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Anexo Tabela de conversão de endereçamento de memória 22 4 23 8 24 16 25 32 26 64 27 128 28 256 29 512 210 1024 1 KB 211 2048 2 KB 212 4096 4 KB 220 1048576 1 MB 221 2097152 2 MB 222 4194304 4 MB 230 1073741824 1 GB 231 2147483648 2 GB 232 4294967296 4 GB 233 8589934592 8 GB 105 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização da memória com mapeamento direto 106 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo de mapeamento direto cache Memória principal de 16 MBytes Rótulo Rótulo Dados Nr da linha Parte do endereço Dados Memória cache de 16 K linhas 8bits 14bits 2bits 107 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Estrutura do mapeamento direto cache 32 bit de endereço 6 bit para identificar a palavra blocos de 64 bytes 26 bit para bloco identificando 16 bit rótulo 2610 10 bit para linha slot Não existe dois blocos do mesmo conjunto na cache mesmo rótulo mais de uma vez na cache É checado o conteúdo do cache para localizar a linha e o rótulo 16 bits 10 bits 6 bits Rótulo tag Linha Palavra 108 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Resumo 109 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento associativo 110 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento Associativo 111 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Associativo Memória Principal Cache Tag 0000 0010 0110 0000 1000 00000101 Endereço 4 bits 16 posições Tag 4 bits 112 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Associativo Memória Principal Cache Tag 0000 0010 0110 0000 1000 00000101 Preenche linha 00 da cache Miss 0000 AAAA 113 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Associativo Memória Principal Cache Tag 0000 0010 0110 0000 1000 00000101 Preenche linha 01 da cache Miss 0000 AAAA 0010 BBBB 114 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Associativo Memória Principal Cache Tag 0000 0010 0110 0000 1000 00000101 Preenche linha 10 da cache Miss 0000 AAAA 0010 BBBB 0101 EEEE 115 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Associativo Memória Principal Cache Tag 0000 0010 0110 0000 1000 00000101 Preenche linha 10 da cache Hit 0000 AAAA 0010 BBBB 0101 EEEE 116 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Associativo Memória Principal Cache Tag 0000 0010 0110 0000 1000 00000101 Preenche linha 11 da cache Miss 0000 AAAA 0010 BBBB 0101 EEEE 1000 DDDD 117 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Associativo Memória Principal Cache Tag 0000 0010 0110 0000 1000 00000101 Preenche linha 11 da cache Hit 0000 AAAA 0010 BBBB 0101 EEEE 1000 DDDD 118 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento Associativo Memória Principal Cache Tag 0000 0010 0110 0000 1000 0000 0101 Linha 01 da cache substituida Miss 0000 AAAA 0101 EEEE 0101 EEEE 1000 DDDD Total 5 Misses e 2 Hits 119 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Substituição na Cache 120 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento associativo por bloco Memória Principal Cache Tag Endereço 6 bits 64 posições Tag 4 bits bloco 2 bits 121 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exemplo Mapeamento associativo por bloco Memória Principal Cache Tag 122 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento associativo estrutura de endereço Tag de 22 bits armazenado a cada bloco de 32 bits de dados Compara campo de tag com entrada de tag na cache para procurar acerto 2 bits menos significativos do endereço identificam qual word de 16 bits é exigida do bloco de dados de 32 bits Ex Endereço Tag Dados Linha de cache FFFFFC 3FFFFF 24682468 3FFF Tag 22 bit Palavra 2 bit 123 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização da memória com mapeamento associativo 124 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Estrutura do mapeamento totalmente associativo cache 125 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Resumo do mapeamento associativo Tamanho do endereço s w bits Número de unidades endereçáveis 2sw words ou bytes Tamanho do bloco tamanho de linha 2w palavras ou bytes Número de blocos na memória principal 2sw2w 2s Número de linhas na cache indeterminado Tamanho da tag s bits 126 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exercício Endereço de 28 bits 256 Mega 25 bits Tag 3 bits 127 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Exercício Das afirmações a seguir sobre memoria cache são verdadeiras 128 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Conclusões 129 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento associativo em conjunto É um meiotermo entre a técnica direta e associativa Cache é dividida em uma série de conjuntos Cada conjunto contém uma série de linhas Determinado bloco é mapeado a qualquer linha em determinado conjunto ExBloco B pode estar em qualquer linha do conjunto i Ex 2 linhas por conjunto Mapeamento associativo com 2 linhas Determinado bloco pode estar em uma de 2 linhas em apenas um conjunto 130 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Organização da memória com mapeamento associativo por conjunto 131 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Mapeamento associativo em conjunto Exemplo Memória cache de 32KB de capacidade constituída de linhas de 8 bytes e conjunto de 4 A MP é de 16MBytes Qual o total de bits da cache 132 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Estrutura do mapeamento associado por conjunto 133 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Técnicas de atualização do cache Escrita direta write though Contra escrita write back Sempre que houver uma escrita o controlador atualiza o cache e em seguida a memória principal Quando houver uma escrita ela é atualizada apenas no cache e só escrita na memória principal quando a posição do cache for requisitada 134 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Política de escrita Não deve sobrescrever bloco de cache a menos que a memória principal esteja atualizada Múltiplas CPUs podem ter caches individuais ES pode endereçar memória principal diretamente 135 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Writethrough Todas as escritas vão para a memória principal e também para a cache Múltiplas CPUs podem monitorar o tráfego da memória principal para manter a cache local à CPU atualizada Muito tráfego Atrasa as escritas Lembrese de caches writethrough falsos 136 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Writeback Atualizações feitas inicialmente apenas na cache Bit de atualização para slot de cache é definido quando ocorre a atualização Se o bloco deve ser substituído escreve na memória principal apenas se o bit atualizado estiver marcado Outras caches saem de sincronismo ES deve acessar a memória principal através da cache 15 das referências de memória são escritas 137 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Obs Blocos maiores Reduzem número de blocos que cabem na cache Dados sobrescritos pouco depois de serem buscados Cada palavra adicional é menos local de modo que é menos provável de ser necessária Nenhum valor ideal definitivo foi descoberto 8 a 64 bytes parece ser razoável Para sistemas HP 64 e 128 bytes mais comum 138 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Algoritmos de substituição Mapeamento direto Sem escolha Cada bloco mapeado apenas a uma linha Substitui essa linha 139 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Algoritmos de substituição Associativa e associativa em conjunto Algoritmo implementado no hardware velocidade Least Recently Used LRU Ex na associativa em conjunto com 2 linhas Qual dos 2 blocos é LRU First In First Out FIFO Substitui bloco que está na cache há mais tempo Least Frequently Used LFU Substitui bloco que teve menos acertos Aleatório 140 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Algoritmo de substituição LRU Menos recentimento usado FIFO FLU Menos frequentemente usado 141 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Caches unificadas versus separadas Uma cache para dados e instruções ou duas uma para dados e uma para instruções Vantagens da cache unificada Maior taxa de acerto Equilibra carga entre buscas de instrução e dados Apenas uma cache para projetar e implementar Vantagens da cache separada Elimina disputa pela cache entre a unidade de buscadecodificação de instrução e a unidade de execução Importante no pipeline de instruções 142 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Format ST506 Gap1 Id Gap2 Data Gap3 Gap1 Id Gap2 Data Gap3 Track Sync Byte Head Sector CRC Sync Byte Data CRC 143 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Disco SCSI Alguns dos possíveis parâmetros SCSI 144 Prof Misael Morais moraiscguolcombr httpsitesgooglecomsitemoraiscg Formato de um bloco do CDROM 00 00 FF x 10 Min Sec Sector Mode Data Layered ECC 12 byte Sync 4 byte Id 2048 byte 288 byte 2352 byte Mode 0blank data field Mode 12048 byte dataerror correction Mode 22336 byte data