CSE 240a - Fall 2006 - Homework and Projects

Homework and Projects

Fall Quarter, 2006

Instructor: Michael Taylor

Homework Policies:

For all homeworks, please create a cover page. The cover page should contain the following info: course (CSE240A), term (Fall 2006), homework number (e.g. HW #1), name(s), and date. To aid in fair grading, please do not put your name(s) on any page other than the cover page.
You make work on homework in groups of 1 or 2. If working with a group of 2, you only need to submit one writeup. Both members will receive the same grade.
All homeworks should be submitted to the TA either in person or placed in his mailbox (room 2237 in the CSE building) on or before the deadline. No late assignments will be accepted!
Typed solutions will make the TA smile but are not strictly required (i.e. please make Sat's life easier by typing up your solutions).
DO NOT submit your homework via e-mail.

Homework:

Homework 3. Due: Tuesday, Nov. 7 at Noon.

Appendix A: A.12

For A.12, assume there is no forwarding available for scoreboard. Once an instruction enters the write stage, an instruction dependent on that write will be able to enter execution on the next cycle.
For A.12(a), assume that the MIPS pipeline resolves branches in the ID stage. Also, assume that instructions will stall in the ID stage until it is safe to proceed (e.g. to avoid structural hazards, RAW, etc.).
For A.12(a), assume that multiple instructions can be in the MEM and WB stage as long as it doesn't cause a structural hazard (e.g. writing to the MEM or register file in the same cycle).
Assume "DSGTUI R3, R1, done" is an integer ALU operation which compares register R1 with unsigned immediate value "done", setting R3 to 1 if R1 > done, 0 otherwise.
For A.12(b-c), SAXPY is actually a typo and should be DAXPY.
For A.12(c), use the same latencies as you used in part (b). Ignore figure A.56.

Chapter 3: 3.6(b), 3.7(a), 3.18, 3.22

For 3.6, ignore the "cycles in ex" column in figure 3.62.
For 3.18, assume the same latencies as in figure 3.27.
You should also try to solve problem 3.21. It is solved in the back of the book so I am not requiring that you hand it in but try to work through it so that you would be prepared for a similar type of question on an exam.
For 3.6 and 3.7, use the reservation station counts from figure 3.62 and use the following values for "cycles in EX": 1 for integer ops, 1 for branches, 4 for FP adds, 7 for FP mults. Ignore figure 3.63. Assume the FP units are NOT pipelined.
For 3.6(b), assume that an instruction after a branch may not issue in the same cycle as the branch. Assume the processor has a single CDB.

Additional Problems:

HW3.P1: Why is it unnecessary to place non-taken branches in the branch target buffer (BTB)?
HW3.P2: Read the "Register Renaming" section on pages 6 and 7 of the paper available here.
What are the two types of "RAT's" in the Netburst architecture? Why are two types needed compared to only 1 in the P6 architecture?
HW3.P3: Hardware based speculation increases performance by guessing an execution path and following it while the outcome of branches are being determined. If the guess was wrong, execution is restarted along the correct path. Why might this be detrimental to power consumption in a microprocessor?

Homework 2. Due: Tuesday, Oct. 10 at Noon.

Notes:

When drawing pipeline diagrams, use the style shown in Figure A.33 in H&P (even if the book problem says to use another style).
Draw in arrows to show forwarding.

Appendix A: A.1, A.5(a-c), A.6(a-c)

For A.1, assume branches are resolved after the ID stage (as in Figure A.24).
For A.6(b-c), you only need to list the new forwarding paths NOT the old ones that have been changed.

Chapter 3: 3.1(a,c), 3.3

For 3.3(b), again assume that branches are resolved after the ID stage.

During a sleepless night, you decide to check out the assembly code for a bunch of programs you have compiled on your SatTech MIPS-based computer. You happen to notice the following sequence of instructions happening a lot in your code (although not necessarily with the same registers):

load R1, 0(R2)
add R1, R1, R3
store R1, 0(R2)

Basically, this sequence fetches a value from memory, increments it by some amount and stores it back immediately. You decide it would be handy to add the following instruction to your ISA:

INC R1, 0(R2)

The INC instruction takes the value in R1 and adds it to the address specified in the 2nd part of the instruction (in this case 0 + address of R2). Unfortunately, you don't have any memory that will support this type of operation in memory so you need to modify your CPU to support it.

a) Using the basic 5-stage MIPS pipeline as your inspiration, create a new pipeline that will be able to handle the new INC instruction. Make sure to explain how your pipeline operates (specifically on load/store ops, ALU ops, and the new INC op) and why it should be ok on other instructions. Remember that all instructions must go through all of the stages (although it is ok if some stages don't do anything on certain instructions).

b) You would like to compare your new pipeline with the INC instruction to the old 5-stage MIPS pipeline without the new instruction. Do so by comparing the number of cycles required for each set of instructions given below on the 2 different pipelines, assuming that you have data forwarding available (draw pipeline diagrams like in Fig. A.33).

load R1, 0(R2)
add R1, R1, R3
store R1, 0(R2)

vs.

inc R3, 0(R2)

load R1, 0(R2)
add R1, R1, R3
store R1, 0(R2)
load R1, 0(R4)
add R1, R1, R5
store R1, 0(R4) vs. inc R3, 0(R2)
inc R5, 0(R4)

Does your performance (relative to the old pipeline) increase with multiple INC instructions in a row?

c) Draw a pipeline diagram (as in Fig. A.33) to show what happens on your new pipeline with the following code fragment.

