Prova 2012.2

Prévia do material em texto

GABARITO
PR - Arquiteturas Avançadas de Computadores
Professor: Leandro Marzulo
2012-2
Nome:
Instruções: Esta prova é composta de quatro questões totalizando 12 (doze) pontos, sendo a nota máxima 10 (dez). Responda as questões de forma sucinta e clara. O uso de lápis é permitido, no entanto, pedidos de revisão serão considerados apenas para questões respondidas a caneta. BOA PROVA!
1) (4,0) Considere o trecho de código abaixo e responda:
loop:	lw $t0, 0($t1)
	addi $t0, $t0, 5
	sw $t0, 0($t1)
	addi $t1, $t1, -4
	beq $t1, $t3, loop
(1,0) Quais são as dependências de dados existentes entre as instruções (marque as dependências no próprio código do enunciado, usando diferentes marcações para cada dependência)?
loop:	lw $t0, 0($t1)
	addi $t0, $t0, 5
	sw $t0, 0($t1)
	addi $t1, $t1, -4
	beq $t1, $t3, loop
(1,0) Supondo que o código acima já tenha sido montado para o processador MIPS que implementa todas as possibilidades de forwarding e sabendo que a comparação na instrução beq é feita no estágio ID. Ocorrerá alguma bolha? Mostre como será a execução das instruções usando o diagrama de representação de pipelines visto em aula. Mostre todos os encaminhamentos feitos no diagrama. Quantos ciclos serão necessários para executar uma iteração do laço?
Teremos duas bolhas!
São necessários 11 ciclos para executar uma iteração do loop.
 (2,0) É possível reordenar o código para reduzir o número de bolhas encontrado no item b (considere modificar também algumas instruções)? Como fica o código ordenado que resulta no menor número de bolhas? Mostre o diagrama de execução para o novo código, incluindo os encaminhamentos.
Sim. Segue o código reordenado:
loop:	lw $t0, 0($t1)
	addi $t1, $t1, -4
	addi $t0, $t0, 5
	sw $t0, 4($t1)
	beq $t1, $t3, loop
Não teremos duas bolhas!
São necessários 9 ciclos para executar uma iteração do loop.
2) (3,0) Considere o código original da questão 1. Sabendo que o laço é executado 5 vezes, informe os mecanismos de previsão de desvio abaixo: (i) a previsão dada em cada rodada, (ii) se cada previsão está certa ou errada e (iii) o percentual de acerto do mecanismo para o programa.
Se o laço é executado 5 vezes, temos 4 desvios tomados e 1 não tomado (T-T-T-T-N)
(1,0) Previsão de sempre tomado;
A previsão em todas as rodadas é a mesma (tomado). O quadro a seguir mostra a previsão, o que deve ocorrer de fato e o status do previsor (acerto ou erro), para cada iteração do laço:
	Real
	T
	T
	T
	T
	N
	Previsão
	T
	T
	T
	T
	T
	Status
	Acerto
	Acerto
	Acerto
	Acerto
	Erro
Logo, o percentual de acerto é de 4/5 = 80%.
(1,0) Previsão de sempre não tomado;
A previsão em todas as rodadas é a mesma (não tomado). O quadro a seguir mostra a previsão, o que deve ocorrer de fato e o status do previsor (acerto ou erro), para cada iteração do laço:
	Real
	T
	T
	T
	T
	N
	Previsão
	N
	N
	N
	N
	N
	Status
	Erro
	Erro
	Erro
	Erro
	Acerto
Logo, o percentual de acerto é de 1/5 = 20%.
(1,0) Preditor de 1 bit com previsão inicial de não tomado;
Nesse caso, a previsão em cada rodada depende da rodada anterior. O quadro a seguir mostra a previsão, o que deve ocorrer de fato e o status do previsor (acerto ou erro), para cada iteração do laço:
	Real
	T
	T
	T
	T
	N
	Previsão
	N
	T
	T
	T
	T
	Status
	Erro
	Acerto
	Acerto
	Acerto
	Erro
