Tema 3 - Resumo - Carlos Alexandre Silva dos Santos

Prévia do material em texto

UNIVERSIDADE FEDERAL DE PELOTAS 
CENTRO DE DESENVOLVIMENTO TECNOLÓGICO 
PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO 
DISCIPLINA: ARQUITETURA DE COMPUTADORES 
PROFESSORES: MARCELO PORTO, LUCIANO AGOSTINI E BRUNO ZATT 
ALUNO: CARLOS ALEXANDRE SILVA DOS SANTOS 
DATA: 06/08/2020 
 
 
RESUMO: 
 
TEMA 3: CONCEITOS BÁSICOS DE HIERARQUIA DE MEMÓRIA, CONCEITOS 
BÁSICOS DE MEMÓRIA CACHE E MAPEAMENTO DE MEMÓRIA CACHE 
 
 
1 - CONCEITOS BÁSICOS DE HIERARQUIA DE MEMÓRIA 
 
Primeiramente, é importante considerar o impacto da memória impacta no 
desempenho regular de um sistema computacional. No intuito de amenizar este impacto, é 
fundamental o entendimento sobre a hierarquia de memórias, assim como os detalhes de 
funcionamento das memórias em seus diferentes níveis, com o propósito de mitigar 
problemas de leitura e escrita, assim como maximizar a performance do sistema. 
Parte considerável do tempo de execução gasto para processamento de uma dado 
ou instrução é proveniente do tempo de acesso à memória. De forma geral, os sistemas 
computacionais atuais apresentam uma hierarquia de memória, em que existem diversas 
tecnologias de fabricação e com diferentes características, tais como velocidade de acesso, 
custo, densidade, capacidade, etc. 
De acordo com o “gargalo” descrito por von Neumann, constata-se que ao longo do 
tempo a evolução de desempenho dos processadores, comparado ao desempenho das 
memórias, é maior. Mesmo com um ganho de desempenho nas memórias, esta diferença 
de desempenho ou “​gap​” em relação ao processador tem um aumentando. 
Com base na informação acima, constata-se uma necessidade de se melhorar o 
desempenho das memórias de forma que as mesmas não sejam um empecilho no 
desempenho geral de um sistema computacional. 
A hierarquia de memória nos sistemas atuais costuma ter de 3 a 4 níveis de níveis 
diferentes com diferentes tipos de tecnologia de fabricação de memórias. Geralmente, esta 
hierarquia é representada na forma de pirâmide, em que no topo se tem as memórias mais 
rápidas, porém com baixa capacidade de armazenamento (com menor número de bits para 
armazenamento por cm​2 em chip) e custo mais elevado. Em contrapartida, nos níveis mais 
baixos tem-se memórias mais lentas, porém com custo mais baixo e alta capacidade de 
armazenamento. A Figura 1 apresenta uma ilustração da hierarquia de memória na forma 
de uma pirâmide. 
 
 
Na Figura 1 observa-se os Registradores no topo, seguido da memória cache, 
memória principal e memórias secundárias ou de massa (disco rígido, SSD, fita magnética, 
etc.). Portanto, o propósito é que se tenham memórias mais rápidas mais próximas ao 
processador, que no caso ilustrado acima são os registradores. 
Com a utilização dos registradores é possível diminuir o ​gap ​entre o processador e a 
memória. Ocorre que a quantidade e densidade de registradores não é suficiente para 
“armazenar” todas os dados e instruções que o processador precisará para processar uma 
informação. Nos processadores atuais observa-se também a hierarquia de memórias, em 
que se tem além dos registradores, também a memórias cache integradas L1, L2 e L3. 
Portanto, o objetivo da utilização de uma hierarquia de memória é dar ao sistema a 
“ilusão” de que se tem uma memória muito rápida e com uma capacidade de 
armazenamento grande, ou seja, que o sistema tem a velocidade da memória mais rápida 
(tecnologia mais cara), e a capacidade de armazenamento da memória mais lenta 
(tecnologia mais barata). 
O gerenciamento desta hierarquia de memórias é realizada conforme segue: 
Registadores com memória o gerenciamento é realizado pelo compilador; cache com 
memória principal, o gerenciamento é realizado pelo ​hardware​; e, memória principal com o 
disco, o gerenciamento é realizado pelo ​hardware ​e pelo sistema operacional (memória 
virtual), e pelo programador (arquivo). 
A hierarquia de memória funciona porque explora o princípio da localidade, que pode 
ser temporal ou espacial, em que se tenta encontrar quais são os dados que se deseja 
manter na memória mais rápida. 
A localidade temporal parte da premissa que se um item é referenciado, ele tende a 
ser referenciado novamente dentro de um espaço curto de tempo. Exemplo: A maioria dos 
programas contém laços (instruções e dados do laço tendem a ser acessados de maneira 
repetitiva. Neste caso, é interessante deixar este dado ou instrução na memória mais 
próxima ao processador, uma vez que este possivelmente precisará deste dado novamente 
em um curto espaço de tempo. 
A localidade espacial parte da premissa que se um item é referenciado, itens cujos 
endereços sejam próximos dele tendem a ser logo referenciados. Exemplo: Nos programas, 
as instruções estão armazenadas na memória de maneira sequencial; os itens de matrizes 
e registros também se encontram armazenados de maneira sequencial. Neste caso, quando 
o processador realizar uma requisição de uma instrução, por exemplo, além desta instrução, 
convém se levar à memória também as instruções que são subsequentes à instrução 
requisitada, uma vez que possivelmente o processador precisará destas também em um 
curto espaço de tempo. 
 
2 - CONCEITOS BÁSICOS DE MEMÓRIA CACHE 
 
Cache é a designação do nível de memória que está entre o processador e a 
memória principal, e este nome foi usado em meados dos anos 60 pela primeira máquina 
que utilizou este tipo de memória. A memória cache utiliza o princípio da localidade. 
Atualmente, utiliza-se este nome para qualquer memória que explore o princípio da 
localidade. 
Quando o processador solicita um determinado dado e não o encontra no nível 
hierárquico de memória mais próximo a ele, ou ​i (nível superior), o que se diz é que este 
determinado dado será buscado em um nível inferior ou​ i+1​. 
Outro conceito importante é o de Bloco, que nada mais é do que a unidade mínima 
de informação, contendo um determinado número de palavras de memória, como por 
exemplo, com 8 palavras de memória, conforme ilustrado na Figura 2. 
 
 
Detalhe interessante é que o quão maior é o tamanho da palavra maior será a 
possibilidade de exploração da localidade espacial. Porém, quão maior o tamanho da 
palavra menos palavras serão possíveis, o que causará uma menor exploração temporal, 
pois menos palavras estarão disponíveis na cache. 
Quando uma informação é solicitada pelo processador e esta está presente no nível 
superior da hierarquia dizemos que ocorreu um ​hit​, ou acerto. Porém, se esta informação 
não puder ser encontrada no nível superior, a tentativa de encontrá-la irá gerar uma falta 
(​fault ou ​miss​). Quando ocorre esta fala, o nível imediatamente inferior é acessado, com o 
propósito de se recuperar o bloco com a informação solicitada pelo processador. 
Ao acessar os níveis inferiores da hierarquia, estas informações serão conduzidas à 
cache, de forma que o processador possa acessá-las e processá-las. Porém, quando isto 
ocorre, pode ser necessário que o dado ou instrução que estejam na cache tenham que ser 
removidos. 
Convém destacar que, se um determinado dado está em um nível superior, ou ​i​, eletambém está presentes no nível ​i+1 da hierarquia, de forma a manter a consistência destes 
dados nos diversos níveis de memória. Exemplo: Se um dado está na memória cache, este 
dado também está presente na memória principal. 
A taxa de acertos ou ​hit ratio é a fração dos acessos à memória que são 
encontrados no nível superior e a taxa de faltas ou ​miss ratio é a fração de acessos à 
memória não encontrados no nível superior. 
Já o tempo de acerto ou ​hit time é o tempo para acessar o nível superior da 
hierarquia, que inclui o tempo necessário para determinar se a tentativa de acesso à 
informação vai gerar um acerto ou uma falta, enquanto que a penalidade por falta ​(fault 
penalty​) é o tempo necessário para substituir um dos blocos do nível superior pelo bloco do 
nível inferior que contém a informação desejada, mais o tempo para enviar a informação ao 
processador. 
Com relação à penalidade por falta deve-se levar em conta o nível hierárquico de 
memória, pois quão mais baixo o nível maior será a penalidade por falta, uma vez que o 
tempo de acesso em níveis mais baixos é muito maior em relação a níveis superiores. 
Para verificar se um dado está na cache e em qual posição é necessário o estudo 
dos modelos básicos de mapeamento, ou seja como se “pega” um bloco da memória e se 
coloca na cache. 
O modelo mais básico é o de Mapeamento Direto, em que um bloco só pode ser 
colocado em exatamente um lugar na cache. Neste modelo, existe um caminho, mapeado 
previamente, de qualquer endereço de bloco da memória principal para uma única posição 
da cache, em que esta posição é dada pelo (endereço do bloco) módulo (número de blocos 
da cache). Neste modelo de mapeamento, portanto, várias posições da memória principal 
devem ser mapeadas para a mesma posição na memória cache. O mapeamento direto não 
é flexível, pois o dado só poderá ser colocado naquela posição calculada. Caso haja outro 
dado já naquela posição da cache este dado será descartado. 
O outro extremo dos tipos de Mapeamento é o Totalmente Associativo, em que um 
bloco da memória principal pode ser colocado em qualquer posição da cache. Neste 
modelo, um bloco de memória pode ser associado a qualquer entrada da cache. Portanto, é 
necessário pesquisar todas as entradas da cache, a fim de localizar um determinado bloco, 
uma vez que este pode estar em qualquer uma das entradas. 
Para reduzir o tempo desta pesquisa é utilizado um comparador para cada entrada 
da cache, de forma que a pesquisa seja realizada em paralelo, o que acarreta em um custo 
elevado de ​hardware​. A chance de acerto na busca de um dado aumenta, porém há o custo 
de ​hardware ​associado. Portanto, este tipo de mapeamento torna-se mais atrativo para 
caches pequenas. 
Um método de mapeamento que tenta reunir características dos métodos 
apresentados anteriormente, é o Associativo por Conjunto ou Bloco Associativo. Neste 
modelo, existe um número fixo de posições na cache (no mínimo duas) nas quais cada 
bloco pode ser colocado. Cada bloco da memória principal é mapeado para um dos 
conjuntos da cache, determinado pelo campo de índice do endereço (sendo que o bloco 
pode ser colocado em qualquer dos elementos deste conjunto). O conjunto que contém o 
bloco de memória é dado por (número do bloco) módulo (número de conjuntos da cache). 
Com relação à política de substituição de dados em cache, no mapeamento direto 
não existe escolha, pois apenas uma posição da cache pode ser substituída, já a 
substituição no mapeamento associativo pode ser realizada aleatoriamente, com o uso 
menos recente (LRU), ou por meio de uma fila, em que o primeiro a entrar é o primeiro a 
sair (FIFO). 
Estas políticas têm vantagens e desvantagens. Na aleatória o bloco a ser substituído 
é escolhido aleatoriamente e é uma estratégia simples para implementação em ​hardware​. 
Já na política de substituição LRU, os acessos aos blocos devem ser registrados e o bloco 
a ser substituído é aquele que está a mais tempo sem ser solicitado. Esta política explora o 
princípio da localidade temporal, e sua complexidade aumenta com o aumento do tamanho 
da cache. É uma política geralmente aproximativa, dada sua complexidade. 
Por fim, a política FIFO é uma forma simplificada de implementar o LRU, uma vez 
que o bloco mais antigo é substituído e não o LRU, tornando, por sua vez, o controle menos 
complexo. 
Com relação às fontes de perdas (​misses​), há diferentes causas. Um ​miss 
compulsório é ocasionado quando a cache será preenchida pela primeira vez. O ​miss ​de 
conflito ou colisão é aquele que acontece, por exemplo, no mapeamento direto, em que se 
precisa guardar um dado em uma posição que já é ocupada. 
Numa cache totalmente associativa este problema não ocorre. Já o conflito de 
capacidade ocorre quando a cache está cheio e inexoravelmente um dado deverá sair da 
cache para que o novo dado seja armazenado. Por fim, o ​miss ​de invalidação é quando um 
dispositivo de I/O altera a memória e o processador vai ler esta informação e ela não mais 
está na cache. 
A Tabela 1 apresenta uma relação entre os métodos de mapeamento e tamanho da 
cache com as diferentes fontes de perda (​misses​). 
 
 
 
Observe, por exemplo, que há uma incidência alto de ​misses de conflito no 
mapeamento direto em relação aos demais mapeamentos, em função da política de 
substituição de dados. Em contrapartida, há no mapeamento completamente associativa 
uma quantidade alta de ​misses ​de capacidade em relação aos demais mapeamentos, pois 
neste mapeamento não há ​misses ​de conflito. 
Com relação às escritas na cache, estas representam 7% do tráfego geral da 
memória e cerca de 28% se for considerado apenas uma cache de dados. Portanto, a maior 
parte dos acessos à memória por parte do processador são para leituras. 
Neste sentido, deve-se otimizar o tempo de leitura para aumentar o desempenho 
médio do sistema. Os processadores tradicionalmente esperam o fim das leituras, mas não 
das escritas. 
Nas escritas em cache podem ocorrer inconsistências. Um exemplo seria a 
execução de uma instrução store em que o dado seja escrito somente na cache, uma vez 
que a memória principal teria um valor diferente do escrito na cache. Para resolver este tipo 
de problema existem duas estratégias: ​Write through​ e ​Write Back​. 
No ​Write Through a informação é escrita no bloco da cache e também na memória 
principal (ou cache de nível inferior). A vantagem desta abordagem é que os dados sempre 
estão estáveis nos diferentes níveis de memória, e a desvantagem é que todas as escritas 
pagam o preço do tempo de escrita na memória mais lenta. 
No ​Write Back a informação é escrita no bloco da cache, e só será escrito na 
memória principal quando for substituído. A vantagem é que esta abordagem pode reduzir o 
número de acessos que se faz no nível inferior, priorizando o desempenho. 
Ainda no contexto da escrita tem se o conceito de ​Write Miss que é quando o 
processador solicita uma escrita o endereço solicitadonão está armazenado na cache. 
Neste problemas, existem duas opções: Alocação de escrita, em que as perdas de escrita 
atuam como perdas de leitura, e a Alocação sem escrita, em que as perdas de escrita não 
afetam a cache e o bloco é modificado apenas na memória principal. 
 
3 - MEMÓRIA CACHE: MAPEAMENTO DIRETO, TOTALMENTE ASSOCIATIVO E 
ASSOCIATIVO POR CONJUNTO 
 
No Mapeamento Direto para cada palavra na cache é atribuído um endereço com 
base no endereço da palavra na memória principal. Como um dado de entrada da cache 
pode armazenar o conteúdo de diversos endereços da memória principal são atribuídos à 
cache um conjunto de rótulos (​tags​), de forma a identificar se o dado armazenado na cache 
corresponde ao solicitado. Estes rótulos são usados em conjunto com o endereço do 
mapeamento para compor o endereço completo, com relação à memória principal. 
Em situações em que a cache está vazia é necessário reconhecer se um bloco da 
cache possui informação válida. Para estes casos é utilizado um bit de validade, em que se 
o bit de validade for igual a 0, a informação contida naquele bloco da cache não é válida. 
No mapeamento direto o endereço é dividido em 2 partes. A parte menos 
significativa é o índice, usado como endereço na cache onde será armazenada a palavra. E 
a parte mais significativa é a ​tag​, armazenada na cache junto com o conteúdo da posição 
de memória. 
Quando o acesso é realizado, o índice é usado para encontrar a palavra na cache. 
Se o ​tag ​armazenado na palavra da cache é igual ao ​tag ​do endereço procurado, então 
houve acerto. Endereços com mesmo índice são mapeados sempre para a mesma palavra 
da cache. 
Dentre as vantagens do mapeamento direto está a não necessidade de algoritmo de 
substituição, ​hardware ​mais simples e de custo mais baixo, e alta velocidade de operação. 
Como desvantagens estão o baixo desempenho se acessos consecutivos são feitos a 
palavras com mesmo índice e um ​hit ratio inferior ao de caches com mapeamento 
associativo. 
Já no Mapeamento Totalmente Associativo, como já explicado, um bloco da 
memória principal pode ser colocado em qualquer posição da cache, ou seja, um bloco de 
memória pode ser associado a qualquer entrada da cache. Neste contexto, este tipo de 
mapeamento requer que sejam pesquisadas todas as entradas da cache, e, em virtude 
disto, para reduzir o tempo de pesquisa são usado comparadores para cada entrada da 
cache. 
Em função da necessidade de implementação desses comparadores o custo de 
hardware ​acaba sendo mais alto. Sendo assim, este tipo de mapeamento é mais adequado 
para caches pequenas. 
No Mapeamento Associativo por Conjunto ou Bloco Associativo, existe um número 
fixo de posições na cache (no mínimo duas), nas quais cada bloco pode ser colocado. A 
cache associativa ​n ​é uma cache associativa por conjunto com ​n ​posições possíveis para 
guardar um bloco. É composta por um determinado número de conjuntos, cada conjunto 
com ​m ​blocos. 
Nesta modalidade de mapeamento, cada bloco da memória principal é mapeado 
para um dos conjuntos da cache, determinado pelo campo de índice do endereço, sendo 
que o bloco pode ser colocado em qualquer dos elementos desse conjunto. 
No que diz respeito à associatividade nas caches convém destacar que o aumento 
do grau de associatividade, geralmente, resulta na redução de taxa de faltas, porém há a 
desvantagem do aumento de tempo para tratamento do acerto e também o custo em 
hardware​. 
A vantagem do mapeamento completamente associativo é a máxima flexibilidade no 
posicionamento de qualquer palavra ou linha da memória principal em qualquer palavra ou 
linha da cache. Dentre as desvantagens estão o custo em ​hardware ​e a necessidade da 
utilização de algoritmo de substituição, em ​hardware​, para selecionar uma linha da cache 
como consequência de um ​miss​. 
O Mapeamento Associativo por Conjunto, em comparação ao mapeamento 
completamente associativo, tem a vantagem de os comparadores serem compartilhados por 
todos os conjuntos, e, por conseguinte, o algoritmo de substituição só precisa considerar 
linhas dentro de um conjunto apenas. 
Convém destacar que o aumento no custo de ​hardware ​à medida que se aumenta a 
associatividade, mencionado anteriormente, se dá porque há também um aumento do 
número de ​tags que serão armazenadas na memória Cache. Portanto, se há a necessidade 
de mais ​tags​, e estas são armazenadas na Cache, terá que ter uma quantidade maior de 
bits somente para realizar a identificação da posição que estão os dados na Cache. 
Este custo, por conseguinte, é proporcional, ou seja, quanto maior o associativismo 
maior será a quantidade de tags para identificar os dados na memória, e maior será a 
quantidade de bits necessários. 
Quando se aumenta a associatividade também é necessário a implementação de 
mais comparadores, que serão utilizados para pode verificar se um determinado dado ou 
instrução estão em determinado (bloco). A Figura 3 apresenta uma ilustração de uma 
Cache com Mapeamento Direto à esquerda, e uma Cache com Mapeamento Conjunto 
Associativo à direita. 
Verifique que na Figura 3 também estão assinaladas as informações que são 
armazenadas na Cache, ou seja, os bits de memória que precisam ser implementados na 
Cache, por exemplo, o ​val.​, ​tag e a informação propriamente dita. Este é um dos motivos da 
impossibilidade de não se utilizar somente a Cache para armazenar informações, e sim uma 
Hierarquia de Memória com diferentes níveis, cada nível com um tipo de tecnologia e custos 
diferentes, uma vez que a Cache necessita, além dos bits para armazenar a informação, 
também bits adicionais (de controle), para poder referenciar estas informações. A seguir 
será retomada a explicação sobre o custo de ​hardware dos diferentes tipos de Mapeamento 
utilizados em memória Cache. 
 
 
Observe que no Mapeamento Direto (à esquerda) há apenas uma porta AND e um 
comparador, uma vez que o índice já leva ao bloco, bastando apenas saber se o ​tag é igual 
ou não e se o bit de validade é válido ou não. Já no Mapeamento Conjunto Associativo de 4 
vias (à direita) há quatro pares de comparador e portas lógica AND, além de uma porta 
lógica OR para verificar de onde veio o hit, e um MUX de 4 entradas para saber qual dos 4 
blocos é o correto (quando o dado sai da memória é necessário que ele passe por este 
MUX), por este motivo que o aumento da associatividade aumenta o tempo de acerto pois 
haverá um custo de processamento do MUX, além do custo de ​hardware ​já mencionado. 
Quanto maior o tamanho do cache associativo, mais lento será. Além disso, são 
necessárias mais ​tags para identificar onde a informação está, pois esta poderá estar nas 4 
diferentes vias do conjunto. 
De acordo com o exposto, convém destacar que por mais que o método de 
Mapeamento Conjunto Associativo tenha um desempenho superior ao Mapeamento Direto, 
é necessário também se levar em conta outros fatores, como por exemplo, o custo em 
hardwareque estes diferentes métodos de mapeamento de memória Cache possuem, 
principalmente levando em conta que o tamanho da memória Cache é dada pela 
quantidade de bits de memória, ou seja, quanto maior a quantidade de ​tags para 
identificação de um dado na memória maior será o tamanho da Cache também. É 
necessário haver um equilíbrio, por exemplo, entre quantos bits são utilizados para a ​tag e 
quantos bits são utilizados para informações.