This tool has been developed to compute and explain how Dynamic Scheduling is obtained using the Scoreboarding
Algorithm for a given set of instructions entered by the user.
Click the following link to view a snapshot of the Interface for the Scoreboarding Algorithm tool developed.
ELEMENTS OF THE TOOL
The interface to the tool has the following elements:
- HELP link: This link redirects the user to this Help page giving a general description about how to use this tool and how the algorithm works.
- Number of Instructions: A text box to enter the number of instructions to be processed. The number should be between 1-10.
- Space to Enter the Instructions to be processed. Drop down boxes have been provided to select the required instruction. Each drop down box is followed by three text boxes to enter the information relevant to each instruction selected.
The user should enter register names beginning with a 'F' or 'f' and the register numbers between 0-31.The user should enter only that many number of complete instructions as entered by him/her in the element number 2 (Number of Instructions).The tool flashes an error message in conditions where the user does not meet the above requirements.
- Space to Enter the number of Execution Cycles taken by each functional unit. This values should be greater than zero or retained as the default values.
- Three Radio buttons have been provided for the user to select the type of result required.
- End Output: gives the final output tables when the set of instructions have been completely processed.
- Step by Step Output: depicts the outputs for all those clock cycles where an instruction is completed or enters a new phase (Issue/Read Operation/Execution/Write Result).
- Clock Cycle: where the user enters the clock cycle number for which the output is required.
- Submit button to get the output when the instrucions have been entered and the type of output required is selected. In case of Step by Step Output selection, this button acts a Next button giving the outputs for subsequent clock cycles.
- Reset button that resets the interface for new instructions to be entered and the output frame is reloaded with the home page.
THEOROTICAL CONCEPTS ABOUT DYNAMIC SCHEDULING
A simple statically scheduled pipeline fetches an instruction and issues it, unless there was a data dependence between an instruction already in the pipeline and the fetched instruction that cannot be hidden with bypassing or forwarding. If there is a data dependence that cannot be hidden, then the hazard detection hardware stalls the pipeline (starting with the instruction that uses the result). No new instructions are fetched or issued until the dependence is cleared.
The major limitation of the simple pipelining techniques is that they all use In-Order Instruction Issue and Execution. If say instruction j depends on a long running instruction i, currently in execution in the pipeline, then all instructions after j must be stalled until i is finished and j can execute.
Dynamic Scheduling: is the technique in which the hardware rearranges the instruction execution to reduce the stalls while maintaining data flow and exception behaviour. The Issue process is separated into two parts: checking for any structural hazards and waiting for the absence of a data hazard. We can check for structural hazard when we issue the instruction; thus, we still use In-Order Instruction Issue, but we want an instruction to begin execution as soon as its data operand is available. Thus, this pipeline does Out-Of-Order Execution, which implies Out-Of-Order Completion.
DYNAMIC SCHEDULING WITH A SCOREBOARD
In scoreboarding, all instructions pass through the Issue stage In-Order (in-order issue); however, they can be stalled or bypass each other in the second stage (read operands) and thus enter Execution Out-Of-Order. Scoreboarding is a technique for allowing instructions to execute out-of-order when there are sufficient resources and no data dependences.
Every instruction goes through the scoreboard, where a record of the data dependences is constructed. The scoreboard then determines when the instruction can read its operand and begin execution. If the scoreboard decides the insruction cannot execute immediately, it monitors every change in the hardware and decides when the instruction can execute. The scoreboard also controls when an instruction can write its result into the destination register. Thus, all hazard detection and resolution is centralized in the scoreboard.
Each instruction undergoes four steps in executing:
- Issue-- If a functional unit for the instruction is free and no other active instruction has the same destination register, the scoreboard issue the instruction to the functional unit and updates its internal data structure. By ensuring that no other active functional unit wants to write its result into the destination register, we guarantee that WAW hazards cannot be present. If a structural or WAW hazard exists, then the instruction issue stalls, and no further instructions will issue until these hazards are cleared.
- Read Operands-- The scoreboard monitors the availability of the source operands. A source operand is available if no earlier issued active instruction is going to write it. When the source operands are available, the scoreboard tells the functional unit to proceed to read operands from the registers and begin execution. The scoreboard resolves RAW hazards dynamically in this tep, and instructions may be sent into execution out of order.
- Execution-- The functional unit begins execution upon receiving operands. When the result is ready, it notifies the scoreboard that it has completed execution.
- Write Result-- Once the Scoreboard is aware that the functional unit has completed execution, the scoreboard checks fro WAR hazards and stalls the completing instruction, if necessary.