Resolução das Lista 1, 2 e 3

Prévia do material em texto

PS: Frases em vermelho : não tenho certeza que a resposta está correta, mas é provavel que esteja
Lista 1
1) Processador, memória e dispositivos de I/O. No CI do processador residem o processador e alguns elementos de memória (registradores, memória cache).
2) Pois instruções de assembler (baixo nível) são mapeadas diretamente (1 a 1) para instruções em código de máquina, que são processadas pela CPU com uma única operação, enquanto instruções de linguagens de alto nível podem representar operações complexas que são decompostas em várias instruções de baixo nível.
3) Softwares de aplicação (programas codados em linguagens de alto nível)
Softwares de sistema (compiladores e sistemas operacionais)
Hardware (arquitetura de instruções e circuitos lógicos)
4) Carregar dados do disco (load), salvar dados no disco (store), alterar dados presentes no disco (edit), remover dados do disco (free) (acho que a resposta dessa questão é pessoal..)
5) Pois as instruções presentes na arquitetura MIPS são diferentes das instruções presentes na arquitetura x86, ou seja, se um programa foi compilado em MIPS (ou escrito em assembler de MIPS), suas instruções de baixo nível não serão reconhecidas num x86.
6) Solução enviada pelo Douglas:
Através do aumento de densidade dos processadores, ou seja, conseguir alocar mais transistores a um mesmo chip, gerando assim um maior poder de processamento A relação com a Lei de Moore é que a capacidade de transistores de um chip é dobrada a cada 18~24 meses.
7) Pois existem barreiras que impedem a evolução rápida de novos processadores, como o consumo de energia (dissipação em dispositivos fixos e bateria em móveis limita aumentos de frequência), paralelismo de instrução (está dificil de extrair mais paralelismo implícito do que já se consegue), e latência de memória (existe um gargalo entre a CPU e a memória).
8) Clock rate = 40x10^6
Instruction Count = 10^5
CPI Efetivo = (Somatória (Instrução[i] * CPI[i])) / Instruction Count
CPI Efetivo = (45000 + 32000*2 + 15000*2 + 8000*2) / 10^5
CPI Efetivo = 155000 / 10^5 = 1,55 * 10^5 / 10^5 = 1,55
CPU Time = Instruction Count * CPI / Clock Rate
CPU Time = 10^5 * 1,55 / (40*10^6) = 10^(-1) * 1,55/40 = 0,38 * 10^(-2)
9)
a) CPI[a] = Tempo * Frequencia / QtInstrucoes = 12 * 5*10^6 / (12*10^6) = 5
CPI[b] = Tempo * Frequencia / QtInstrucoes = 1 * 25*10^6 / (18*10^6) = 25/18 =~ 1,39
b) Irei chamar de QtIns, quantas instruções uma arquitetura executa por segundo
QtIns[a] = Frequencia / CPI[a] = 10^6 instruções por segundo
QtIns[b] = Frequencia / CPI[b] =~ 17,98 * 10^6 instruções por segundo
Portanto a razão entre a velocidade de B e a de A é dada por QtIns[b] / QtIns[a] = 17,98, ou seja, B é 17,98 vezes mais rápido que A.
Isto explica porquê a arquitetura B executa um programa com mais instruções que o programa executado em A, e leva menos tempo. Esta diferença acontece pois B executa mais ciclos por segundo (maior frequência de relógio) e também consegue executar uma mesma operação com menos instruções que A (menor CPI)x
10) Duas multiplicações e uma subtração, portanto o cálculo demora 21 ns.
Podemos otimizar a equação para d = a * (b - c), assim teremos uma multiplicação e uma subtração apenas, e o cálculo demora apenas 11 ns.
11) Os registradores estão integrados no mesmo chip da unidade de processamento, enquanto a memória é outro componente separado destes. Portanto, a unidade de processamento consegue acessar os registradores bem mais rápido do que a memória, o que significa que instruções que precisam acessar a memória precisam de mais ciclos para serem executadas, do que instruções que usam apenas os registradores.
12) Para que as memórias mais caras e mais rápidas (registradores, cache) fiquem próximas ao processador, e possamos aproveitá-las ao máximo.
Talvez dê pra falar mais alguma coisa nessa questão.
13)
a) Minha solução (Lucas):
2^32 bits (4Mb)
2^29 bytes (0,5 MB)
2^27 palavras
Solução enviada pelo Henrique:
o MIPS consegue acessar endereços de até 32 bits da memóra.
Só que cada endereço representa 1 byte de memória.
Então o MIPS suporta uma memoria de (2^32) bytes = 2^35 bits e 2^30 palavras
b) Ultimo endereço em notacao binaria : 1111...1111 (32 vezes)
Ultimo endereço em notaçao decimal : 4294967295
Total de posicoes endereçaveis : 4294967296
c) 2GB = 2*10^9 Bytes = (2*10^9 / 4) Palavras = (5 * 10^8) Palavras
Cada palavra leva 30 ns (30*10^(-9) s) para ser transferida, então temos
Tempo total = 5 * 10^8 * 30 * 10^(-9) = 150 * 10^(-1) = 15 segundos
Lista 2
PS: Trechos de código estarão todos com fonte itálica
1)
a)
add $t0, $s1, $s2	# t0 = g + h
add $t1, $s3, $s4	# t1 = i + j
add $s0, $t0, $t1	# f = t0 + t1
b)
addi $t0, $s2, 5	# t0 = h + 5
add $s0, $s1, $t0	# f = g + t0
c)
add $t0, $s1, $s2	# t0 = g + h
add $t1, $s3, $s4	# t1 = i + j
add $t2, $t0, $t1	# t2 = t0 + t1
addi $t2, $t2, 2		# t2 = t2 + 2
add $s0, $s0, $t2	# f = f + t2
d)
addi $t0, $s0, 5	# t0 = f + 5
sub $s0, $s1, $t0	# f = g - t0
e)
add $t0, $s1, $s2	# t0 = g + h
lw $t1, 16($s7)		# t1 = *(B+4) = B[4]
add $s0, $t0, $t1	# f = t0 + t1
f)
correção enviada pelo Henrique:
lw $t0, 16($s7)		# t0 = B[4]
sll $t0, $t0, 2		# multiplica t0 por 4
add $t1, $s6, $t0	# t1 = &A[t0] = &A[B[4]]
lw $t2, 0($t1)		# t2 = *t1 = A[B[4]]
sub $s0, $s1, $t2	# f = g - t2
2)
a)
f = f + h;
b)
f = -f;
f++;
c)
f = h - g;
d)
h = f + 1;
f = g - h;
e)
int *pointer = &A[1];
f = *pointer; // f recebe o conteudo que esta em &A[1]
f)
// s6 recebe &A[-5]
// s6 recebe &A[-5+g]
// f carrega o conteudo de &A[-5+g+2], ou seja, A[-3+g] ou A[g-3]
// entao estas instrucoes representam apenas uma linha de codigo:
f = A[g-3];
Nao tenho certeza mas acho que está certo
3)
0x70000000 = 011100000000….0000 em base 2
0x7FFFFFFF = 0111111111111….1111 em base 2
Então, soma = 1110111111111….1111 em base 2 = 0xEFFFFFFF em base 16
Ocorreu overflow, pois a soma de dois números positivos teve como resultado um número negativo (sabemos disso pelo bit de sinal).
0x70000000 = 011100000000….0000 em base 2
0xD0000000 = 110100000000….0000 em base 2
Então, soma = 010000000000….0000 em base 2 = 0x40000000 em base 16
Temos uma soma de um numero positivo e um negativo, neste caso, é impossivel ocorrer overflow.
4)
0xAE0BFFFC = 1010 1110 0000 1011 1111 1111 1111 1100 na base 2
Vamos separar estes 32 digitos acima, de acordo com quantos digitos precisamos para o opcode, rs, rt, etc:
	OPCode
	Rs
	Rt
	Constant
	101011
	10000
	01011
	1111111111111100
