aula-IFC-SUP-CCO-ArqComp-07-hierarquia-mem-CACHE-NOTAS_AULA

Prévia do material em texto

<p>INSTITUTO FEDERAL</p><p>Catarinense</p><p>Campus Videira</p><p>Arquitetura de Computadores</p><p>Memória Interna: Cache</p><p>Gerson Luiz Camillo</p><p>Março 2019</p><p>Memória Cache: Introdução e</p><p>Motivação</p><p>Motivação: gap de desempenho CPUxRAM</p><p>Figura 1: Diferença (gap) de performance entre CPU e DRAM no decorrer do tempo.</p><p>Motivação: gap de desempenho CPUxRAM</p><p>Figura 2: Fatores de aumento de velocidade de CPU e DRAM e fator de aumento de</p><p>densidade da DRAM. 3</p><p>Motivação: gap de desempenho CPUxRAM e Cache</p><p>Solução: hierarquia de memória.</p><p>Cache</p><p>"Um lugar seguro para esconder ou guardar coisas."Webster’s New</p><p>World Dictionary</p><p>Representar o nível da hierarquia de memória entre o</p><p>processador e a memória principal.</p><p>4</p><p>Motivação: gap de desempenho CPUxRAM</p><p>O processador tem um tempo de acesso aproximado determinado</p><p>principalmente pelo nível 1 da hierarquia e ainda tenha uma</p><p>memória tão grande quanto o último nível (memória RAM).</p><p>Tempos de acesso típicos:</p><p>- Memória SRAM: 0,5 - - 2,5 ns</p><p>- Memória DRAM: 50 - 70 ns</p><p>5</p><p>Benefícios das caches</p><p>- Reduz o tempo de acesso médio à</p><p>memória (diminuição da latência).</p><p>- "Amplifica"a banda da memória (vazão).</p><p>- Eficiência energética: quando comparado a</p><p>processadores com mesmo desempenho mas com</p><p>maiores frequências de operação.</p><p>- Possibilita rápida comunicação entre threads.</p><p>6</p><p>Memória Cache: Princípios e</p><p>Definições</p><p>Princípio da localidade</p><p>Os programas acessam uma parte relativamente pequena de seu espaço de</p><p>endereçamento em qualquer instante de tempo. Por exemplo, a CPU executa</p><p>90% do tempo em 10% do código.</p><p>Esse princípio de localidade permite criar a ilusão de uma memória grande que</p><p>podem podemos acessar tão rapidamente quanto uma memória pequena muito</p><p>mais rápida.</p><p>Temporal - ou localidade no tempo</p><p>- O princípio em que se um local de dados é referenciado, então, ele tenderá</p><p>a ser referenciado novamente em breve.</p><p>- Manter próximo ao processador os itens mais acessados recentemente .</p><p>Espacial - ou localidade no espaço</p><p>- O princípio de localidade em que, se um local de dados é referenciado,</p><p>então, os dados com endereços próximos tenderão a ser referenciados em</p><p>breve.</p><p>- Transferir blocos de múltiplas palavras contíguas da memória para níveis</p><p>superiores na hierarquia.</p><p>Caching : ideia da predição baseada na localidade.</p><p>7</p><p>Organização e estrutura da memória cache</p><p>8</p><p>Organização e estrutura da memória cache</p><p>Nível superior: está próximo ao processador e é o mais rápido.</p><p>Nível inferior: está longe do processador e se torna cada vez mais</p><p>lento.</p><p>9</p><p>Organização e estrutura da memória cache</p><p>K = número de palavras por bloco</p><p>M = quantidade de blocos = 2n/K</p><p>m = quantidade de linhas na cache</p><p>10</p><p>Organização e estrutura da memória cache</p><p>Blocos</p><p>- Um bloco é um conjunto de 2n bytes em endereço consecutivo na</p><p>memória RAM.</p><p>- Cada bloco é constituído por um conjunto de endereços, sendo todos os</p><p>blocos de tamanho igual.</p><p>- Determina quanta informação é movida entre a RAM e a cache</p><p>(maximizar performance).</p><p>m</p><p>continuação.</p><p>Política de escrita</p><p>Write Through ou Write Back.</p><p>Algoritmo de substituição</p><p>Usado menos recentemente (LRU - Least Recently Used).</p><p>Primeiro a entrar, primeiro a sair (FIFO - First in, First out)</p><p>Usado menos frequentemente (LFU - Least Frequently Used)</p><p>Aleatória.</p><p>25</p><p>Memória Cache: esquemas de</p><p>mapeamento</p><p>Esquemas de mapeamento de dados da RAM para cache</p><p>Como a memória RAM é mapeada na memória cache. Determina a</p><p>organização da cache.</p><p>Mapeamento direto</p><p>Cada local da memória é mapeado exatamente para um local</p><p>na cache.</p><p>Associativa</p><p>Um bloco pode ser posicionado em qualquer lugar da cache.</p><p>Associativa por conjunto</p><p>Possui um número fixo de locais (no mínimo dois) onde cada</p><p>bloco pode ser colocado.</p><p>26</p><p>Esquemas de mapeamento de dados da RAM para cache</p><p>27</p><p>Cache de mapeamento direto</p><p>Atribuição de um local na cache: basear no endereço da palavra na</p><p>memória.</p><p>Mapeia cada bloco da memória principal para uma</p><p>determinada linha de cache.</p><p>Cada bloco somente pode ser carregado na linha de cache</p><p>especificamente mapeada para tal.</p><p>Posição de um bloco de memória é determinado por:</p><p>(endereco−ou−num−do−bloco)modulo(num−de−blocos−na−cache)</p><p>Se número de entradas na cache for potência de dois, então o</p><p>módulo serão os log2 bits menos significativos do endereço.</p><p>28</p><p>Cache de mapeamento direto</p><p>Exemplo: cache com 8 linhas (blocos), então usará os três bits</p><p>menos significativos do endereço (8 = 23).</p><p>Endereço de me-</p><p>mória</p><p>Posições da cache Tag (parte superior</p><p>endereço)</p><p>000001 001 00</p><p>11101 101 11</p><p>10101 101 10</p><p>29</p><p>Cache de mapeamento direto</p><p>Exemplo: cache com 8 linhas (blocos), então usará os três bits</p><p>menos significativos do endereço (8 = 23).</p><p>30</p><p>Cache de mapeamento direto</p><p>- Precisa conter apenas a parte superior do endereço.</p><p>31</p><p>Cache de mapeamento direto</p><p>32</p><p>Cache de mapeamento direto</p><p>33</p><p>Cache de mapeamento direto</p><p>34</p><p>Cache de mapeamento direto</p><p>35</p><p>Cache de mapeamento direto</p><p>36</p><p>Cache de mapeamento direto</p><p>37</p><p>Cache de mapeamento direto</p><p>38</p><p>Cache de mapeamento direto</p><p>Uma cache de 4KiB = 1024 linhas</p><p>com blocos do tamanho de uma</p><p>palavra de 32 bits.</p><p>Índice: especifica de modo único o</p><p>endereço de memória da palavra</p><p>contida no bloco de cache.</p><p>Tamanho da cache = 2n blocos,</p><p>sendo n o número de bits do índice.</p><p>39</p><p>Questões sobre a cache de mapeamento direto</p><p>Vantagem: mais simples e barata implementação de cache.</p><p>Desvantagens e problemas: - Múltiplos blocos podem mapear</p><p>para uma única linha de cache.</p><p>- Algumas linhas podem ser requisitadas frequentemente por</p><p>diferentes blocos, enquanto outras linhas serem raramente</p><p>requisitadas, o que implica uso não ótimo da capacidade total da</p><p>cache.</p><p>40</p><p>Questões sobre a cache de mapeamento direto</p><p>Tamanho de bloco</p><p>Tamanho real = 2n blocos X (tamanho do bloco + tamanho da tag</p><p>+ tamanho campo validade)</p><p>Por exemplo: para uma cache de 16KiB e 1024 blocos de 4</p><p>palavras (128 bits)</p><p>Tamanho real: 18,4 KiB para 16KiB.</p><p>Tamanho de bloco e taxa de falhas</p><p>Quanto maior o tamanho do bloco:</p><p>- diminui a taxa de falhas</p><p>- melhora a eficiência reduzindo a quantidade de armazenamento de</p><p>tag em relação à quantidade de dados</p><p>Problema: aumenta a penalidade das falhas. 41</p><p>Questões sobre a cache de mapeamento direto</p><p>Figura 3: Fonte: obtido de Patterson e Hennessy (2017).</p><p>42</p><p>Caches totalmente associativa e</p><p>associativa por conjunto</p><p>Cache totalmente associativa</p><p>O controlador de cache compara o número de bloco e o campo de TAG de</p><p>todas as linhas simultaneamente (busca associativa).</p><p>Se um TAG combina o número de bloco e o bit válido é ON, então é um</p><p>acerto, senão uma falta.</p><p>Vantagens:</p><p>- Permite que o bloco de memória possa ser carregado em qualquer linha da</p><p>cache.</p><p>- Possui uma taxa de acerto mais alta que caches de mapeamento direto.</p><p>Desvantagem: mecanismo de comparação é onerosa (comparadores), o que a</p><p>torna mais lenta que a de mapeamento direto.</p><p>Consequências: O projeto de cache totalmente associativa somente é usado</p><p>para pequenas capacidades (L1).</p><p>43</p><p>Cache totalmente associativa</p><p>44</p><p>Associativa por conjunto</p><p>Cache associativa por conjunto de k vias: cada k representa a</p><p>associatividade do conjunto.</p><p>k-way associative set</p><p>Conjunto determinado por:</p><p>(numero−do−bloco)modulo(numero−de−conjuntos−na−cache)</p><p>45</p><p>Associativa por conjunto</p><p>Figura 4: Fonte: obtido de Patterson e Hennessy (2017).</p><p>46</p><p>Associativa por conjunto: exemplo</p><p>Exemplo: cache associativa por conjunto com duas vias (dois</p><p>conjuntos)</p><p>Tag de endereço: fornece o endereço do bloco (comparação</p><p>associativa)</p><p>Valor do índice (conjunto): usado para selecionar o conjunto</p><p>contendo o endereço de interesse (mapeamento direto)</p><p>Considerando um conjunto de endereços de memória: 0, 8, 0, 6, 8,</p><p>5, 7, 4 e 3.</p><p>Considerando a cache tem dois conjuntos (índices 0 e 1) com dois</p><p>elementos por conjunto (duas vias): então pelo cálculo do</p><p>mapeamento direto, tem-se:</p><p>47</p><p>Associativa por conjunto: exemplo</p><p>Endereço de memória Conjunto</p><p>0 (0 modulo 2) = 0</p><p>3 (3 modulo 2) = 1</p><p>4 (4 modulo 2) = 0</p><p>5 (5 modulo 2) = 1</p><p>6 (6 modulo 2) = 0</p><p>7 (7 modulo 2) = 1</p><p>8 (8 modulo 2) = 0</p><p>48</p><p>Associativa por conjuntos: questões de desempenho</p><p>Impacto do tamanho do conjunto (associatividade) nas falhas,</p><p>considerando os extremos entre diretamente mapeada para</p><p>totalmente associativa. O tamanho total da cache é mantido</p><p>constante.</p><p>49</p><p>Associativa por conjuntos: questões de desempenho</p><p>Impacto do tamanho do conjunto (associatividade) na razão de falhas</p><p>cache, considerando diferentes tamanhos.</p><p>A partir duas vias e, principalmente, quatro vias, não há um ganho</p><p>significativo aumentando a associatividade.</p><p>As caches pequenas se beneficiam mais que as grandes com o aumento</p><p>da associatividade.</p><p>50</p><p>Associativa por conjuntos: variações</p><p>Cache diretamente mapeada: os conjuntos associativos contém cada um uma</p><p>única linha (bloco).</p><p>Cache totalmente associativa: associativa por conjuntos com um único</p><p>conjunto.</p><p>Esquema Número de Conjuntos Blocos por conjunto</p><p>Mapeamento direto Número de blocos na cache 1</p><p>Associativo por conjunto Número de blocos na cache /</p><p>Associatividade</p><p>Associatividade (normal-</p><p>mente de 2 a 16)</p><p>Totalmente associativo 1 Número de blocos na cache</p><p>51</p><p>Associativa por conjuntos: variações</p><p>52</p><p>Outros parâmetros em cache</p><p>Algoritmos de substituição</p><p>Nas caches associativas e associativas por conjunto, quando ocorre uma colisão</p><p>(falha), há necessidade de uma algoritmo de substituição de linha (bloco).</p><p>LRU (Least Recently Used) - Usado Menos Recentemente</p><p>- Substituir o que permaneceu mais tempo sem referências.</p><p>- Para caches de duas vias: uso de um bit (USE) que recebe o valor 1 para um</p><p>acesso.</p><p>FIFO (First In, First Out) - Primeiro a Entrar, Primeiro a Sair</p><p>- Substituir o que esteve mais tempo na cache.</p><p>- Implementação com a técnica round-robin ou de buffer circular.</p><p>LFU (Least Frequently Used) - Usado Menos Frequentemente</p><p>- Substituir o que teve menos referências.</p><p>- Implementação através de um contador.</p><p>Aleatória</p><p>Implementação simples.</p><p>53</p><p>Algoritmo de substituição</p><p>Algoritmos usados na prática:</p><p>- Para associatividade de duas vias, o LRU é o que é mais simples</p><p>de ser implementado e o que oferece menor taxa de falhas.</p><p>- Para associatividades maiores: LRU aproximado ou Aleatório.</p><p>Para esses casos o LRU começa a se tornar oneroso em termos de</p><p>implementação. A taxa de falhas entre LRU aproximado e Aleatório</p><p>se aproximam para caches de tamanho maior.</p><p>- Para caches grandes: a substituição aleatória á melhor opção.</p><p>Os algoritmos precisam ser eficientes para implementação em</p><p>hardware.</p><p>54</p><p>Política de escrita</p><p>Problema: um bloco está para ser substituído, mas ele foi alterado.</p><p>Duas situações:</p><p>a) A memória principal pode ter sido alterada por E/S;</p><p>b) Em sistemas multinúcleos, um core pode ter alterado o mesmo</p><p>endereço de memória em sua cache local.</p><p>Write Through</p><p>- As informações são escritas na cache e na memória de nível inferior</p><p>(memória principal).</p><p>- Outras caches podem monitorar o barramento para atualização.</p><p>- Vantagem: implementação simples, mas precisa</p><p>de buffer de escrita.</p><p>- Desvantagem: gera um tráfego alto.</p><p>55</p><p>Política de escrita</p><p>Write Back</p><p>- Escritas apenas no bloco da cache.</p><p>- A alteração faz com que o bit de modificação ou bit de uso seja</p><p>marcado.</p><p>- Apenas na substituição, a escrita é propagada para a memória principal.</p><p>- Problema é que partes da memória podem ficar inválidas</p><p>(inconsistência).</p><p>- Vantagens: boa performance pois a escrita ocorre na velocidade do</p><p>processador (não há stall) e possibilidade de diversas escritas em um</p><p>único bloco.</p><p>Conforme Stallings (2017):</p><p>- Porcentagem de referências à memória que são escritas: 15%, 33%</p><p>(HPC: multiplicação de vetores), 50% (HPC: transposição de matrizes)</p><p>Em sistemas multiprocessadores e multinúcleos: problema de coerência</p><p>de cache.</p><p>56</p><p>Cache: questões de performance</p><p>Questão de performance</p><p>Evolução da performance (razão de acerto - hit ratio) de L1 e L2</p><p>com o aumento do tamanho da cache.</p><p>57</p><p>Questão de performance</p><p>Taxa de falhas associada às falhas oriundas dos 3 C: compulsórias,</p><p>capacidade e conflito.</p><p>58</p><p>Valores típicos</p><p>As taxas de acerto das caches são na prática maiores que 95%</p><p>(conforme Patterson e Hennessy (2017)</p><p>59</p><p>Valores típicos</p><p>Figura 5: Intel Core I79800X</p><p>Figura 6: Amd Ryzen Treadripper 1920X</p><p>60</p><p>Referências</p><p>Referências I</p><p>61</p><p>Memória Cache: Introdução e Motivação</p><p>Memória Cache: Princípios e Definições</p><p>Memória Cache: esquemas de mapeamento</p><p>Caches totalmente associativa e associativa por conjunto</p><p>Outros parâmetros em cache</p><p>Cache: questões de performance</p>