CSCE 614, Homework 4

Assume we have a MIPS machine that uses the speculative version of Tomasulo's algorithm. It can issue up to four instructions per clock cycle, but branches must always issue alone. You should make the following assumptions about the machine:

1. There is one branch unit (BU) that does branch target address calculation and conditional evaluation in one cycle, and it has one reservation station (BR1)
2. FP addition and subtraction execute in 3 cycles
3. FP multiplication executes in 5 cycles
4. FP division executes in 8 cycles, uses a floating point multiply unit, and is unpipelined
5. Integer operations and effective address addition execute in 1 cycle
6. Data can be accessed in the data cache in 1 cycle
7. The FPUs are fully pipelined (except for division!), and there are 2 FP adders (FA1,FA2), 1 FP multiplier (FM1)
8. There are two ALUs (A1,A2), which handle effective address calculation along with all other integer operations.
9. There are 8 entries in the reorder buffer
10. The Issue and Commit columns of the table can handle up to four instructions (each) per cycle
11. The CDB can handle up to two instructions per clock cycle
12. At most one instruction may be accessing the data cache in each clock cycle
13. The remaining FUs all have two reservation stations are, named: FMUL[1,2], FAD[1,2], ALU[1,2], ST[1,2], LD[1,2]

Hint: This table is a hint to get you started:

About the hint:

• The first four instructions can all issue in cycle 1; there are no structural hazards between them and all of the register values are available in the register file. The fifth instruction, L.D, waits because we are only issuing up to 4 instructions per cycle, and L.D cannot issue until a Load reservation station becomes available after cycle 4.
• The 2nd through 5th instructions all use the A[1-2] functional units because they are all memory instructions that need to compute an effective address.
• Why does the LW read memory in cycle 4 instead of 3? Two reasons: 1) the effective address computation occurs in the 3rd cycle because A[1-2] were in use before then by other instructions, and 2) even if we had ample adder function units, we still want loads to access memory in order to avoid data hazards through memory. (A more robust machine with memory disambiguation might be able to do both loads simultaneously.)
• Why can't the second instruction, L.D, commit in cycle 5, one cycle after it has broadcast its result to the CDB? Because we commit in order. Remember, we issue in order, execute out of order, and commit in order.
• Why does the S.D instruction use A2 and not A1? Because A1 is busy in cycle 2, so the issue logic chooses A2 instead.
• Why does the L.D F3,0(R1) instruction use the A1 function unit and not the A2 functional unit? No reason. Both of them were available when the instruction was issued, so the issue logic could have chosen either one, and so can you. However, it's a good idea to choose the lowest numbered functional unit that is available since that is probably what your instructor is going to do and it makes it easier to grade :-)
• Why isn't the MEM field filled out for the S.D instruction? On page 121 of your book, see a similar table. MEM is an abbreviation for "Read access at clock number." We don't really need to worry about writes to memory, just reads because we need to make sure they happen in order with respect to one another.

Your assignment should be nicely typed or word-processed. Turn in this assignment before the beginning of class on the due date as a PDF file.

Late assignments will not be accepted.