CS 61C Homework 6-1

Background reading

P&H 6.1-5

Administrative requirements

Submit your solution online by 8 pm on the 1st of August, 2004. Do this by creating a directory named hw6-1 that contains the file hw6-1.txt (put your answers to the problems in here). From within the directory, type:

     submit hw6-1

This is not a partnership assignment -- hand in your work, and don't collaborate with anyone else.

Problem 1: Pipelining

P&H 6.2, 6.3, 6.4 (use simple ascii art for problems that ask you to draw)

Problem 2: More Pipelining

Consider the following program:

                   addiu  $5, $0, 0
           loop:   lw     $10, 0($20)
                   addu   $5, $5, $10
                   sw     $5,  0($21)
                   sw     $10, 0($22)
                   addiu  $8, $8, 1
                   addiu  $20, $20, 4
                   bne    $20, $16, loop

Suppose that this code runs using a pipeline that neither stalls nor forwards on hazards. Add as few "no-op" instructions as necessary to prevent data and control hazards, and draw the progress through the pipeline for the first nine original instructions (up through the lw of the second iteration of the loop) in a format similar to that of Figure 6.3. Use ascii art. For example, the progress of the first two instructions may be written as:
```
      addiu  $5, $0, 0   IF  ID   EX  ME  WB
      lw     $10, 0($20)     IF   ...
```
Assume that branch logic is done during the second stage of the pipeline.
Consider the same code from part (a). Suppose now that the pipeline forwards whenever possible. Minimize the number of "no-ops" while preserving correctness, and draw the progress through the pipeline and the forwarding paths used for the first nine original instructions in a format similar to that of Figure 6.9.
Consider the same code from part (a), and still assume that the pipeline forwards whenever possible. Reorder the instructions in the loop to minimize the number of "no-ops" while preserving correctness, and draw the progress through the pipeline for the first nine original instructions. Remember that the reordered program should have exactly the same function as the original program in part (a). It is not acceptable to sacrifice correctness for optimizations.

Problem 3: Even More Pipelining

For each piece of code, describe the forwarding path necessary in order to minimize the number of "no-ops" between instructions. If no forwarding path is necessary, say so, and explain why a forwarding path would not help to minimize the number of "no-ops". Otherwise, determine the number of "no-ops" necessary inbetween the instructions with and without forwarding. And briefly describe your reasoning. Assume that branch logic is done during the second stage of the pipeline.

For example:

           addu   $8, $8, $9
           addu   $16, $8, $0

Forwarding path: Execute to Execute
No-ops without forwarding: 2
No-ops with forwarding: 0
Reasoning: The two addu's require forwarding from the output of the ALU to the input of the ALU because the second addu instruction depends on the result of the previous addu instruction (read after write). Waiting until the first addu instruction writes its result back to the register would require 2 stalls in order for the second addu instruction to retrive the correct value of $8 from the register. Forwarding the result of the addition $8 + $9 to the input of the ALU for the second addu instruction means that there will be no need to stall because the ALU stage for the second addu instruction immediately follows the ALU stage for the first addu instruction.

      addu   $8, $8, $9
      addiu  $9, $9, 1
      addu   $16, $8, $0

      lw     $8, 0($4)
      addu   $2, $8, $9

      addu $8, $8, $9
      beq  $8, $16, L

      lw   $8, 0($4)
      beq  $8, $16, L