Path speculating instruction scheduler

Details Path speculating instruction scheduler Path speculating instruction scheduler

1999-11-12

2004-01-06

Dam, Tuan (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S157000

Reexamination Certificate

active

06675380

ABSTRACT:

FIELD OF THE INVENTION
The present invention pertains to the field of computer architecture, and more particularly to a path speculating instruction scheduler.
BACKGROUND
A computer program, also called software, is executed by a computer system as a series of instructions. An instruction is a command to a processor in the computer system to perform a basic logical or mathematical operation such as an add, a subtract, or a load from memory. A compiler translates source language code of the software into a series of instructions, and then schedules the instructions for execution by the processor. The processor fetches and executes the instructions according to the schedule in what is called an instruction stream.
Operands are required to execute each instruction, and are available as immediate data in the instruction stream or as a result of the execution of another instruction. For example, an instruction stream comprising instructions
51
and
52
may be defined by the following operands:
instruction
51
: a=5+3
instruction
52
: b=a*9
The instruction
51
has both of its operands, the constant values 5 and 3, immediately available in the instruction stream. However, the operand a for instruction
52
is a result of the execution of instruction
51
. An instruction, such as instruction
52
, which requires the execution result of another instruction for an operand is referred to as a data dependent instruction or a data successor. An instruction, such as instruction
51
, that provides an operand for a data dependent instruction is referred to as a source instruction or a data predecessor.
Conventional computer systems have in-order execution pipelines to execute instructions. An in-order execution processor usually fetches an instruction stream from a memory and executes each instruction in the instruction stream according to a sequential program order. Accordingly, an instruction in an in-order execution processor generally begins execution after the execution of prior instructions in the program order. A delay in the execution of an earlier instruction in the program order can delay the execution of a later instruction. Such delays may have several causes. For example, the earlier instruction may need to wait for an operand to be fetched from an external data storage device. The resulting delay in the beginning of the execution of the later instruction similarly delays the beginning of execution of succeeding instructions in the program order.
Instructions can be scheduled out of order to improve the instruction execution performance of a processor. The instructions may be scheduled out of order according to the availability of resources required to execute each instruction. More particularly, later instructions in a program order that have the resources required for execution available may be scheduled for execution ahead of earlier instructions in the program order. The instruction execution performance of a processor that executes instructions scheduled out of order may be enhanced over in-order execution processors because a delay in the execution of earlier instructions in the program order typically does not delay the execution of later instructions in the program order.
There remains a need for improved methods of scheduling instructions for execution such that a processor may execute the instructions more rapidly.
SUMMARY OF THE INVENTION
According to one embodiment of the present invention instructions are placed into a control flow graph having blocks of the instructions, the control flow graph defining a number of paths of control flow through the blocks of instructions. A list of candidate instructions to be scheduled into a target block in the control flow graph for execution is built, and one of the candidate instructions is selected to be scheduled into the target block based on whether a single copy on a path property for the selected instruction in the target block will be maintained or terminated on one or more paths through the target block.
Advantages of the invention will be apparent to one skilled in the art upon an examination of the detailed description.


REFERENCES:
patent: 5619502 (1997-04-01), Kahn et al.
patent: 5724565 (1998-03-01), Dubey et al.
patent: 5842036 (1998-11-01), Hinton et al.
patent: 6032244 (2000-02-01), Moudgill
Bala et al., “Efficient Instruction Scheduling Using Finite State Automata”, IEEE, pp.: 46-56, Dec. 1995.*
Park et al., “Evaluation of Scheduling Techniques on a SPARC-Based VLIW Testbed”, IEEE, pp.: 104-113, 1997.*
Krishnamurthy, S.M., “A Brief Survey of Papers on Scheduling for Pipelined Processors”,SIGPLAN Notices, Vol. 25, A Monthly Publication of the Special Interest Group on Programming Languages, 97-106, (Jul. 1990).
Smotherman, M., et al., “Efficient DAG Construction and Heuristic Calculation for Instruction Scheduling”,Proceedings of the 24th Annual International Symposium on Microarchitecture, 93-102, (Nov. 18-20, 1991).
Bernstein, D., et al., “Code Duplication: An Assist for Global Instruction Scheduling”,Proceedings of the 24th Annual International Symposium on Microarchitecture, 103-113, (Nov. 1991).

Affiliated with

Also associated with

Rating

Path speculating instruction scheduler does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Path speculating instruction scheduler, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path speculating instruction scheduler will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3223344