CPSC 330 - Fall 2009
Homework 3
Due on Monday, November 2


1. 4.1.1 a and b - Give values for all control signals in Fig. 4.2 as
                   well as whether each of the three muxes selects its
                   upper or lower input to pass through.  For ALU
                   operation, use one of the function names in the table
                   on p. 316.  For other control signals, use either 0 or
                   1, and assume Zero = 0.

2. 4.1.4 a and b - identify the components in the critical path

3. 4.13.1 a - identify data dependences and types (RAW,WAR,WAW)

4. 4.13.2 a (without forwarding) - assume register file writes occur in
                                   the first half cycle and reads in the
                                   second half cycle

5. 4.13.3 a (with forwarding)

6. Run the following program on WinDLX.  (See the HW 3 examples for info
   on using WinDLX.)

			.data
	a:	 	.word		1,2,3,4
	b:		.word		0,0,0,0

			.text
			.global	main
	main:
			addi		r1,r0,a
			addi		r3,r0,b
			addi		r4,r0,4
	loop:
			lw		r2,0(r1)
			addi		r2,r2,1
			sw		0(r3),r2
			addi		r1,r1,4
			addi		r3,r3,4
			subi		r4,r4,1
			seqi		r5,r4,0
			beqz		r5,loop
	finish:
			trap		0

   The program calculates b[i] = a[i] + 1 for i = 0 to 3

   (a) Compare the cycles required to run this program with and without
       forwarding.

   (b) Can you reorder the instructions in a way that preserves program
       correctness to reduce the cycle count even in the case of forwarding
       enabled?  If so, show the reordered program and give the cycle count.

6. 4.23.2 - using the instruction type frequencies from row a of the
            first table, calculate the extra CPI for both rows a and b
            of the second table.  Assume branch outcomes are determined
            in the EX stage and off-path instructions already fetched
            are immediately cancelled.

7. Download the program http://www.cs.clemson.edu/~mark/330/predictors.c
   Run the predictors with these two input files:

     trace1

	1 1 1 1 1 1 1 1 1 0
	1 1 1 1 1 1 1 1 1 0
	1 1 1 1 1 1 1 1 1 0
	1 1 1 1 1 1 1 1 1 0
	1 1 1 1 1 1 1 1 1 0
	-1

     trace2

	1 0 1 0 1 0 1 0 1 0
	1 0 1 0 1 0 1 0 1 0
	1 0 1 0 1 0 1 0 1 0
	1 0 1 0 1 0 1 0 1 0
	1 0 1 0 1 0 1 0 1 0
	-1

   (a) Draw the state diagram for the encoding 0x3127b.

   (b) For trace2, explain how the eight gshare PHT entries end up as
       they do.  As part of your explanation, for the training period
       identify which PHT entries are accessed and how they are updated.
       (You can modify the program to print this info.)