|
Problem 4 (4 parts, 25 points) |
Tomasulo’s Algorithm |
Here's a snapshot of a system employing Tomasulo's dynamic scheduling.
Instruction Status:
|
Instruction |
Issued? |
EX Complete? |
Results Written? |
|
1: ADDF F1, F2, F3 |
* |
- |
- |
|
2: SUBF F4, F1, F5 |
- |
- |
- |
|
3: LF F1, 0(R1) |
- |
- |
- |
|
4: ADDF F4, F4, F1 |
- |
- |
- |
|
5: MULTF F6, F3, F4 |
- |
- |
- |
|
6: SF 0(R1), F6 |
- |
- |
- |
Reservation Stations:
|
Name |
Busy? |
Op |
Value1 |
Value2 |
Producer1 |
Producer2 |
|
Add1 |
Y |
ADDF |
2 |
3 |
- |
- |
|
Add2 |
N |
- |
- |
- |
- |
- |
|
Mult1 |
N |
- |
- |
- |
- |
- |
|
Mult2 |
N |
- |
- |
- |
- |
- |
Load/Store Buffers:
|
Name |
Busy? |
Address |
Producer |
|
Load1 |
N |
- |
- |
|
Load2 |
N |
- |
- |
|
Store1 |
N |
- |
- |
|
Store2 |
N |
- |
- |
Register File Status
|
Register: |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
|
Producer: |
Add1 |
- |
- |
- |
- |
- |
|
Value: |
- |
2 |
3 |
4 |
5 |
6 |
4a) [5 points] Suppose that instruction 1 issued in cycle C0. Which instructions will issue in the next 6 cycles (C1- C6)? For those instructions that cannot issue, briefly explain why they cannot.
Instructions 2, 3, and 4 will issue. Instruction 4 doesn’t issue until C6, so instructions 5 and 6 can’t issue until after C6.
4b) [10 points] Show the state of the system at the end of cycle 6 (C6).
Instruction Status:
|
Instruction |
Issued? |
EX Complete? |
Results Written? |
|
1: ADDF F1, F2, F3 |
X |
X |
X |
|
2: SUBF F4, F1, F5 |
X |
- |
- |
|
3: LF F1, 0(R1) |
X |
X |
X |
|
4: ADDF F4, F4, F1 |
X |
- |
- |
|
5: MULTF F6, F3, F4 |
- |
- |
- |
|
6: SF 0(R1), F6 |
- |
- |
- |
Reservation Stations:
|
Name |
Busy? |
Op |
Value1 |
Value2 |
Producer1 |
Producer2 |
|
Add1 |
Y |
add |
- |
Mem(100) |
Add2 |
- |
|
Add2 |
Y |
sub |
5 |
5 |
- |
- |
|
Mult1 |
- |
- |
- |
- |
- |
- |
|
Mult2 |
- |
- |
- |
- |
- |
- |
Load/Store Buffers:
|
Name |
Busy? |
Address |
Producer |
|
Load1 |
- |
- |
- |
|
Load2 |
- |
- |
- |
|
Store1 |
- |
- |
- |
|
Store2 |
- |
- |
- |
Register File Status
|
Register: |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
|
Producer: |
- |
- |
- |
Add1 |
- |
- |
|
Value: |
Mem(100) |
2 |
3 |
- |
5 |
6 |
4c) [5 points] Check the box below each instruction that wrote its results back to the register file during cycles C0-C6.
|
Instruction: |
1 |
2 |
3 |
4 |
5 |
6 |
|
Wrote to Register File? |
N |
N |
Y |
N |
N |
N |
4d) [5 points] Check the box below each instruction that broadcasted its results on the Common Data Bus during cycles C0-C6.
|
Instruction: |
1 |
2 |
3 |
4 |
5 |
6 |
|
Broadcasted to CDB? |
Y |
N |
Y |
N |
N |
N |