O Acesso em Pormenor

Este artigo vai abordar a descrição em detalhe do que se passa dentro dos circuitos lógicos de uma Memória Cache nas suas diferentes situações de mapeamento. Não é uma descrição feita sob uma visão virada para aquilo que a Cache faz e a forma lógica como o faz, sem descer aos pormenores dos circuitos, como a que fizemos no artigo anterior. É sim uma descrição feita sob uma visão detalhada da constituição e forma de funcionamento  do que poderiam ser os circuitos lógicos  que  levam a Cache a fazer o que atrás descrevemos.

Esta introdução tem por fim prevenir aqueles que aqui cheguem sobre aquilo que aqui vão encontrar, para que só continuem conscientes do tipo de descrição que vão encontrar. Seria bom que continuassem, pois iriam aprofundar mais a experiência com o comportamento lógico das portas lógicas e dos circuitos pelas mesmas constituídos, mas seria desagradável fazerem-no sem saberem exatamente ao que vão.

Generalidades

A descrição que se segue vai ser apoiada nas figuras que se encontram mais à frente, em cada uma das situações de mapeamento. As notas  (x) nessas figuras serão referidas unicamente pelos seus números, sendo omitido o número da figura. Para poderem acompanhar a descrição sempre em presença da figura descrita devem tocar ou clicar nela para a ampliarem e  abrirem noutra janela..

Tudo na Cache é resolvido em hardware. É portanto importante imaginar a lógica  a implementar em circuitos, através da qual se pode a atingir o objetivo de conseguir selecionar um Byte específico dentro de uma Cache, usando unicamente o endereço na MP. Vamos fazer este exercício de lógica em relação aos diversos mapeamentos. O Bloco (linha) da nossa cache imaginária vai ter 8 bytes, ou 64 bits. Vamos dar-lhe só 4 linhas, para facilitar a compreensão da análise. A MP que serve a Cache será aquela que usámos no início do Capítulo anterior, com 4KB de dimensão.

Comecemos por ver os sinais que a MMU envia na consulta que faz à Cache:

• O endereço do valor que pretende, designado pelos bits A0 a A11 (12 bits para  4KB), que é colocado num registador de entrada (7).
• O sinal CS (Chip Select) , através do qual a MMU diz à cache a que pretende aceder: “Hei! É contigo que estou a falar.”
• Os sinais RD (ReaD), ativo a 0, quando pretende fazer uma leitura.
• O sinal WR (WRite), ativo a 0, quando pretende escrever um valor na cache.
• O sinal WRBL (WRite BLock), ativo a 0, quando pretende escrever um bloco que foi buscar a outro nível da cache ou à MP.
• O sinal WRVL (WRite VaLid bit). ativo a 0, quando pretende escrever o valor do bit de validade de um bloco da cache.

Seleção da Coluna

Os 3  bits de menor peso desse endereço, A0, A1 e A2, que definem o deslocamento, são ligados aos bits de seleção de um MUX de portas NAND (2), que coloca ativa a 0 uma só saída, a correspondente à coluna identificada por esses 3 bits. São 3 bits, porque só temos 8 (2³) bytes no bloco. Se tivéssemos por exemplo 64 (2⁶) bytes no Bloco teríamos de escolher os 6 bits de menor ordem.

As saídas das portas do MUX (2), vão ligar a portas AND onde a outra das entradas corresponde ao sinal WRBL, que é enviado de cada vez que um bloco for escrito em cache e vem da Unidade de Controlo (1). Quando WRBL estiver ativo (0) todas as portas AND devolvem 0. Se WRBL estiver inativo (1), só a porta selecionada pelo MUX (2) devolve 0. O objetivo deste estratagema é tornar todas as saídas do MUX (2) a 0 quando WRBL estiver ativo, podendo dessa forma forçar a ativação de todas as portas tristate das linhas de entrada e admitir a escrita da totalidade do bloco.

As saídas destas portas AND vão ligar a 2 portas OR cada, onde o seu sinal é analisado em conjunto com os sinais RD ou WR/WRBL nas portas que ativam a leitura ou   nas portas que ativam a escrita, conforme for o caso.

Estes sinais vêm já devidamente tratados da Unidade de Controlo do circuito (1). Desta forma fica selecionada uma coluna para RD ou WR ou a totalidade das colunas para a escrita de um bloco.

