Desempenho de Organizações de Máquinas

Prévia do material em texto

UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
1 
 
 
 
Escola EACH TURMA 
Nota do aluno na PROVA 
Curso Sistemas de Informação 
Disciplina Arquitetura de Computador Data da Prova 12/11/20 
Professor Clodoaldo Aparecido de Moraes Lima 
Aluno 
No. USP 
 
 
1ª Questão) Um processador RISC é implementado em duas versões de organização síncrona: uma monociclo, em que cada instrução 
executa em exatamente um ciclo de relógio, e uma versão pipeline de 5 estágios. Os estágios da versão pipeline são: (1) busca de 
instrução, (2) busca de operandos, (3) execução da operação, (4) acesso à memória e (5) atualização do banco de registradores. A 
frequência máxima de operação das organizações foi calculada em 100 MHz para a versão monociclo e 400 MHz para a versão 
pipeline. Um programa X que executa 200 instruções é usado para comparar o desempenho das organizações. Das 200 instruções, 
apenas 40% fazem acesso à memória, enquanto as demais operam apenas sobre registradores internos da organização. Assuma, que o 
programa não apresenta nenhum conflito de dados ou de controle entre instruções que podem estar simultaneamente dentro do pipeline 
da segunda organização. Calcule o tempo de execução do programa X nas organizações monociclo e pipeline. 
 
Organização da máquina Versão 1 - Monociclo 
Período para execução de uma instrução [1/(100 x 10^6)] s = 10 ns 
Período para execução de 200 instruções 200 x 10 ns = 2.000 ns 
 
 
Período do pipeline [1/(400 x 10^6)] s = 2,5 ns 
Período para execução de 200 instruções (Observar o princípio da Figura 1) 
40% fazem acesso à memória (80 instruções – utilizam 5 estágios) 
60% operam apenas sobre registradores internos da organização (120 instruções – utilizam 4 estágios). 
Estágio 1: 200 períodos de clock (200 instruções) 
Estágio 2: tem início no segundo período de clock para a instrução 1. Logo, para execução deste estágio em todas as instruções, temse 
mais um período de clock em relação ao estágio anterior; Estágio 3: .... 
Importante: 40% e 60% (descritos anteriormente) estarão inseridos no tempo necessários à execução do pior caso (5 estágios). 
 Logo, o período para execução das 200 instruções é: (200 + 1 + 1 +1 +1) x 2,5 ns = 510 ns 
 
 C1 C2 C3 C4 C5 C6 C7 C8 C9 
Inst 1 BI DI EX Mem WB 
Instr2 BI DI EX Mem WB 
Instr3 BI DI EX WB 
Instr4 BI DI WB 
Instr5 BI WB 
 
 
 
 
 
 
 
2ª Questão) Supondo que melhoramos uma máquina fazendo as instruções de adição serem executadas 2 vezes mais rápidas, e as 
instruções de multiplicação 4 vezes mais rápidas. Se o tempo de execução de certo benchmark antes do melhoramento é de 100s, 
sendo 20s em adição e 40s em multiplicação. 
a) calcular o speedup 
𝑇𝑎𝑑𝑖çã𝑜
𝑜𝑙𝑑 = 20 
 
𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 = 100 ∗ [(1 − 0.2) +
0.2
2
] = 90 𝑠 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
2 
 
𝑠𝑝𝑒𝑒𝑑𝑢𝑝 =
𝑇𝑎𝑑𝑖çã𝑜
𝑜𝑙𝑑
𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 =
100
90
= 1.11 
 
𝑇𝑎𝑑𝑖çã𝑜
𝑜𝑙𝑑 𝑇𝑚𝑢𝑙𝑡 = 40 
𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 = 100 ∗ [(1 − 0.4) +
0.4
4
] = 70 𝑠 
𝑠𝑝𝑒𝑒𝑑𝑢𝑝 =
𝑇𝑎𝑑𝑖çã𝑜
𝑜𝑙𝑑
𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 =
100
70
= 1.43 
 
 
b) calcular o fator de melhoramento total 
 
𝑇𝑡𝑜𝑡𝑎𝑙
𝑛𝑒𝑤 = 100 − 𝑅𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 − 𝑅𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 = 100 − 10 − 30 = 60 
𝑠𝑝𝑒𝑒𝑑𝑢𝑝 =
𝑇𝑎𝑑𝑖çã𝑜
𝑜𝑙𝑑
𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 =
100
60
= 1,67 
 
