Lifetime-sensitive instruction scheduling mechanism and method

Details Lifetime-sensitive instruction scheduling mechanism and method Lifetime-sensitive instruction scheduling mechanism and method

1998-06-18

2001-10-16

Elmore, Reba I. (Department: 2187)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C717S152000

Reexamination Certificate

active

06305014

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
This invention generally relates to the optimization of computer programs, and more specifically relates to a computer mechanism and method for determining the scheduling of instructions in a computer program.
2. Background Art
The development of the EDVAC computer system in 1948 is generally considered the beginning of the computer era. Since that time, dramatic advances in both hardware and software (e.g., computer programs) have drastically improved the performance of computer systems. Modern software has become very complex when compared to early computer programs. Many modern computer programs have tens or hundreds of thousands of instructions. The execution time (and hence, performance) of a computer program is very closely related to the number of instructions that are executed as the computer program runs. Thus, as the size and complexity of computer programs increase, the execution time of the computer program increases as well.
Unlike early computer programs, modern computer programs are typically written in a high-level language that is easy to understand by a human programmer. Special software tools known as compilers take the human-readable form of a computer program, known as “source code”, and convert it into “machine code” or “object code” instructions that may be executed by a computer system. Because a compiler generates the stream of machine code instructions that are eventually executed on a computer system, the manner in which the compiler converts the source code to object code affects the execution time of the computer program.
Computer hardware has evolved to provide faster execution of computer programs. For example, most modern processors include multiple instruction pipelines that can process two instructions in parallel if the two instructions are not dependent on each other. In an environment with multiple pipelines, the execution time of a computer program, especially complex computer programs, is a function of the arrangement of the instructions within the computer program. Modern compilers typically include an instruction scheduling mechanism that determines the dependences among instructions and produces a schedule or ordering of instructions in an attempt to maximize the parallelism in the computer program by scheduling, when possible, instructions to be executed simultaneously by different pipelines. However, known compilers do not take advantage of some parallelism that may exist in the computer program. Without an improved instruction scheduling mechanism and method, pipelines in a computer system will not be used to their maximum potential, and performance of computer systems will therefore suffer.
DISCLOSURE OF INVENTION
According to the present invention, an instruction scheduler in an optimizing compiler schedules instructions in a computer program by determining the lifetimes of fixed registers in the computer program. By determining the lifetimes of fixed registers, the instruction scheduler can achieve a schedule that has a higher degree of parallelism by relaxing dependences between instructions in independent lifetimes of a fixed register so that instructions can be scheduled earlier than would otherwise be possible if those dependences were precisely honored.
The foregoing and other features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings.


REFERENCES:
patent: 5386562 (1995-01-01), Jain et al.
patent: 5761514 (1998-06-01), Aizikowitz et al.
patent: 5812854 (1998-09-01), Steinmetz et al.
patent: 5828886 (1998-10-01), Hayashi
patent: 5930510 (1999-07-01), Beyun et al.
patent: 6009272 (1999-12-01), Goebel
Mantripragada et al, ‘A New Framework for Integrated Global Local Scheduling’: IEEE pp. 167-174, Mar. 1998.*
Mangione-Smith et al, ‘Register Requirements of Pipelined Processors’, ACM pp. 260-271, Jun. 1992.*
Silvera et al, ‘A Register Pressure Sensitive Instruction Scheduler for Dynamic Issue Processors’, IEEE pp. 78-89, Mar. 1997.*
Eichenberger et al, ‘Register Allocation for Predicated Code’, IEEE, Micro-28 pp. 180-191, 1995.*
Gillies et al., ‘Global Predicate Analysis and its Application to Register Allocation’, IEEE pp. 114-125, 1996.*
Chou et al., ‘An Optimal Instruction Scheduler for Superscalor Processor’, IEEE pp. 303-313, 1995.*
Chang et al., ‘Efficient Exploitation of Instruction-Level Parallelism for Superscaler Processors by the Conjugate Register File Scheme’, IEEE pp. 278-293, 1996.*
Ramakrishna et al., ‘Storage Allocation Strategies for Data Path Synthesis of ASICs’, IEEE pp. 41-44, 1994.*
Koseki et al, ‘A Register Allocation Technique Using Guarded PDG’, ACM pp. 270-277, 1996.*
Lu et al., ‘A Lifetime-Sensitive Scheduling Method’IEEE pp. 351-354, May 1996.*
Franklin et al., ‘Register Traffic Analysis for Streamlining Inter-Operation Communication in Fine-Grain Parallel Processors’, IEEE pp. 236-245, Sep. 1992.*
Norris et al. An Experimental Study of Several Cooperative Register Allocation and Instructions Scheduling Strategies. IEEE. pp. 169-179, 1995.*
Koseki et al. A Register Allocation Technique Using Guarded PDG. ACM. pp. 270-277, 1996.

Affiliated with

Also associated with

Rating

Lifetime-sensitive instruction scheduling mechanism and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Lifetime-sensitive instruction scheduling mechanism and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lifetime-sensitive instruction scheduling mechanism and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2570984