GABARITO DA LISTA 1

Prévia do material em texto

UNIVERSIDADE FEDERAL FLUMINENSE 
INSTITUTO DE COMPUTAÇÃO 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 
Sistemas de Computação 2020.2 
Lista 1 - GABARITO 
 
1. (2,0) Suponha que a empresa que você trabalha projetou um processador M1 com as seguintes 
medidas de CPIs: 
 
Tipo de instrução CPI 
Load/Store 5 
Operações lógicas/aritméticas 2 
Branches 4 
Jumps 3 
 
O tempo de ciclo de clock desta máquina é 1,5 ns. 
 
a) (1,0) Suponha que você escreveu um programa de benchmark P1 composto de um loop 
executado 200 vezes cujo corpo contém 1.000.000 instruções que apresentam as seguintes 
características: 50 % são do tipo load/store, 30 % do tipo lógica/aritmética, 15 % do tipo 
branches e 5% do tipo jumps. Qual é a medida de CPI obtida na execução deste programa e 
qual é o tempo de execução deste programa? 
 
Resposta: A CPI esperada é dada por: 
CPI=(5×50%)+(2×30%)+(4×15%)+(3×5%)=2,5+0,6+0,6+0,15=3,85 
O tempo de execução será: 
Tempo de execução=Instruções× CPI × Tempo de ciclo = (200 × 1.000.000) Instruções × 3,85 
CPI × 1,5 ns = 11,55 × 10-1segundos = 1,155 segundos 
Um competidor de sua empresa criou uma máquina M2 com as seguintes características: 
 
 
Tipo de instrução CPI 
Load/Store 6 
Operações lógicas/aritméticas 1 
Branches 3 
Jumps 2 
 
A freqüência do clock desta máquina é de 1 GHZ. 
 
b) (1,0) Para o mesmo programa de benchmark P1 qual das duas máquinas (M1 ou M2) será 
mais rápida e por quantas vezes mais? 
 
Resposta: A CPI para M2 será: 
 
CPI M2=(6 × 50%)+(1 × 30%) + (3 × 15%) + (2 x 5%)=3,0+0,3+0,45+0,1=3,85 
 
O tempo de execução de I instruções para M1 e M2 é dado por: 
 
Tempo de execução M1=Instruções × CPI × Tempo de ciclo = I instruções x 3,85 CPI x 1,5 ns 
Tempo de execução M2=Instruções × CPI × Tempo de ciclo = I instruções × 3,85 CPI × 1ns 
 
DM2/DM1 = Tempo de execução M1/ Tempo de execução M2 = I instruções × 3,85 CPI x 
1,5 ns / I instruções × 3,85 CPI × 1ns = 1,5 
 
Logo dizemos que M2 é aproximadamente 1,5 vezes mais rápida que M1. 
 
2. (2.0) Considere o conjunto de bits abaixo: 
 
 1010 1110 0000 1001 0000 0000 1000 1000 
 
a) (0,2) um inteiro sem sinal 
Resposta: 1×231 + 1×229 + 1×227+ 1×226 +1×225+1×219+ 1×216+1×27 + 1×23 = 2.919.825.544 
b) (0,2) um inteiro em sinal e magnitude 
Resposta: -(1+ 1×229 + 1×227+ 1×226 +1×225+1×219+ 1×216+1×27 + 1×23 ) =772.341.896 
1. 0,4) um inteiro complemento a 2 
Resposta:- 1×231 + 1×229 + 1×227+ 1×226 +1×225+1×219+ 1×216+1×27 + 1×23 = -1.375.141.752 
ou inverte e soma 1 para saber o módulo: inv(1010 1110 0000 1001 0000 0000 1000 1000) 
+1=0101 0001 1111 0110 1111 1111 0111 1000) = 1×230 + 1×228 + 1×224+ 1×223 + 1×222 + 
1×221 + 1×220 + 1×218 + 1×217 + 1×215 + 1×214+ 1×213 + 1×212 + 1×211 + 1×210 + 1×29 + 1×28+ 
1×26 + 1×25 + 1×24 + 1×23= 1.375.141.752, portanto -1.375.141.752 
c) (0,6) um número representado no padrão IEEE 754 
Resposta: 
Mantissa= 000 1001 0000 0000 1000 1000, Expoente = (010 1110 0)2 – 127 = 92-127=-35 
Valor = -(1, 000 1001 0000 0000 1000 1000)2 × 2-35 = 2-35 + 2-39 + 2-42+ 2-51+ + 2-56 ≈ 3,115 × 
10-11 
d) (0,6) uma instrução MIPS 
Resposta: 
Os primeiros seis bits da instrução se referem ao código de operação. Nesse caso o código é 
101011 = 43, que corresponde à instrução sw. A instrução sw utiliza o formato I, então ela 
possui os três valores seguintes: rs, rt e o immediate. O campo para rs é de 5 bits e tem o valor 
10000 = 16 que corresponde ao registrador $s0. O campo para rt também é de 5 bits e tem o 
valor 01001 = 9 que corresponde ao registrador $t1. E finalmente o campo immediate são os 
16 bits finais da instrução que contêm o valor 0000 0000 1000 1000. Esse valor em 
complemento a 2, corresponde ao valor +136. 
Então a instrução completa é: 
 sw $t1, 136($s0) 
 
 
3. (1,5) Suponha que você tenha que implementar uma nova pseudoinstrução no MIPS chamada lmi, 
para realizar um endereçamento indireto. Essa instrução tem a seguinte sintaxe: 
 