3ª Questão) Suponhamos que melhoramos uma máquina fazendo todas as instruções de ponto-flutuante serem executadas 5 vezes 
mais rápido. 
a) Se o tempo de execução de certo benchmark antes do melhoramento é de 10s, qual seria o speedup se metade dos 10s é 
despendida em instruções de ponto-flutuante? 
𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 = 10 ∗ [(1 − 0.5) +
0.5
5
] = 6 𝑠 
𝑠𝑝𝑒𝑒𝑑𝑢𝑝 =
𝑇𝑎𝑑𝑖çã𝑜
𝑜𝑙𝑑
𝑇𝑎𝑑𝑖çã𝑜
𝑛𝑒𝑤 =
10
6
= 1,67 
 
b) Estamos procurando um benchmark para testar a nova unidade de ponto-flutuante acima, e queremos que o benchmark todo 
mostre um speedup de 3. Um benchmark é executado em 100s, com o antigo hardware de ponto-flutuante. Quanto do tempo de 
execução as instruções de ponto-flutuante devem corresponder nesse programa para que possamos produzir o speedup desejado 
nesse benchmark? 
 
𝑠𝑝𝑒𝑒𝑑𝑢𝑝 =
𝑇𝑝𝑓
𝑜𝑙𝑑
𝑇𝑝𝑓
𝑛𝑒𝑤 ⟶ 𝑇𝑝𝑓
𝑛𝑒𝑤 =
𝑇𝑝𝑓
𝑜𝑙𝑑
𝑠𝑝𝑒𝑒𝑑𝑢𝑝
=
100
3
 
 
 
100
3
= 100 ∗ [(1 − 𝑓𝑟𝑎𝑐𝑡𝑖𝑜𝑛) +
𝑓𝑟𝑎𝑐𝑡𝑖𝑜𝑛
5
] 
 
5
3
= [5 − 4 ∗ 𝑓𝑟𝑎𝑐𝑡𝑖𝑜𝑛] 
 
𝑓𝑟𝑎𝑐𝑡𝑖𝑜𝑛 =
10
12
= 83% 
 
4ª Questão) Apresente os valores dos sinais de controle ALUSrc, ALUOp, MemRead, MemWrite, RegWrite, MemtoReg e RegDst, na 
implementação da instrução addi no MIPS pipeline, indicando em que estágio cada um desses sinais são usados. 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
3 
 
 
 
Addi $5, $6, 10 Add $5, $6, $7 
 
ALUSrc ALUOp MemRead, MemWrite RegWrite, MemtoReg RegDst 
1 00 0 0 1 0 0 0,25 
EX EX MEM MEM WB WB WB 0,25 
Cada item incorreto 0,07 
 
5ª Questão) Por que a instrução addi não pode ser considerada uma instrução de formato R, com opcode igual 000000? 
 6 5 5 5 5 6 
 OP Rs Rt const 
 OP RS RT RD Shamt function 
 
 
6ª Questão) Descreva detalhadamente o que cada código faz 
a) 0,5 
b) 0,5 
a) .text 
main: 
li $v0, 5 
syscall 
move $t0, $v0 
li $v0, 5 
syscall 
move $t1, $v0 
bgt $t0, $t1, t0_bigger 
move $t2, $t1 
b endif 
t0_bigger: 
move $t2, $t0 
endif: 
move $a0, $t2 
li $v0, 1 
syscall 
li $v0, 10 
syscall 
b) .text 
 .globl main 
main: 
li $a0, 5 
jal Funcao 
move $s0, $v0 
li $v0, 10 
syscall 
Funcao: 
sub $sp,$sp,4 
sw $ra, 0($sp) 
li $t1, 1 
slti $t0, $a0, 2 
beq $t0, $zero, Calcula 
add $v0, $zero, $zero 
beq $a0, $zero, Sai 
add $v0, $t1, $zero 
Sai: 
lw $ra, 0($sp) 
add $sp, $sp, 4 
jr $ra 
Calcula: 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
4 
 
add $a1, $a0, $zero 
Loop: 
sub $a1, $a1, $t1 
jal Multiplica 
add $a0, $v0, $zero 
bne $a1, $t1, Loop 
j Sai 
Multiplica: 
mult $a0, $a1 
mflo $v0 
 jr $ra 
 
 