A Unidade de Controlo

A esta Unidade de Controlo (1) vêm ligar os sinais enviados pela MMU, CS, RD, WR, WRBL e WRVL e um outro sinal que vem de um Controlador de Validade (5) a que vamos chamar VL, de que falaremos já de seguida.

Nesta Unidade de Controlo (1) os sinais  RD e WR são validados pelos sinais CS e VL que vão ligar conjuntamente com aqueles a duas portas OR. Qualquer destes sinais é ativo a 0, pelo que quando alguma dessas portas devolver 0 é porque está ativa uma escrita ou uma leitura validada. O sinal WRBL é validado com CS também numa porta OR cuja saída vai ligar diretamente às portas AND após a saída do MUX (2). O sinal WRBL validado também vai ligar em conjunto com WR validado a uma porta AND que devolve 0 desde que algum deles seja ativo. A saída desta porta é a que vai ligar às portas OR de validação das escritas.

Os sinais WRBL e WRVL também vão ser tratados  em conjunto:

• Por uma porta NAND, que só devolve 0 quando forem ambos inativos (1).
• Por uma porta AND que só devolve 1 quando forem ambos inativos (1).

As saídas destas portas vai servir para a seleção da linha nas situações de escrita de bloco ou bit de validade em alternativa a escrita ou leitura de dados. Veremos como, em cada situação de mapeamento.

Esta Unidade de Controlo (1) ainda tem mais uma saída, mas agora para o exterior, concretamente para a MMU. Através de uma porta OR, que valida o valor VL com CS, produz uma saída que é ativa a 0 e a que vamos chamar CH (Cache Hit). Portanto, se CS estiver selecionado, quando VL for 0 CH será 0 e teremos um cache hit. Se VL for 1 então CH será 1 e teremos um  cache miss, informação esta que é ligada à MMU.

Controlador de Validade

Genericamente o objetivo do Controlador de Validade (5) é verificar o resultado da comparação da etiqueta, o valor do bit de validade e o valor da linha selecionada. Estes 3 valores serão ligados a portas AND, uma por cada linha de cache. Se forem válidos (1), estando ligados a portas AND (uma por linha), essa porta devolverá 1. Todas as portas AND estão ligadas a uma porta NOR. NOR só devolve 1 se todas as entradas forem 0. Basta que uma porta AND devolva 1 (só uma o pode fazer) e a saída VL do conjunto (5) devolve 0, o valor a que VL é ativo para o quadro (1). Neste caso teremos um cache hit e a consulta é válida, isto é, pode-se validar um sinal RD ou WR e comunicar um cache hit, o que é realizado pela Unidade de Controlo (1).

Bit de Validade

Falámos atrás em bit de validade mas ainda não dissemos para que serve. Quando o computador arranca, a cache fica com valores indefinidos e incoerentes nas suas linhas e nos seus bits de etiqueta. Pode acontecer que ao fazer uma consulta se encontre por mero acaso o valor pretendido em termos de endereço, um cache hit, sem que o valor contido nessa posição tenha qualquer relação com o trabalho que está em curso. Para evitar tais situações, sempre que a cache é iniciada os bits de validade são todos colocados a 0, só passando ao estado 1 conforme se forem escrevendo valores nos blocos que pertençam ao trabalho em curso.

Falámos até aqui das questões que são genéricas aos gráficos de todos os mapeamentos. A partir daqui já cada um tem especificidades próprias que serão tratadas nos devidos subcapítulos para o mapeamento próprio.

Mapeamento Direto

Na Figura 1 está representado um gráfico do circuito de controlo da nossa cache em mapeamento direto e na Figura 2 a pormenorização do acesso às células da etiqueta e do bit de validade. Na análise que vamos fazer, as notas  (x) nessas figuras serão referidas unicamente pelos seus números, sendo omitido o número da figura. Para poderem acompanhar a descrição sempre em presença da figura devem tocar ou clicar nela para a ampliarem e  abrirem noutra janela.

Situação de RD e WR

 São os bits A3 e A4 do endereço, aqueles que compõem o índice, que vão ser usados para a seleção da linha. Para isso, estão ligados a um MUX (4) que vai tornar ativa (ativa a 1) a saída correspondente à linha selecionada pelo índice.

 Ativada a linha, fica também ativa a ligação das células dos bits  B5 a B11 da sua etiqueta a uma das entradas do comparador (3). À outra entrada estão ligados os bits equivalentes do endereço, A5 a A11.

