Patent
1995-11-17
1999-02-02
Kriess, Kevin A.
G06F 944
Patent
active
058677119
ABSTRACT:
Apparatus and methods are disclosed for performing time-reversed scheduling of a data dependency graph representing a target program instruction loop in an optimizing compiler. The instruction scheduling function is the modulo scheduling function of an optimizing compiler and it is noted that the time-reverse transforms preserve all modulo constraints. Most modern microprocessors have the ability to issue multiple instructions in one clock cycle and/or possess multiple pipelined functional units and typically contain multi-level memory devices such as on-chip cache, off-chip cache as well as main memory. For such microprocessors this invention can, where applicable, accelerate the process of modulo-scheduling loops in the target program code. The invention consists of a technique to transform the data dependency graph of the target program instruction loop in order to produce an improved schedule of the loop instructions.
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 Dependance", 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.
Baylin Boris
Subramanian Krishna
Basinski Erwin J.
Kriess Kevin A.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for time-reversed instruction scheduling wi 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 time-reversed instruction scheduling wi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for time-reversed instruction scheduling wi will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1126293