inc R1, 0(R2)
load R2, 0(R3)
inc R1, 0(R2)

d) Now assume that you are able to change your pipeline control so that operations that don't use all the stages of your new pipeline can skip the ones that they don't use. How would or wouldn't this improve the performance of your pipeline (give a specific example)?

Homework 1. Due: Tuesday, Oct. 3 at 11am.

Unless otherwise noted, all problems are from the Hennessy & Patterson textbook.
Chapter 1 - 1.2, 1.3, 1.7, 1.15

For 1.7, assume a clock frequency of 300MHz.

Chapter 2 - 2.5, 2.6, 2.10, 2.16a, 2.19

For 2.5b, use the following assumptions. If the offset is 0-8 bits, 1 instruction is required. 9-16 bits requires 2 instructions. 17-24 requires 3 instructions. Please be aware that you are giving the average bits per instruction. This means that even though each instruction would be 24 bits, for a branch with an offset of 10 would have a length of 48 bits (2 instructions needed instead of 1). Give your answer in bits, not bytes.
For 2.5, assume that loads and stores are the only data references, conditional branches are the only branches. All other instructions fit under the "ALU instruction."
For 2.16a, it is recommended you use gcc for compilation. To figure out the assembly code, you can either use the "-S" option with gcc or use the program objdump, which takes a binary and spits out the assembly code for it.

Your engineering team tells you that there are four possible enhancements they can make to your CPU. The speedups for each of these enhancements are:

speedup1 = 10
speedup2 = 15
speedup3 = 10
speedup4 = 15

However, they also tell you it is only feasible to use enhancements 1 and 2 together or enhancements 3 and 4 together (no other combinations possible). Enhancements 1 and 2 are used 20% and 30% of the time, respectively, and only one of these enhancements is in use at any given time. Enhancements 3 and 4 may be used 25% and 30% of the time, respectively, but 15% of the time they overlap and the speedup of the combined enhancements is only 10. Both sets of enhancements would require the same amount of time and cost to implement.
a) What is the overall speedup with each set of enhancements?
b) You later realize that the speedup during the overlap of enhancements 3 and 4 is actually 15, NOT the 10 that you were told. Does this change the recommendation for which speedup to use?

Projects:

Project 1 (12.5% of your grade) - Branch Predictor Simulation

Click here for the project 1 description.

Project 2 (12.5% or 17.5% of your grade) - TBA