O comparador (3) vai fornecer em resposta um sinal Ig (Igual) que é 1 se forem iguais e 0 se forem diferentes. No nosso caso Ig=1.

 Este sinal Ig, junto com as saídas do MUX (4) e os valores dos bits de validade de cada linha vão ligar à unidade de Controlo de Validade (5). O comportamento deste circuito (5) já foi descrito de uma forma genérica pelo que se remete para essa descrição.

Vamos agora analisar em pormenor a leitura da etiqueta, e do bit de validade na Figura 2. Vamos reduzir o tamanho da etiqueta a 3 bits para efeitos desta análise.

As células da etiqueta e do bit de validade são idênticas às células de dados. Na realidade são dados que elas guardam, só que com um significado diferente. É pela leitura dessas células que é detetada a validade do bloco e é comparada a etiqueta com o mesmo valor do endereço.

Durante os sinais RD ou WR tanto as células do bit de validade como da etiqueta são lidas para verificação.

Já para as células de dados, RD e WR vão com a função específica de cada um, já confirmados pelo sinal VL da unidade (5) que vamos obter através da leitura das células da etiqueta e do bit de validade.

Para isso a saída para leitura das células da etiqueta está ligada  a uma das entradas do circuito comparador (3). À outra entrada estão ligados os bits equivalentes do endereço.

As células de cada coluna que a cada momento vão ligar ao comparador, são definidas pela seleção de linha. É a linha ativa que abre os transístores e permite a comunicação do valor memorizado na célula à linha de leitura.

As células selecionadas serão as células da etiqueta do bloco (linha) em que se pretende ler ou escrever, portanto da linha selecionada e ativa.

Às portas AND da entrada do Controlador de Validade (5) vão ligar:

• O sinal Ig devolvido pelo comparador (3), a todas as portas AND. Ele é o mesmo para todas as linhas estando a cada momento a comparar a linha ativa.
• As linhas de leitura das células do bit de validade, cada uma à porta AND referente a essa linha.
• O valor da linha propriamente dita, à porta AND que lhe é referente.

Só nos interessa a porta que se refere à linha ativa, portanto ao bit de validade que está a ser lido e ao sinal Ig da comparação com a etiqueta dessa linha.

Se para a linha ativa estas 3 condições forem  verdadeiras (1) essa porta AND vai devolver verdade (1), o que fará VL=0, ativo portanto. VL a 0 indica cache hit, portanto vai validar o sinal RD ou WR que estiver no caso a ser executado.

Neste tipo de mapeamento, nesta fase temos já uma só linha selecionada, da forma que descrevemos. O valor de VL encontrado vai ou não permitir a abertura das portas tristate de entrada ou saída da coluna selecionada, conforme seja o caso de WR ou RD.

Situação WRBL e WRVL

Esta é a situação em que se pretende escrever na Cache, mas de uma forma diferente. Não resulta de um pedido da CPU mas de uma alteração ao conteúdo de uma linha feita pela MMU:

• Porque, na sequência de um cache miss foi buscar o bloco em falta e agora pretende escrevê-lo.
• Porque pretende alterar o valor do bit de validade.

Quando se escreve um bloco na Cache, duas situações diferentes se vão verificar:

• A etiqueta vai ser escrita, registando o valor correspondente do endereço desse bloco.
• A linha de cache é escrita na totalidade, isto é, em todas as colunas.

No caso do mapeamento direto que estamos agora a analisar, a linha onde se vai escrever o novo bloco é aquela que está referenciada pelo índice do endereço e que deu origem ao cache miss.

Como já vimos, no mapeamento direto a cada índice corresponde uma só linha possível na cache.

A forma como o sinal WRBL atua para que todas as colunas da linha fiquem ativas para escrita, já foi referenciada nas generalidades, pelo que para aí remetemos. Para que a escrita na etiqueta se possa efetuar o sinal WRBL é aquele que fica ligado aos buffers tristate que ativam a escrita nas suas células.

Da mesma forma, para que a escrita do bit de validade se possa efetuar, WRVL é o sinal que fica ligado aos buffers tristate que ativam a escrita nas suas células. Para escrever o bit de validade em qualquer situação independente de uma escrita de um bloco, a MMU só tem que identificar a linha onde o pretende fazer no índice do endereço e ativar o sinal WRVL.

