Enhanced modulo scheduling for loops with conditional branches

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Enhanced modulo scheduling for loops with conditional branches

Full text

Pdf (1.21 MB)

Source

International Symposium on Microarchitecture archive
Proceedings of the 25th annual international symposium on Microarchitecture table of contents

Portland, Oregon, United States

Pages: 170 - 179

Year of Publication: 1992

ISBN:0-8186-3175-9

Also published in ...

Authors

Nancy J. Warter
Grant E. Haab
Krishna Subramanian
John W. Bockhaus

Sponsors

IEEE-CS : Computer Society
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Computer Society Press Los Alamitos, CA, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 7, Citation Count: 31

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/144953.145796 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Charlesworth, "An approach to scientific array processing: The architectural design of the AP- 120B/FPS-164 family," in IEEE Computer, September 1981.
	2	Roy F. Touzeau, A Fortran compiler for the FPS-164 scientific computer, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.48-57, June 17-22, 1984, Montreal, Canada
	3	M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
	4	Roland L. Lee , Alex Y. Kwok , Fayé A. Briggs, The floating point performance of a superscalar SPARC processor, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.28-37, April 08-11, 1991, Santa Clara, California, United States
	5	A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
	6	K. Ebcioğlu , Toshio Nakatani, A new compilation technique for parallelizing loops with unpredictable branches on a VLIW architecture, Selected papers of the second workshop on Languages and compilers for parallel computing, p.213-229, May 1990, Urbana, Illinois, United States
	7	Bogong Su , Jian Wang, GURPR*: a new global software pipelining algorithm, Proceedings of the 24th annual international symposium on Microarchitecture, p.212-216, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123509]
	8	Janak H. Patel , Edward S. Davidson, Improving the throughput of a pipeline by insertion of delays, Proceedings of the 3rd annual symposium on Computer architecture, p.159-164, January 19-21, 1976
	9	B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
	10	Monica Sin-Ling Lam, A systolic array optimizing compiler, 1987
	11	C. Eisenbeis, Optimization of horizontal microcode generation for loop structures, Proceedings of the 2nd international conference on Supercomputing, p.453-465, June 1988, St. Malo, France [doi>10.1145/55364.55408]
	12	Reese B. Jones , Vicki H. Allan, Software pipelining: an evaluation of enhanced pipelining, Proceedings of the 24th annual international symposium on Microarchitecture, p.82-92, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123481]
	13	J. A. Fisher, "Trace scheduling: A technique for global microcode compaction," IEEE Transactions on Computers, vol. c-30, pp. 478-490, July 1981.
	14	B. Ramakrishna Rau , David W. L. Yen , Wei Yen , Ross A. Towie, The Cydra 5 Departmental Supercomputer: Design Philosophies, Decisions, and Trade-Offs, Computer, v.22 n.1, p.12-26, 28-30, 32-35, January 1989 [doi>10.1109/2.19820]
	15	James C. Dehnert , Peter Y.-T. Hsu , Joseph P. Bratt, Overlapped loop support in the Cydra 5, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.26-38, April 03-06, 1989, Boston, Massachusetts, United States
	16	Ross Albert Towle, Control and data dependence for program transformations., 1976
	17	J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
	18	F. Gasperoni, "Compilation techniques for VLIW architectures," Tech. Rep. 66741, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY 10598, August 1989.
	19	N. J. Warter and W. W. Hwu, "Enhanced modulo scheduling," Tech. Rep. CRHC-92-11, Center for Reliable and High-Performance Computing, University of Illinois, Urbana, IL, November 1992.
	20	J. C. H. Park and M. Schlansker, "On Predicated Execution," Tech. Rep. HPL-91-58, Hewlett Packard Software Systems Laboratory, May 1991.
	21	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	22	D. C. Lin, "Compiler support for predicated execution in superscalar processors," Master's thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, 1992.
	23	P. Tirumalai , M. Lee , M. Schlansker, Parallelization of loops with exits on pipelined architectures, Proceedings of the 1990 conference on Supercomputing, p.200-212, October 1990, New York, New York, United States
	24	J. W. Bockhaus, "An implementation of GURPR*: A software pipelining algorithm," Master's thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, 1992.
	25	Intel, i860 6y-Bit Microprocessor. Santa Clara, CA, 1989.
	26	N. J. Wafter, D. M. Lavery, and W. W. Hwu, "The benefit of Predicated Execution for software pipelining,' in Proceedings o.f the ~3rd Hawaii International Conference on System Sciences, to appear January 1993.
	27	B. R. Rau , M. Lee , P. P. Tirumalai , M. S. Schlansker, Register allocation for software pipelined loops, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.283-299, June 15-19, 1992, San Francisco, California, United States
	28	William Y. Chen , Roger A. Bringmann , Scott A. Mahlke , Sadun Anik , Tokuzo Kiyohara , Nancy J. Warter , Daniel M. Lavery , Wen-mei W. Hwu , Richard E. Hank , John C. Gyllenhaal, Using Profile Information to Assist Advaced Compiler Optimization and Scheduling, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.31-48, August 03-05, 1992

