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 m 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 k 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 r+1?

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:
  1. A ideia de equivalência de instruções (m vezes mais poderosas).
  2. O overhead de interpretação: n instruções de um nível para cada instrução do nível acima.
  3. A relação entre número de instruções, tempo por instrução e tempo total.

Passo 2

Tempo no nível 2
  1. 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.
  2. 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.
  3. 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.
  4. 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}.

Passo 3

Tempo no nível 3
  1. 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.
  2. 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.
  3. 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}}.

Passo 4

Tempo no nível 4
  1. 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³.
  2. 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.
  3. 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}}.

Resposta

T₂ = \frac{n,k}{m}, T₃ = \frac{n{2},k}{m{2}}, T₄ = \frac{n{3},k}{m{3}}

Exercícios relacionados