MIPS Scoreboarding and Tomasulo Algorithm

EECE 552 Computer Design

Authors: Eugene Merecki

Description:

Scoreboarding

Scoreboarding is a centralized method, first used in the CDC 6600 computer, for dynamically scheduling a pipeline so that the instructions can execute out of order when there are no conflicts and the hardware is available

Instructions are decoded in order and go through the following four stages.

• Issue
• Read Operands
• Execution
• Write Result

Tomasulo’s

Tomasulo’s algorithm is a computer architecture hardware algorithm for dynamic scheduling of instructions that allows out-of-order execution and enables more efficient use of multiple execution units.

Instructions are decoded in order and go through the following four stages.

• Issue
• Execution
• Write Result

Note

This program is coded in Python 2.7.12 then converted to Python 3.7

---

Functional Unit:

To specify properties of a Functional Unit in the input file the line must begin with a period '.' Immediately afterwards will be the type of FU (integer, add, mult, div). The next two spaced integers will be the number of FUs being created then the length of its clock cycle The format and an example are as follows:

Format: .[FU type] [number of FUs] [number of clock cycles]

.integer 2 1

---

MIPS Instructions:

Without a period, it will be assumed as an instruction. The formatting of the instruction follows standard MIPS structure. There are 32 Floating point registers. These are referenced with an 'F' then 0-31 Example: F15 There are 32 Integer registers. These are referenced with a '$' then 0-31 Example: $15

[OP code] [Destination register] [Source 1 register] [Source 2 Register]

ADD.D F3, F4, F3
ADD $5, $3, $2

---

Branches:

Branches are are FULLY functional. They are not assuming either always taken or not always taken. WARNING: endless loops will be created unless the instructions make sense. Activating a branch will result in a loop of instructions being inserted into the existing list of instructions.

---

Input File

When creating the input file, there must NOT be any empty lines. Otherwise the program will not run because of a null instruction.

Example Scoreboarding Input File (with looping):

These insructions are supplied in the scoreboard_input.txt file.

This provides a convenient table for deciphering the parts of the instruction.

Functional Unit Inputs

Func Unit	Num Avail.	Clock Cycles
.integer	2	1
.mult	2	10
.add	4	2
.div	1	40

MIPS Instructions

Instruction	Dest	Src1	Src2
L.D	F4	10($0)
L.D	F2	0($0)
L.D	F1	9($0)
ADDI	F2	F2	1
MULT.D	F3	F4	F2
DIV.D	F1	F1	F1
DIV.D	F10	F3	F3
ADD.D	F3	F3	F3
ADD.D	F2	F2	F1
BNE	F2	F4	4
MULT.D	F5	F4	F4
SUB.D	F6	F5	F4
S.D	F3	0($0)
S.D	F4	2($0)
S.D	$5	3($0)