Question

Assume that 20 percent of the dynamic count of the instructions executed for a program are branch instructions. Delayed branching is used, with one delay slot. Assume that there are no stalls caused by other factors. First, derive an expression for the execution time in cycles if all delay slots are filled with NOP instructions. Then, derive another expression that reflects the execution time with 70 percent of delay slots filled with useful instructions by the optimizing compiler. From these expressions, determine the compiler’s contribution to the increase in performance, expressed as a speedup percentage.

Answer 1

Answer:

Explanation:

From the given information;

The first objective is to derive an expression for the execution time in cycles

For an execution time T for the non-pipelined processor;

$T = \dfrac{N \times S}{R}$

where

N = instruction count

S = average number of clock cycles to fetch & execute an instruction

R = clock rate

From the average number of clock

$S = 1 + \delta _{branch\_penality }$

where;

$\delta _{branch\_penality }= {Dynamic \ count \times Delay \ Slots}$

Similarly, we are given that the dynamic count is 20%

∴

The execution time required for all the delayed slots that is filled with NOP instructions can be estimated as:

$\delta _{branch\_penality }=0.20 \times 1.00$

$\delta _{branch\_penality }=0.20$

Therefore;

S = 1 + 0.20

S = 1.2

Recall that:

For an execution time T for the non-pipelined processor;

$T = \dfrac{N \times S}{R}$

$T = \dfrac{N \times 1.2}{R}$

$T = \dfrac{ 1.2 \ N}{R}$

To derive another expression that reflects the execution time of 70% delay; we have:

$\delta_{branch\_penality} = 0.20 \times ( 1-0.7)$

$\delta_{branch\_penality} = 0.20 \times ( 0.3)$

$\delta_{branch\_penality} = 0.06$

S = 1 + 0.06

S = 1.06

For an execution time T for the non-pipelined processor;

$T = \dfrac{N \times S}{R}$

$T = \dfrac{N \times 1.06}{R}$

$T = \dfrac{ 1.06 \ N}{R}$

Finally, the compiler's contribution to the increase in speed up percentage for the above two cases is:

$=\begin {pmatrix}\dfrac{T_{all \ delay \ slots }}{T_{70\% \ delay \ slots } } -1 \end {pmatrix} \times 100$

$= \begin {pmatrix}\dfrac{1.2 }{1.06 } -1 \end {pmatrix} \times 100$

= (1.1320 - 1) × 100

= 0.1320 × 100

= 13.20%

Therefore, the compiler's contribution to increasing performance as expressed as speed up percentage is 13.20%