Efficient DAG construction and heuristic calculation for instruction scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient DAG construction and heuristic calculation for instruction scheduling

Full text

Pdf (992 KB)

Source

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

Albuquerque, New Mexico, Puerto Rico

Pages: 93 - 102

Year of Publication: 1991

ISBN:0-89791-460-0

Authors

Mark Smotherman	Department of Computer Science, Clemson University, Clemson, SC
Sanjay Krishnamurthy	Department of Computer Science, Rice University, Houston, TX
P. S. Aravind	Department of Computer Science, Clemson University, Clemson, SC
David Hunnicutt	Department of Computer Science, Clemson University, Clemson, SC

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 22, Citation Count: 5

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/123465.123482 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	David Bernstein , Michael Rodeh, Global instruction scheduling for superscalar machines, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.241-255, June 24-28, 1991, Toronto, Ontario, Canada
	2	David G. Bradlee , Susan J. Eggers , Robert R. Henry, Integrating register allocation and instruction scheduling for RISCs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.122-131, April 08-11, 1991, Santa Clara, California, United States
	3	Philip B. Gibbons , Steven S. Muchnick, Efficient instruction scheduling for a pipelined architecture, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.11-16, June 25-27, 1986, Palo Alto, California, United States
	4	D.N. Glass, "Compile-time instruction scheduling for superscalar processors," Proc. COMPCON Spring 90, San Francisco, CA, 1990, pp. 630-633.
	5	J. R. Goodman , W.-C. Hsu, Code scheduling and register allocation in large basic blocks, Proceedings of the 2nd international conference on Supercomputing, p.442-452, June 1988, St. Malo, France [doi>10.1145/55364.55407]
	6	John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
	7	D. Hunnicutt, "DDG construction algorithms," M.S. paper, Dept. of Computer Science, Clemson University, May 1991.
	8	S. Krishnamurthy, "Static scheduling of multi-cycle operations for a pipelined RiSC processor," M.S. paper, Dept. of Computer Science, Clemson University, May 1990.
	9	Sanjay M. Krishamurthy, A brief survey of papers on scheduling for pipelined processors, ACM SIGPLAN Notices, v.25 n.7, p.97-106, July 1990 [doi>10.1145/382076.382650]
	10	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]
	11	James W. Rymarczyk, Coding guidelines for pipelined processors, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.12-19, March 01-03, 1982, Palo Alto, California, United States
	12	M. Schlansker, "Compilation for VLIW and superscalar processors," ASPLOS-IV Tutorial, Santa Clara, CA, April 1991, pp. mss~l - mss-74.
	13	J.-J. Shieh , C. Papachristou, On reordering instruction streams for pipelined computers, Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture, p.199-206, August 14-16, 1989, Dublin, Ireland
	14	R. Sites, "Instruction ordering for the Cray-1 computer,'' Technical Rept. 78-CS-023, Comp. Sci., University of California, San Diego, July 1978.
	15	M.D. Tiemann, "The GNU instruction scheduler," CS343 course report, Comp. Sci., Stanford University, June 1989.
	16	H. S. Warren, Jr., Instruction scheduling for the IBM RISC System/6000 processor, IBM Journal of Research and Development, v.34 n.1, p.85-92, Jan. 1990
	17	J. Wilson, Cygnus Inc., personal correspondence, May 1991.
	18	Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

CITED BY 5

	Tyrel Russell , Abid M. Malik , Michael Chase , Peter van Beek, Learning basic block scheduling heuristics from optimal data, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.242-253, October 17-20, 2005, Toranto, Ontario, Canada
	Mark Smotherman , Shuchi Chawla , Stan Cox , Brian Malloy, Instruction scheduling for the Motorola 88110, Proceedings of the 26th annual international symposium on Microarchitecture, p.257-262, December 01-03, 1993, Austin, Texas, United States
	Abid M. Malik , Tyrel Russell , Michael Chase , Peter Beek, Learning heuristics for basic block instruction scheduling, Journal of Heuristics, v.14 n.6, p.549-569, December 2008
	Steven S. Muchnick , Phillip B. Gibbons, Efficient instruction scheduling for a pipelined architecture, ACM SIGPLAN Notices, v.39 n.4, April 2004
	A. Parikh , Soontae Kim , M. Kandemir , N. Vijaykrishnan , M. J. Irwin, Instruction Scheduling for Low Power, Journal of VLSI Signal Processing Systems, v.37 n.1, p.129-149, May 2004

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Optimization

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

I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE
I.2.8 Problem Solving, Control Methods, and Search
Subjects: Heuristic methods

General Terms:
Algorithms, Measurement, Performance, Theory

Collaborative Colleagues:

Mark Smotherman: colleagues

Sanjay Krishnamurthy: colleagues

P. S. Aravind: colleagues

David Hunnicutt: 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

Adobe Acrobat

QuickTime

Windows Media Player

Real Player