Attached

Question 1:

The design team for a simple, single-issue processor is choosing between a pipelined or

non-pipelined implementation. Here are some design parameters for the two possibilities:

(a) For a program with 20% ALU instructions, 10% control instructions and 75% memory

instructions, which design will be faster? Give a quantitative CPI average for each case.

(b) For a program with 80% ALU instructions, 10% control instructions and 10% memory

instructions, which design will be faster? Give a quantitative CPI average for each case.

Problem 2

The execution flow in a pipelined CPU is clearly visible by drawing the pipeline

execution diagram. Draw the pipeline execution diagram of the following code, taking

hazards into account What kinds of hazards are there and explain why? Show in the

diagram with arrows how to fix the hazards

lw $2, 16($3)

sub $4, $2, $1

add $3, $4, $1

sw $3, 8($8)

Problem 3.

a) Calculate the performance of a processor taking into account stalls due to data cache and

instruction cache misses. The data cache (for loads and stores) is the same as

described in Part B and 30% of instructions are loads and stores. The instruction

cache has a hit rate of 90% with a miss penalty of 50 cycles. Assume the base CPI

using a perfect memory system is 1.0. Calculate the CPI of the pipeline, assuming

everything else is working perfectly. Assume the load never stalls a dependent

instruction and assume the processor must wait for stores to finish when they miss the

cache. Finally, assume that instruction cache misses and data cache misses never

occur at the same time. Show your work.

• Calculate the additional CPI due to the icache stalls.

• Calculate the additional CPI due to the dcache stalls.

• Calculate the overall CPI for the machine.

Problem 4.

a. Explain in detail what the advantage of pipelining is? (5 points)

b. A Single-cycle CPU is running at 500MHz. How much time does it take to execute 2

billion instructions on the CPU, assuming the perfect cache (that is, memory access

takes 1 CPU clock cycle)? (3 points)

c. You decided to convert the single-cycle CPU to a 5-stage pipelined CPU for

performance. Assume that you completely balanced the pipeline stages. What is the

operating clock frequency and why? (3 points)

d. Among the same 2 billion instructions, 30% of the instructions are lw instructions

and 40% of the load outcomes are used by the next instructions. How much time

does it take to execute 2 billion instructions on the pipelined CPU, assuming the

perfect cache?

Problem5

1. For the MIPS datapath shown below, several lines are marked with “X”. For each one:

• Describe in words the negative consequence of cutting this line relative to the working, unmodified

processor.

• Provide a snippet of code that will fail

• Provide a snippet of code that will still work

Problem 6

Structural, data and control hazards typically require a processor pipeline to stall. Listed

below are a series of optimization techniques implemented in a compiler or a processor

pipeline designed to reduce or eliminate stalls due to these hazards. For each of the

following optimization techniques, state which pipeline hazards it addresses and how it

addresses it. Some optimization techniques may address more than one hazard, so be sure

to include explanations for all addressed hazards.

(a) Branch Prediction

(b) Instruction Scheduling

(c) delay slots

(d) increasing availability of functional units (ALUs, adders etc)

(e) caches

(b) Instruction Scheduling

(c) delay slots

(d) increasing availability of functional units (ALUs, adders etc)

(e) caches

Problem 7

Pipelining is used because it improves instruction throughput. Increasing the level of

pipelining cuts the amount of work performed at each pipeline stage, allowing more

instructions to exist in the processor at the same time and individual instructions to

complete at a more rapid rate. However, throughput will not improve as pipelining is

increased indefinitely. Give two reasons for this.