Optimal weighted loop fusion for parallel programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal weighted loop fusion for parallel programs

Full text

Pdf (1.25 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures table of contents

Newport, Rhode Island, United States

Pages: 282 - 291

Year of Publication: 1997

ISBN:0-89791-890-8

Authors

Nimrod Megiddo	IBM Almaden Research Center and Tel Aviv University
Vivek Sarkar	MIT Laboratory for Computer Science and IBM Software Solutions Division

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 8

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/258492.258520 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	John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
	2	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]
	3	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	4	C. D. Callahan, II, A global approach to detection of parallelism, Rice University, Houston, TX, 1987
	5	Jyh-Herng Chow , Leonard E. Lyon , Vivek Sarkar, Automatic parallelization for symmetric shared-memory multiprocessors, Proceedings of the 1996 conference of the Centre for Advanced Studies on Collaborative research, p.5, November 12-14, 1996, Toronto, Ontario, Canada
	6	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]
	7	Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
	8	Guang R. Gao , R. Olsen , Vivek Sarkar , Radhika Thekkath, Collective Loop Fusion for Array Contraction, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.281-295, August 03-05, 1992
	9	Allen Goldberg , Robert Paige, Stream processing, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.53-62, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802021]
	10	IBM. IBM Optimization Subroutine Library (OSL) User Guide and Reference, Version 1, Release 2.1. Technical report, International Business Machines, 1995. Pub. No. SC23-0519-04 (also see http://www.research.ibm.com/osl/osl).
	11	F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
	12	Ken Kennedy , Kathryn S. McKinley, Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.301-320, August 12-14, 1993
	13	Ken Kennedy and Kathryn S. McKinley. Typed Fusion with Applications to Parallel and Sequential Code Generation. Technical report, Department of Computer Science, Rice University, 1993. TR93-208.
	14	Michael Metcalf , John Reid, Fortran 90 explained, Oxford University Press, Inc., New York, NY, 1990
	15	George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
	16	V. Sarkar, Determining average program execution times and their variance, ACM SIGPLAN Notices, v.24 n.7, p.298-312, July 1989
	17	Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
	18	V. Sarkar, Automatic partitioning of a program dependence graph into parallel tasks, IBM Journal of Research and Development, v.35 n.5-6, p.779-804, Sept./Nov. 1991
	19	V. Sarkar, Automatic selection of high-order transformations in the IBM XL FORTRAN compilers, IBM Journal of Research and Development, v.41 n.3, p.233-264, May 1997
	20	Vivek Sarkar , Radhika Thekkath, A general framework for iteration-reordering loop transformations, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.175-187, June 15-19, 1992, San Francisco, California, United States
	21	Ko-Yang Wang, Wei-Min Ching, Manish Gupta, Sam Midkiff, Edith Schonberg, and Dave Shields. Improving the Performance of HPF Compilers. Proceedings of the Fifth Workshop on Compilers .for Parallel Computers (CPC '95), Malaga, Spain, June 1995.
	22	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
	23	M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
	24	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

CITED BY 8

	Zhong Wang , Qingfeng Zhuge , Edwin H.-M. Sha, Scheduling and partitioning for multiple loop nests, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada
	Zhong Wang , Edwin H.-M. Sha , Xiaobo (Sharon) Hu, Combined partitioning and data padding for scheduling multiple loop nests, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA
	Meilin Liu , Qingfeng Zhuge , Zili Shao , Edwin H.-M. Sha, General loop fusion technique for nested loops considering timing and code size, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA
	Alain Darte , Guillaume Huard, New Complexity Results on Array Contraction and Related Problems, Journal of VLSI Signal Processing Systems, v.40 n.1, p.35-55, May 2005
	Ken Kennedy, Fast Greedy Weighted Fusion, International Journal of Parallel Programming, v.29 n.5, p.463-491, October 2001
	Youcef Bouchebaba , Bruno Girodias , Gabriela Nicolescu , El Mostapha Aboulhamid , Bruno Lavigueur , Pierre Paulin, MPSoC memory optimization using program transformation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.43-es, September 2007
	Rehab F. Abdel-Kader, Resource-constrained loop scheduling in high-level synthesis, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
	Meikang Qiu , Edwin H. -M. Sha , Meilin Liu , Man Lin , Shaoxiong Hua , Laurence T. Yang, Energy minimization with loop fusion and multi-functional-unit scheduling for multidimensional DSP, Journal of Parallel and Distributed Computing, v.68 n.4, p.443-455, April, 2008