main: 
li $v0, 5 
 syscall 
Realiza a leitura de um valor inteiro 
 move $t0, $v0 Copia o valor lido para $t0 
li $v0, 5 
 syscall 
Realiza a leitura de um valor inteiro 
 move $t1, $v0 
 bgt $t0, $t1, t0_bigger Se $t0 > $t1 vá para t0_bigger 
 move $t2, $t1 Copia o valor $t1 para $t2 
b endif Instrução branch 
t0_bigger: 
 move $t2, $t0 Copia o valor $t0 para $t2 
endif: 
 move $a0, $t2 Copia o valor $a0 para $t2 
li $v0, 1 
 syscall 
li $v0, 10 Realiza EXIT 
 syscall 
 
Faz a leitura de 02 valores e imprime o maior valor na tela 0.2 
 
Comentários sobre o código 0.3 
 
 
 
.text 
.globl main 
 
main: # Programa Principal 
li $a0, 5 # Parametro = 5 
jal funcao # Chama a função fatorial, 
# armazenando o endereco da proxima instrucao em $ra 
move $s0, $v0 # Registrador $s0 recebe o valor resultado 
li $v0, 10 # Serviço do sistema no. 10 : Exit 
Syscall # Chamada de serviço do sistema 
# Obs. Isto é necessário para encerrar aqui o programa 
funcao: # Função Fatorial. Retorna o fatorial de n ($a0) 
sub $sp,$sp,4 # Abre espaço para armazenar 1 item na pilha 
sw $ra, 0($sp) # Armazena o conteúdo do registrador $ra 
# Obs: Caso os registradores $s0 - $s9 fossem alterados, 
seria necessário guardá-los na pilha também, e restaurá-los 
ao fim do procedimento. Por convenção, os registradores 
temporários $t* não precisam ser guardados. 
li $t1, 1 # $t1 = 1 
slti $t0, $a0, 2 # Seta $t0 se $a0 < 2 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
5 
 
beq $t0, $zero, Calcula # Se $t0 não setado, $a0 > 1, portanto Calcula 
add $v0, $zero, $zero # Se não, $v0 = 0 
beq $a0, $zero, Sai # Se $a0 = 0, Sai 
add $v0,$t1, $zero # Se não, $v0 = 1 
Sai: 
lw $ra, 0($sp) # Carrega o registrador $ra da pilha 
add $sp, $sp, 4 # Elimina 1 item da pilha 
jr $ra # Retorna ao programa principal 
Calcula: 
add $a1, $a0, $zero # $a1 = $a0 
Loop: 
sub $a1, $a1, $t1 # $a1 = $a1 - 1 
jal Multiplica # Multiplica $a0 por $a1 
add $a0, $v0, $zero # $a0 = resultado da multiplicação 
bne $a1, $t1, Loop # Enquanto $a1 for diferente de 1, Loop 
j Sai 
Multiplica: 
mult $a0, $a1 # Multiplica $a0 por $a1 
mflo $v0 # resultado em $v0 
# Obs:. O resultado da instrução mult fica armazenado nos 
registradores # $hi e $lo. Para buscar os seus valores, 
utiliza-se mflo e mfhi. Para # podermos trabalhar com 
valores maiores em nosso programa bastaria retornar o $lo em 
$v0 e o $hi em $v1. 
jr $ra # Retorna 
 
 
 
Implementar um procedimento para o cálculo do fatorial de n. Tal procedimento deverá ser feito de tal maneira a chamar um 
segundo procedimento. 
 
 
 
 
 
 
 
7ª Questão) Considere o seguinte loop em MIPS 
LOOP: slt $t2, $0, $t1  $t1 > 0 
beq $t2, $0, DONE 
subi $t1, $t1, 1 
addi $s2, $s2, 2 
j LOOP 
DONE: 
a)Assuma que o registrador $t1 é inicializado com o valor 0. Qual é o valor no registrador $S2 assumindo que $S2 inicialmente 
possui valor zero. 
while (t1>0){ 
t1=t1-1; 
s2=s2+2; 
} 
S2 será igual a 0 
b)Para o código escrito em assembly MIPS, escreva a rotina equivalente em C. Assuma que os registradores $s1, $s2, $t1 e $t2 são 
inteiros A, B, i e temp, respectivamente. 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
6 
 
