P1_2012.2 - Com gabarito

Prévia do material em texto

P1 - Arquiteturas Avançadas de Computadores I
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) (2,0) Um arquiteto de computadores precisa projetar o pipeline de um novo processador. Ele tem um núcleo de um programa exemplo com 109 instruções. Cada instrução 
exige 10ns para terminar.
a) (1,0) Quanto tempo será necessário para executar esse núcleo de programa em um processador sem pipeline?
Resp.: Temos 109 instruções, sendo que cada uma leva 10ns (ou 10 * 10-9s) para executar. Portanto:
Tempo total = 109 * 10 * 10-9s = 10s
b) (1,0) O processador mais moderno tem cerca de 20 estágios de pipeline. Suponha que ele tenha um pipeline perfeito. Qual é o tempo do ciclo deste novo processador 
(considerando que uma instrução leva 10ns para terminar)? Qual é o ganho de velocidade conseguido em comparação com o processador sem pipeline?
Resp.: Se o pipeline é perfeito, não temos bolhas causadas por hazards e todos os estágios são perfeitamente balanceados. Sendo assim, o tempo de execução 
de 1 estágio é de 10ns / 20 = 0,5ns (tempo do ciclo). O pipeline leva 19 ciclos para "encher" e, depois disto, temos 1 instrução pronta a cada ciclo. Portanto, o 
programa estará completo em 19 + 109 ciclos (que pode ser aproximado para 109 ciclos, pois os 19 ciclos iniciais são irrelevante, dada a grande quantidade de 
instruções). Portanto:
Tempo total = 109 * 0,5 * 10-9s = 0,5s, ou seja, o ganho de velocidade é de aproximadamente 20 vezes em relação ao processador sem pipeline.
2) (2,0) Quais fatores influenciam na latência das instruções e quais fatores influenciam na vazão das instruções em um processador com pipeline?
Resp.: Citaremos aqui os principais fatores abordados neste curso, embora existam diversos outros.
Fatores que influenciam na latência (tempo do ciclo):
1 - Balanceamento dos estágios - O tempo do ciclo de um processador com pipeline é dado pelo tempo do estágio mais longo, sendo assim, um pipeline 
desbalanceado aumenta o tempo do ciclo.
2 - Hazards - Para evitar a ocorrência de hazards, muitas vezes, o caminho de dados de um processador com pipeline é modificado, como é o exemplo da mudança 
da comparação de desvios condicionais no MIPS para o estágio ID, ou mesmo a criação de mecanismos de encaminhamento. Dependendo das características destas 
soluções, o tempo do ciclo pode ser afetado, devido ao aumento da complexidade dos estágios. Preocupações com hazards não existem em processadores sem 
pipeline. Hazards, portanto, geralmente acarretam em overheads no caminho de dados.
3 - Profundidade do pipe - Quanto mais profundo o pipe, mais difícil ter estágios balanceados e maior é a chance da ocorrência de hazards.
Fatores que influenciam na vazão (quantidade de instruções prontas por ciclo de clock):
1 - Hazards - A existência de hazards não resolvidos por mecanismos da arquitetura gera bolhas no pipeline, ou seja, um atraso no término de algumas instruções. 
Hazards de dados, por exemplo, quando não resolvidos pela técnica de encaminhamento ou por reordenação de código, causarão um stall no pipe. No caso de 
hazards de controle, um desvio previsto incorretamente irá acarretar em um flush no pipe para cancelar as instruções buscadas incorretamente e carregar a 
instrução do alvo correto.
2 - Profundidade do pipe - Quanto mais profundo maior é a chance da ocorrência de hazards.
3 - Ocorrência exceções - causam flush no pipe para cancelar as instruções afetadas e chamar o SO para o tratamento. 
3) (5,0) Considere o trecho de código abaixo e responda:
lw $t0, 0($t1)
sw $t0, 0($t0)
add $t2,$t3,$t4
addi $t3, $t2, 4
beq $t3, $t0, label
a) (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)?
Resp:
lw $t0, 0($t1)
sw $t0, 0($t0)
add $t2,$t3,$t4
addi $t3, $t2, 4
beq $t3, $t0, label
b) (1,0) Supondo que o código acima já tenha sido montado para o processador MIPS visto em aula e que não tenhamos nenhum mecanismo de forwarding no 
processador. Ocorrerá alguma bolha? Mostre como será a execução das instruções usando o diagrama de representação de pipelines visto em aula. Quantos ciclos 
serão necessários para executar o programa?
Resp: Sim, teremos bolhas. O programa irá executar em 15 ciclos. O diagrama segue abaixo:
c) (1,5) É possível reordenar o código para reduzir o número de bolhas encontrado no item b? Como fica o código ordenado?
Resp.: Sim, segue o código reordenado e o diagrama de execução
:
add $t2,$t3,$t4
lw $t0, 0($t1)
addi $t3, $t2, 4
sw $t0, 0($t0)
beq $t3, $t0, label
d) (1,5) Usando o código do item c, considerando todas as possibilidades de forwarding, conforme a tarefa 2 e sabendo que a comparação na instrução beq é feita no 
estágio EX, 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 o programa?
Resp.: Serão necessários 9 ciclos para executar o programa. O diagrama segue abaixo.
4) (3,0) Temos um núcleo de programa consistindo em 5 desvios condicionais. O núcleo do programa será executado milhares de vezes. A seguir estão os resultados de cada 
desvio para uma execução do núcleo do programa (T=tomado, N=não tomado).
Branch 1: T-T-T
Branch 2: N-N-N-N
Branch 3: T-N-T-N-T-N
Branch 4: T-T-T-N-T
Branch 5: T-T-N-T-T-N-T
Considere que o comportamento de cada desvio permanece o mesmo para cada execução do núcleo do programa. Para esquemas dinâmicos, suponha que cada desvio tenha 
seu próprio buffer de previsão e que cada buffer seja inicializado com o mesmo estado antes de cada execução. Liste as previsões e a exatidão das previsões para os seguintes 
esquemas de previsão de desvios:
a) (1,0) Sempre não tomado.
Resp.: Este mecanismo é estático. Portanto, todas as previsões serão de não tomado.
Situação Ocorrência 1 Ocorrência 2 Ocorrência 3 Ocorrência 4 Ocorrência 5 Ocorrência 6 Ocorrência 7 Acertos % Acertos
Branch 1 Errado Errado Errado 0 0
Branch 2 Correto Correto Correto Correto 4 100
Branch 3 Errado Correto Errado Correto Errado Correto 3 50
Branch 4 Errado Errado Errado Correto Errado 1 20
Branch 5 Errado Errado Correto Errado Errado Correto Errado 2 28,57
Percentual de acerto geral = 10/25 = 40%
b) (1,0) Previsor de 1 bit, inicializado para prever "tomado".
Resp.: Este mecanismo é dinâmico. Quando erramos a previsão, a próxima previsão será oposta da anterior.
Situação Ocorrência 
1
Ocorrência 2 Ocorrência 3 Ocorrência 4 Ocorrência 5 Ocorrência 6 Ocorrência 7 Acertos % 
Acertos
Branch 1 Previsão T T T
Status Correto Correto Correto 3 100
Branch 2 Previsão T N N N
Status Errado Correto Correto Correto 3 75
Branch 3 Previsão T T N T N T
Status Correto Errado Errado Errado Errado Errado 1 16,67
Branch 4 Previsão T T T T N
Status Correto Correto Correto Errado Errado 3 60
Branch 5 Previsão T T T N T T N
Status Correto Correto Errado Errado Correto Errado Errado 3 42,86
Percentual de acerto geral = 13/25 = 52%
c) (1,0) Previsor de 2 bits, inicializado para prever "tomado" levemente.
Resp.: Este mecanismo é dinâmico e segue o seguinte diagrama:
Todas as previsões começam no estado 10.
Situação Ocorrência 
1
Ocorrência 2 Ocorrência 3 Ocorrência 4 Ocorrência 5 Ocorrência 6 Ocorrência 7 Acertos % 
Acertos
Branch 1 Previsão T (10) T (11) T (11)
Status Correto Correto Correto 3 100
Branch 2 Previsão T (10) N (00) N (00) N (00)
Status Errado Correto Correto Correto 3 75
Branch 3 Previsão T (10) T(11) T(10) T (11) T(10) T (11)
Status Correto Errado Correto Errado Correto Errado 3 50
Branch 4 Previsão T (10) T (11) T (11) T (11) T(10)
Status Correto Correto Correto Errado Correto 4 80
Branch 5 Previsão T (10) T (11) T (11) T(10) T (11) T (11) T(10)
Status Correto Correto Errado Correto Correto Errado Correto 5 71,43
Percentual de acerto geral = 18/25 = 72%