Time chart for different scheduling algorithms

For Programmers

The software provides two .jar files to do further programming for static scheduling (with forwarding and without forwarding) and dynamic scheduling (Tomasulo and Scoreboarding).

• scheduling.jar: Contains implementation of static scheduling with and without forwarding and dynamic scheduling (Tomasulo and Scoreboarding).
• baieley.jar: Contains implementation of java graph library (From Duane A. Bailey, Williams College).

Some of the important classes used for implementation which are visible to programmers are:

• "Instruction": Attributes of each instruction (type, destination, source1, source2).
• "Stages": Time of start for each pipeline phase (Issue, Decode, ExecStart, ExecEnd, Write) for each instruction
• "FunctionalUnit": Number of functional units for each function (load/store, add/sub, multiply, and divide)
• "PipelineUnit": Whether different functional units (load/store, add/sub, multiply, and divide) are pipelined or not
• "InstructionNode": Contains a "instruction" structure and corresponding "stages" structure.

Getters and setters are defined corresponding to each of these primary classes to access the private fields. Source code is available for these classes and various fields and functions are self-explanatory.

Four main classes which implements the different scheduling algorithms are:

• WithForwardingInstructionGraph: Implements static scheduling with forwarding.
• WithoutForwardingInstructionGraph: Implements static scheduling without forwarding.
• TomasuloInstructionGraph: Implements dynamic scheduling algorithm - Tomasulo
• ScoreboardingInstructionGraph:  Implements dynamic scheduling algorithm - Scoreboarding.

All these four main classes implements following two functions which are visible to programmers are:

• GenerateDataHazardGraph: Construct a dependency graph with nodes as a instruction and a directed edge between two nodes showing data and structural hazards between two instructions.
• TopologicalTraversal: Performs a topological traversal of the generated dependency graph showing data and structural hazards and calculated the time cycle for each phase of the pipeline execution.

Output is stored in 2-D string array called "timechart" which is defined in all the four main classes implementing various scheduling algorithms.

Sample code for implementing "static scheduling with forwarding"

WithForwardingInstructionGraph withforwardingInstrGraph = new WithForwardingInstructionGraph (int number_of_instruction, PipelineUnit p, FunctionalUnit f);

for(int i=0; i<number_of_instruction; i++) {

Instruction tempInstr = new Instruction (String type, String destination, String source1, String source2, int execution_cycle);

InstructionNode tempNode = new InstructionNode(tempInstr, i);

withforwardingInstrGraph.addInstr(tempNode);

Sample code for implementing "static scheduling without forwarding"

WithoutForwardingInstructionGraph withoutforwardingInstrGraph = new WithoutForwardingInstructionGraph (int number_of_instruction, PipelineUnit p, FunctionalUnit f);

for(int i=0; i<number_of_instruction; i++) {

Instruction tempInstr = new Instruction (String type, String destination, String source1, String source2, int execution_cycle);

InstructionNode tempNode = new InstructionNode(tempInstr, i);

withoutforwardingInstrGraph.addInstr(tempNode);

Sample code for implementing "dynamic scheduling - Tomasulo"

TomasuloInstructionGraph tomasuloInstrGraph = new TomasuloInstructionGraph (int number_of_instruction, PipelineUnit p, FunctionalUnit f, FunctionalUnit reservation_stations);

for(int i=0; i<number_of_instruction; i++) {

Instruction tempInstr = new Instruction (String type, String destination, String source1, String source2, int execution_cycle);

InstructionNode tempNode = new InstructionNode(tempInstr, i);

tomasuloInstrGraph.addInstr(tempNode);

Sample code for implementing "dynamic scheduling - Scoreboarding"

ScoreboardingInstructionGraph withoutforwardingInstrGraph = new ScoreboardingInstructionGraph (int number_of_instruction, PipelineUnit p, FunctionalUnit f);

for(int i=0; i<number_of_instruction; i++) {

Instruction tempInstr = new Instruction (String type, String destination, String source1, String source2, int execution_cycle);

InstructionNode tempNode = new InstructionNode(tempInstr, i);

scoreboardingInstrGraph.addInstr(tempNode);