Method for optimizing instruction scheduling for a processor having multiple functional resources

• US 5,202,975 A
• Filed: 06/10/1992
• Issued: 04/13/1993
• Est. Priority Date: 06/11/1990
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Supercomputer Systems Limited Partnership
• Inventors: Rasbold, James C., Van Dyke, Don A.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US07/896,895
• Time in Patent Office: 307 Days
• Field of Search: 395/375, 395/500, 395/700, 395/800
• US Class Current: 717/151
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

A method for scheduling instructions for a processor having multiple functional resources wherein the reordering of the instructions is accomplished in response to a simulation of the run-time environment of the target machine. The simulation of the run-time environment of the target machine is performed at compile time after the machine instructions have been generated by a compiler, or after instruction generation by an assembler. The present invention rearranges the machine instructions for a basic block of instructions into an order that will result in the fastest execution based upon the results of the simulation of the interaction of the multiple functional resources in the target machine.

Claims

1. In a computer that compiles or assembles a source code program to produce object code instructions, an improved method of scheduling instructions in a basic instruction block for execution, the method comprising the steps of:

identifying a leader set of instructions as being those instructions without resource dependencies from other instructions within the basic instruction block;

identifying a read set as those instructions in the leader set that would execute without interlock interruption if issued immediately based upon a simulation of the execution of those instructions in the leader set for all combinations of the available functional units in the target computer; and

issuing the instruction in the ready set with the highest cumulative pendency cost, wherein the cumulative pendency cost represents the cost of not issuing the instruction in terms of how many other instruction depend upon this instruction issuing.

2. In a computer that compiles or assembles a source code program to produces object code instructions, an improved method of scheduling instructions in a basic instruction block for execution, the method comprising the steps of:

identifying a leader set of instructions as being those instructions without resource dependencies from other instructions within the basic instruction block;

simulating a completion time for each instruction in the basic block, wherein the completion time for each instruction is based upon immediate issue of the instruction;

determining a desired issue time for each instruction in the leader set, wherein the desired issue time is the latest point in time at which the instruction can be issued and still complete by the completion time;

identifying a ready set of instructions as being those instructions in the leader set whose desired issue time is immediately or earlier; and

issuing the instruction in the ready set with the highest cumulative pendency cost, wherein the cumulative pendency cost represents the cost of not issuing the instruction in terms of how many other instruction depend upon this instruction issuing.

3. In a computer that compiles or assembles a source code program to produces object code instructions, as part of a method for scheduling a ready set of instructions comprising the steps of:

identifying a leader set of instructions as being those instructions without resource dependencies from other instructions within the basic instruction block;

predicting instruction completion time for each instruction in the leader set based upon a simulation of the execution of each instruction in the leader set for all combinations of the available functional units in the target computer;

determining a desired issue time for each instruction in the leader set, wherein the desired issue time is the latest point in time at which the instruction can be issued and still complete by the predicted completion time; and

identifying a ready set of instructions as being those instructions in the leader set whose desired issue time is immediately or earlier.