O que é a Cache

Agora o António é responsável pelo arquivo de uma grande empresa.

De cada vez que alguém precisava de um documento pedia-o ao António e ele lá ia corredor após corredor, entrava na sala devida, procurava a estante indicada, verificava qual a prateleira em questão, ia buscar um escadote para aceder à prateleira, procurava a pasta em questão e finalmente tirava dessa pasta o documento solicitado, fotocopiava-o e voltava a guardar o original.

Depois percorria todo o caminho de volta, entregava a fotocópia a quem lha tinha pedido e como já tinha mais pessoas à espera, lá ia ele percorrer de novo caminhos idênticos para satisfazer os pedidos seguintes.

Como o António já não era propriamente um jovem, chegava ao fim de cada dia de trabalho extremamente cansado de tanto correr.

Então começou a pensar numa forma de não se cansar tanto. Começou a anotar os locais onde ia buscar os documentos que lhe pediam e verificou que ia várias vezes aos mesmos sítios para ir buscar documentação que se encontrava na proximidade ou até a mesma documentação por várias vezes.

Então, resolveu começar a fazer duas fotocópias em lugar de uma, guardando numa gaveta grande da sua secretária a segunda fotocópia.

Verificou que já se deslocava menos vezes para longe da sua secretária, pois muitas vezes já lá tinha aquilo que lhe iam pedir, limitando-se a fazer uma fotocópia numa fotocopiadora que tinha junto de si.

Também reparou que quanto mais folhas tinha dentro da gaveta, menos eram as vezes que tinha de se deslocar ao arquivo.

Entretanto, porque os documentos na gaveta já eram muitos, arranjou separadores onde colocava as cópias identificadas pelo seu endereço no arquivo, isto é,  a sala, a estante, a prateleira e a pasta.

Assim, quando lhe pediam qualquer documento verificava o seu endereço e procurava na gaveta pelo separador com o mesmo endereço. Se encontrasse, verificava se o documento em questão lá estava. Se não encontrasse, fazia as tais duas fotocópias e guardava uma, criando o separador para a mesma se ainda não existisse.

De cada vez que o António não encontrava o documento pedido na gaveta, ficava furioso e tentava melhorar a sua atuação para isso acontecer cada vez menos.

Verificou que havia sempre uma proximidade das folhas que lhe pediam, isto é, eram habitualmente vizinhas.

Então decidiu que, de cada vez que ia ao arquivo buscar uma folha, trazia não só fotocópia dessa como das que lhe estavam à volta e guardava-as na gaveta.

Reparou que o resultado era positivo, pois cada vez se deslocava menos ao arquivo. Só havia um problema. A gaveta estava completamente cheia. Mas o método estava a resultar. Já lhe doíam menos as pernas e as costas ao fim do dia. Não era altura de parar.

Vai daí, o António imaginou uma outra solução. Pediu ajuda a uns colegas, foi buscar uma estante que estava desocupada e colocou-a por detrás da sua secretária. Por cada vez que colocava uma cópia na gaveta colocava outra na estante junto com uma outra cópia do que punha na gaveta.

Mas era preciso tirar cópias da gaveta. Como tinha anotado que os documentos que lhe pediam eram mais frequentemente os mais recentes começou por retirar os mais antigos da gaveta, colocando-os na estante. Mas isso não foi boa solução, porque esses eram muitas vezes os mais pedidos.

Então começou a marcar os documentos para saber sempre dentro de cada separador qual era o menos pedido, aquele que devia retirar.

Conforme a estante se ia enchendo o António, deliciado, verificava que cada vez  ia menos ao arquivo. E gabava-se aos seus amigos da estratégia que tinha inventado e que, quando a estante ficou cheia, lhe proporcionava escassas idas ao arquivo durante o dia.

E esta é a história da Cache, contada na pessoa do António.

A Cache não é mais nem menos do que o espaço onde o António guardava as suas cópias. A gaveta era a Cache L1 (de nível 1) e a estante a Cache L2 (de nível 2). As pessoas que lhe iam pedir os documentos representam a CPU e o António é a Interface de Memória ou MMU (Memory Management Unit).

