Dynamic Scheduling

Scoreboard

We'll assume a machine with 2 integer units, 2 FP add units, 1 FP multiply unit, and 1 FP divide unit. A scoreboard consists of three parts: the instruction status, the functional unit status, and the register status. These parts are shown and explained below.

Instruction status

Instruction	Issue	Read operands	Execution	Write result
LD F2,0(R1)	x	-	-	-
ADDD F6,F2,F4	x	-	-	-
MULTD F8,F6,F0	x	-	-	-
LD F10,-8(R1)	x	-	-	-
ADDD F12,F10,F4	x	-	-	-
MULTD F14,F12,F0	-	-	-	-
SUBI R1,R1,#16	-	-	-	-
BNEZ R1,Loop	-	-	-	-

Functional unit status

Name	Busy	Op	Fi	Fj	Fk	Qj	Qk	Rj	Rk
Int1	Yes	Load	F2	R1	-	-	-	No	-
Int2	Yes	Load	F10	R1	-	-	-	No	-
Add1	Yes	Add	F6	F2	F4	Int1	-	No	Yes
Add2	Yes	Add	F12	F10	F4	Int2	-	No	Yes
Mult1	Yes	Add	F8	F6	F0	Add1	-	No	Yes
Div1	No	-	-	-	-	-	-	-	-

Register result status

F0	F2	F4	F6	F8	F10	F12	F14
-	Int1	-	Add1	Mult1	Int2	Add2	-

The instruction status table indicates which stage a particular instruction is in. In this example, we assume that the table is large enough so it can fit all the instructions. The functional unit status table indicates the state of the functional unit. The fields are as follow:

Busy - whether or not unit is busy
Op - which operation unit is performing
Fi,Fj,Fk - destination and source operands respectively
Qj,Qk - functional units producing results for Fj and Fk, if any
Rj,Rk - whether or not Fj and Fk are ready to be read (this is set to No after operands are read)

The register result status table indicates which functional units are writing to which registers.

In the tables above, we have filled out the initial status of the tables, assuming all the instructions had been fetched into the instruction status table. We issue instructions sequentially until we encounter a WAW hazard or we run out of functional units. In this case, we ran out of functional units. Note that we have issued five instructions at once. This may not be realistic depending on the particular machine. For now, we will assume this is legal.

Continue...

Back to Scoreboarding

Author: Allan Tong

Contact actong@wam.umd.edu