Mapeamento Totalmente Associativo.

Na Figura 3 está representado um gráfico do circuito de controlo da nossa cache em mapeamento associativo e na Figura 4 a pormenorização do acesso às células da etiqueta, do bit de validade e a seleção de linha para escrita de bloco ou bit de validade. Na análise que vamos fazer, as notas  (x) nessas figuras serão referidas unicamente pelos seus números, sendo omitido o número da figura. Para poderem acompanhar a descrição sempre em presença da figura devem devem tocar ou clicar nela para a ampliarem e  abrirem noutra janela.

 

Neste caso não existe o seletor de linha indicado com (4) no quadro anterior, pois no mapeamento associativo não há índice. A procura da linha é feita pela comparação das etiquetas com o endereço, utilizando-se para isso um comparador dedicado a cada bloco (linha) de cache.

À partida todas as linhas estão selecionadas na zona das células das etiquetas e dos bits de validade.

É com base no resultado Ig dos comparadores (3) e no valor do bit de validade, que é selecionada e ativada a linha que vai servir as células de dados, ou seja, o bloco que contém o byte desejado.

O resultado da leitura das células da etiqueta de cada bloco, vai ligar a uma das entradas do comparador (3) dedicado a esse bloco (linha). À outra entrada de todos os comparadores (3) estão ligados os bits do endereço que se pretendem comparar. O sinal de saída Ig de cada um destes comparadores vai-se juntar com o sinal de saída da célula do bit de validade da linha do bloco comparado numa porta AND no circuito de controlo de validação (5).

Como funciona este circuito (5) já vimos nas generalidades, pelo que para lá remetemos, com a exceção de que neste caso não se liga o valor da linha para lá ligar, uma vez que todas elas estão sempre selecionadas..

Deste circuito sairá o sinal VL que permitirá ou não a ação dos sinais RD ou WR sobre o byte selecionado, conforme haja ou não um cache hit.

Em caso de cache miss, o sinal CH (CH=1) dá do mesmo conhecimento à MMU. Enquanto procura noutro nível de Cache ou na MP, a MMU efetua os procedimentos necessários ao algoritmo de substituição de bloco da cache, determinará qual o bloco a ser substituído e ativará então em exclusivo a linha do bloco escolhido na zona das células do bit de validade e da etiqueta, da forma que podemos verificar na Figura 4.

Os sinais WRBL e WRVL ligados em conjunto a uma porta AND, garantem que o sinal por ela devolvido é 1 desde que ambos estejam inativos (1). Esse valor, ligado às portas OR em que a outra entrada pertence ao seletor de linhas (4), força todas as saídas e portanto as linhas a 1.

Mas, quando qualquer um dos sinais WRBL ou WRVL estiver inativo, AND devolve 0 e esse valor, ligado às tais portas OR, permite que elas devolvam o valor igual ao da outra entrada, pois 1 OR 0 = 1 e 0 OR 0 = 0, prevalecendo a ativação da linha correspondente à saída ativa do MUX (4).

Os bits de seleção do MUX (4) serão os endereços L0 e L1 da linha escolhida pela MMU para colocar o novo bloco.

A ativação da linha de dados dá-se normalmente pelo processo anterior, pois a etiqueta do bloco é igual aos bits do endereço a comparar e como tal vai permitir a ativação dessa linha. A ativação da coluna de dados será efetuada da mesma forma que foi descrita para o mapeamento direto.

No caso de WRBL e escrito o bloco e a sua etiqueta, a cache prossegue com RD ou WR, aquele que deu cache miss.

Mapeamento Associativo por Conjuntos

Na Figura 5 está representado um gráfico do circuito de controlo da nossa cache em mapeamento associativo por conjuntos e na Figura 6 a pormenorização do acesso às células da etiqueta, do bit de validade e a seleção de linha para escrita de bloco ou bit de validade. Na análise que vamos fazer, as notas  (x) nessas figuras serão referidas unicamente pelos seus números, sendo omitido o número da figura. Para poderem acompanhar a descrição sempre em presença da figura devem tocar ou clicar nela para a ampliarem e  abrirem noutra janela.

 

Este caso é um misto das duas situações atrás descritas. Temos dois conjuntos de mapeamento direto e totalmente associativos entre eles.

