Uniform techniques for loop optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Uniform techniques for loop optimization

Full text

Pdf (1.41 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 5th international conference on Supercomputing table of contents

Cologne, West Germany

Pages: 341 - 352

Year of Publication: 1991

ISBN:0-89791-434-1

Author

William Pugh

Dept. of Computer Science and Institute or Advanced Computer Science, Univ. of Maryland, College Park

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 56, Citation Count: 21

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/109025.109108 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.

	AK87	Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
	Ban79	Utpal Banerjee, Speedup of ordinary programs, 1979
	Ban88	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	Ban90	U. Banerjee, "Unimodular Transformations of Double Loops," Proc. of 3rd Workshop on Programming Languages and Compilers for Parallel Computing, Irvine, CA, August 1990.
	Chen86	Marina C. Chen, A design methodology for synthesizing parallel algorithms and architectures, Journal of Parallel and Distributed Computing, v.3 n.4, p.461-491, December 1, 1986 [doi>10.1016/0743-7315(86)90010-9]
	DE73	G.B. Dantzin and B.C. Eaves, Fourier-Motzkin Elimination and Its Dual, Journal of Combznatorial Theory (A) 14 (1973), 288-297.
	Grun90	D. Grunwald, "Data Dependence: The ~. Test Revisted," 1990 International Conference on Parallel Processing, Penn State Univ. Press, 1990, pages II-220- II223,
	KKP90	X. Kong, D. Klappholz and K. Psarris, "The I Test: A new test for subscript data dependence," 1990 International Conference on Parallel Processing, Penn State Univ. Press, 1990, pages II-204 - II211.
	KMW67	Richard M. Karp , Raymond E. Miller , Shmuel Winograd, The Organization of Computations for Uniform Recurrence Equations, Journal of the ACM (JACM), v.14 n.3, p.563-590, July 1967 [doi>10.1145/321406.321418]
	Lam74	Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
	LYZ89	Zhiyuan Li , Pen-Chung Yew , Chuag-Qi Zhu, Data dependence analysis on multi-dimensional array references, Proceedings of the 3rd international conference on Supercomputing, p.215-224, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318813]
	Nico87	A. Nicolau, Loop quantization of unwinding done right, Proceedings of the 1st International Conference on Supercomputing, p.294-308, March 1988, Athens, Greece
	Poly88	Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
	Pug91	William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, University of Maryland at College Park, College Park, MD, 1991
	Ribas90	Hudson Ribas, Obtaining Dependence Vectors for Nested- Loop Computations, 1990 International Conference on Parallel Processing.
	RK88	S.K. Rao and T. Kailath, "Regular Iterative Algorithms and their Implementation on Processor Arrays," Proc. of the IEEE, Vol 76, No. 3, pp 259-269, March 1988.
	Wol89	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
	Wol90	Michael Wolfe, Massive Parallelism through program Restructuring, Symposium on Frontiers on Massively Parallel Computation, College Park, ME), October, 1990
	WS90	D. Whitfield , M. L. Soffa, An approach to ordering optimizing transformations, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.137-146, March 14-16, 1990, Seattle, Washington, United States
	WT90	Michael Wolfe and Chau-Wen Tseng. The Power Test for Data Dependence, Tech. Report CS/E90-015, Oregon Graduate Institute, August 1990.
	ZC91	Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990
	ZY90	Zhiyuan Li , Pen-Chung Yew, Some results on exact data dependence analysis, Selected papers of the second workshop on Languages and compilers for parallel computing, p.374-401, May 1990, Urbana, Illinois, United States

CITED BY 21

	William Pugh, Definitions of dependence distance, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.261-265, Sept. 1992
	Vadim Maslov, Enhancing array dataflow dependence analysis with on-demand global value propagation, Proceedings of the 9th international conference on Supercomputing, p.265-269, July 03-07, 1995, Barcelona, Spain
	William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992
	Peiyi Tang , Nianshu Gao, Vectorization beyond data dependences, Proceedings of the 9th international conference on Supercomputing, p.434-443, July 03-07, 1995, Barcelona, Spain
	Xavier Redon , Paul Feautrier, Scheduling reductions, Proceedings of the 8th international conference on Supercomputing, p.117-125, July 11-15, 1994, Manchester, England
	William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States
	David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994
	William Pugh , David Wonnacott, Static analysis of upper and lower bounds on dependences and parallelism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1248-1278, July 1994
	Vadim Maslov, Lazy array data-flow dependence analysis, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-325, January 16-19, 1994, Portland, Oregon, United States
	William Pugh , David Wonnacott, Constraint-based array dependence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.635-678, May 1998
	Michael O'Boyle , G. A. Hedayat, A transformational approach to compiling Sisal for distributed memory architectures, Proceedings of the 6th international conference on Supercomputing, p.335-346, July 19-24, 1992, Washington, D. C., United States
	Qing Yi , Ken Kennedy , Vikram Adve, Transforming Complex Loop Nests for Locality, The Journal of Supercomputing, v.27 n.3, p.219-264, March 2004
	Qing Yi , Ken Kennedy, Improving Memory Hierarchy Performance through Combined Loop Interchange and Multi-Level Fusion, International Journal of High Performance Computing Applications, v.18 n.2, p.237-253, May 2004
	Qing Yi , Ken Kennedy , Haihang You , Keith Seymour , Jack Dongarra, Automatic blocking of QR and LU factorizations for locality, Proceedings of the 2004 workshop on Memory system performance, June 08-08, 2004, Washington, D.C.
	Yanhong A. Liu , Scott D. Stoller , Ning Li , Tom Rothamel, Optimizing aggregate array computations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.1, p.91-125, January 2005
	Naraig Manjikian , Tarek S. Abdelrahman, Fusion of Loops for Parallelism and Locality, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.193-209, February 1997
	Sylvain Girbal , Nicolas Vasilache , Cédric Bastoul , Albert Cohen , David Parello , Marc Sigler , Olivier Temam, Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies, International Journal of Parallel Programming, v.34 n.3, p.261-317, June 2006
	Nicolas Vasilache , Cedric Bastoul , Albert Cohen , Sylvain Girbal, Violated dependence analysis, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Min Zhao , Bruce R. Childers , Mary Lou Soffa, An approach toward profit-driven optimization, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.3, p.231-262, September 2006
	Min Zhao , Bruce R. Childers , Mary Lou Soffa, A Model-Based Framework: An Approach for Profit-Driven Optimization, Proceedings of the international symposium on Code generation and optimization, p.317-327, March 20-23, 2005
	M. F. P. O'Boyle , J. M. Bull, Expert Programmer versus Parallelizing Compiler: A Comparative Study of Two Approaches for Distributed Shared Memory, Scientific Programming, v.5 n.1, p.63-88, January 1996