ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
A dynamic-programming technique for compacting loops
Full text PdfPdf (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): 4,   Downloads (12 Months): 12,   Citation Count: 8
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Review this Article  
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
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
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
Christoph Kessler , Andrzej Bednarski, Optimal integrated code generation for clustered VLIW architectures, ACM SIGPLAN Notices, v.37 n.7, July 2002
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
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
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

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
This Article has also been published in:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player