Global instruction scheduling for superscalar machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Global instruction scheduling for superscalar machines

Full text

Pdf (1.16 MB)

Source

Conference on Programming Language Design and Implementation archive
Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation table of contents

Toronto, Ontario, Canada

Pages: 241 - 255

Year of Publication: 1991

ISBN:0-89791-428-7

Also published in ...

Authors

David Bernstein	IBM Israel Scientific Center, Technion City, Haifa 32000, Israel
Michael Rodeh	IBM Israel Scientific Center, Technion City, Haifa 32000, Israel

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 67, Citation Count: 62

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/113445.113466 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.

	BG89	David Bernstein , Izidor Gertner, Scheduling expressions on a pipelined processor with a maximal delay of one cycle, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.57-66, Jan. 1989 [doi>10.1145/59287.59291]
	BRG89	David Bernstein , Micheal Rodeh , Izidor Gertner, Approximation algorithms for scheduling arithmetic expressions on pipelined machines, Journal of Algorithms, v.10 n.1, p.120-139, Mar. 1989 [doi>10.1016/0196-6774(89)90027-8]
	BJR89	D. Bernstein , J. M. Jaffe , M. Rodeh, Scheduling arithmetic and load operations in parallel with no spilling, SIAM Journal on Computing, v.18 n.6, p.1098-1127, Dec. 1989 [doi>10.1137/0218074]
	BEH89	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
	CHH89	R. Cytron , M. Hind , W. Hsieh, Automatic generation of DAG parallelism, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.54-68, June 19-23, 1989, Portland, Oregon, United States
	CFRWZ	R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
	E88	Ebcioglu, K., "Some design ideas for a VLIW architecture for sequential-natured software", Proc. of the IFIP Conference on Parallel Processing, (April 1988), Italy.
	EN89	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
	E85	John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
	FOW87	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	F81	Fisher, J., "Trace scheduling: A technique for global microcode compaction", IEEE Trans. on Computers, C-30, No. 7 (July 1981), 478-490.
	GM86	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
	GR90	M. C. Golumbic , V. Rainish, Instruction scheduling beyond basic blocks, IBM Journal of Research and Development, v.34 n.1, p.93-97, Jan. 1990
	GO89	Groves, R.D., and Oehler, R., "An IBM second generation RISC processor architecture", Proc. of the IEEE Conference on Computer Design, (October 1989), 134-137.
	HG83	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]
	JW89	N. P. Jouppi , D. W. Wall, Available instruction-level parallelism for superscalar and superpipelined machines, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.272-282, April 03-06, 1989, Boston, Massachusetts, United States
	L88	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
	P85	David A. Patterson, Reduced instruction set computers, Communications of the ACM, v.28 n.1, p.8-21, Jan. 1985 [doi>10.1145/2465.214917]
	SLH90	Michael D. Smith , Monica S. Lam , Mark A. Horowitz, Boosting beyond static scheduling in a superscalar processor, Proceedings of the 17th annual international symposium on Computer Architecture, p.344-354, May 28-31, 1990, Seattle, Washington, United States
	S89	"SPEC Newsletter", Systems Performance Evaluation Cooperative, Vol. 1, Issue 1, (Sep. 1989).
	W90	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