Começamos por definir as linhas ativas, que será sempre uma em cada conjunto. Mas neste caso as linhas serão definidas já  com MUX independentes para cada conjunto. Com estes MUX, encontramos uma linha ativa por Via.

Cada Via (entendamos Via como o conjunto) dispõe de um comparador (3) dedicado.

Numa das entradas de cada comparador (3) estão ligadas as linhas de leitura das células das etiquetas da Via a que ele pertence.

Na outra entrada estão ligados os bits do endereço a comparar.

Dos dois comparadores só um pode dar um valor de coincidência, se algum der.

A seleção da linha ativa na zona de dados é tratada de forma semelhante à anterior cache associativa. Em resumo, cada linha liga a uma porta AND onde ligam ainda o bit de validade e o sinal Ig do comparador da Via a que essa linha pertence. Quando todos forem 1, essa porta AND devolve 1 e ativa essa linha.

Estes mesmos valores vão ligar a um controlador de validade (5) já descrito anteriormente.

No caso em que existe uma situação com os três valores a 1, dá-se um cache hit e VL assume o valor 0, assim permitindo que RD ou WR executem as suas funções, conforme for o caso.

Em caso negativo, estaremos perante uma situação de cache miss. Assim VL assume o valor 1 e CH também, ficando a MMU a saber da cache miss por esta forma.

Enquanto procura noutro nível de Cache ou na MP, a MMU efetua os procedimentos necessários ao algoritmo de substituição de bloco da cache, determinará qual o bloco a ser substituído e ativará então em exclusivo a linha do bloco escolhido na zona das células do bit de validade e da etiqueta, da forma que podemos verificar na Figura 6. Numa cache associativa de 2 Vias com 2 blocos por Via, a seleção é feita por MUX de 1 para 2, o que se resolve com portas NOT, não permitindo uma análise com algum rigor da forma como se escolhe a linha que se pretende, tanto nas situações de RD e WR como nas situações de WRBL e WRVL.

Por essa razão juntámos a forma de fazer essa seleção num gráfico à parte na  Figura 7, que ilustra a seleção de linha numa cache associativa por conjuntos de 4 Vias e 4 blocos por Via.

No caso A (direita) está em curso uma operação RD ou WR, sendo selecionadas 4 linhas, uma em cada Via, através dos bits A3 e A4 que definem o índice, igual em todas as linhas selecionadas.

No caso B (esquerda) deu-se um cache miss e a MMU pretende agora escrever um bloco numa linha que escolheu entre as 4 possíveis, concretamente a linha definida por A3 e A4  da Via 2 (10), que define pelos bits V0 e V1.

O mesmo circuito tem que servir as duas situações. Na situação A tanto WRBL como WRVL estão inativos (1). Na situação B pelo menos um deles está ativo (0). É com esta diferença que temos que fazer diferenciar as escolhas.

Uma entrada a 1 num MUX (3) de 1 para 4 com portas AND deixa que as saídas mantenham o valor correspondente à seleção. Uma entrada a 0 força todas as saídas a 0.

Afinal é isto que nós pretendemos. Ou todas com as saídas definidas pela seleção (A) ou só uma com as saídas definidas pela seleção e todas as outras a 0 (B).

Temos que fazer chegar uma entrada a 1 a todos os MUX definidos por (3). Mas também temos que poder converter essa entrada no valor correspondente ao das saídas do MUX (1) de seleção de Via.

Este MUX (1) de seleção de Via é um MUX de  4 saídas com portas NAND, em que todas as saídas estão a 1 menos a selecionada.

Se agora fizermos entrar as saídas deste MUX em portas NOR em conjunto com o valor devolvido por uma porta AND cujas entradas são WRBL e WRVL, verificaremos que:

Sempre que eles forem ambos inativos (1), a saída de AND força as portas NOR todas a 1.

Sempre que pelo menos um deles esteja ativo a saída de AND deixa de forçar as portas NOR que assim passam a ter nas saídas o inverso das saídas do MUX (1), isto é, a Via selecionada a 1 e as restantes a 0.

Então basta-nos ligar as saídas das portas NOR à entrada do MUX (3) da respetiva Via e temos o pretendido.

Completo o processo de escrita de bloco e etiqueta em cache a MMU reativa o processo RD ou WR interrompido com o endereço que ainda se encontra no registador de endereços, agora com cache hit garantido.