This page was generated using an imperfect translator. Text may be poorly positioned and mathematics will be barely readable and some characters may be omitted. Illustrations will not show at all. If possible, view the PostScript or PDF versions of these notes.
10-1 Dynamic Scheduling *
* 10-1
This Set
- Scheduling and Dynamic Execution Definitions
From various parts of Chapter 4.
- Description of Three Dynamic Scheduling Methods
Not yet complete.
(Material below may repeat material above.)
- Tomasulo's Algorithm Basics
Section 4.2
- Reorder Buffer and Tomasulo's Algorithm
Sections 4.2 and 4.8 plus non-text material.
Non-text material.
- Sample Problems
10-1 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-1
10-2 Dynamic Scheduling *
* 10-2
Scheduling:
Organizing instructions to improve execution efficiency.
Static Scheduling:
Organizing of instructions by compiler or programmer to improve execution efficiency.
Dynamic Scheduling [processor implementation]:
A processor that allows instructions to start execution : : :
: : :even if preceding instructions are waiting for operands.
Static scheduling advantage: time and processing power available to scheduler (part
of compiler).
Dynamic scheduling advantage: branch outcomes known.
10-2 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-2
10-3 Scheduling Examples *
* 10-3
Unscheduled Code
______________________________________________________________________________________________*
*_______
addf f0, f1, f2
subf f3, f0, f4
multf f5, f6, f7
ld f8, 0(r1)
addi r1, r1, #8
subi r2, r2, #1
______________________________________________________________________________________________*
*_______
10-3 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-3
10-4 *
* 10-4
Unscheduled Code on Chapter-3 DLX
______________________________________________________________________________________________*
*_______
Cycle: 0 1 2 3 4 5 6 7 8 9 10 11
addf f0, f1, f2 IF ID A0 A1 A2 A3 WB
subf f3, f0, f4 IF ID ---------> A0 A1 A2 A3 WB
multf f5, f6, f7 IF ---------> ID M0 M1 M2 M3 M4 M5 M6 WB
ld f8, 0(r1) IF ID -> EX MEM WB
addi r1, r1, #8 IF -> ID EX MEM WB
subi r2, r2, #1 IF ID EX MEM WB
______________________________________________________________________________________________*
*_______
Execution has four stall cycles.
10-4 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-4
10-5 *
* 10-5
Code Static Scheduled on Chapter-3 DLX
Instructions reordered by compiler or programmer to remove stalls.
______________________________________________________________________________________________*
*_______
Cycle: 0 1 2 3 4 5 6 7 8 9 10 11
addf f0, f1, f2 IF ID A0 A1 A2 A3 WB
ld f8, 0(r1) IF ID EX MEM WB
multf f5, f6, f4 IF ID M0 M1 M2 M3 M4 M5 M6 WB
addi r1, r1, #8 IF ID EX MEM WB
subf f3, f0, f4 IF ID A0 A1 A2 A3 WB
subi r2, r2, #1 IF ID EX MEM WB
______________________________________________________________________________________________*
*_______
Execution has zero stall cycles.
10-5 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-5
10-6 *
* 10-6
Execution of unscheduled code on dynamically scheduled processor:
______________________________________________________________________________________________*
*_______
Cycle: 0 1 2 3 4 5 6 7 8 9 10 11
addf f0, f1, f2 IF ID A0 A1 A2 A3 WB
subf f3, f0, f4 IF ID RS RS RS A0 A1 A2 A3 WB
multf f5, f6, f7 IF ID M0 M1 M2 M3 M4 M5 M6 WB
ld f8, 0(r1) IF ID EX MEM WB
addi r1, r1, #8 IF ID EX MEM WB
subi r2, r2, #1 IF ID EX MEM WB
______________________________________________________________________________________________*
*_______
Processor delays subf until f0 is available.
Note that instructions start out of order (multf before subf) : : :
: : :this is called out-of-order execution.
RS is a reservation station (waiting area) were subf is held until it can execute.
10-6 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-6
10-7 Dynamic Scheduling Overview *
* 10-7
What a dynamically scheduled processor must do:
Provide storage for instructions waiting for operands.
Detect when operands for waiting instructions become available.
These will avoid stalls due to true dependencies.
What a dynamically scheduled processor may do:
Assign a new name to a register each time it is written : : :
: : :and use those names for source operands.
This will avoid stalls due to name dependencies.
10-7 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-7
10-8 *
* 10-8
Dynamic Scheduling Terminology
Issue [an instruction]
Assignment of an instruction to a reorder buffer entry.
Initiate Execution
Movement of an instruction into an execution unit.
Complete [Execution]
Movement of an instruction out of an execution unit with the result computed.
Commit (a.k.a. Retire)
Irreversibly write an instruction's results to a register or memory.
In Flight
The state of an instruction after being issued but before being committed.
(Definitions will be illustrated in reorder buffer example.)
10-8 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-8
10-9 Dynamic Scheduling Methods *
* 10-9
Three main methods described, differ in what temporary name refers to:
Reorder buffer entry number.
Reservation station number.
Physical register number.
Common Features:
Use of reorder buffer for exception and misprediction recovery 1.
Use of register map to translate between architected (e.g., r1, f10) register name and tem-
porary name.
Common data bus used to broadcast instruction results.
_______________________
1 In some 20th century homeworks the reorder buffer is omitted.
10-9 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 from*
* lsli10. 10-9
10-10 *
* 10-10
Method 1: Reorder Buffer Entry Naming
Characteristics
Fastest and simplest method.
May not be used in real processors (though parts are).
Major Parts (N.B.: Parts used differently with other methods.)
Reorder Buffer (ROB):
A list, in order, of executing instructions.
Register Map:
Used in place of register file. Provides value or ROB entry # for each register.
Register File:
Holds committed register values, used for recovery.
Reservation Station:
A buffer where instructions wait to execute.
10-10 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-10
10-11 *
* 10-11
(Method 1) Hardware
Stage name shown next to hardware used in that stage.
The following are omitted:
Branch hardware, immediates, load/store hardware.
Connections used for recovery.
10-11 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-11
10-12 *
* 10-12
(Method 1) Reorder Buffer
Reorder Buffer (ROB):
A list, in order, of in-flight instructions.
Each entry holds information on an instruction:
PC IR Status Value Dest..
____________________________________________________________________________
_ __ __ _ _ _ _ _
____________________________________________________________________________ _
PC: Program counter (address) of instruction.
IR: The decoded instruction. (Not used here.)
Status: Whether completed, and whether raised an exception.
Value: The result produced (if applicable).
Dest.: The destination register to be written.
An instruction "uses" the reorder buffer three times.
10-12 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-12
10-13 *
* 10-13
(Method 1) Register Map
Register Map
Used in ID and WB stage.
Indexed using architected register number.
When an architected register number placed at Addr input : : :
: : :provides the latest value or : : :
: : :the ROB entry # of instruction that will produce latest value.
Has four ports:
Two for reading source operands (during ID).
One for writing the new ROB # of the destination (during ID).
One for writing results (during WB).
10-13 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-13
10-14 (Method 1) Register File *
* 10-14
Register File
Works like register file in statically scheduled (Chapter-3) implementation.
Values written when instructions commit.
Used to recover from an exception or misprediction.
10-14 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-14
10-15 *
* 10-15
(Method 1) Reservation Station
Reservation Station:
A buffer where instructions wait to execute.
Each functional unit has a set of reservation stations.
In ID an instruction is assigned to a RS based on opcode.
Reservation Station Entry:
Op ROB# Dest Val1 ROB#1 Val2 ROB#2
____________________________________________________________________________________________*
*_______
_ __ _ _ __ _ _ __ _ _ *
* _
____________________________________________________________________________________________*
*________
Op: Operation (May not be same as opcode, but specifies same operation.)
ROB#: Reorder buffer entry holding instruction (name of result).
Dest: Destination register number.
Val1,ROB#1: Value of hrs1 i (operand 1) or ROB entry of instruction that will produce it.
Val2,ROB#2: Value of hrs2 i or ROB entry of instruction that will produce it.
10-15 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-15
10-16 (Method 1) Common Data Bus *
* 10-16
Common Data Bus (CDB):
A bus connecting functional units to other parts of the processor, used to broadcast
results.
Data on CDB:
Dest ROB# Status Value
_______________________________________________________
_ __ _ _ __ _
_______________________________________________________ _
Dest: Destination register.
ROB #: Reorder buffer entry number. (Temporary name of dest.)
Status: Happy ending, or an exception?
Value: The result. Can't forget that.
10-16 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-16
10-17 *
* 10-17
(Method 1) Operation
Stages in execution of an instruction.
IF: Same as chapter 3. (Will change later.)
ID:
Initialize new reorder buffer entry.
Reorder buffer provides the new ROB #.
Val can be set to anything, Status bits: complete, 0; exception, 0.
Controller chooses reservation station.
Read operands from register map.
Result of read is either value or ROB #.
Write ROB# (new name for destination) to register map.
10-17 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-17
10-18 *
* 10-18
RS/EX:
If both operands found in register map, start execution, otherwise wait in reservation st*
*ation.
If waiting in reservation station:
"Listen" to CDB for ROB # of missing operands : : :
: : :when "heard" copy value into RS entry.
When both values available, execution can start.
WB:
When functional unit completes execution it tries to get control of CDB (contending wi*
*th
other units).
When it gets control it places result and other information on the bus : : :
: : :instructions waiting in RS may copy the result (if they need it) : : :
: : :the result is written into the register map : : :
: : :the status (hopefully complete, but there could have been an exception) is written
into the reorder buffer.
10-18 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-18
10-19 *
* 10-19
C (Commit):
When instruction reaches the head of the ROB : : :
: : :the controller checks the status.
If execution complete and unexceptional:
Value written into register file.
If execution complete but encountered an exception:
Recovery is initiated : : :
: : :All instructions in reorder buffer squashed, : : :
: : :the register file is copied to the register map, and : : :
: : :exception handler address loaded into PC.
10-19 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-19
10-20 *
* 10-20
(Method 1) Comments
Method for handling loads and stores covered later.
Details, such as handling of immediates and branches omitted.
If it's the 21st century, ask for more examples.
A value can be in several places:
The register map, the reorder buffer, the register file, and a reservation station.
This uses alot of storage and wires (which is expensive to implement) but has two advanta*
*ges:
Relatively simple to explain.
Fast because values are stored at functional units (in RS).
10-20 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-20
10-21 Method 2: Reservation Station Entry Naming *
* 10-21
Differences with method 1:
Reservation station number, rather than ROB entry used to identify operands.
Reservation station held by an instruction until it completes execution : : :
: : :to avoid name duplication.
For example, addf below keeps RS 0 and subf is assigned RS 1. This way when addf finishes
and writes RS 0 on the CDB to identify the result we can be sure no other instruction is
using RS 0 for the result (as subf might have).
____________________________________________________________________________________________*
*_________
! Cycle 0 1 2 3 4 5 6 7 8 9 10
addf f0, f1, f2 IF ID 0:A0 0:A1 0:A2 0:A3 WC
subf f0, f0, f4 IF ID 1:RS 1:RS 1:RS 1:A0 1:A1 1:A2 1:A3 WC
mulf f5, f0, f6 IF ID 2:RS 2:RS 2:RS 2:RS 2:RS 2:RS 2:M1...
____________________________________________________________________________________________*
*_________
No diagram for method 2 (since very similar to method 1).
10-21 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-21
10-22 Method 3: Physical Register Naming *
* 10-22
Difference with method 1:
A single register file, called the physical register file used to store values.
Instructions wait in an instruction queue for execution. (No reservation stations.)
A scheduler chooses instructions from queue to execute : : :
: : :when chosen they read registers and in the next cycle: : :
: : :move to an execution unit.
Two register maps are used:
One provides physical register numbers for architected registers taking into account issu*
*ed
instructions.
One provides physical register numbers for architected registers taking into account com-
mitted instructions. (Used for recovery.)
10-22 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-22
10-23 *
* 10-23
Two free lists are used.
Free list holds list of unused physical registers.
One free list holds physical register not holding committed values.
One free list holds physical register not holding any needed values.
10-23 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-23
10-24 *
* 10-24
(Method 3) Hardware
Stage name shown next to hardware used in that stage.
The following are omitted:
Execute stage, branch hardware, immediates, load/store hardware.
Connections used for recovery.
10-24 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-24
10-25 *
* 10-25
Loads and Stores in Dynamically Scheduled Processors
Load/Store Unit (LSU)
Loads and stores done in two steps:
L1: Address computation, and
L2: Memory read or write.
L2 may encounter a cache miss (data far away).
Cache used with load/store unit can be blocking or non-blocking.
10-25 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-25
10-26 *
* 10-26
If cache is blocking must wait for data to arrive before attempting other loads or stores.
For example,
____________________________________________________________________________________________*
*_________
! Example: 0(r4) in cache, but 0(r2) not in cache.
! Cycle 0 1 2 3 10 11 12 13 14
lw r1, 0(r2) IF ID L1 L2 ------... --> WB
lh r3, 0(r4) IF ID L1 ------... --> L2 WB
add r10, r10, r1 IF ID RS RS... RS EX -> WB
sub r11, r11, r3 IF ID RS... RS RS EX -> WB
____________________________________________________________________________________________*
*_________
Because cache is blocking miss by lw forces lh (and sub) to wait, even though data cached.
10-26 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-26
10-27 *
* 10-27
If cache is non-blocking can attempt other loads and stores while handling miss:
With a non-blocking cache, instruction would not wait in L2 during cache miss.
For example,
____________________________________________________________________________________________*
*_________
! Example: 0(r4) in cache, but 0(r2) not in cache.
! Cycle 0 1 2 3 4 5 6 ... 10 11 12 13 14
lw r1, 0(r2) IF ID L1 L2 RS -------... L2 WB
lh r3, 0(r4) IF ID L1 L2 WB
add r10, r10, r1 IF ID RS RS RS... RS EX WB
sub r11, r11, r3 IF ID EX WB
____________________________________________________________________________________________*
*_________
Because cache is non-blocking miss by lw does not delay lh (or sub).
10-27 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-27
10-28 *
* 10-28
Load and Store Dependencies
Loads and stores have dependencies too.
Consider:
____________________________________________________________________________________________*
*_________
! At cycle 5 we know 0(r1) != 0(r5), but the processor is not omniscient.
! Cycle 0 1 2 3 4 5 6 ... 10 11 12 13 14
lw r1, 0(r2) IF ID L1 L2 RS -------... L2 WB
sw 0(r1),r3 IF ID RS RS L1 L2 WB
lw r4, 0(r5) IF ID L1 RS ----... RS L2 WB
add r5, r4, r5 IF ID RS ----... RS RS EX -> WB
____________________________________________________________________________________________*
*_________
sw had to wait because of the true dependency on r1.
Since r1 not available the second lw has to wait because of : : :
: : :a possible address dependency: 0(r1)=?0(r5).
10-28 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-28
10-29 *
* 10-29
The situation is different when the store address is available:
Consider:
____________________________________________________________________________________________*
*_________
! At cycle 5 we know 0(r3) != 0(r5), and the processor does too.
! Cycle 0 1 2 3 4 5 6 ... 10 11 12 13 14
lw r1, 0(r2) IF ID L1 L2 RS -------... L2 WB
sw 0(r3),r1 IF ID L1 RS L2 WB
lw r4, 0(r5) IF ID L1 L2 WB
add r5, r4, r5 IF ID RS EX WB
____________________________________________________________________________________________*
*_________
Here, the second lw uses a different address than the sw, so it doesn't have to wait.
10-29 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-29
10-30 *
* 10-30
Load/Store Units for Non-Blocking Caches
LSU maintains a queue of instructions in program order.
It keeps track of which instructions are waiting for addresses.
Store instructions write the cache when they retire.
Load instructions can read (bypass) data from store instructions in the queue.
The memory (L2) part of a load operation can proceed if: : :
: : :its address is available : : :
: : :addresses for all preceding queued store instructions are available : : :
: : :the load address does not match any preceding store instructions or: : :
: : :the address does match a store and the (latest) store data is available.
10-30 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-30
10-31 Editorial Comment *
* 10-31
The slides that follow contain material that has not yet been integrated into t*
*he
material above, and so it may seem repetitive or out of place.
10-31 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-31
10-32 Dynamic Scheduling Methods *
* 10-32
Scoreboard
Avoids stalls due to true dependencies.
Covered in text section 4.2, but not in class.
Tomasulo's Algorithm
Avoids stalls due to name dependencies : : :
: : :by assigning a new name to (renaming) each destination register.
Avoids stalls due to true dependencies : : :
: : :by holding instructions (in reservation stations) waiting for operands.
Three variations covered in class.
Widely used in real systems.
10-32 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-32
10-33 *
* 10-33
Tomasulo's Algorithm Basics
Implementation methods vary, a simple system described.
Reservation Station (RS)
Buffer area where instructions wait for operands and an execution unit.
Each functional unit has several reservation stations.
Common Data Bus (CDB)
A bus connecting functional unit output to : : :
: : :register file (in some cases) : : :
: : :reservation stations : : :
: : :other devices awaiting instruction completion.
CDB used to pass results from functional unit to : : :
: : :waiting instructions : : :
: : :and (in some cases indirectly) the register file.
10-33 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-33
10-34 Tomasulo's Algorithm Basics *
* 10-34
When an instruction is in ID (during issue):
A reservation station is assigned to the instruction.
A temporary name is chosen for destination register.
Following instructions refer to that temporary name.
When an instruction completes execution:
Result broadcast on CDB along with temporary name and other information.
Result read from CDB by instructions in RS that need it.
Depending on variation result is: : :
: : :written to register file (if it's the latest value) : : :
: : :or written to other storage area before reaching register file.
10-34 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-34
10-35 *
* 10-35
Execution With Reservation Stations
Pipeline Execution Diagram Notation
Instruction in reservation station x indicated by: x:RS.
Instruction using RS 3 in stage 4 of multiply: 3:M4.
Timing
Option 1: CDB to execution unit and RS.
Waiting instruction starts while dependent instruction in WB.
Option 2: CDB to RS, RS to execution unit.
Waiting instruction starts cycle after dependent instruction in WB.
10-35 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-35
10-36 Example: *
* 10-36
Reservation station numbers: fp add unit, 0-3; fp mult unit, 4-5.
Timing uses option 1, reservation station numbers will be used for temporary names.
____________________________________________________________________________________________*
*_________
Cycle 0 1 2 3 4 5 6 7 8 9 10 11 12 *
* 13
multf f0, f1, f2 IF ID 4:M1 4:M2 4:M3 4:M4 4:M5 4:M6 4:M7 4:WB
subf f3, f0, f4 IF ID 0:RS 0:RS 0:RS 0:RS 0:RS 0:RS 0:A1 0:A2 0:A3 0:A4 0:WB
addf f0, f5, f6 IF ID 1:A1 1:A2 1:A3 1:A4 1:WB
ltf f0, f7 IF ID 2:RS 2:RS 2:RS 2:A1 2:A2 2:A3 2:A4 2:WB
____________________________________________________________________________________________*
*_________
In cycle 1 multf assigned RS 4 and it reads values for f1 and f2. RS 4 is the temporary
name given to its result, f0.
In cycle 2 subf assigned RS 0. It reads the value of f4 and the reservation station that *
*will
produce f0, RS 4.
In cycle 3 subf sits in RS 0 waiting for multf to finish to get f0, a.k.a., RS 4.
Meanwhile, in ID, addf is assigned RS 1, f0 will now be known as RS 1. Values for f5 and
f6 are read.
In cycle 4 ltf assigned RS 2. It reads a value for f7 but it will have to wait for RS 1 *
*to
finish to get f0. (f0 and f7 are source operands of ltf, the destination is the floating-*
*point
condition code register).
10-36 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-36
10-37 *
* 10-37
Example, continued.
____________________________________________________________________________________________*
*_________
Cycle 0 1 2 3 4 5 6 7 8 9 10 11 12 *
* 13
multf f0, f1, f2 IF ID 4:M1 4:M2 4:M3 4:M4 4:M5 4:M6 4:M7 4:WB
subf f3, f0, f4 IF ID 0:RS 0:RS 0:RS 0:RS 0:RS 0:RS 0:A1 0:A2 0:A3 0:A4 0:WB
addf f0, f5, f6 IF ID 1:A1 1:A2 1:A3 1:A4 1:WB
ltf f0, f7 IF ID 2:RS 2:RS 2:RS 2:A1 2:A2 2:A3 2:A4 2:WB
____________________________________________________________________________________________*
*_________
In cycle 8 addf writes the common data bus, ltf copies the result and starts execution.
In cycle 8 the register file is updated since RS 1 is the latest name of f0. (The registe*
*r file
would not be updated in this cycle if a reorder buffer were being used. See next example.)
In cycle 9 multf writes the CDB, subf copies the result.
In cycle 9 the register file is not updated since RS 4 is an outdated name for f0.
10-37 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-37
10-38 *
* 10-38
Example:
Reservation station numbers: fp add unit, 0-1; fp mult unit, 4-5, 6-9 integer unit.
Add unit has one less reservation station than in last example.
Timing uses option 2.
Reservation stations will be used for temporary names.
____________________________________________________________________________________________*
*_________
Cycle 0 1 2 3 4 5 6 7 8 9 10 11 12 *
* 13 14
multf f0, f1, f2 IF ID 4:M1 4:M2 4:M3 4:M4 4:M5 4:M6 4:M7 4:WB
subf f3, f0, f4 IF ID 0:RS 0:RS 0:RS 0:RS 0:RS 0:RS 0:RS 0:A1 0:A2 0:A3 0:A4 0:WB
addf f0, f5, f6 IF ID 1:A1 1:A2 1:A3 1:A4 1:WB
ltf f0, f7 IF ID ------------------> 1:A1 1:A2 1:A3 1:A4 1:WB
xor r1, r2, r3 IF ------------------> ID 6:EX 6:WB
____________________________________________________________________________________________*
*_________
Because of CDB timing option 2, subf waits an extra cycle to start, during cycle 9.
Because there are not enough add reservation stations, decoding stalls at cycle 5.
10-38 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-38
10-39 *
* 10-39
Dynamic Scheduling with Tomasulo's Algorithm Variations
Three variations, differ in what "temporary name" refers to:
- Reservation Stations Only
Temporary name is reservation station number of instruction producing result.
(Used in examples above.)
- Reorder Buffer and Reservation Stations
Temporary name is reorder buffer entry number of instruction producing result.
- Reorder Buffer, Reservation Stations, Physical (Rename) Registers
Temporary name is name of a special rename register.
Second and third variations commonly used.
10-39 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-39
10-40 Reorder Buffer *
* 10-40
Reorder Buffer
A buffer holding information about instructions, kept in program order.
Each instruction occupies a reorder buffer entry.
Each entry has a unique number which can be used to identify the instruction.
10-40 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-40
10-41 Reorder Buffer Use *
* 10-41
In ID reorder buffer entry created for instruction.
Entry updated during instruction execution.
Entry removed if : : :
: : :it is the oldest entry : : :
: : :and the instruction has completed execution.
When an entry is removed : : :
: : :the register file is written if the instruction writes a register : : :
: : :memory is written if the instruction writes memory.
When an entry is removed the instruction is said to commit.
Hardware limits number of instructions that can commit per cycle : : :
: : :usually the same as the number that can issue per cycle (1 so far).
_______
Commit shown in execution diagram with a WC or __WB____if it occurs during writeback
or C if it occurs later.
Removal of item from reorder buffer sometimes called retirement.
10-41 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-41
10-42 *
* 10-42
Example:
Reservation station numbers: fp add unit, 0-3; fp mult unit, 4-5.
Timing uses option 1.
Reorder buffer entry numbers will be used for temporary names. (Entry numbers not shown
in diagram.)
____________________________________________________________________________________________*
*_________
Cycle 0 1 2 3 4 5 6 7 8 9 10 11 12 *
* 13 14 15
multf f0, f0, f2 IF ID M1 M2 M3 M4 M5 M6 M7 WC
subf f3, f0, f4 IF ID 0:RS 0:RS 0:RS 0:RS 0:RS 0:RS A1 A2 A3 A4 WC
addf f0, f5, f6 IF ID A1 A2 A3 A4 WB C
ltf f0, f7 IF ID 2:RS 2:RS 2:RS A1 A2 A3 A4 WB *
* C
____________________________________________________________________________________________*
*_________
RS assignment same as earlier examples however RS freed when execution starts. Note
commit symbols in diagram.
Table showing time of events during instruction execution:
Instr____Issue___Initiate_Ex.__Complete_Ex._____Commit______
multf 1 2 8 9
subf 2 9 12 13
addf 3 4 7 14
ltf 4 8 11 15
10-42 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-42
10-43 *
* 10-43
Reorder Buffer and Exceptions
Precise exceptions easily provided with a reorder buffer.
Reorder buffer entry has an exception bit.
Bit is tested when instruction reaches head of buffer (is oldest in buffer).
If bit is set reorder buffer cleared and a trap instruction inserted in pipeline.
Because bit tested when faulting instruction reaches buffer head : : :
: : :all preceding instructions have executed and their registers and memory written.
Because buffer cleared, none of the following instructions have written registers or memo*
*ry.
Therefore, exceptions are precise.
10-43 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-43
10-44 *
* 10-44
Register Mapping
Register Mapping (noun)
The temporary name (RS, reorder buffer entry, or rename register) of an architecturally
visible register.
Register Mapping (verb)
The process of finding the temporary name of an architecturally visible register.
Method of Register Mapping (useful in all variations)
Maintain a table indexed by architecturally visible register number : : :
: : :the table can be part of the register file itself : : :
: : :or use a separate memory device (easier to implement).
The table provides the latest temporary name, if any.
(If latest value is in register file, there is no temporary name.)
Table called a register map.
10-44 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-44
10-45 *
* 10-45
Register Mapping and Cancelled Instructions
Initially all registers map to the architecturally visible ones.
As instructions are issued the register map is updated with temporary names.
If an in-flight instruction is cancelled, the register map file may become invalid.
To safely cancel an instruction (e.g., for an exception) when using a reorder buffer:
Wait for instruction to reach head of reorder buffer.
At this point the register file has been updated for all preceding instructions.
Cancel remaining instructions.
Reset the map file (so that all registers map to the architecturally visible ones).
10-45 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-45
10-46 Sample Problems *
* 10-46
Dynamic Scheduling
EE 4720 terminology notes:
Before 1999, dynamic scheduling called dynamic issue in course materials.
Rename registers were not used in problems before 1999. Do not confuse register renami*
*ng
(assignment of a temporary name to a destination register) with rename registers (a set
of additional registers to hold results until an instruction commits).
1998 Homework 4, Problems 4 and 5.
1997 Final Exam, Problems 2a and 2b.
See also multiple-issue sample problems, at end of lecture notes sets 11 and 12.
10-46 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-46
10-47 *
* 10-47
Reorder Buffer
EE 4720 terminology note: before 1999 the term retire is used instead of commit.
1998 Homework 6, Problem 1. (Includes later material.)
1998 Final Exam, Problem 2. (Includes later material.)
10-47 EE 4720 Lecture Transparency. Formatted 12:25, 8 November 1999 fr*
*om lsli10. 10-47
| David M. Koppelman - koppel@ee.lsu.edu | Modified 18 Nov 1999 14:30 (20:30 UTC) |