×

Method and apparatus for cost-based heuristic instruction scheduling

  • US 5,202,993 A
  • Filed: 02/27/1991
  • Issued: 04/13/1993
  • Est. Priority Date: 02/27/1991
  • Status: Expired due to Term
First Claim
Patent Images

1. A method for cost-based heuristic instruction scheduling instructions for execution in a pipelined processor, said instructions comprising definitions, resources for use in said pipeline processor, or definitions and resources for use in said pipelined processor, said method comprising the steps of:

  • building an instruction dependency graph data structure for an instruction block, said instruction block comprising a plurality of instructions to be scheduled and said dependency graph data structure comprising said plurality of instructions arranged in a serial relationship such that a higher level instruction will precede a lower level instruction when definitions or use of a resource of said higher level instruction are necessary for said pipelined processor to execute said lower level instruction;

    accessing free instructions in said instruction dependency graph data structure, said free instructions comprising instructions that do not have a higher preceding instruction;

    building a free instruction list data structure comprising said free instructions;

    providing a plurality of component modeling means for determining a plurality of cost heuristics for said pipelined processor;

    simulating clock cycles and instruction execution in said pipelined processor for each of said free instructions so as to determine a plurality of cost heuristics by accessing said component modeling means for said plurality of cost heuristics;

    computing a total cost for each free instruction by summing said plurality of cost heuristics;

    building a cost table data structure comprising said total cost for each free instruction; and

    scheduling for execution in said pipelined processor one of said free instructions based on a lowest total cost in said cost table data structure wherein execution time pipeline interlocks in said pipelined processor are reduced thereby improving execution speed in said pipelined processor for said plurality of instructions in said instruction block.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×