Problem 3. Dynamic Scheduling Programming Assignment

In this programming assignment, you will need to implement the Tomasulo-like algorithm for an out-of- order execution pipeline architecture. It is preferred that you write this project in C or C++ but any other language is also acceptable. Please document your source code as you develop it. On the due day, a short video is desirable that briefly explains your code, parameters, as well as execution results.

Pipeline Configuration:

You will implement the following 3 stages: Issue, Execute, and Write-back. The tasks performed in each stage were explained in class. You will implement only the FP pipeline. We will consider the following FUs:

FP adder which can perform both FP add and FP sub; 3 cycles

FP multiplier which performs FP multiplication; 10 cycles

FP divider which performs FP division; 40 cycles

load unit; 2 cycles

store unit; 2 cycles

32 general-purpose integer registers and 32 general-purpose floating-point registers

Note that

The hardware configuration should be fully parameterizable, i.e., the number of functional units and the number of execution cycles for each FU should all be the inputs to your simulator.

You do NOT have to use Tomasulo-specific components such as Reservation stations, Load-store queue, etc. to implement this assignment. I'll leave the implementation details to you as long as you have your own way of initializing the hardware configurations, providing the input MIPS source sequence, and printing the result.

The simulator does NOT care about the input/output values as we are mostly concerned about the data dependencies.

Input format

The input MIPS source code will be given in the form:

where is 0 (ADDD), 1 (SUBD), 2(MULTD), or 3 (DIVD),

and register numbers are even integers in the range [0..30]. They denote FP registers.

Or, it is in the form of:

where is 4 (LD) or 5 (SD),

destination register number is an even integer in the range [0..30]. It denotes a FP register (e,g, F4). Source register number is an integer in the range [0..31]. It denotes an integer register (e.g., R3).

Immediate number is an integer in the range [0..65535].

For example,

4 2 2740 5 means LD F2, 2740(R5) or F2 Memory[R5 + 2740] 0 4 2 6 means ADDD F4 F2 F6 or F4 F2 + F6

2 8 4 6 means MULTD F8 F4 F6 or F8 F4 * F6

Output result format

Output result should print

; issue execute write-back

LD F2 #2740 R5	; 1	2-3	4
ADDD F4 F2 F6	; 2	4-6	7
MULTD F8 F4 F6	; 3	7-16	17

Note that the second instruction (ADDD) can begin execution at cycle 4 because the first instruction (LD) produces an updated value of F2, which is only available after cycle 3. Note also that the third instruction (MULTD) can begin execution at cycle 7 because of the data hazard on F4.

Your program

Your program is to process one instruction at a time in sequence. However, you need to make sure your simulator deals with the RAW, WAR and WAW hazards correctly. For example, consider the following RAW & WAW hazard case.

MULTD F0, F6, F8 ; issue at 1, execute 2-11, write back 12 F0 available at 12 ADDD F0, F2, F8 ; issue at 2, execute 3-5, write back 6 F0 available at 6 SUBD F10, F0, F14 ; issue at 3, execute begins at 12 or 6(???)

Here is another RAW & WAW hazard case.

ADDD F0, F2, F8 ; issue at 1, execute 2-4, write back 5 F0 available at 5 MULTD F0, F6, F8 ; issue at 2, execute 3-12, write back 13 F0 available at 13 SUBD F10, F0, F14 ; issue at 3, execute begins at 13 or 5(???)

This is RAW & WAR hazards case.

DIVD F8, F10, F12 ; issue at 1, execute 2-41, write 42 F8 available at 42 MULTD F0, F6, F8 ; issue at 2, execute 42-51, write 52 F0 available at 52 ADDD F6, F2, F4 ; issue at 3, execute 4-6, write 7 F6 available at 7