Pelo OPCode sabemos que se trata da instrução SW, que está no formato I-format.
Seus protótipo é: sw $rt, constant($rs)
Seus argumentos são $11 ($rt), e 65532($16) (constant($rs))
Ou seja, este código binário representa a instrução sw $11, 65532($16)
0x8D08FFC0 = 1000 1101 0000 1000 1111 1111 1100 0000 na base 2
Fazendo o mesmo processo do outro numero…
	OPCode
	Rs
	Rt
	Constant
	100011
	01000
	01000
	1111111111000000
Pelo OPCode sabemos que se trata da instrução LW, que está no formato I-format.
Seus protótipo é: lw $rt, constant($rs)
Seus argumentos são $8 ($rs), e 65472($8) (constant($rt))
Ou seja, este código binário representa a instrução lw $8, 65472($8)
5)
a)
ori $s0, $s1, 25	# a = b | 25
b)
and $s0, $s1, $s2	# a = b & c
c)
add $s0, $zero, $zero		# a = 0
beq $s1, $zero, Exit		# if (b == 0) vá para Exit
beq $s2, $zero, Exit		# if (c == 0) vá para Exit
addi $s0, $zero, 1		# a = 1 (o codigo somente chega aqui se b e c forem diferentes de 				#	 0, ou seja , se a expressao (b && c) é verdadeira)
Exit:
d) Simplificando a expressao, temos o seguinte codigo em C:
if (a != 0)
 a = b;