int A,B,i, temp; 
while (i>0){ 
i=i-1; 
B=B+2; 
} 
 
8ª Questão) Traduza o seguinte código em C para assembly MIPS. Use o número mínimo de instruções. Assuma que os valores de 
a, b, i e j estão armazenados nos registradores $s0, $s1, $t0 e $t1 respectivamente. Também, assuma que registrador $s2 armazene o 
endereço base da vetor D 
for(i=0; i<a; i++) 
for(j=0; j<b; j++) 
D[4*j] = i + j; 
 
addi $t0, $zero, 0 # i = 0 
FOR1: slt $t2, $t0, $s0 # $t2 = 1 se i < a 
beq $t2, $zero, SAIDAe # se i >= a sai do for externo 
addi $t1, $zero, 0 # j = 0 
FOR2: slt $t3, $t1, $s1 # $t3 = 1 se j < b 
beq $t3, $zero, SAIDAi # se j >= b sai do for interno 
sll $t4, $t1, 4 # $t4 = 4*j (como cada palavra tem 4B, pula 16B) 
add $t5, $s2, $t4 # $t5 = &D[4*j] 
add $t6, $t0, $t1 # $t6 = i + j 
sw $t6, 0($t5) # D[4*j] = i + j 
addi $t1, $t1, 1 # j++ j FOR2 # de volta ao la¸co interno 
SAIDAi: addi $t0, $t0, 1 # i++ 
j FOR1 # de volta ao la¸co externo 
 SAIDAe: 
 
9ª Questão) Traduza o seguinte loop para C. Assuma que o inteiro i é armazenado no registrador $t1, $s2 armazena o inteiro 
chamado result, e $s0 armazena o endereço base do inteiro MemArray 
add $t1, $0, $0 
LOOP: lw $s1, 0($s0) 
add $s2, $s2, $s1 
addi $s0, $s0, 4 
addi $t1, $t1, 1 
slti $t2, $t1, 100 
bne $t2, $0, LOOP 
 
int result; 
int i =0; 
do{ 
 result = result + MemArray[i]; 
 i=i+1; 
while{i<100} 
 
 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
7 
 
10ª Questão) Os problemas neste exercício referem-se a seguinte sequência de instruções, e suponha que seja executada em um 
pipeline de 5 estágios: 
add $5,$2,$1 
lw $3,4($5) 
lw $2,0($2) 
or $3,$5,$3 
sw $3,0($5) 
a)Se não houver encaminhamento ou detecção de conflito, insira nops para garantir a execução correta. 
add $5,$2,$1 
NOP 
NOP 
lw $3,4($5) 
lw $2,0($2) 
NOP 
or $3,$5,$3 
NOP 
NOP 
sw $3,0($5) 
 C1 C2 C3 C4 C5 
add 
$5,$2,$1 
BI DI EX Mem WB 
NOP BI DI EX MEM WB 
NOP BI DI EX MEM WB 
lw 
$3,4($5) 
 BI DI EX MEM WB 
lw 
$2,0($2) 
 BI DI EX MEM WB 
NOP BI DI EX MEM 
or 
$3,$5,$3 
 BI DI EX MEM WB 
NOP BI DI EX MEM WB 
NOP BI DI EX MEM 
sw 
$3,0($5) 
 BI DI 
 
 
 
 
 
b)Use nops apenas quando um conflito não puder ser evitado alterando ou reorganizando essas instruções. Você pode assumir o 
registro $7 pode ser usado para manter valores temporários em seu código modificado. 
add $5,$2,$1 
lw $3,4($5) 
lw $2,0($2) 
or $3,$5,$3 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
8 
 
sw $3,0($5) 
 
c)Se o processador tem encaminhamento, mas esquecemos de implementar a unidade de detecção de conflito, o que acontece 
quando este código é executado? 
Add $5,$2,$1 BI DI EX MEM WB 
lw $3,4($5) BI DI EX MEM WB 
lw $2,0($2) BI DI EX MEM WB 
or $3,$5,$3 BI DI EX MEM WB 
sw $3,0($5) BI DI EX MEM WB 
 
Não haveria nenhum problema na execução do programa. 
 
