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

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Tarsy, Gregory, Woodard, Michael J.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): KATBAB, ABDOLLAH
• Application Number:
  US07/661,674
• Time in Patent Office: 776 Days
• Field of Search: 395/700, 395/600
• US Class Current: 717/152
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

A method and apparatus for cost based heuristic instruction scheduling for a pipelined processor is disclosed which has particular application to compile time instruction scheduling after code generation. The method and apparatus schedules instructions of an instruction block one at a time, based on the lowest total cost among all the current eligible free instructions. The total cost of each of the current eligible free instructions is computed based on the weighted sum of a plurality of cost heuristics. The cost heuristics used in the preferred embodiment comprise a resource dependency cost, a data dependency cost, a dependency wait cost, a dependent cycle cost, a floating point ratio cost, a store ratio cost and a floating point queue cost. Additionally, in the preferred embodiment, a number of the cost heuristics are modeled by a processor model. As a result, improved overall effectiveness in speeding up the execution time of an instruction block is achieved.

Claims

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.

2. The method for cost-based heuristic instruction scheduling for execution in a pipelined processor as set forth in claim 1, wherein said method further comprises the steps of:

refreshing said free instruction list data structure for the remaining instructions based on said instruction dependency graph data structure, excluding said scheduled instruction and including said instructions that become free due to said scheduled instruction;

updating said component modeling means after scheduling each of said free instructions;

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;

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

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

scheduling another one of said refreshed list of free instructions for execution said pipeline processor based on a lowest total cost in said refreshed cost table data structure.

3. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 2, wherein said steps of refreshing said free instruction list, updating said component modeling means and scheduling another one of said refreshed list of free instructions are repeated until said instructions of said instruction block are all scheduled.

4. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of cost heuristics comprise a resource dependency cost, said resource dependency cost equaling the number of hold cycles due to resource dependencies caused by scheduling said free instruction.

5. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of cost heuristics comprise a data dependency cost, said data dependency cost equaling the number of data interlocks due to data dependencies caused by scheduling said free instruction.

6. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of cost heuristics comprise a dependency wait cost, said dependency wait cost equaling the number of extra wait cycles for resources caused by scheduling said free instruction.

7. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of cost heuristics comprise a dependent cycle cost (DCC), said dependent cycle cost (DCC) equaling-DC/max(1, RC-DC), where

DC equals the number of dependent cycles on said free instruction,

RC equals the number of cycles required for the remaining instructions of said instruction block.

8. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of cost heuristics comprise a floating point ratio cost (FPRC), said floating point ratio cost (FPRC) equaling (RFPC/RNFPC)-FPTR, where

RFPC equals the number of floating point cycles required for the remaining instructions of said instruction block after scheduling said free instruction,

RNFPC equals the number of non-floating point cycles required for the remaining instructions of said instruction block after scheduling said free instruction,

FPTR equals a floating point target ratio of floating point cycles required to non-floating point cycles required for said instruction block.

9. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 8, wherein said floating point target ratio (FPTR) is adjustable, said floating point target ratio (FPTR) being adjusted after each of said scheduling of said free instructions.

10. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of cost heuristics comprise a store ratio cost (SRC), said store ratio cost (SRC) equaling (RSIC/RNSIC)-SITR, where

RSIC equals the number of store instruction cycles required for the remaining instructions of said instruction block after scheduling said free instruction,

RNSIC equals the number of non-store instruction cycles required for the remaining instructions of said instruction block after scheduling said free instruction,

SITR equals a store instruction target ratio of store instruction cycles required to non-store instruction cycles required for said instruction block.

11. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 10, wherein said store instruction target ratio (SITR) is adjustable, said store instruction target ratio (SITR) being adjusted after each of said scheduling of said free instructions.

12. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of cost heuristics comprise a floating point queue cost (FPQC), said floating point queue cost (FPQC) equaling zero for said free instruction that is a non-floating point instruction, and equaling FSIU-AFQS for said free instruction that is a floating point instruction, where

FSIU equals the number of floating point operations currently being held in the floating point queue, and

AFQS is the initial number of slots available on the floating point queue for holding floating point operations.

13. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of component modeling means comprise a resource model and at least one resource table,

said resource tables being initialized for said instruction block, and updated after each of said scheduling of said free instructions.

14. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of component modeling means comprise a data dependency model and at least one data dependency table,

said data dependency tables being initialized for said instruction block, and updated after each of said scheduling of said free instructions.

15. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of component modeling means comprise a floating point unit model and at least one simulated floating point unit queue,

said simulated floating point unit queues being initialized for said instruction block, and updated after each of said scheduling of said free instructions.

16. The method for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 3, wherein said plurality of component modeling means comprise a store buffer model and at least one simulated store buffer,

said simulated store buffers being initialized for said instruction block, and updated after each of said scheduling of said free instructions.

17. The method for cost-based heuristic instruction scheduling for execution in a pipelined processor as set forth in claim 3, wherein said plurality of cost heuristics are weighted by multiplying in said pipeline processor an assigned weight to each individual cost heuristic so as to reflect the relative importance of each individual cost heuristic.

18. An apparatus for scheduling cost-based heuristic 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 apparatus comprising:

a driver means for driving said cost-based heuristic instruction scheduling for an instruction block comprising a plurality of instructions to be scheduled, said driver means comprising an interface for receiving said instruction block;