CITED BY 62

	Santosh G. Abraham , Vinod Kathail , Brian L. Deitrich, Meld Scheduling: A Technique for Relaxing Scheduling Constraints, International Journal of Parallel Programming, v.26 n.4, p.349-381, August 1998
	Henk Corporaal , Johan Janssen , Marnix Arnold, Computation in the Context of Transport Triggered Architectures, International Journal of Parallel Programming, v.28 n.4, p.401-427, August 2000
	Ko-Yang Wang, Precise compile-time performance prediction for superscalar-based computers, ACM SIGPLAN Notices, v.29 n.6, p.73-84, June 1994
	Stefan M. Freudenberger , Thomas R. Gross , P. Geoffrey Lowney, Avoidance and suppression of compensation code in a trace scheduling compiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1156-1214, July 1994
	Cliff Young , Michael D. Smith, Static correlated branch prediction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.1028-1075, Sept. 1999
	Ali-Reza Adl-Tabatabai , Thomas Gross, Source-level debugging of scalar optimized code, ACM SIGPLAN Notices, v.31 n.5, p.33-43, May 1996
	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
	Michael D. Smith , Mark Horowitz , Monica S. Lam, Efficient superscalar performance through boosting, ACM SIGPLAN Notices, v.27 n.9, p.248-259, Sept. 1992
	David Bernstein , Doron Cohen , Dror E. Maydan, Dynamic memory disambiguation for array references, Proceedings of the 27th annual international symposium on Microarchitecture, p.105-111, November 30-December 02, 1994, San Jose, California, United States
	Jason R. C. Patterson, Accurate static branch prediction by value range propagation, ACM SIGPLAN Notices, v.30 n.6, p.67-78, June 1995
	Soo-Mook Moon , Kemal Ebcioğlu, Parallelizing nonnumerical code with selective scheduling and software pipelining, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.853-898, Nov. 1997
	Thomas Ball, What's in a region?: or computing control dependence regions in near-linear time for reducible control flow, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.1-16, March–Dec. 1993
	Cindy Norris , Lori L. Pollock, Register allocation over the program dependence graph, ACM SIGPLAN Notices, v.29 n.6, p.266-277, June 1994
	Cindy Norris , Lori L. Pollock, Register allocation over the program dependence graph, ACM SIGPLAN Notices, v.29 n.6, p.266-277, June 1994
	Ali-Reza Adl-Tabatabai , Geoff Langdale , Steven Lucco , Robert Wahbe, Efficient and language-independent mobile programs, ACM SIGPLAN Notices, v.31 n.5, p.127-136, May 1996
	Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, ACM SIGARCH Computer Architecture News, v.20 n.2, p.46-57, May 1992
	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
	Johan Janssen , Henk Corporaal, Partitioned register file for TTAs, Proceedings of the 28th annual international symposium on Microarchitecture, p.303-312, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	Allen Leung , Krishna V. Palem , Amir Pnueli, Scheduling time-constrained instructions on pipelined processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.73-103, Jan. 2001
	Johan Janssen , Henk Corporaal, Making graphs reducible with controlled node splitting, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.1031-1052, Nov. 1997
	Mark Smotherman , Sanjay Krishnamurthy , P. S. Aravind , David Hunnicutt, Efficient DAG construction and heuristic calculation for instruction scheduling, Proceedings of the 24th annual international symposium on Microarchitecture, p.93-102, September 1991, Albuquerque, New Mexico, Puerto Rico
	Keshav Pingali , Gianfranco Bilardi, APT: a data structure for optimal control dependence computation, ACM SIGPLAN Notices, v.30 n.6, p.32-46, June 1995
	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
	Akira Koseki , Hideaki Komatsu , Yoshiaki Fukazawa, A register allocation technique using guarded PDG, Proceedings of the 10th international conference on Supercomputing, p.270-277, May 25-28, 1996, Philadelphia, Pennsylvania, United States
	Soo-Mook Moon , Kemal Ebcioğlu, A study on the number of memory ports in multiple instruction issue machines, Proceedings of the 26th annual international symposium on Microarchitecture, p.49-59, December 01-03, 1993, Austin, Texas, United States
	Vivek Sarkar , Barbara Simons, Anticipatory instruction scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.119-130, June 24-26, 1996, Padua, Italy
	Anne Rogers , Kai Li, Software support for speculative loads, ACM SIGPLAN Notices, v.27 n.9, p.38-50, Sept. 1992
	Shlomit S. Pinter, Register allocation with instruction scheduling, ACM SIGPLAN Notices, v.28 n.6, p.248-257, June 1993
	Raymond Lo , Sun Chan , Fred Chow , Shin-Ming Liu, Improving resource utilization of the MIPS R8000 via post-scheduling global instruction distribution, Proceedings of the 27th annual international symposium on Microarchitecture, p.148-152, November 30-December 02, 1994, San Jose, California, United States
	Keshav Pingali , Gianfranco Bilardi, Optimal control dependence computation and the Roman chariots problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.462-491, May 1997
	David M. Gillies , Dz-ching Roy Ju , Richard Johnson , Michael Schlansker, Global predicate analysis and its application to register allocation, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.114-125, December 02-04, 1996, Paris, France
	Santosh G. Abraham , Vinod Kathail , Brian L. Deitrich, Meld scheduling: relaxing scheduling constraints across region boundaries, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.308-321, December 02-04, 1996, Paris, France
	Philip H. Sweany , Steven J. Beaty, Dominator-path scheduling: a global scheduling method, ACM SIGMICRO Newsletter, v.23 n.1-2, p.260-263, Dec. 1992
	Cindy Norris , Lori L. Pollock, An experimental study of several cooperative register allocation and instruction scheduling strategies, Proceedings of the 28th annual international symposium on Microarchitecture, p.169-179, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	Kemal Ebcioglu , Randy D. Groves , Ki-Chang Kim , Gabriel M. Silberman , Isaac Ziv, VLIW compilation techniques in a superscalar environment, ACM SIGPLAN Notices, v.29 n.6, p.36-48, June 1994
	Daniel Weise , Roger F. Crew , Michael Ernst , Bjarne Steensgaard, Value dependence graphs: representation without taxation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.297-310, January 16-19, 1994, Portland, Oregon, United States
	Chingren Lee , Jenq Kuen Lee , Tingting Hwang , Shi-Chun Tsai, Compiler optimization on VLIW instruction scheduling for low power, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.2, p.252-268, April 2003
	Chris J. Newburn , Derek B. Noonburg , John Paul Shen, A PDG-based Tool and its Use in Analyzing Program Control Dependences, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.157-168, August 24-26, 1994
	Rafael Capurro, Informationstechnik in der Lebenswelt, Informatik und Schule 1991, Informatik: Wege zur Vielfalt beim Lehren und Lernen, p.16-26, October 11, 1991
	Jay Bharadwaj , Kishore Menezes , Chris McKinsey, Wavefront scheduling: path based data representation and scheduling of subgraphs, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.262-271, November 16-18, 1999, Haifa, Israel
	Soo-Mook Moon , Kemal Ebcioğlu, An efficient resource-constrained global scheduling technique for superscalar and VLIW processors, ACM SIGMICRO Newsletter, v.23 n.1-2, p.55-71, Dec. 1992
	David Bernstein , Doron Cohen , Hugo Krawczyk, Code duplication: an assist for global instruction scheduling, Proceedings of the 24th annual international symposium on Microarchitecture, p.103-113, September 1991, Albuquerque, New Mexico, Puerto Rico
	David Bernstein , Doron Cohen , Yuval Lavon , Vladimir Rainish, Performance evaluation of instruction scheduling on the IBM RISC System/6000, ACM SIGMICRO Newsletter, v.23 n.1-2, p.226-235, Dec. 1992
	Nancy J. Warter , Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Three Architectural Models for Compiler-Controlled Speculative Execution, IEEE Transactions on Computers, v.44 n.4, p.481-494, April 1995
	David A. Berson , Rajiv Gupta , Mary Lou Soffa, Resource Spackling: A Framework for Integrating Register Allocation in Local and Global Schedulers, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.135-146, August 24-26, 1994
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, ACM SIGPLAN Notices, v.29 n.6, p.147-158, June 1994
	T. Nakatani , K. Ebcioglu, Making Compaction-Based Parallelization Affordable, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1014-1029, September 1993
	Cindy Norris , Lori L. Pollock, Experiences with Cooperating Register Allocation and Instruction Scheduling, International Journal of Parallel Programming, v.26 n.3, p.241-283, June 1998
	Cindy Norris , Lori L. Pollock, Register allocation sensitive region scheduling, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.1-10, June 27-29, 1995, Limassol, Cyprus
	Soo-Mook Moon , Scott D. Carson, Generalized Multiway Branch Unit for VLIW Microprocessors, IEEE Transactions on Parallel and Distributed Systems, v.6 n.8, p.850-862, August 1995
	Ching-Long Su , Chi-Ying Tsui , Alvin M. Despain, Saving Power in the Control Path of Embedded Processors, IEEE Design & Test, v.11 n.4, p.24-30, October 1994
	Andrew Riffel , Aaron E. Lefohn , Kiril Vidimce , Mark Leone , John D. Owens, Mio: fast multipass partitioning via priority-based instruction scheduling, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France
	Soo-Mook Moon , Kemal Ebcioglu , Ashok K. Agrawala, Selective Scheduling Framework for Speculative Operations in VLIW and Superscalar Processors, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.229-242, January 20-22, 1993
	Ciaran O'Donnell, High Level Compiling for Low Level Machines, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.309-320, January 20-22, 1993
	D. Edelsohn , W. Gellerich , M. Hagog , D. Naishlos , M. Namolaru , E. Pasch , H. Penner , U. Weigand , A. Zaks, Contributions to the GNU compiler collection, IBM Systems Journal, v.44 n.2, p.259-278, January 2005
	Ghassan Shobaki , Kent Wilken, Optimal Superblock Scheduling Using Enumeration, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.283-293, December 04-08, 2004, Portland, Oregon
	Joseph A. Fisher , Stefan M. Freudenberger, Predicting conditional branch directions from previous runs of a program, ACM SIGPLAN Notices, v.27 n.9, p.85-95, Sept. 1992
	Allen Leung , Krishna V. Palem , Amir Pnueli, TimeC: A Time Constraint Language for ILP Processor Compilation, Constraints, v.7 n.2, p.75-115, April 2002
	Ivan D. Baev , Waleed M. Meleis , Santosh G. Abraham, Backtracking-Based Instruction Scheduling to Fill Branch Delay Slots, International Journal of Parallel Programming, v.30 n.6, p.397-418, December 2002
	David A. Berson , Rajiv Gupta , Mary Lou Soffa, GURRR: a global unified resource requirements representation, ACM SIGPLAN Notices, v.30 n.3, p.23-34, March 1993
	Ghassan Shobaki , Kent Wilken , Mark Heffernan, Optimal trace scheduling using enumeration, ACM Transactions on Architecture and Code Optimization (TACO), v.5 n.4, p.1-32, March 2009
	R. J. Blainey, Instruction scheduling in the TOBEY compiler, IBM Journal of Research and Development, v.38 n.5, p.577-593, Sept. 1994