11ª Questão) Os problemas neste exercício referem-se a seguinte sequência de instruções, e suponha que seja executada em um 
pipeline de 5 estágios: 
add $5,$2,$1 
lw $7,4($5) 
or $3,$5,$3 
lw $2,0($2) 
sw $7,0($5) 
a)Se não houver encaminhamento ou detecção de conflito, insira nops para garantir a execução correta. 
add $5,$2,$1 
NOP 
NOP 
lw $7,4($5) 
or $3,$5,$3 
lw $2,0($2) 
NOP 
sw $7,0($5) 
 
add 
$5,$2,$1 
BI DI EX MEM WB 
NOP BI DI EX MEM WB 
NOP BI DI EX MEM WB 
lw 
$7,4($5) 
 
 BI DI EX MEM WB 
or 
$3,$5,$3 
 
 BI DI EX MEM WB 
lw 
$2,0($2) 
 BI DI EX MEM WB 
sw 
$7,0($5) 
 
 BI EX 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
9 
 
 
 
 
 
 
 
b)Use nops apenas quando um conflito não puder ser evitado alterando ou reorganizando essas instruções. Você pode assumir o 
registro $7 pode ser usado para manter valores temporários em seu código modificado. 
add $5,$2,$1 
NOP 
NOP 
lw $7,4($5) 
lw $2,0($2) 
or $3,$5,$3 
sw $7,0($5) 
 
c)Se o processador tem encaminhamento, mas esquecemos de implementar a unidade de detecção de conflito, o que acontece 
quando este código é executado? 
Add $5,$2,$1 BI DI EX 
$5 
MEM 
$5 
WB 
or $3,$5,$3 BI DI EX MEM WB 
lw $3,4($5) BI DI EX MEM 
$3 
WB 
lw $2,0($2) BI DI EX MEM WB 
sw $3,0($5) BI DI EX MEM WB 
 
Não haveria nenhum problema na execução do programa. 
 
 
12ª Questão) Assuma que o seguinte código é executado sobre um processador pipeline com 5 estágio, com adiantamento e um 
preditor de desvio (o qual assume que todo desvio para trás é tomado) 
 
a)Desenhe o diagrama de execução para este código, assumindo que não há slots de atraso e o que desvio executa no estágio MEM 
Sem preditor 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
10 
 
 1 2 3 4 5 6 7 8 9 10 11 12 
lw $1,40 ($6) BI DI EX Mem WAR 
beq $2,$3, Label2 BI DI EX MEM WAR 
Add $1, $6, $4 BI DI EX X X 
beq $1, $2, Labe1 BI DI X X X 
sw $2, 20($4) BI X X X X 
beq $1, $2, Labe1 BI DI EX MEM WAR 
sw $2, 20($4) BI DI EX MEM WAR 
and $1, $1, $4 BI DI EX MEM WAR 
 
 
Com preditor (atua no estagio DI tomando decisão) 
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
lw $1,40 ($6) BI DI EX MEM WAR 
beq $2,$3, Label2 BI DI EX MEM WAR Preditor assume que desvio não deve ser tomado 
no clock igual a 3. Instrução em verde é carregada 
baseada na decisão do preditor 
 
Add $1, $6, $4 BI DI EX X X 
beq $1, $2, Labe1 BI DI X X X 
sw $2, 20($4) BI X X X X 
beq $1, $2, Labe1 BI DI EX MEM WB 
sw $2, 20($4) BI X X X X Instrução descartada pelo preditor 
lw $1,40 ($6) BI DI X X X 
beq $2,$3, Label2 BI X X X X 
sw $2, 20($4) BI DI EX MEM WB 
and $1, $1, $4 BI DI EX MEM WB 
 
 
b)Qual é o speed-up alcançado ao mover a execução de desvio para o estagio DI. Assuma que a comparação no estágio DI não afeta 
o tempo de ciclo de clock. 
 1 2 3 4 5 6 7 8 9 10 
lw $1,40 ($6) BI DI EX MEM WAR 
beq $2,$3, Label2 BI DI EXMEM WAR 
Add $1, $6, $4 BI X X X X 
beq $1, $2, Labe1 BI DI EX MEM WAR 
sw $2, 20($4) BI DI EX MEM WAR 
and $1, $1, $4 BI DI EX MEM WAR 
 
Speed_up =12/10 = 1.2 em relação a arquitetura sem preditor 
Speed_up =15/10 = 1.5 em relação a arquitetura com preditor 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
UNIVERSIDADE DE SÃO PAULO 
SEGUNDO SEMESTRE LETIVO DE 2020 
PROVA P1 
 
11