CITED BY 31

	Alexandre E. Eichenberger , Edward S. Davidson, A reduced multipipeline machine description that preserves scheduling constraints, ACM SIGPLAN Notices, v.31 n.5, p.12-22, May 1996
	SangMin Shim , Soo-Mook Moon, Split-path enhanced pipeline scheduling for loops with control flows, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.93-102, November 1998, Dallas, Texas, United States
	Alexandre E. Eichenberger , Edward S. Davidson , Santosh G. Abraham, Optimum modulo schedules for minimum register requirements, Proceedings of the 9th international conference on Supercomputing, p.31-40, July 03-07, 1995, Barcelona, Spain
	Alexandre E. Eichenberger , Edward S. Davidson, Stage scheduling: a technique to reduce the register requirements of a modulo schedule, Proceedings of the 28th annual international symposium on Microarchitecture, p.338-349, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	Alexandre E. Eichenberger , Edward S. Davidson , Santosh G. Abraham, Minimum register requirements for a modulo schedule, Proceedings of the 27th annual international symposium on Microarchitecture, p.75-84, November 30-December 02, 1994, San Jose, California, United States
	SangMin Shim , Soo-Mook Moon, Split-Path Enhanced Pipeline Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.14 n.5, p.447-462, May 2003
	Vicki H. Allan , U. R. Shah , K. M. Reddy, Petri net versus modulo scheduling for software pipelining, Proceedings of the 28th annual international symposium on Microarchitecture, p.105-110, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	Dragan Milicev , Zoran Jovanovic, Control Flow Regeneration for Software Pipelined Loops with Conditions, International Journal of Parallel Programming, v.30 n.3, p.149-179, June 2002
	Alexandre E. Eichenberger , Edward S. Davidson, Register allocation for predicated code, Proceedings of the 28th annual international symposium on Microarchitecture, p.180-191, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	Nancy J. Warter , Scott A. Mahlke , Wen-Mei W. Hwu , B. Ramakrishna Rau, Reverse If-Conversion, ACM SIGPLAN Notices, v.28 n.6, p.290-299, June 1993
	Eric Stotzer , Ernst Leiss, Modulo scheduling for the TMS320C6x VLIW DSP architecture, ACM SIGPLAN Notices, v.34 n.7, p.28-34, July 1999
	Steve Carr , Philip Sweany, An experimental evaluation of scalar replacement on scientific benchmarks, Software—Practice & Experience, v.33 n.15, p.1419-1445, December 2003
	Stephen Hines , David Whalley , Gary Tyson, Adapting compilation techniques to enhance the packing of instructions into registers, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea
	Jenn-Yaun Tsai , Jian Huang , Christoffer Amlo , David J. Lilja , Pen-Chung Yew, The Superthreaded Processor Architecture, IEEE Transactions on Computers, v.48 n.9, p.881-902, September 1999
	Mikhail Smelyanskiy , Scott A. Mahlke , Edward S. Davidson , Hsien-Hsin S. Lee, Predicate-aware scheduling: a technique for reducing resource constraints, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
	Daniel M. Lavery , Wen-mei W. Hwu, Modulo scheduling of loops in control-intensive non-numeric programs, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.126-137, December 02-04, 1996, Paris, France
	Josep Llosa , Stefan M. Freudenberger, Reduced code size modulo scheduling in the absence of hardware support, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
	Richard A. Huff, Lifetime-sensitive modulo scheduling, ACM SIGPLAN Notices, v.28 n.6, p.258-267, June 1993
	Nancy J. Warter-Perez , Noubar Partamian, Modulo scheduling with multiple initiation intervals, Proceedings of the 28th annual international symposium on Microarchitecture, p.111-119, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	Mark G. Stoodley , Corinna G. Lee, Software pipelining loops with conditional branches, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.262-273, December 02-04, 1996, Paris, France
	Mikhail Smelyanskiy , Scott Mahlke , Edward S. Davidson, Probabilistic Predicate-Aware Modulo Scheduling, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.151, March 20-24, 2004, Palo Alto, California
	Erik R. Altman , R. Govindarajan , Guang R. Gao, Scheduling and mapping: software pipelining in the presence of structural hazards, ACM SIGPLAN Notices, v.30 n.6, p.139-150, June 1995
	Josep Llosa , Mateo Valero , Eduard Ayguadé , Antonio González, Modulo Scheduling with Reduced Register Pressure, IEEE Transactions on Computers, v.47 n.6, p.625-638, June 1998
	Sebastian Unger , Frank Mueller, Handling irreducible loops: optimized node splitting versus DJ-graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.4, p.299-333, July 2002
	Dragan Milicev , Zoran Jovanovic, A finite state machine based format model of software pipelined loops with conditions, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
	Erik R. Altman , Guang R. Gao, Optimal Modulo Scheduling Through Enumeration, International Journal of Parallel Programming, v.26 n.3, p.313-344, June 1998
	John Ruttenberg , G. R. Gao , A. Stoutchinin , W. Lichtenstein, Software pipelining showdown: optimal vs. heuristic methods in a production compiler, ACM SIGPLAN Notices, v.31 n.5, p.1-11, May 1996
	Won So , Alexander G. Dean, Reaching fast code faster: using modeling for efficient software thread integration on a VLIW DSP, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea
	Alexander Aiken , Alexandru Nicolau , Steven Novack, Resource-Constrained Software Pipelining, IEEE Transactions on Parallel and Distributed Systems, v.6 n.12, p.1248-1270, December 1995
	Won So , Alexander G. Dean, Complementing software pipelining with software thread integration, ACM SIGPLAN Notices, v.40 n.7, July 2005
	Vicki H. Allan , Reese B. Jones , Randall M. Lee , Stephen J. Allan, Software pipelining, ACM Computing Surveys (CSUR), v.27 n.3, p.367-432, Sept. 1995

INDEX TERMS

Primary Classification:
B. Hardware
B.2 ARITHMETIC AND LOGIC STRUCTURES
B.2.1 Design Styles
Subjects: Pipeline

Additional Classification:
B. Hardware
B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
B.1.4 Microprogram Design Aids
Subjects: Languages and compilers
B.1.5 Microcode Applications
Subjects: Instruction set interpretation

D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Compilers

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sequencing and scheduling

General Terms:
Design, Languages, Performance

Collaborative Colleagues:

Nancy J. Warter: colleagues

Grant E. Haab: colleagues

Krishna Subramanian: colleagues

John W. Bockhaus: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

This Article has also been published in:

ACM SIGMICRO Newsletter
Volume 23 , Issue 1-2 Dec. 1992

Adobe Acrobat

QuickTime

Windows Media Player

Real Player