Lista 3 - Hierarquia de Memoria Respondida

Prévia do material em texto

1) Qual é o impacto de duas organizações de caches diferentes sobre o desempenho de um processador?
· Considere que o CPI com uma cache perfeita é de 1,6, o tempo de ciclo de clock é de 0,35ns, existe 1,4 referência de memória por instrução, o tamanho das duas caches é de 128 KB e ambos possuem tamanho de bloco de 64 bytes.
· Uma cache é mapeada diretamente e a outra é associativa por conjunto com duas vias. Para caches associativas por conjunto, temos que acrescentar um multiplexador para selecionar entre os blocos no conjunto, dependendo do resultado da comparação das tags. Como a velocidade do processador pode estar ligada diretamente à velocidade de um acerto na cache, considere que o tempo de ciclo de clock do processador deva ser esticado 1,35 vez para acomodar o multiplexador de seleção da cache associativa por conjunto.
· Para a primeira aproximação a penalidade por falta na cache é de 65ns para qualquer organização de cache.
· Primeiro, calcule o tempo médio de acesso à memória e depois o desempenho do processador. Considere que o tempo de acerto seja de um ciclo de clock, a taxa de falta de uma cache de 128KB mapeado diretamente seja de 2,1% e a taxa de falta para uma cache associativa por conjunto com duas vias do mesmo tamanho seja de 1,9%.
Resposta:
O tempo médio de acesso à memória é
Tempo médio de acesso à memória = + Tempo de acerto Taxa de falta P× enalidade de falta
Assim, o tempo para cada organização é
Tempo médio de acesso à memória1via = + 0,35 (0,021 65) × = 1,72 ns
Tempo médio de acesso à memória2 vias = × 0,35 1,35+ × (0,019 65) = 1,71 ns
O tempo médio de acesso à memória é melhor para a cache associativa por conjunto com duas vias. O desempenho do processador é
Substituindo (Penalidade por falta × Tempo de ciclo de clock) por 65 ns, o desempenho de cada organização de cache é
 
e o desempenho relativo é
2) Qual tem a menor taxa de falta: uma cache de instruções de 32 KB com uma cache de dados de 32KB ou uma cache unificada de 64KB? A taxa de faltas para uma cache de instrução de 32 KB é de 1,36 faltas por 1.000 instruções. Para uma cache de dados de 32 KB a taxa de faltas será de 38,4 faltas por 1000 instruções. Já para uma cache unificada de 64 KB a taxa de faltas será de 39,4 faltas por 1.000 instruções. Considere que 40% das instruções são instruções de transferências de dados. Considere que um acerto utiliza um ciclo de clock e a penalidade por falta é de 200 ciclos de clock. Um acerto no carregamento ou armazenamento utiliza um ciclo de clock extra em uma cache unificada. Qual o tempo médio de acesso a memória em cada caso? Considere caches write-through com um buffer de escrita e ignore os stalls devidos ao buffer de escrita.
Resposta:
 
 
 
3) Considere uma cache write-back totalmente associativa com muitas entradas de cache que começam vazias. A seguir apresentamos uma sequência de sete operações de memória (o endereço está em colchetes):
Write Mem[200]; Write Mem [100]; Write Mem[100]; Read Mem[200]; Read Mem [100]; Write Mem[200]; Write Mem[100]; Write Mem[300]
Quais são os números de acertos e falhas quando se usam no-write allocate e write allocate?
Resposta:
Para a no-write allocate, o endereço 100 não está na cache e não existe write allocate, de modo que as duas primeiras escritas resultarão em faltas. O endereço 200 também não está na cache, de modo que a leitura também é uma falta. A escrita subsequente no endereço 200 é um acerto. A última escrita em 100 ainda é uma falta. O resultado para a alocação sem escrita são quatro faltas e um acerto. Para a alocação de escrita, os primeiros acessos a 100 e 200 são faltas, e o restante são acertos, pois 100 e 200 são encontrados na cache. Assim, o resultado para a alocação de escrita são duas faltas e três acertos.
4) A transposição de uma matriz troca suas linhas e colunas e é ilustrada a seguir:
Aqui está um código simples em C para mostrar a transposição
Considere que as matrizes de entrada e saída sejam armazenadas na ordem principal de linha. Suponha que você esteja executando uma transposição de uma matriz 256 x 256 de elementos de precisão simples (32 bits) em um processador com cache de dados de 16 KB totalmente associativa nível 1 por substituição LRU, com blocos de 64 bytes. Suponha que a cache tenha a política de escrever-alocar-buscar na escrita para faltas de escrita. Suponha, de modo não realista que a volta dos blocos modificados exija 0 ciclo.
a. Por que a implementação mostrada acima não é ideal?
Resposta:
A ordem de execução é não ideal para a matriz de entrada. Pois mesmo usando uma aplicação de uma otimização de troca de loops criaria uma ordem não ideal para a matriz de saída. Como a troca de loops não é suficiente para melhorar seu desempenho, ele precisa ser bloqueado. 
b. Quantos blocos desta cache precisariam ser usados para alocar uma linha inteira da matriz input e quantos blocos para alocar uma linha
inteira de output?
Resposta:
Cada elemento é 8B. Como um cacheline 64B tem 8 elementos, e cada acesso à coluna resultará na busca de uma nova linha para a matriz não ideal, precisamos de um mínimo de 8x8 (64 elementos) para cada matriz. Portanto, o tamanho mínimo do cache é 128 × 8B = 1 KB
c. Qual o tamanho mínimo de cache necessário para se obter vantagem de uma execução com a técnica de bloqueio?
Resposta:
Técnica de bloqueio: Em vez de operar sobre linhas ou colunas inteiras de um array, os algoritmos bloqueados operam sobre submatrizes ou blocos. O objetivo é maximizar os acessos aos dados carregados na cache, antes que eles sejam substituídos, cada elemento das matrizes tem 4 bytes. Como cada bloco de cache tem 16 elementos e cada acesso a uma coluna de input irá resultar na busca de uma nova linha de output, nós precisamos de, no mínimo 16*16 = 256 elementos de precisão simples para cada matriz (de entrada e de saída). Logo, o tamanho mínimo de cache necessário para se obter vantagem de uma execução com a técnica de bloqueio é de 256* 2 * 4 B = 28 * 2 * 22 = 211 = 2 KB.
d. Escreva um código para realizar a transposição com um parâmetro de tamanho de bloco B que usa B x B blocos.
Resposta:
for (i = 0; i < 256; i=i+B) {
		for (j = 0; j < 256; j=j+B) {
			for(m=0; m<B; m++) {
				for(n=0; n<B; n++) {
					output[j+n][i+m] = input[i+m][j+n];
				}
			}
		}