a dependency graph building means coupled to said driver means for building an instruction dependency graph data structure for said instruction block, said instruction 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;

a list building means coupled to said driver means for building a free instruction list data structure for said instructions, said free instructions comprising said instructions in said dependency graph data structure which do not have a higher level preceding instruction; and

processor modeling means for modeling said plurality of cost heuristics, said processor modeling means comprising a time passage simulation means and a plurality of component modeling means, said time passage simulation means simulates clock cycles and instruction execution in said pipelined processor for said free instruction based on said component modeling means for said free instruction to ascertain a plurality of cost heuristics, said processor modeling means being initialized for said instruction block;

a scheduling means coupled to said driver means and said processor modeling means for scheduling one of said free instructions, said scheduling means computing a total cost for each free instruction by summing said plurality of cost heuristics and scheduling for execution in said pipelined processor one of said free instructions based on a lowest total cost 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.

19. The apparatus for cost-based heuristic instruction scheduling for execution in a pipelined processor as set forth in claim 18, wherein

said list building means further comprises a list building refreshing means, said refreshing means being invoked by said driver means for refreshing said free instruction list data structure for the remaining instructions based on said instruction dependency graph data structure after said scheduling means scheduled said free instruction, said list building means excludes said scheduled instruction and includes said instructions that become free due to said scheduled instruction;

processor modeling means further comprises updating means for updating said component modeling means after scheduling each of said free instructions and component modeling refreshing means for 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; and

said scheduling means further comprises a scheduling refreshing means, said scheduling refreshing means being invoked by said driver means again for scheduling another one of said refreshed list of free instructions by computing a total cost for each free instruction by summing said plurality of cost heuristics determined from said processor modeling means.

20. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 19, wherein said list building means, processor modeling means and said scheduling means further comprises a repeating means, said repeating means being invoked by said driver means for repeating said refreshing and said scheduling until said instructions of said instruction block are all scheduled.

21. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of cost heuristics comprise a resource dependency cost, said resource dependency cost equaling the number of hold cycles due to resource dependencies caused by scheduling said free instruction.

22. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of cost heuristics comprise a data dependency cost, said data dependency cost equaling the number of data interlocks due to data dependencies caused by scheduling said free instruction.

23. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of cost heuristics comprise a dependency wait cost, said dependency wait cost equaling the number of extra wait cycles for resources caused by scheduling said free instruction.

24. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of cost heuristics comprise a dependent cycle cost (DCC), said dependent cycle cost (DCC) equaling-DC/max(1, RC-DC), where

DC equals the number of dependent cycles on said free instruction,

RC equals the number of cycles required for the remaining instructions of said instruction block.

25. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of cost heuristics comprise a floating point ratio cost (FPRC), said floating point ratio cost (FPRC) equaling (RFPC/RNFPC)-FPTR, where

RFPC equals the number of floating point cycles required for the remaining instructions of said instruction block after scheduling said free instruction.

RNFPC equals the number of non-floating point cycles required for the remaining instructions of said instruction block after scheduling said free instruction,

FPTR equals a floating point target ratio of floating point cycles required to non-floating point cycles required for said instruction block.

26. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 25, wherein said floating point target ratio (FPTR) is adjustable, said floating point target ratio (FPTR) being adjusted after each of said scheduling of said free instructions.

27. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of cost heuristics comprise a store ratio cost (SRC), said store ratio cost (SRC) equaling (RSIC/RNSIC)-SITR, where

RSIC equals the number of store instruction cycles required for the remaining instructions of said instruction block after scheduling said free instruction,

RNSIC equals the number of non-store instruction cycles required for the remaining instructions of said instruction block after scheduling said free instruction,

SITR equals a store instruction target ratio of store instruction cycles required to non-store instruction cycles required for said instruction block.

28. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 27, wherein said store instruction target ratio (SITR) further comprises store instruction target ratio adjustable means, said store instruction target ratio (SITR) adjustable means being adjusted after each of said scheduling of said free instructions.

29. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of cost heuristics comprise a floating point queue cost (FPQC), said floating point queue cost (FPQC) equaling zero for said free instruction that is a non-floating point instruction, and equaling FSIU-AFQS for said free instruction that is a floating point instruction, where

FSIU equals the number of floating point operations currently being held in the floating point queue, and

AFQS is the initial number of slots available on the floating point queue for holding floating point operations.

30. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of component modeling means comprise a resource model and at least one resource table,

said resource tables being initialized for said instruction block, and updated after each of said scheduling of said free instructions.

31. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of component modeling means comprise a data dependency model and at least one data dependency table,

said data dependency tables being initialized for said instruction block, and updated after each of said scheduling of said free instructions.

32. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of component modeling means comprise a floating point unit model and at least one simulated floating point unit queue,

said simulated floating point unit queues being initialized for said instruction block, and updated after each of said scheduling of said free instructions.

33. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said plurality of component modeling means comprises a store buffer model and at least one simulated store buffer,

said simulated store buffers being initialized for said instruction block, and updated after each of said scheduling of said free instructions.

34. The apparatus for cost-based heuristic instruction scheduling for a pipelined processor as set forth in claim 20, wherein said scheduling means further comprises a weighting means, said weighting means weights said plurality of cost heuristics by multiplying an assigned weight to each individual cost heuristic so as to reflect the relative importance of each individual cost heuristic.