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