SOF108 COMPUTER ARCHITECTURE
TUTORIAL 9: Pipelining
1. What is the difference between hazard and dependency?
2. Assuming that there is a 2 stage pipeline (Fetch & Execute), where each stage requires 1 cycle.
Copyright By PowCoder代写 加微信 powcoder
With the aid of a timing diagram, deduce the time units needed for four instructions.
3. A program consisting of 500 instructions is executed on a 5-stage processor. How many cycles
would be required to complete the program?
i) without pipelining?
ii) with pipelining? Assume ideal overlap in case of pipelining, with 1 cycle per stage.
4. Assume a pipeline with four stages: fetch instruction (FI), decode instruction and calculate addresses (DA), fetch operand (FO), and execute (EX). Draw a timing diagram for a sequence of instructions, in which the third instruction is a branch to instruction 15, that is taken and in which there are no data dependencies. Also, assume that the outcome of the branch instruction
is known only after execution stage of the branch instruction.
5. Consider the execution of a program of 15,000 instructions by a linear pipeline processor with
a clock rate of 25 MHz. Assume that the instruction pipeline has five stages and that one stage gets completed per clock cycle. The penalties due to branch instructions and out-of-sequence executions are ignored.
a) Calculate the speedup factor in using this pipeline to execute the program as compared
with the use of an equivalent non-pipelined processor with an equal amount of flow-
through delay.
b) Calculate the Cycles per Instruction (CPI) for the pipeline processor.
6. Consider the following instructions: I1: add $r2, $r1, $r3
I2: sub $r4, $r2, $r1
I3: and $r5, $r1, $r2
I4: sub $r6, $r2, $r4
I5: add $r7, $r2, $r3
a) Identify all the data dependencies in the following code. Fill in the table below for each
data dependency you find. For example, if instruction 2 depends on register 14 from
instruction 0, you would write ¡°R14 from 2¡±. If there is no data dependency leave the table entry blank.
Instruction
I1: add $r2, $r1, $r3 I2: sub $r4, $r2, $r1 I3: and $r5, $r1, $r2 I4: sub $r6, $r2, $r4 I5: add $r7, $r2, $r3
Depends on Register from Instruction
Depends on Register from Instruction
Depends on Register from Instruction
b) Assume a standard 5-stage MIPS pipeline discussed in class (IF, ID, EX, MEM, WB). Fill out the schedule for executing the above instructions correctly. The cycles (time) are on the horizontal axis. Fill in IF, ID, EX, MEM, and WB in the appropriate time for each instruction. Label all stalls with ¡®¡Á¡¯. Fill out the schedule for a pipeline with no forwarding.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 I1
I2 I3 I4 I5
c) Assume a standard 5-stage MIPS pipeline discussed in class (IF, ID, EX, MEM, WB). Fill out the schedule for executing the above instructions correctly. The cycles (time) are on the horizontal axis. Fill in IF, ID, EX, MEM, and WB in the appropriate time for each instruction. Label all stalls with ¡®¡Á¡¯. Fill out the schedule for a pipeline with forwarding. Draw arrows on the scheduling to specify what is forwarded and where.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 I1
I2 I3 I4 I5
7. Consider the instructions in the following example: DADD R1, R2, R3
LD R4, 0(R1)
SD R4, 12(R1)
Here DADD, LD, and SD are similar to MIPS ADD, LW and SW instructions, but for double- word. Draw five stage MIPS pipeline datapath to describe how forwarding can be used to avoid the data hazards in the above example.
8. Consider the following instructions where the branch instruction is taken. The pipeline uses stall and forwarding to avoid the hazards. Consider that the branch is taken and the pipeline does not use any branch prediction scheme.
addi $1, $1, 4
beq $1, $6, L1
L1: and $12, $2, $5
Draw the five stage MIPS pipeline to show the use of stall and forwarding to avoid the hazards in these instructions.
9. Consider the instructions in the following example: add $1, $2, $3
add $4, $5, $6
add $7, $8, $9
beq $1, $4, target
Draw the five stage MIPS pipeline diagram to show the use of forwarding to avoid the data hazards in the above example
Other questions
10. Draw a five stage MIPS pipeline data path and describe the purpose of each of these stages.
11. Why predicted taken branch does not provide any additional advantage in a 5-stage MIPS
12. With the aid of an example discuss how delayed branch can be used to address the control
hazards in a MIPS five stage pipeline.
– End of Paper –
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com