Logo, o percentual de acerto é de 3/5 = 60%.
3) (3,5) Ainda para o programa original da questão 1, considere um computador com despacho múltiplo estático (feito em compilador) que permite a execução em paralelo de instruções de acesso a memória (LW e SW) com as demais instruções. Considere que o processador implementa um pipeline de 5 estágios com forwarding e que não existe, no processador, a detecção de dependências entre instruções que executam em paralelo (como no exemplo do livro). Assuma também que a máquina em questão implementa um preditor de desvio perfeito (que sempre acerta o resultado da previsão, não resultando em flushes). Responda:
(1,5) Suponha que o compilador usado, além de reordenar e escalonar instruções, seja capaz de alterar instruções (modificar deslocamentos de acesso a memória e imediatos nas instruções ADDI). Qual é o escalonamento que proporciona o melhor desempenho? Quantas instruções por ciclo serão entregues (IPC médio), desconsiderando os ciclos para encher o pipe?
Este é o melhor escalonamento:
	Ciclo
	Instrução sem acesso a memória
	Instrução de acesso a memória
	1
	
	lw $t0, 0($t1)
	2
	addi $t1, $t1, -4
	
	3
	addi $t0, $t0, 5
	
	4
	beq $t1, $t3, loop
	sw $t0, 4($t1)
Com este escalonamento teremos um IPC médio de 5/4 = 1,25.
(2,0) Desenrole o laço para dobrar o número de elementos processados por iteração. Considere que o número de iterações do laço original é múltiplo de 2. Mostre o código desenrolado, o melhor escalonamento (considerando o mesmo compilador do item a) e o IPC médio (desconsiderando os ciclos para encher o pipe).
Desenrolando o loop, temos:
loop:	lw $t0, 0($t1)
	lw $t2, -4($t1)
	addi $t0, $t0, 5
	addi $t3, $t3, 5
	sw $t0, 0($t1)
	sw $t3, -4($t1)
	addi $t1, $t1, -8
	beq $t1, $t3, loop
Este é o melhor escalonamento:
	Ciclo
	Instrução sem acesso a memória
	Instrução de acesso a memória
	1
	addi $t1, $t1, -8
	lw $t0, 0($t1)
	2
	
	lw $t2, 4($t1)
	3
	addi $t0, $t0, 5
	
	4
	addi $t2, $t2, 5
	sw $t0, 8($t1)
	5
	beq $t1, $t3, loop
	sw $t2, 4($t1)
IPC médio de 8/5 = 1,6.
4) (1,5) Qual é a importância de um protocolo de coerência de cache em um sistema com múltiplos processadores. Em linhas gerais, como um protocolo de coerência de cache funciona (explique a importância das invalidações e do write-back)?
O protocolo de coerência de cache mantém uma visão global consistente dos dados compartilhados por diferentes processadores na memória. Embora os diversos processadores, geralmente possuam uma memória principal única, cópias de blocos de dados podem ser mantidas nas caches privadas de cada processador. O protocolo de coerência garante que alterações em um bloco de cache de um processador sejam vistas por outros processadores que possuam uma cópia desse bloco em suas caches. Isso pode ser feito por atualizações em todas as cópias no momento em que um processador faz uma modificação. Entretanto, este broadcast de informação é custoso, visto todos os processadores que possuem uma cópia do bloco terão que atualizar o bloco, mesmo que esse bloco não seja mais acessado no futuro. Para resolver este problema, o processador que altera o bloco faz broadcast de um pedido de invalidação nas cópias. Cada processador, seja para invalidar ou atualizar um bloco, geralmente monitora o barramento comum em busca das mensagens de atualização/invalidação. Quando um processador acessa um bloco inválido ele terá que buscar a última versão do bloco no processador que fez a última alteração ou na própria memória (caso já tenha sido feito um write-back). Em caches write-through, toda escrita na cache é repassada diretamente para os níveis inferiores na hierarquia de memória. Este método facilita a coerência, pois ao buscar um bloco inválido, o processador tem a certeza de que a última versão está na memória. Entretanto, se tivermos escritas consecutivas em um bloco, pagaremos, para cada escrita, a penalidade de ir na memória, mesmo sabendo que poderíamos escrever somente o último valor. Com uma cache write-back, o bloco só é escrito no nível inferior da hierarquia quando for necessário substituir o bloco. Esta solução apresenta melhor desempenho, mas torna mais complexo o protocolo de coerência.