Patent
1995-11-17
1998-09-15
Trammell, James P.
G06F 945
Patent
active
058093087
ABSTRACT:
Apparatus and methods are disclosed for determining a recurrence minimum iteration interval (rmii) vector for use in modulo scheduling target program instructions during the code optimization pass of an optimizing compiler. Most modem 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. For such microprocessors this invention can, where applicable, accelerate the process of modulo-scheduling target program loops. The invention consists of a technique to determine a rmii vector, which is a set of rmii values which correspond to different values of instruction load latency. The disclosed invention makes the determination of the entire vector with only minimal effort over determining a single rmii value.
REFERENCES:
patent: 5333284 (1994-07-01), Nugent
patent: 5367651 (1994-11-01), Smith et al.
patent: 5367687 (1994-11-01), Tarsy et al.
patent: 5491823 (1996-02-01), Ruttenberg
patent: 5537620 (1996-07-01), Breternitz, Jr.
Ramakrishnan, S., "Software pipliining in PA-RISC compilers," Hewlett-Packard Journal, v43, N3, p. 39(7), Jun. 1992.
"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 Generation 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", 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.
Basinski Erwin J.
Corcoran, III Peter J.
Sun Microsystems Inc.
Trammell James P.
LandOfFree
Method and apparatus for efficient determination of an RMII vect 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 efficient determination of an RMII vect, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficient determination of an RMII vect will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-101639