lmi $t0, desl.( $t1) # $t0 = Mem[Mem[$t1+desl.]] 
 
O registrador $t0 é carregado com o conteúdo da memória, cujo endereço está na posição de 
memória ($t1+desl.). Escreva as instruções MIPS que executam essa função. 
 Resposta: Esta é uma maneira de codificar. Outras poderão estar corretas. 
 lw $t2, desl($t1) 
 lw $t0, 0($t2) 
 
 
4. (2,0) Suponha que você tenha os três procedimentos com os cabeçalhos de código objeto 
mostrados nas tabelas abaixo, com valores hexadecimais: 
 
 
Cabeçalho 
 Nome Procedure A 
 Tamanho de texto 100 
 Tamanho de dados 20 
Segmento de texto Endereço Instrução 
 0 sw $al, 0($gp) 
 4 jal B 
 ... ... 
Segmento de dados 0 (Y) 
 ... ... 
Informação de relocação Endereço Tipo de instrução Dependência 
 0 Sw Y 
 4 Jal B 
Tabela de símbolos Label Endereço 
 Y - 
 B - 
 
 
 
Cabeçalho 
 Nome Procedure B 
 Tamanho de texto 200 
 Tamanho de dados 30 
Segmento de texto Endereço Instrução 
 0 lw $al, 0($gp) 
 4 jal C 
 8 sw $v0, 0($gp) 
 ... ... 
Segmento de dados 0 (X) 
 4 (Z) 
 ... ... 
Informação de relocação Endereço Tipo de instrução Dependência 
 0 Lw X 
 4 Jal C 
 8 Sw Z 
Tabela de símbolos Label Endereço 
 X - 
 C - 
 Z - 
 
 
 
Cabeçalho 
 Nome Procedure C 
 Tamanho de texto 300 
 Tamanho de dados 40 
Segmento de texto Endereço Instrução 
 0 lw $al, 0($gp) 
 4 jal A 
 ... ... 
Segmento de dados 0 (K) 
 ... ... 
Informação de relocação Endereço Tipo de instrução Dependência 
 0 Lw K 
 4 Jal A 
Tabela de símbolos Label Endereço 
 K - 
 A - 
 
 
 
Mostre o endereço de cada instrução após a ligação dos três procedimentos. Suponha que o código 
deve ser carregado a partir do endereço 400000, os dados a partir do endereço 10000000 e que o 
registrador $gp é carregado com o valor 10008000 (todos os valores expressos em hexa). 
Resposta: 
 
O procedimento A utiliza a variável Y e o procedimento B. 
O procedimento B utiliza a variável X e Z e o procedimento C. 
O procedimento C utiliza a variável K e procedimento A. 
 
Supondo que os três procedimentos serão ligados na ordem A, B e C, teremos: 
 Endereço de A: 40 0000 
 Endereço de B: 40 0100 
 Endereço de C: 40 0300 
 Endereço de Y: 1000 0000 
 Endereço de X: 1000 0020 
 Endereço de Z: 1000 0024 
 Endereço de K: 1000 0050 
 
 
Segmento de texto 
 
Endereço Instrução 
0040 0000 sw $a1, 8000($gp) 
0040 0004 jal 0040 0100 
….. 
0040 0100 lw $a1,8020($gp) 
0040 0104 jal 0040 0300 
0040 0108 sw $v0, 8024($gp) 
… 
0040 0300 lw $a1,8050($gp) 
0040 0304 jal 0040 0000 
 
 
 
 
 
Segmento de dados 
 
Endereço Dado 
1000 0000 (Y) 
1000 0020 (X) 
1000 0020 (Z) 
1000 0050 (K) 
 
 
 
 
5. (2,5) Considere a estrutura de dados em C utilizada para representar uma lista de alunos de uma 
turma. O campo prox contém o endereço do próximo elemento da lista e caso ele seja 0 indica 
final de lista. 
 
 
struct Lista_Alunos { 
 int matricula; 
 char[30] nome; 
 struct Lista_Alunos *prox; 
} 
 
a) (0,5) Mostre como esta lista de alunos será armazenada na memória respeitando as restrições 
de alinhamento. 
Resposta: 
E é um endereço múltiplo de 4 
 
 
 
 
 
 
matricula nome X X prox 
 E E +4 E + 34 E+36 E+40 
b) (2,0) A função em C abaixo verifica se um aluno com uma determinada matrícula está na lista. 
 
int procuraaluno (Lista_Alunos *lista, int mat); 
{ 
 while (lista != 0) { 
 if (lista->matricula == mat) 
 return (1) 
 else 
 lista = lista->prox; 
 } 
return (0); 
} 
 
Codifique esta função em MIPS, assumindo que o endereço inicial da lista é passado no 
registrador $a0 e a matrícula do aluno sendo procurado em $a1. O valor de retorno deve ser 
armazenado em $v0. Você pode utilizar a pilha para salvar valores que achar necessários. 
Resposta: 
Esta é uma maneira de resolver. Existem outras. 
 
 add$v0,$0,$0 #inicializa retorno como não achado 
PROCURA: beq $a0,$0,FIM #verifica se fim de lista 
lw $t0,0($a0) #carrega número de matrícula 
beq $t0,$a1,ACHOU #compara com matrícula desejada 
lw $a0,36($a0) #procura próximo registro 
j PROCURA #volta para testar fim de lista 
ACHOU: addi $v0,$0,1 #valor de retorno indica que achou 
FIM: jr $ra