Prova 2013.2 - P1

Prévia do material em texto

GABARITO 
P1 - Arquiteturas Avançadas de Computadores 
Professor: Leandro Marzulo 
2013-1 
 
Instruções: Esta prova é composta de três 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 um programa composto apenas por instruções de LW e ADD, com o total de 10
9
 instruções. Neste programa as instruções de LW e ADD ocorrem 
alternadamente, sendo a primeira instrução do programa um LW. Cada ADD usa o dado carregado pelo LW imediatamente anterior não há dependências entre instruções de 
ADD e as instruções de LW são totalmente independentes. Responda: 
 
a) (1,0) Quanto tempo será necessário para executar esse programa em um processador sem pipeline e monociclo, considerando que o tempo do ciclo é 13ns 
(1ns = 10
-9
s)? 
 
Resp.: Em um processador monociclo, cada instrução executa em 1 ciclo. Logo, na questão, cada instrução é executada em 13ns. Sendo assim, o tempo total é: 
 
13 * 10
-9
 * 10
9 
s = 13s 
 
b) (1,0) Quanto tempo será necessário para executar esse núcleo de programa em um processador MIPS com pipeline de 5 estágios (visto em sala de aula), COM 
detecção de hazard de dados e SEM forwarding, considerando que o tempo do ciclo é 3ns (1ns = 10
-9
s) e dado que o programa foi compilado sem reordenação de 
instruções? Qual é o ganho de desmpenho conseguido em comparação com o processador sem pipeline? 
 
Resp.: As dependência ocorrem apenas entre cada instrução de ADD e o LW imediatamente anterior. Vamos analisar apenas um trecho do programa: 
 
 
podemos dizer portanto, que, depois que o pipe encher, a cada 4 ciclos teremos 2 instruções finalizadas (ou 1 instrução a cada 2 ciclos - simplificando). Logo: 
 
Tempo de execução = Tempo para encher o pipe + (Tempo para completar uma instrução * número de instruções) 
 
Tempo para encher o pipe = 4 * 3 * 10
-9
s (desprezível, dado o grande número de instruções) 
 
Tempo de execução ≈ Tempo para completar uma instrução * número de instruções 
Tempo de execução ≈ 2 * 3 * 10-9 * 109 s 
Tempo de execução ≈ 6s 
 
13/6 ≈ 2,16 
 
A máquina é 2,16 vezes mais rápida que a versão monociclo. 
 
c) (1,0) Se o processador do item b não tivesse também a unidade de detecção de hazard de dados, para poder executar o programa em questão o que poderia ser feito 
pelo compilador? 
 
Resp.: O compilador pode inserir instruções de NOP (o que é equivalente ao processador gerar bolhas) ou pode reordenar o código para eliminar as bolhas ou reduzir 
a necessidade de NOPs. 
d) (1,0) Quanto tempo será necessário para executar esse núcleo de programa em um processador MIPS com pipeline de 5 estágios (visto em sala de aula), COM 
detecção de hazard de dados, COM forwarding, considerando que o tempo do ciclo é 3ns (1ns = 10
-9
s) e dado que o programa foi compilado sem reordenação de 
código? Qual é o ganho de desempenho conseguido em comparação com o processador sem pipeline? 
 
Resp.: Com forward passamos a ter apenas 1 bolha a cada par LW/ADD, como na figura: 
 
 
 
podemos dizer portanto, que, depois que o pipe encher, a cada 3 ciclos teremos 2 instruções finalizadas (ou 1 instrução a cada 1,5 ciclos - simplificando). Logo: 
 
Tempo de execução = Tempo para encher o pipe + (Tempo para completar uma instrução * número de instruções) 
 
Tempo para encher o pipe = 4 * 3 * 10
-9
s (desprezível, dado o grande número de instruções) 
 
Tempo de execução ≈ Tempo para completar uma instrução * número de instruções 
Tempo de execução ≈ 1,5 * 3 * 10-9 * 109 s 
Tempo de execução ≈ 4,5s 
 
13/4,5 ≈ 2,89 
 
A máquina é 2,89 vezes mais rápida que a versão monociclo. 
 
 
2) (2,0) Quais são a vantagens e desvantagens dos processadores com pipelines profundos (com muitos estágios)? 
 
