Homework 6 Solutions

1. (a) (b)

2.

NOTE: When the execution times for this solutions were calculated, 1 cycle was added for the time it took an instruction to move from the scoreboard to execution stages. It is not necessary to add this extra cycle. If this cycle is not added, completion times may differ from those given below.

Assume starting values: F1=A, F2=B, F6=C

Annotated code:

100 MULF F3,F2,F1   D=B*A
104 DIVF F2,F1,F2   E=A/B
108 MULF F7,F6,F1   F=C*A
10C SUBF F4,F2,F1   G=E-A
110 ADDF F2,F1,F3   H=A+D
114 SUBF F1,F3,F2   I=D-H

The following activities take place during the first 7 cycles:

Time 0:

• Issue 100 (MULF) as F3' <- B*A
• F3 is now mapped to F3'
• F3' becomes Busy and Invalid
• F1' becomes not busy and added to free list
• Issue 104 (DIVF) as F4' <- A/B
• F2 is now mapped to F4'
• F4' becomes Busy and Invalid
• F14' becomes not busy and added to free list

Time 1:

• Execute F3' <- B*A (will complete at time=6)
• Execute F4' <- A/B (will complete at time=21)
• Issue 108 (MULF) as F6' <- C*A (will execute at time=3)
• F7 is now mapped to F6'
• F6' becomes Busy and Invalid
• F9' becomes not busy and added to free list
• Issue 10C (SUBF) as F7' <- F4'-A (will execute at time=21)
• F4 is now mapped to F7'
• F7' becomes Busy and Invalid
• F12' becomes not busy and added to free list

Time 2:

• Issue 110 (ADDF) as F8' <- A+F3' (will execute at time=6)
• F2 is now mapped to F8'
• F8' becomes Busy and Invalid
• F4' becomes not busy but is not free because it is invalid
• Note: Cannot issue 114 (SUBF) because the ADD/SUB station is full

Time 3:

• Execute F6' <- C*A (will complete at time=8)
• Note: Still cannot issue 114 (SUBF)

Time 6:

• Complete F3' <- B*A
• Assign F3' <- D
• F3' is valid
• Execute F8' <- A+D (will complete at time=9)
• Issue 114 (SUBF) as F10' <- D-F8' (will execute at time=9)
• F1 is now mapped to F10'
• F10' becomes Busy and Invalid
• F2' becomes not busy and is added to free list

(a) When each instruction begins and ends:

Instruction  Issue  Execute  Write
   100         0       1        6
   104         0       1       21
   108         1       3        8
   10C         1      21       24
   110         2       6        9
   114         6       9       12

(b) Register Map:

Architecture  F0   F1   F2   F3   F4   F5   F6   F7
Physical      F0'  F10' F8'  F3'  F7'  F5'  F15' F6'

Register status:

Register  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Busy      Y  n  n  Y  n  Y  Y  Y  Y  n  Y  n  n  n  n  Y
Valid     Y  Y  Y  Y  n  Y  n  n  n  Y  n  Y  Y  Y  Y  Y
Value     /  /  /  D  /  /  /  /  /  /  /  /  /  /  /  C

Free List:

F11', F13', F1', F14', F9', F12', F2'

Reservation Stations:

Add:  F7'  <- F4' -  A
      F10' <-  D  - F8'

Mult: empty

Div: empty