Os princípios com base nos quais o António selecionou os registos para a gaveta e estante foram:

•  O princípio da localidade espacial, segundo o qual há uma grande probabilidade de os registos na proximidade de um acesso serem acedidos nos acessos seguintes e
• O princípio da localidade temporal, segundo o qual os registos com mais probabilidade de voltarem a ser acedidos são aqueles que foram acedidos mais recentemente.

Vamos então concentrar a nossa análise na Cache e deixar o António sossegado.

A CPU consulta a memória na Cache L1, que se encontra dividida em dois blocos iguais e separados, a Cache L1 I (instruções) e a Cache L1 D (dados).

Esta é a memória que a CPU conhece. Quando o valor não se encontra na Cache L1 dá-se aquilo a que se chama uma Cache Miss (falha de procura na Cache). A partir daqui é a MMU que vai gerir a consulta a outros níveis de Cache ou à MP (Memória Principal),  a esta já através do CM (Controlador de Memória).

Seguindo as deduções do António, devemos ter tanto quanto possível nesta cache elementos que se encontrem em proximidade na MP. É o tal princípio da Localidade Espacial.

Para que isso aconteça, e no sentido de melhor aproveitar os tempos de acesso à MP, deve-se trazer o maior número possível de registos, aproveitando a leitura em rajada, reduzindo assim o tempo médio de acesso.

Se trouxermos 64 bits por leitura numa rajada de 8, trazemos de uma vez para a cache 64 Bytes que se encontram em proximidade.  E esse valor poderá constituir o Bloco de Cache que corresponde a uma Linha de Cache. Os movimentos de e para a Cache são sempre feitos por Blocos, portanto no caso de que estamos a falar, em quantidades de 64 Bytes.

Os compiladores colocam as instruções dos programas todas em sequência num determinado local da memória e não espalhadas uniformemente. As instruções repetidas são frequentes, como é o caso de acesso a certas sub-rotinas ou a execução de loops. Os dados das constantes e variáveis utilizados por um programa também são todos colocados em proximidade. Estão reunidas todas as condições para que, quanto maior for a cache e os blocos que possa ter em proximidade, maior a possibilidade de obter uma boa taxa de sucesso. Em termos estatísticos fala-se de taxas de sucesso da ordem dos 95% nos acessos feitos pela CPU à Cache.

Cache Hit ou Cache Miss são os termos que designam um acerto de cache ou uma falha de cache e que definem as taxas de sucesso ou de insucesso no acesso à Cache.

Vamos descer à pequenez da nossa memória e analisar a Cache com base numa perspetiva simples. Para já sempre em termos de Byte, que é a dimensão da nossa palavra. Convém lembrar que os acessos à memória são sempre feitos ao Byte e que os endereços referem um Byte específico.

As Células da Cache

Vamos agora tentar montar os circuitos que permitem à memória Cache cumprir o objetivo para que foi concebida e a sua forma de funcionamento.

Os circuitos são simplesmente o resultado de deduções lógicas que permitem obter os resultados pretendidos. Qualquer comparação a circuitos comerciais é pura coincidência. Não tivemos acesso a qualquer desses circuitos.

Mas certamente que esses circuitos serão muito mais eficientes do que aqueles que imaginámos, pois resultam de muitos milhares de horas de trabalho de especialistas em permanente tentativa de melhorar as soluções já existentes.

Mas não serão certamente a melhor forma de perceber como é que com portas lógicas, portanto com 0 e 1, se continua a conseguir cumprir o objetivo, de uma forma simples.

A partir daí, a complexidade vai resultar da soma de muitas simplicidades.

A Cache é constituída por memória estática ou SRAM (Static Random Access Memory).

Estática porquê?

Porque os valores nela armazenados são estáticos (fixos) até serem alterados ou cortada a alimentação, contrariamente à MP, que é dinâmica porque os valores guardados nas suas células necessitam de refrescamento.

