A dynamic-programming technique for compacting loops

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A dynamic-programming technique for compacting loops

Full text

Pdf (1.27 MB)

Source

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

Portland, Oregon, United States

Pages: 180 - 188

Year of Publication: 1992

ISBN:0-8186-3175-9

Also published in ...

Author

Stephen R. Vegdahl

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): 0, Downloads (12 Months): 4, Citation Count: 8

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.145797 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. 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
	2	V. Allan, Private communication, September 1992.
	3	S. Davidson, D. Landskov, B.D. Shriver, and P.W. Mallett, Some Experiments in Local Microcode Compaction for Horizontal Machines. IEEE Transactions on Computers, C-30(7):460-477, July 1981.
	4	E.W. Dijkstra, A Note on Two Problems in Connection with Graphs. Numerische Mathematik, 1:269-271, 1959.
	5	Kemal Ebcioğlu, A compilation technique for software pipelining of loops with conditional jumps, Proceedings of the 20th annual workshop on Microprogramming, p.69-79, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255317]
	6	John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
	7	J.A. Fisher, Trace-Scheduling: A Technique for Global Microcode Compaction. IEEE Transactions on Computers, C-30(7):478-490, July 1981.
	8	Guang R. Gao , Yue-Bong Wong , Qi Ning, A timed Petri-net model for fine-grain loop scheduling, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.204-218, June 24-28, 1991, Toronto, Ontario, Canada
	9	Jan Hoogerbrugge , Henk Corporaal , Hans Mulder, Software pipelining for transport-triggered architectures, Proceedings of the 24th annual international symposium on Microarchitecture, p.74-81, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123479]
	10	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]
	11	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
	12	David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980 [doi>10.1145/356819.356822]
	13	T. Nakatani , K. Ebcioğlu, “Combining” as a compilation technique for VLIW architectures, Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture, p.43-55, August 14-16, 1989, Dublin, Ireland
	14	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]
	15	Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982

CITED BY 8

	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
	M. Rajagopalan , V. H. Allan, Efficient scheduling of fine grain parallelism in loops, Proceedings of the 26th annual international symposium on Microarchitecture, p.2-11, December 01-03, 1993, Austin, Texas, United States
	Christoph Kessler , Andrzej Bednarski, Optimal integrated code generation for clustered VLIW architectures, ACM SIGPLAN Notices, v.37 n.7, July 2002
	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
	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
	Markus Pister , Daniel Kästner, Generic software pipelining at the assembly level, Proceedings of the 2005 workshop on Software and compilers for embedded systems, p.50-61, September 29-October 01, 2005, Dallas, Texas
	Christoph Keßler , Andrzej Bednarski, A Dynamic Programming Approach to Optimal Integrated Code Generation, ACM SIGPLAN Notices, v.36 n.8, p.165-174, Aug. 2001
	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.1 CONTROL STRUCTURES AND MICROPROGRAMMING
B.1.4 Microprogram Design Aids
Subjects: Optimization

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

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:
Algorithms, Design, Performance

Keywords:
compaction, dynamic programming, horizontal, pipelining, scheduling

Collaborative Colleagues:

Stephen R. Vegdahl: colleagues

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

Open signaling for ATM, internet and mobile networks (OPENSIG'98) ACM SIGCOMM Computer Communication Review 29, 1
Andrew T. Campbell , Irene Katzela , Kazuho Miki , John Vicente
Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Active bridging ACM SIGCOMM Computer Communication Review 27, 4
D. Scott Alexander , Marianne Shaw , Scott M. Nettles , Jonathan M. Smith
Active electronic mail Proceedings of the 2002 ACM symposium on Applied computing
S. Karnouskos , A. Vasilakos
Object-oriented database management system for process control systems—development and evaluation Proceedings of the 1999 ACM symposium on Applied computing
Ryuji Wakizono , Toshikazu Kawamura , Takehiko Tsuchiya , Takahiro Hatanaka , Tatsuji Tanaka

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