Time chart for different scheduling algorithms

Following are the steps to use this software (for default execution, Step 2-5 can be skipped initially):

Step1: Selection of MIPS instruction set

Insert MIPS instructions by pressing “Insert Instruction”. After an instruction is inserted, its type, destination and sources can be changed. Last instruction can be removed by pressing “Remove Instruction”.

Step 2: Configuring number of cycles for different execution

The number of cycles for execution of each function can be configured. For e.g.: number of cycles to execute “Multiply” can be chosen from 1 to 10 cycles.

Step 3: Configuring number of functional units

The number of functional units for each function can be configured. For e.g.: number of functional units for load/store can be chosen from 1 to 10.

Step 4: Configuring number of reservation stations (ONLY for Tomasulo)

The number of reservation stations for each functional unit in Tomasulo dynamic scheduling algorithms can be configured. For e.g: number of reservation stations for add/sub can be chosen between 1 and 10.

Step 5: Configuring whether functional units are pipelined or not

Different functional units can be separately configured for pipeline or not pipeline execution.

Step 6: Selection of scheduling algorithms

The software implements static scheduling with forwarding and without forwarding and dynamic scheduling namely Tomasulo and Scoreboarding. It provides flexibility to chose one or more scheduling algorithms.

Step 7: Start the execution

The execution can be started by pressing “Execute”. It executes the chosen algorithm in the background and shows the empty time chart.

Step 8: Viewing results

Time chart can be view step-by-step by pressing “Step-by-Step” on the basis of cycle. The total time chart can be seen any time by pressing “Final”. The time chart is shown in different colors for different scheduling algorithms and the stall cycles are shown in dark red color to clearly differentiate it from other pipeline stages and helps in differentiating across the algorithms.

The whole process can be reset anytime by pressing “Reset” button. Then you can start by going to Step 1.

Assumptions for Scoreboarding Implementation

Scoreboarding can be implemented in such a way that time chart for scoreboarding and tomasulo will be same. In this software, the scoreboarding is implemented based on the following design description:

Issue—decode instructions & check for structural hazards (I)

• Instructions issued in program order (for hazard checking)

• Don’t issue if structural hazard

Read operands—wait until no data hazards, then read operands (D)

• No forwarding of data in this model

Execution — operate on operands (E)

• All real dependencies (RAW hazards) resolved in this stage, since we wait for instructions to write back data

• The functional unit begins execution upon receiving operands. When the result is ready, it notifies the scoreboard that it has completed execution

Write result — finish execution (W)

• Don’t issue if instruction is output dependent on any previously issued but uncompleted instruction (no WAW hazards)

• Stall until no WAR hazards with previous instructions