Method and apparatus for instruction scheduling in an optimizing

Details Method and apparatus for instruction scheduling in an optimizing Method and apparatus for instruction scheduling in an optimizing

1995-11-17

1998-11-10

Kriess, Kevin A.

G06F 944

Patent

active

058357769

ABSTRACT:
Apparatus and methods are disclosed for scheduling target program instructions during the code optimization pass of an optimizing compiler. Most modern microprocessors have the ability to issue multiple instructions in one clock cycle and/or possess multiple pipelined functional units. They also have the ability to add two values to form the address within memory load and store instructions. In such microprocessors this invention can, where applicable, accelerate the execution of modulo-scheduled loops. The invention consists of a technique to achieve this speed up by systematically reducing the number of certain overhead instructions in modulo scheduled loops. The technique involves identifying reducible overhead instructions, scheduling the balance of the instructions with normal modulo scheduling procedures and then judiciously inserting no more than three copies of the reducible instructions into the schedule.

REFERENCES:
patent: 5265253 (1993-11-01), Yamada
patent: 5339238 (1994-08-01), Benson
patent: 5367651 (1994-11-01), Smith et al.
patent: 5386562 (1995-01-01), Jain et al.
patent: 5418958 (1995-05-01), Goebel
patent: 5418959 (1995-05-01), Smith et al.
patent: 5448737 (1995-09-01), Burke et al.
patent: 5485616 (1996-01-01), Burke et al.
patent: 5491823 (1996-02-01), Ruttenberg
patent: 5606698 (1997-02-01), Powell
"Register Allocation for Modulo Scheduled Loops: Strategies, Algorithms and Heuristics", by B.R. Rau, M. Lee, P.P. Tirumalai, M.S. Schlansker, Computer Systems Laboratory, HPL-92-48, Apr. 1992, pp. 1-34.
"Parallelizations of WHILE Loops on Pipelined Architectures", by Parthasarathy P. Tirumalai, Meng Lee, and Michael S. Schlansker, Hewlett-Packard Laboratories, The Journal of Supercomputing, 5. (1991), pp. 119-136.
"Code Genreation Schema for Modulo Scheduled Loops", B. Ramakrishna Rau, Michael S. Schlansker, P.P. Tirumalai, Hewlett-Packard Laboratories, 1992, pp. 158-169.
"UltraSparc Unleashes SPARC Performance", Next-Generation Design Could Put Sun Back in Race, by Linley Gwennap, Microprocessor Report, The Insiders Guide to Microprocessor Hardware, Oct. 3, 1994, vol. 8, No. 13, pp. 5-9.
"Partners in Platform Design", To create a successful new high-performance processor, the chip architects and compiler designers must collaborate from the project's very start, Focus Report, by Marc Tremblay and Partha Tirumalai, Sun Microsystems, Inc. IEEE Spectrum, Apr. 1995, pp. 20-26.
"Overlapped Loop Support in the Cydra5", by James C. Dehnert, Apogee Software, Inc., Peter Y.T. Hsu, Sun Microsystems, Inc., and Joseph P. Bratt, Ardent Computer, pp. 26-38, 1989, ACM.
"Parallelization of Loops With Exits On Pipelined Architectures", by P.Tirumalai, M. Lee, M.S. Schlansker, Hewlett-Packard Laboratories, 1990, pp. 200-212.
"The Cydra5 Departmental Supercomputer", Design Philosophies, Decisions, and Trade-offs, by B. Ramakrishna Rau, David W. L. Yen, Wei Yen, and Ross A. Towle, Cydrome, Inc., Computer, Jan. 1989, pp. 12-35.
"Sentinel Scheduling for VLIW and Superscalar Processors", by Scott A. Mahike, William Y. Chen, Wen-mei W. Hwu, B. Ramakrishna Rau, and Michael S. Schlansker, Hewlett-Packard Laboratories, Center for Reliable and High-Performance Computing, Universityof Ill., 1992, pp. 238-247.
"Conversion of Control Dependence to Data Dependence", by J.R. Allen, Ken Kennedy, Carrie Porterfield & Joe Warren, Depart. of Mathematical Sciences, Rice University, IBM Corporation, 1983, pp. 177-189.
"Register Allocation for Software Pipelined Loops", by B. R. Rau, M. Lee, P.P. Tirumalai, & M.S. Schlansker, Hewlett-Packard Laboratories, SIGPLAN 1992, pp. 283-299.
"Some Scheduling Techniques and An Easily Schedulable Horizontal Architecture for High Performance Scientific Computing", by B.R. Rau, and C.D. Glaeser, Advanced Processor Technology Group, ESL, Inc., Oct. 1981, pp. 183-198.
"Software Pipelining: An Effective Scheduling Technique for VLIW Machine", by Monica Lam, Depart. of Computer Science, Carnegie Mellon University, Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, Jun. 22-24, 1988, pp. 318-328.
"Counterflow Pipeline Processor Architecture", Robert F. Sproull, Ivan E. Sutherland, and Charles E. Molnar, Sun Microsystems Laboratories, Inc., Apr. 1994, pp. 1-21.
"Compiler Design In C", by Allen I. Holub, Prentice Hall Software Series, 1990, pp. 673-679.

Affiliated with

Also associated with

Rating

Method and apparatus for instruction scheduling in an optimizing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for instruction scheduling in an optimizing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for instruction scheduling in an optimizing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1527495