A respeito da organização estruturada de computadores, responda às seguintes perguntas:
Considere um computador multinível no qual todos os níveis são diferentes. Cada nível tem instruções que são
vezes mais poderosas do que as do nível abaixo dele; isto é, uma instrução de nível r pode fazer o trabalho de m instruções de nível r-1. Se um programa de nível 1 requer
segundos para executar, quanto tempo levariam programas equivalentes nos níveis 2,3 e 4 admitindo que são necessárias n instruções de nível r para interpretar uma única instrução de nível
?
Considere um computador multinível no qual todos os níveis são diferentes. Cada nível tem instruções que são
Passo 1
Beleza, vamos começar resumindo tudo. O enunciado fala de um computador “multinível”, onde cada nível r tem instruções m vezes mais poderosas que as do nível r–1. Isso significa que uma instrução de nível r faz o trabalho de m instruções de nível r–1. Além disso, para cada instrução de nível r+1, o sistema precisa interpretar usando n instruções de nível r.
O programa original, escrito em nível 1, leva k segundos para rodar. A gente precisa descobrir quanto tempo leva a mesma tarefa se ela for feita nos níveis 2, 3 e 4, levando em conta esse “poder extra” (m) e o “custo de interpretação” (n).
O que vamos usar:
O programa original, escrito em nível 1, leva k segundos para rodar. A gente precisa descobrir quanto tempo leva a mesma tarefa se ela for feita nos níveis 2, 3 e 4, levando em conta esse “poder extra” (m) e o “custo de interpretação” (n).
O que vamos usar:
- A ideia de equivalência de instruções (m vezes mais poderosas).
- O overhead de interpretação: n instruções de um nível para cada instrução do nível acima.
- A relação entre número de instruções, tempo por instrução e tempo total.
Passo 2
Tempo no nível 2
- Seja I₁ o número de instruções de nível 1 do programa original. Como ele demora k segundos, podemos pensar que cada instrução gasta, em média, k/I₁ segundos.
- No nível 2, como cada instrução vale m instruções de nível 1, o programa precisa de I₂ = I₁/m instruções de nível 2 para fazer o mesmo trabalho.
- Mas cada instrução de nível 2 é interpretada usando n instruções de nível 1. Então o total de instruções de nível 1 executadas é I₂·n = (I₁/m)·n.
- Como cada instrução de nível 1 gasta k/I₁ segundos, o tempo total em nível 2 é
T₂ = (I₁/m)·n · (k/I₁) = n·k/m.
Em LaTeX:
T₂ = \frac{n,k}{m}.
T₂ = \frac{n,k}{m}.
Passo 3
Tempo no nível 3
- Cada instrução de nível 3 vale m instruções de nível 2, que por sua vez valem m instruções de nível 1. Logo valem m² instruções de nível 1. Assim o programa precisa de I₃ = I₁/m² instruções de nível 3.
- Para interpretar cada instrução de nível 3, usamos n instruções de nível 2, e cada uma delas precisa de n instruções de nível 1 para rodar o intérprete. Logo, 1 instrução de nível 3 gera n·n = n² instruções de nível 1.
- O total de instruções de nível 1 executadas é I₃·n² = (I₁/m²)·n². Em tempo isso dá:
T₃ = (I₁/m²)·n² · (k/I₁) = n²·k/m².
Em LaTeX:
T₃ = \frac{n{2},k}{m{2}}.
T₃ = \frac{n{2},k}{m{2}}.
Passo 4
Tempo no nível 4
- Uma instrução de nível 4 vale m instruções de nível 3, m×m instruções de nível 2 e m³ instruções de nível 1. Então I₄ = I₁/m³.
- Para interpretar cada instrução de nível 4, precisamos de n instruções de nível 3, cada uma gerando n² instruções de nível 1 (pelo passo anterior). No total, 1 instrução de nível 4 gera n·n² = n³ instruções de nível 1.
- Logo o total de instruções de nível 1 é I₄·n³ = (I₁/m³)·n³, e o tempo:
T₄ = (I₁/m³)·n³ · (k/I₁) = n³·k/m³.
Em LaTeX:
T₄ = \frac{n{3},k}{m{3}}.
T₄ = \frac{n{3},k}{m{3}}.
Resposta
T₂ = \frac{n,k}{m}, T₃ = \frac{n{2},k}{m{2}}, T₄ = \frac{n{3},k}{m{3}}