Resp.: Pipelines profundos possibilitam maior paralelismo. No caso ideal (pipe balanceado, sem overheads no tempo do ciclo e sem hazards), a versão com pipeline é E vezes 
mais rápida que a versão monociclo (E = nº de estágios do pipe). As desvantagens são que pipes profundos, na vida real, causam + hazards e overheads. Quanto mais estágios, 
mais possibilidades de hazards devem ser tratadas. 
 
3) (6,0) Considere o trecho de código abaixo e responda: 
 
loop: lw $t0, 0($t1) 
 add $t2,$t0,$t0 
 sw $t0, 0($t2) 
 addi $t1, $t1, -4 
 bne $t1, $t3, loop 
 
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.: 
 
loop: lw $t0, 0($t1) 
 add $t2,$t0,$t0 
 sw $t0, 0($t2) 
 addi $t1, $t1, -4 
 bne $t1, $t3, loop 
 
Note que a instrução ADDI escreve em $t1 e na iteração seguinte esse valor será lido pelo LW e pelo próprio ADDI. 
 
b) (1,0) Considerando todas as possibilidades de forwarding, conforme a tarefa 2 e sabendo que a comparação na instrução bne é feita no estágio EX, mostre como será a 
execução das instruções de uma iteração do laço (sem reordenação) 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 trecho do programa? 
 
Resp.: Considerando apenas as dependências de 1 iteração, temos: 
 
 
 
Esse trecho de código executa 10 ciclos. 
 
c) (1,0) Reordene o código de forma a reduzir ao máximo o número de bolhas e mostre o novo diagrama com encaminhamentos. Quantos ciclos serão necessários para 
executar o trecho do programa? 
 
Resp.: Reordenando o código, podemos eliminar a bolha existente no item b. O código reordenado é o seguinte: 
 
loop: lw $t0, 0($t1) 
 addi $t1, $t1, -4 
 add $t2,$t0,$t0 
 sw $t0, 0($t2) 
 bne $t1, $t3, loop 
 
 
Considerando apenas as dependências de 1 iteração, temos: 
 
 
 
Esse trecho de código executa 9 ciclos. 
 
 
d) (1,0) Considerando que o corpo do laço é executado 10 vezes, liste as previsões e a exatidão das previsões para um esquema de previsão de desvios estático que prevê 
todos os desvios como não tomados. 
 
Resp.: Como o corpo do laço executa 10 vezes, os 9 primeiros desvios devem ser tomados e o último não tomado. Sendo assim, temos (T=tomado e N=não tomado): 
 
Real T T T T T T T T T N 
Previsão N N N N N N N N N N 
Status Errado Errado Errado Errado Errado Errado Errado Errado Errado Certo 
 
Percentual de Acerto = 1/10 = 10% 
 
e) (1,0) Considerando que o corpo do laço é executado 10 vezes, liste as previsões e a exatidão das previsões para um esquema de previsão de desvios dinâmico de 1 bit, 
inicializado para prever "não tomado". 
 
Resp.: Como o corpo do laço executa 10 vezes, os 9 primeiros desvios devem ser tomados e o último não tomado. Em um esquema de previsão dinâmico de 1 bit, o bit indica 
se o devio será previsto como tomado (1) ou não tomado (0). Caso a previsão esteja errada, o bit é invertido. Sendo assim, temos (T=tomado e N=não tomado): 
 
 
Real T T T T T T T T T N 
Bit 0 1 1 1 1 1 1 1 1 1 
Previsão N T T T T T T T T T 
Status Errado Certo Certo Certo Certo Certo Certo Certo Certo Errado 
 
Percentual de Acerto = 8/10 = 80% 
 
 
f) (1,0) Considerando que o corpo do laço é executado 10 vezes, liste as previsões e a exatidão das previsões para um esquema de previsão de desvios dinâmico de 2 
bits, inicializado para prever "tomado fortemente". 
 
Resp.: Como o corpo do laço executa 10 vezes, os 9 primeiros desvios devem ser tomados e o último não tomado. Um esquema de previsão dinâmico de 2 bit segue o 
esquema abaixo: 
 
 
 
Sendo assim, temos (T=tomado e N=não tomado): 
 
 
Real T T T T T T T T T N 
Bit 11 11 11 11 11 11 11 11 11 11 
Previsão T T T T T T T T T T 
Status Certo Certo Certo Certo Certo Certo Certo Certo Certo Errado 
 
Percentual de Acerto = 9/10 = 90%