else 
 a = c;
Entao, passando para assembler de MIPS, temos:
beq $s0, $zero, Else		# if (a == 0) vá para Else
add $s0, $s1, $zero		# a = b (o codigo somente chega aqui se a != 0)
j Exit
Else:
add $s0, $s2, $zero		# a = c
Exit:
6)
sll $t0, $t1, 9	# esconde os 9 bitsmais significativos de t1, ou seja, os bits 31~23
srl $t0, $t0, 14	# esconde os (14-9) bits menos significativos de t1, ou seja, os bits 0~4
7)
addi $t7, $zero, 32	# t7 = 31 (seria 32 se fosse “inclusive” o valor j)
sub $t7, $t7, $t3	# t7 = 31 - j
sllv $t0, $t1, $t7	# esconde os (31-j) bits mais significativos de t1, ou seja, 31~(j+	1)
add $t7, $t7, $t2	# t7 = 31 - j + i
srlv $t0, $t0, $t7	# esconde os i bits menos significativos de t1, ou seja, 0~(i-1)
8)
# Resultado será guardado no registrador $t0
slt $t1, $s0, $zero		# if (s0 < 0) then t1 = 1; else t1 = 0
bne $t1, $zero, Negativo	# if (t1 != 0) vá para Negativo
add $t0, $zero, $s0		# se s0 é positivo, seu valor absoluto é ele mesmo
j Exit
Negativo:			# se s0 é negativo, seu valor absoluto é seu complemento de 2
addi $t2, $zero, -1		# t2 = -1
xor $t2, $t2, $s0		# t2 recebe a negação de s0
addi $t2, $t2, 1			# t2++; Agora t2 é o complemento de 2 de s0
add $t0, $zero, $t2		# t0 = t2, ou seja, t0 tem o valor absoluto de s0
Exit:
9)
add $t0, $zero, $zero		# i = 0
Loop:
slt $t3, $t0, $t2			# if (i < x) then t3 = 1; else t3 = 0
beq $t3, $zero, Exit		# if (t3 == 0) vá para Exit
addi $t1, $t1, 1			# y++
addi $t0, $t0, 1			# i++
j Loop				# Volta para o inicio do loop
Exit:
10)
Sabemos que o tamanho do deslocamento em uma instrução de desvio condicional (beq/bne) é de no máximo 16 bits. Como estes bits têm sinal, podemos avançar até (2^15 -1) instruções, ou retornar até 2^15 instruções.
Para as instruções de desvio incondicional temos 26 bits para guardar o valor do deslocamento, portanto podemos avançar até (2^25 -1) instruções, ou retornar até 2^25 instruções.
Para saber a distância da instrução 0x00000020 até cada uma das outras instruções “n”, faremos “n” - 0x00000020, e se essa distância couber em 16 bits, é possível fazer o desvio condicional. Se a distância couber em 26 bits, é possivel fazer o desvio incondicional.
Sabemos que a-b = a+(-b), então iremos encontrar o complemento de 2 de 0x00000020:
0000….00100000 → 0x00000020 em binario
1111….11011111 → 0x00000020 negado
1111….11100000 → comp. 2 de 0x00000020
Agora, as subtraçoes:
0x000C0000 - 0x00000020:
0000 0000 0000 1100 0000 0000 0000 0000 → 0x000C0000
1111 1111 1111 1111 1111 1111 1110 0000 → 0x00000020 (negativo)
0000 0000 0000 1011 1111 1111 1110 0000 → soma
A soma não cabe em 16 bits, portanto não podemos fazer o desvio condicional para 0x000C0000. Mas podemos fazer o desvio incondicional, pois o número ocupa 20 bits (cabe em 26 bits).
0x0FFFFFFF - 0x00000020:
0000 1111 1111 1111 1111 1111 1111 1111 → 0x0FFFFFFF
1111 1111 1111 1111 1111 1111 1110 0000 → 0x00000020 (negativo)
0000 1111 1111 1111 1111 1111 1101 1111 → soma
A soma não cabe em 16 bits, nem em 26 bits, portanto não podemos fazer o desvio condicional nem o desvio incondicional para este endereço.
0xD0000000 é negativo (sabemos isso pois o primeiro bit é 1), então para saber a distância de 0x00000020 até 0xD0000000 temos que fazer 0x00000020 - 0xD0000000, então também precisamos saber o complemento de 2 de 0xD0000000
1101 0000 0000 0000 0000 0000 0000 0000 → 0xD0000000 em binario
0010 1111 1111 1111 1111 1111 1111 1111 → 0xD0000000 negado
0011 0000 0000 0000 0000 0000 0000 0000 → comp. 2 de 0xD0000000
0000 0000 0000 0000 0000 0000 0010 0000 → 0x00000020 em binario
0011 0000 0000 0000 0000 0000 0010 0000 → soma
A soma não cabe em 16 bits nem em 26 bits, portanto não podemos fazer o desvio condicional nem o desvio incondicional para este endereço.
11)
add $t0, $zero, $zero		# t0 recebe 0
laço:
beq $a1, $zero, fim		# se a1 == 0 , vá para fim
add $t0, $t0, $a0		# t0 recebe t0 + a0
addi $a1, $a1, -1		# diminui o valor de a1 em 1 (a1--)
j laço				# vá para laço
fim:
add $v0, $t0, $zero		# v0 recebe t0
O programa executa a multiplicação a * b através de um laço iterativo.
12)
Supondo *p em $a0 e temp em $t0:
lw $t0, 0($a0)		# temp = *p;
lw $t1, 4($a0)		# t1 = *(p+1)
sw $t1, 0($a0)		# *p = *(p+1)
sw $t0, 4($a0)		# *(p+1) = temp
13)
Pelo que entendi, ele estaria fazendo swap de variaveis de 1 byte (char) em vez de 4 bytes (int), na função em C…
Então o codigo ficaria assim:
lb $t0, 0($a0)		# temp = *p; -- usamos lb (load byte) ao inves de lw
lb $t1, 1($a0)		# t1 = *(p+1) -- pulamos apenas 1 byte ao inves de 4
sb $t1, 0($a0)		# *p = *(p+1) -- usamos sb (store byte) ao inves de sw
sb $t0, 1($a0)		# *(p+1) = temp -- aqui tambem pulamos apenas 1 byte
14) Não entendi muito bem este exercicio.. Indexadas de 0 a 2499 significa apenas que o índice delas é 0~2499? Ou além disso, que cada elemento de índice x tem valor x? Por exemplo, v[10] = 10.
Os tamanhos em a2 e a3 seriam fixamente 2500, ou poderiam variar?
sll $a2, $a2, 2			# a2 = a2 * 4
sll $a3, $a3, 2			# a3 = a3 * 4
add $v0, $zero, $zero		# v0 = 0
add $t0, $zero, $zero		# t0 = 0
externo:
add $t4, $a0, $t0		# t4 = a0 + t0
lw $t4, 0($t4)			# t4 = *t4
add $t1, $zero, $zero		# t1 = 0
interno:
add $t3, $a1, $t1		# t3 = a1 + t1
lw $t3, 0($t3)			# t3 = *t3
bne $t3, $t4, pula		# se t3 != t4 vá para pula
addi $v0, $v0, 1		# v0++
pula:
addi $t1, $t1, 4			# t1 += 4
bne $t1, $a3, interno		# se t1 != a3 vá para interno
addi $t0, $t0, 4			# t0 += 4
bne $t0, $a2, externo		# se t0 != a2 vá para externo
15)
Lista 3
1) 7FFF FFFA(16) = 0111 1111 1111 1111 1111 1111 1010 (2)
2) 1100 1010 1111 1110 1111 1010 1100 1110 (2) = CAFE FACE (16)
3) 4096 (10) = 2^12 (10) = 0000 0000 0000 0000 0001 0000 0000 0000 (2)
2047(10) = 2^10 + 2^9 + … + 2^0 (10) = 0000 0000 0000 0000 0000 0111 1111 1111 (2)
Então obtemos -2047 a partir do complemento de 2 do número acima, que é
1111 1111 1111 1111 1111 1000 0000 0001 (2)
4) Este número é negativo (bit de sinal 1), então fazemos o complemento de 2 primeiro para saber seu valor absoluto:
1111 1111 1111 1111 1111 1111 1110 1111 → numero original
0000 0000 0000 0000 0000 0000 0001 0001 → comp 2 do número
Em decimal, isto vale 17. Como o número original estava em complemento de 2, ele representa o número -17.
5)
Estou assumindo que o exercício pede pra simular a soma , como se estivesse sendo feita na ULA, caso seja apenas pra colocar o resultado no exercício, basta olhar o final de cada alternativa
Para referência:
06 em binário : 00000110
13 em binário : 00001101
-06 em binário: 11111010
-13 em binário: 11110011
a)
1. Soma : não inverte sinal do segundo número
2. Primeiro digito: 0+1+0 = 1		carry 0 :: resultado = 1
3. Segundo digito: 1+0+0 = 1		carry 0 :: resultado = 11
4. Terceiro digito: 1+1+0 = 0		carry 1 :: resultado = 011
5. Quarto digito: 0+1+1 = 0		carry 1 :: resultado = 0011
6. Quinto digito: 0+0+1 = 1		carry 0 :: resultado = 10011
7. Sexto digito: 0+0+0 = 0		carry 0 :: resultado = 010011
8. Setimo digito: 0+0+0 = 0		carry 0 :: resultado = 0010011
9. Oitavo digito: 0+0+0 = 0		carry 0 :: resultado = 00010011 = 19
b)
1. Soma : não inverte sinal do segundo número
2. Primeiro digito: 0+1+0 = 1		carry 0 :: resultado = 1
3. Segundo digito : 1+0+0 = 1		carry 0 :: resultado = 11
4. Terceiro digito: 0+1+0 = 1		carry 0 :: resultado = 111
5. Quarto digito: 1+1+0 = 0		carry 1 :: resultado = 0111
6. Quinto digito: 1+0+1 = 0		carry 1 :: resultado = 00111
7. Sexto digito: 1+0+1 = 0		carry 1 :: resultado = 000111
8. Setimo digito: 1+0+1 = 0		carry 1 :: resultado = 0000111
9. Oitavo digito: 1+0+1 = 0		carry 1 :: resultado = 00000111 = 7
O carry 1 no final é ignorado
c)
1. Subtração : inverte sinal do segundo número e realiza soma
2. Primeiro digito : 0+1+0 = 1		carry 0 :: resultado = 1
3. Segundo digito: 1+1+0 = 0		carry 1 :: resultado = 01
4. Terceiro digito: 1+0+1 = 0		carry 1 :: resultado = 001
5. Quarto digito: 0+0+1 = 1		carry 0 :: resultado = 1001
6. Quinto digito: 0+1+0 = 1		carry 0 :: resultado = 11001
7. Sexto digito: 0+1+0 = 1		carry 0 :: resultado = 111001
8. Setimo digito: 0+1+0 = 1		carry 0 :: resultado = 1111001
9. Oitavo digito: 0+1+0 = 1		carry 0 :: resultado= 11111001 = -7
d)
1. Subtração : inverte sinal do segundo número e realiza soma
2. Primeiro digito : 0+1+0 = 1		carry 0 :: resultado = 1
3. Segundo digito: 1+1+0 = 0		carry 1 :: resultado = 01
4. Terceiro digito: 0+0+1 = 1		carry 0 :: resultado = 101
5. Quarto digito: 1+0+0 = 1		carry 0 :: resultado = 1101
6. Quinto digito: 1+1+0 = 0		carry 1 :: resultado = 01101
7. Sexto digito: 1+1+1 = 1		carry 1 :: resultado = 101101
8. Setimo digito: 1+1+1 = 1		carry 1:: resultado = 1101101
9. Oitavo digito: 1+1+1 = 1		carry 1 :: resultado = 11101101 = -19
6) Olhando o bit de sinal dos operandos e do resultado. Ao somar dois números positivos, se o resultado for negativo, certamente houve overflow. Assim como se ao somar dois números negativos o resultado for positivo, também houve overflow.
a) 0011 + 1111 = 0010 (cada operando tem um sinal, não há chance de ocorrer overflow)
b) 0011 + 0111 = 1010 (operandos positivos e resultado negativo, ocorreu overflow)
c) 1111 + 1111 = 1110 (operandos negativos e resultado negativo, não ocorreu overflow)
7)
8)
addi $v0, $zero, 0	# v0 = 0
Loop:
beq $a1, $zero, Exit	# if (a1 == 0) vá para Exit
andi $t0, $a1, 1	# t0 recebe o bit menos significativo de a1
beq $t0, $zero, Prox	# se este bit for 0, nao fazemos a soma nesta iteração
add $v0, $v0, $a0	# v0 += a0
Prox:
sll $a0, $a0, 1		# deslocamos a0 um bit para a esquerda
srl $a1, $a1, 1		# deslocamos a1 um bit para a direita
j Loop
Exit:
9)
10)
Representação binária do valor 0x24A60004 → 00100100101001100000000000000100
Como um inteiro sem sinal, ele representa o valor 614858756 em decimal
Como um inteiro em complemento de 2, se estivermos considerando que o número tem 32 bits, ele também representa o valor 614858756, mas se considerarmos 30 bits (ignorando os dois 0 a esquerda), ele representa o complemento de 2 do valor 011011010110011111111111111100(2), ou seja, -458883068 em decimal
Quebrando este valor em uma instrução mips, temos:
	OPCode
	Rs
	Rt
	Constant
	001001
	00101
	00110
	0000000000000100
Isto representa a instrução addiu (add unsigned immediate), que tem o protótipo addiu $rt, constant($rs)
Ou seja, temos a instrução addiu $6, 4($5)
Em ponto flutuante, separamos os bits da seguinte forma: 
	Sinal
	Expoente
	Fração
	0
	01001001
	01001100000000000000100
Sinal = 0 (numero positivo)
Expoente = 01001001 = 73(base 2)
Expoente real = 73 -127 = -54
Fração = 01001100000000000000100 = 2^-2 + 2^-5 + 2^-6 + 2^-21
num = (1 + 2^-2 + 2^-5 + 2^-6 + 2^-21) x 2^(-54)
# ignorei esse 2^-21 pra fazer a aproximação…
num = 1,296875 x 2^(-54) (base 2)