Electrical, Computer, and Systems Engineering

ECSE-4730 Computer Systems Architecture

Fall 1998

 

Problem Set 3/4 [SOLUTIONS]-- Due Friday, October 23, 1998

 

Your Name

Circle Your Section

8-9:50 am 10-11:50 am noon-1:50pm

 

Notes:

    1. Be brief.
    2. The answers you submit should be the result of your own individual work. This should not be a collaborative activity.
    3. Refer to the course syllabus under "General Policies Regarding Graded Material" for important notes regarding problem sets. Reminder, as stated in syllabus: SUBMISSIONS NOT HANDEDTO COURSE STAFF (E.G. SLIPPED UNDER DOOR, PLACED IN MAILBOX) WILL AUTOMATICALLY BE MARKED LATE.
    4. If after working on the problems, you feel you may need some help, please don’t hesitate to see the instructor or TA. Instructor office hours are 10-11:30 MW, and TAs will conduct the problem sessions on Friday, Sept 11th where you can seek their help
    5. Make sure the pages are stapled together before handing it in.

 

----------------------------------Do not write below this line-----------------------------------------

 

1

2

3

4

Total

20*

40

20

40

100

* problem 1 is for extra credit.

 

TA Signature :___________________________________

 

1. (Extra credit: 20 points) [Reading assignments]

  1. (Extra credit: 10 points) [Micro-programming, Exceptions, Real Stuff, History], Read Sections 5.5-5.10 (pg 399-425). Summarize points NOT covered in class. Check section 5.11 to see if you understand all the key terms. Note that, except for micro-programming, the reading part is advanced and will not be covered in exams.

    2.  

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

  2. (Extra Credit: 10 points) [Exceptions, Superscalar, Dynamic Pipeline Scheduling, Real Stuff, History] Read pg 498-503 (dynamic branch prediction), Sec 6.7-6.12 (pg 505-528). Summarize key points NOT covered in class. Check 6.13 to see if you understand all the key terms. Note that these reading sections are advanced and will not be evaluated in exams.
  1. (40 points) [Multi-cycle data path/control] Using fig 5.33 and 5.42, describe how a "lw" (load word) instruction executes in the multi-cycle data path. Specifically, describe what operations, control signals and data path elements are accessed in every cycle. You can use the RTL equation formats (eg: IR = Memory[PC]) .

    2.  

    Operations:

     

    IR = Memory[PC];

    # Components: IR, Memory, PC

    # Control signals: IorD = 0, MemRead = 1,IRWrite = 1

    PC = PC + 4;

    # Components: PC, ALU

    #Control signals: ALUSrcB = 01, ALUOp = 00,PCWrite= 1, PCSource = 00

    A = Reg[IR[25-21]];

    # Components: A, Reg file, IR

    # Control Signals: none

    B = Reg[IR[20-16]];

    # Components: B, Reg file, IR

    # Control Signals: none


    ALUOut = PC +(sign-extend(IR[15-0]) <<2);

    # Components: PC, Sign-extend, Shift Left 2, IR, ALU

    # Control Signals: ALUSrcA = 0, ALUSrcB =11, ALUOp = 00


    ALUOut = A + sign-extend(IR[15-0]);

    # Components: A, sign extend, IR, ALU

    # Control Signals: ALUSrcA = 1, ALUSrcB =10, ALUOp = 00

     

    MDR = Memory[ALUOut];
    # Components: MDR, Memory, ALUOut

    # Control Signals: MemRead = 1, IorD = 1

     

    Reg[IR[20-16]]= MDR;
    # Components: Reg file, IR, MDR

    # Control Signals: RegDst = 0, RegWrite = 1, MemtoReg = 1



     

     

     

  2. (20 points) [Data/Control Hazards] Do Exercise 6.23 of chapter 6 (on page 534, P&H). Explain why you think you are right (either through text or through comments).

    3.  

    Solution:

     

    lw $3, 0($5)

    add $7, $7, $3 ## Forced load-use hazard => stall

    sw $6, 0($5)

    lw $4, 4($5)

    add $8, $8, $4 ## Forced load-use hazard => stall

    add $10, $7, $8 # resolved by forwarding

    beq $10, $11, Loop # resolved by forwarding

     

     

  4. (40 points) [Pipelined Data path, Control] In fig 6.71 (pg 531), what is the instruction in the EX stage of the pipeline shown ? Show how you figured the answer out. Hint: consider building a table of control signals similar to fig 5.20, pg 361 (the table you build will have only one row for the instruction you are trying to find, and the values you fill there will lead you to the instruction type. This combined with the register numbers you see on fig. 6.71 should give you the answer).

 

Solution:

 

The instruction is:

sw $6, 16 ($5)

 

We need look only at the EX stage and MEM stage to figure out what instruction this is, and what its operands are.

 

We know that the instruction is either an R-type, lw, sw or a beq. In the EX stage, I observe that the ALUSrc control signal is 1. This rules out R-type instructions and 'beq' (because they use the contents of 'rs' and 'rt' in the ALU, not the sign-extended offset). Now we can eliminate 'lw' by examining the set of control signals for MEM (which in this case is 001). Looking ahead in the MEM stage, we observe that 001 stands for: Branch = 0, MemRead = 0, MemWrite = 1. Now a 'lw' does not write to memory and cannot have MemWrite = 1, so it must be a 'sw' instruction.

 

Now what's left is the operands…

You can deduce the operands $6, $5 by looking at the 'rs' and 'rt' lines before the ALU. You can deduce the offset 16 by looking at the result of the sign-extend. This gives our full answer.