CSE 410 Computer Systems - Homework 4 - Spring 2009

CSE Home

About Us

Search

Contact Info

Due: Thursday, April 30, at 11 pm. This is an absolute deadline. No late assignments will be accepted after this time, even if you have unused late days. That will allow us to distribute sample solutions on Friday and discuss these problems in class then as part of reviewing for the midterm exam that is scheduled for the following Monday.

The purpose of this assignment is to explore some of the issues involved in pipelining and instruction execution.

1. What is the difference between latency and throughput? What is the effect of pipelining on these two metrics?
   
   
2. Describe the different types of dependencies and their causes.
   
   
3. The following instructions implement the assignment statement x=a+b-c, assuming that a, b, c, and x are all local variables in the current procedure's stack frame, and the variable offsets are a 20, b 24, c 28, and x 32. The instructions are numbered to make it easier to reference them in your answers below.

      lw  $t0, 20($sp)    # (1) load a
      lw  $t1, 24($sp)    # (2) load b
      add $t0, $t0, $t1   # (3) $t0 = a+b
      lw  $t1, 28($sp)    # (4) load c
      sub $t0, $t0, $t1   # (5) $t0 = a+b-c
      sw  $t0, 32($(sp)   # (6) store x
   

   1. Suppose that these instructions are executed on a MIPS processor that has a 5-stage pipeline (IF, ID, EX, MEM, WB), but that the processor stalls whenever there is a data dependency between two instructions (i.e., no forwarding). Draw a pipeline timing diagram showing the execution of these instructions (i.e., write the stages for each instruction on successive lines with the stages that are executing simultaneously lined up vertically as done on the lecture slides and in the book). How many total cycles does it take to execute these 6 instructions?
   2. Now suppose that we execute these instructions on a processor that has a 5-stage pipeline with internal forwarding of results from one instruction to the next. Draw a pipeline timing diagram showing the execution of these instructions on this processor. How many total cycles does it take to execute these instructions on this pipeline with forwarding?
   3. Rewrite these instructions to minimize the total number of cycles needed to perform the assignment statement x=a+b-c. You still need to load the data from memory and store the result back, but you may rearrange the order of the instructions and use different registers if you wish. You should assume that the pipeline has internal forwarding as in part (b). Draw the pipeline timing diagram for your rewritten code. How many total cycles does it take to execute the instructions now?
      
      
4. The following instructions implement the loop while (i!=n && a[i]!=0) i++;. Assume that variable i is in $s0, n is in $s1, and the address of a[i] is in $s2.

   loop:
      beq  $s0, $s1, done    # (1) if i == n then exit
      lw   $t0, 0($s2)       # (2) load a[i]
      beq  $t0, $zero, done  # (3) if a[i] == 0 then exit
      add  $s0, $s0, 1       # (4) i++
      add  $s2, $s2, 4       # (5) increment pointer to a[i]
      b    loop              # (6) repeat (beq $zero, $zero, loop)
   done:
   

   
   What types of hazards exist in the above code fragment? Identify each of the hazards and explain whether it causes a stall or can be resolved by forwarding or some other hardware mechanism.
   
   

Turn-in Instructions: Use the turn-in drop box link on the main course web page to submit a file containing your solutions. You can use any common file format, including plain text, word, or pdf. If you wish, you could also scan in a hand-written solution and submit that, but if you do that, please be sure your handwriting is neat and legible. Please be sure to include your name at the top of your answers.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to Hal Perkins]