Question

We have a multi-level computer which has hardware at level 1 and identical levels of translation at all levels above it. Each level has W times more powerful instructions compared to the level below it. An instruction being W times as powerful means that optimally sequenced W instructions at level n-1 do the same work of one instruction at level n. In practice, the optimal translation from a level to the one below it is hard to achieve. Therefore, we will assume that an instruction at level n is translated into S instructions at level n-1, where S > W. Assuming we have 6 levels in this multi-level computer find the ratio of the time it takes to execute a program at level 6 to the time it takes an optimal sequence of instructions to do the same work at level 1. Assume all instruction types at one level take the same amount of time to execute. Generalize your answer to N levels.

Answer 1

Given,

Practically, an instruction at n level is translated to S instructions at n-1 level

Optimally, an instruction at n level is translated to W instructions at n-1 level

For practical case,

For a program, let the no. of instructions at level n be x

x instructions are translated to S*x instructions at level n-1

S*x instructions are translated to S²x instructions at level n-2

After calculating, x instructions are translated to S^n-1x instructions at level 1.

For optimal case,

x instructions are translated to W*x instructions at level n-1

W*x instructions are translated to W²x instructions at level n-2

After calculating, x instructions are translated to W^n-1x instructions at level 1.

Ratio of the time taken to execute a program at level n to the time taken to optimally execute a program at level 1

= (S^n-1*x*time taken per instruction)/(W^n-1*x*time taken per instruction)

= (S/W)^n-1

For a program at level 6, the required ratio is (S/W)^6-1=(S/W)⁵

Answer:

Ratio of the time taken to execute a program at level n to the time taken to optimally execute a program at level 1 = (S/W)^n-1

Ratio of the time taken to execute a program at level 6 to the time taken to optimally execute a program at level 1 = (S/W)⁵