A SRAM memoriza os valores através de transístores inseridos em circuitos sequenciais que já analisámos:

• O Flip Flop SR (Set Reset), que assume diferentes valores à saída, conforme as variáveis à entrada assumem o estado 1, fazendo SET e RESET.
• O Flip Flop D, que é um avanço do primeiro, com a vantagem de poder ser por nós controlado, guardando o valor de um dado D consoante a atuação do sinal de clock ou outro com o qual o queiramos controlar.

Com base nestes elementos, vamos então analisar o que pode ser uma célula de memória estática ou SRAM. Para isso vamos utilizar os quadros das Figura 1 e Figura 2.

Nestes quadros os sinais RD e WR referem-se a leitura e escrita e são ativos em baixa, o sinal CS (Chip Select) é ativo em baixa, e o sinal SB (Select Byte) representa a seleção das colunas que compõem o byte a que pretendemos aceder.

Comecemos por analisar o  Quadro I.

A célula propriamente dita está sobre um fundo azul. É constituída por um Flip Flop SR construído com portas NOR, porque se pretende que não seja sensível à situação das duas entradas em baixa ou 0.

As entradas do Flip Flop SR  estão condicionadas por dois interruptores nMOS cujas portas estão ligados à linha. Portanto, só deixam passar informação quando a célula pertence a uma linha ativa (a linha é ativa em alta ou 1).

E que informação é que deixam passar?

Na base de cada coluna temos duas portas AND onde ligam o dado D e a sua negação ¬D. Nas duas outras entradas das portas AND vai ligar ¬WR (a negação de WR), isto é, quando WR estiver ativo (WR é ativo em baixa ou 0), a sua negação vai funcionar como o sinal de  clock de um Flip Flop D composto por este conjunto sobre fundo rosa e pelo Flip Flop SR da célula ativa. As linhas que saem do conjunto rosa como entradas da célula ativa são WRBL (WRite Bit Line) ou linha de bit de escrita e ¬WRBL.

E assim, escrevemos no Flip Flop SR o valor que queremos quando o sinal WR (escrita) estiver ativo.

 No Quadro II podemos ver a situação em que a célula fica inativa, por a linha ativa não ser a sua. Como se vê, fazendo a análise lógica, o facto de as duas entradas estarem em baixa não afeta o valor da saída. O valor guardado pela célula mantém-se até que seja alterado, mesmo para leitura ou após leitura, como veremos.

No Quadro III a linha da célula volta a estar ativa, mas desta vez para uma operação de leitura. Estão abertos os transístores nMOS só que não há nada para escrever, pois a informação foi cortada pelo BT (Buffer Tristate) que controla a escrita na célula. Novamente se verifica que o valor guardado não se altera. O valor só pode ser alterado por um SET ou um RESET, que correspondem à existência de um valor 1 em uma das entradas do Flip Flop SR. A leitura é feita através de uma outra linha, a RDBL (ReaD Bit Line) ou linha de bit para leitura, que está ligada à saída dos Flip Flop SR também através de um transístor nMOS cuja porta é ativada pela linha.

No Quadro IV escreve-se na célula o valor 1, seguindo o mesmo raciocínio que fizemos para o valor 0. Voltamos a ter um Flip Flop D em que D é o valor a escrever e o clock é exercido pelo sinal WR.

No Quadro V, verifica-se que o valor 1 se mantém memorizado quando a linha em que se encontra deixa de estar ativa.

No Quadro VI, verifica-se a leitura deste valor 1 e o facto de o mesmo não ser alterado durante este processo.

Na Figura 3 apresentamos o que consideramos ser uma situação exemplo de acesso a 4 linhas e 4 colunas de uma memória cache, com as respetivas portas Tristate e toda a outra lógica de que falámos, agora já dedicada a várias células.  Os sinais IG, LS e VL que selecionam a linha ativa serão analisados a seguir quando falarmos do mapeamento das caches.