CMP 334 Homework 13: CPI

This problem considers the performance of several different implementations of the same instruction set architecture on a particular suite of applications. Of the instructions executed by these applications, half are ALU operations, 20% are loads, 5% are stores, 20% are conditional branches, and 5% are unconditional branches. Of the conditional branches, three-quarters are not-taken and one-quarter are taken.

1) On the multi-cycle implementation of the ISA, ALU instructions require

Load instructions require Store instructions require Untaken conditional branch instructions require Taken conditional branch instructions require Unconditional branch instructions require

4 cycles to execute 6 cycles to execute 5 cycles to execute 5 cycles to execute 8 cycles to execute 4 cycles to execute

What is the average CPI for this ISA implementation on this application suite? Hint: This is a weighted average problem.

a) Before you do any arithmetic, show the equation(s) you will use to obtain a solution. (Briefly explain any variables you invent for this step.)

b) Then substitute numeric values for the variables of the preceding step.

c) Without using a calculator, estimate the numeric value of the formula from the preceding step. (This step is for our mutual edification. You will not be graded on it.)

d) (If you are unsure of your answer from the preceding step) use a calculator to obtain an answer that is correct to three significant digits.

2) In another implementation of the ISA every instruction is executed in a single (long) cycle. The execution is made up of five sequential stages (with the indicated durations):

IF ID EX MA WB

How long is

Instruction Fetch Instruction Decode EXecute Memory Access Write Back

400 ps (a pico second, ps, is 10-12 seconds) 200 ps 250 ps 200 ps

150 ps the clock cycle for this implementation?

3) In a third implementation of the ISA, the stages of part 2 are executed in a perfect pipeline. How long is the clock cycle for this implementation?

4) A fourth implementation is the single cycle per instruction implementation like the one in part 2, except that execution of the IF stage has been magically reduced to take only 200 ps. How long is the clock cycle for this implementation?

5) In yet another implementation of the ISA, the stages of part 4 are implemented in a perfect pipeline. How long is the clock cycle for this implementation?

6) In the final ISA implementation, the perfect pipeline of part 5 experiences a 2 cycle stall for each taken conditional branch. On average, how many cycles are required to execute an instruction on this implementation (what is its CPI)? On average, how long does an instruction take to execute?