CPSC 418: Homework 09

Home

Suggestion Box

CPSC 418 --- Advanced Computer Architecture --- Spring 1996
Homework 09 --- Due 19 Mar

General Information for This Homework

When drawing ``execution tables'' for pipelines:

If a value does not change from one clock-cycle to the next, simply draw a horizontal line, as has been done for the registers from time 2--5 in Figure 2.
For each stage, show the computation that it performs (e.g. R7=S1&S2 for the FetchOperands stage in cycle 3 of Fig 2), and not just the instruction in the stage.
The gray region at the left hand side of the tables represent computations that happened in the past, which we are not concerned with.
Additional, blank execution tables are available on the Web pages as Handout 13.

Problem 1 (10 Points)

Refer to the pipeline shown in Fig 1.
As with all pipeline stages, each stage can contain at most one instruction.
``BY'' is the register for the bypass from the output of Execute to its input.
``S1'' and ``S2'' are the registers where the register file puts the values currently stored in the registers corresponding to the operands in the FetchOps stage (e.g. if FO has ADD R5, R3, R2, then S1 has the value currently stored in R5 and S2 has the value currently stored in R3.
The block diagram of the pipeline does not show the functional units for loads and stores, because this homework does not mention those instructions.

Given the following assembly code:

      ; initial values:  R1=A, R2=B, R3=C, R4=D, R5=E
      1000 :  SUBx  R1, R2, R3  
      1001 :  ADDx  R2, R3, R1  
      1002 :  ANDx  R1, R4, R5  
      1003 :  XORx  R2, R4, R5

Problem 1.a (2 points)

Comment the code by giving a unique character to each value, as was done in lecture. (NOTE: Be nice to the TA and assign characters in alphabetical order.)

Label all of the hazards in the code and explain what causes each hazard. (e.g. RAW on R4 between lines 2034 and 2048)

Problem 1.b (4 points)

Assuming that the bypass path in Fig 1 does not exist, complete the execution table in Fig 3. For each clock-cycle show the values stored/produced at the end of the clock-cycle for:

(PC) Program counter
(FI, DI, FO, EX, WB) Output of each stage in the pipeline
(S1, S2) Source operands produced by register file
(R1--R5) Registers (also show when invalid)

Problem 1.c (4 points)

Using the bypass path, complete the execution table in Fig 4. For each clock-cycle show the values stored/produced at the end of the clock-cycle for:

(PC) Program counter
(FI, DI, FO, EX, WB) Output of each stage in the pipeline
(BY) Execute unit bypass path
(S1, S2) Source operands produced by register file
(R3--R7) Registers (also show when invalid)

Problem 2 (9 points)

Refer to the pipeline shown in Fig 2.
All ``normal'' arithmetic and logical instructions (e.g. ADD, SUB, XOR, MULT, etc.) use the Execute stage and then go directly to WriteBack. Divide (DIV) instructions use Execute, and then loop through the Divide stage twice, before going to WriteBack.
As with all pipeline stages, each stage can contain at most one instruction.
``BY'' is the register for the bypass from the output of Execute to its input.
``S1'' and ``S2'' are the registers where the register file puts the values currently stored in the registers corresponding to the operands in the FetchOps stage (e.g. if FO has ADD R5, R3, R2, then S1 has the value currently stored in R3 and S2 has the value currently stored in R2.
There is no bypass path from the output of Divide to the input of Execute. Divide instructions must be written to the register file before they can be used.
The block diagram of the pipeline does not show the functional units for loads and stores, because this homework does not mention those instructions.

Given the following assembly code:

      ; initial values:  R1=A, R2=B, R3=C, R4=D
      1001 :  DIVx  R1, R2, R3
      1002 :  DIVx  R4, R2, R1
      1003 :  SUBx  R1, R4, R3
      1004 :  ADDx  R4, R3, R4

Problem 2.a (2 points)

Comment the code by giving a unique character to each value, as was done in lecture. (NOTE: Be nice to the TA and assign characters in alphabetical order.)

Label all of the hazards in the code and explain what causes each hazard. (e.g. RAW on R4 between lines 2034 and 2048)

Problem 2.b (5 points)

Complete the execution table in Fig 5. For each clock-cycle show the values stored/produced at the end of the clock-cycle for:

(PC) Program counter
(FI, DI, FO, EX, WB) Output of each stage in the pipeline
(BY) Execute unit bypass path
(S1, S2) Source operands produced by register file
(R1--R4) Registers (also show when invalid)

Problem 2.c (2 points)

What would be the costs and performance gains, if any, for adding a bypass path from the output of the Divide stage to the input of the Execute stage?

Problem 3 (1 Point)

How much time did you spend total on the assignment and on each of these problems? Which problems were useful or useless? How well did the lectures and text book prepare you for this homework? Which concepts needed better explanation?

Figure 1: Block Diagram of Simple Microprocessor Pipeline

Figure 2: Block Diagram of Complex Microprocessor Pipeline

Home

Suggestion Box

Last modified: 05 Mar 96