Fast greedy weighted fusion

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast greedy weighted fusion

Full text

Pdf (832 KB)

Source

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

Santa Fe, New Mexico, United States

Pages: 131 - 140

Year of Publication: 2000

ISBN:1-58113-270-0

Author

Ken Kennedy

Center for High Performance Software, Rice University

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/335231.335244 What is a DOI?

ABSTRACT

Loop fusion is important to optimizing compilers because it is an important tool in managing the memory hierarchy. By fusing loops that use the same data elements, we can reduce the distance between accesses to the same datum and avoid costly cache misses. Unfortunately the problem of optimal loop fusion for reuse has been shown to be NP-hard, so compilers must resort to heuristics to avoid unreasonably long compile times. Greedy strategies are often excellent heuristics that produce high-quality solutions quickly. We present an algorithm for greedy weighted fusion, in which the heaviest edge (the one with the most reuse) is selected for possible fusion on each step. The algorithm is shown to be fast in the sense that it takes O(V(E+V)) time, which is arguably optimal for this problem.

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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
	3	r. Allen , D. Callahan , K. Kennedy, Automatic decomposition of scientific programs for parallel execution, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.63-76, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41631]
	4	Randy Allen , Ken Kennedy, Vector Register Allocation, IEEE Transactions on Computers, v.41 n.10, p.1290-1317, October 1992 [doi>10.1109/12.166606]
	5	R. Allen and K. Kennedy. Advanced Compilation for High Performance Computers. Morgan Kauffman, to be published October 2000.
	6	Steven Mark Carr, Memory-hierarchy management, Rice University, Houston, TX, 1993
	7	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
	8	Alain Darte, On the Complexity of Loop Fusion, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.149, October 12-16, 1999
	9	Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global and dynamic cache reuse, 2000
	10	The Memory Bandwidth Bottleneck and its Amelioration by a Compiler, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.181, May 01-05, 2000
	11	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]
	12	D. C. R. Ju , C. L. Wu , P. Carini, The Classification, Fusion, and Parallelization of Array Language Primitives, IEEE Transactions on Parallel and Distributed Systems, v.5 n.10, p.1113-1120, October 1994 [doi>10.1109/71.313127]
	13	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
	14	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
	15	K. Kennedy and K. McKinley. Typed fusion with applications to parallel and sequential code generation. Technical Report CRPC-TR94646, Center for Research on Parallel Computation, Rice University, 1994.
	16	Vivek Sarkar , Guang R. Gao, Optimization of array accesses by collective loop transformations, Proceedings of the 5th international conference on Supercomputing, p.194-205, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109077]

CITED BY 15

	Waibhav Tembe , Santosh Pande, Loop Restructuring for Data I/O Minimization on Limited On-Chip Memory Embedded Processors, IEEE Transactions on Computers, v.51 n.10, p.1269-1280, October 2002
	Apan Qasem , Ken Kennedy, Profitable loop fusion and tiling using model-driven empirical search, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Daniel Cociorva , Gerald Baumgartner , Chi-Chung Lam , P. Sadayappan , J. Ramanujam , Marcel Nooijen , David E. Bernholdt , Robert Harrison, Space-time trade-off optimization for a class of electronic structure calculations, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Steve Carr , Soner Önder, A case for a working-set-based memory hierarchy, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
	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.
	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
	Yonghong Song , Rong Xu , Cheng Wang , Zhiyuan Li, Improving Data Locality by Array Contraction, IEEE Transactions on Computers, v.53 n.9, p.1073-1084, September 2004
	Peng Zhao , Shimin Cui , Yaoqing Gao , Raúl Silvera , José Nelson Amaral, Forma: A framework for safe automatic array reshaping, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.2-es, November 2007
	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
	D. Cociorva , J. W. Wilkins , C. Lam , G. Baumgartner , J. Ramanujam , P. Sadayappan, Loop optimization for a class of memory-constrained computations, Proceedings of the 15th international conference on Supercomputing, p.103-113, June 2001, Sorrento, Italy
	Swarup Kumar Sahoo , Sriram Krishnamoorthy , Rajkiran Panuganti , P. Sadayappan, Integrated Loop Optimizations for Data Locality Enhancement of Tensor Contraction Expressions, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.13, November 12-18, 2005
	Chen Ding , Maksim Orlovich, The Potential of Computation Regrouping for Improving Locality, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.13, November 06-12, 2004
	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
	Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global cache reuse, Journal of Parallel and Distributed Computing, v.64 n.1, p.108-134, January 2004
	Zhiyuan Li , Yonghong Song, Automatic tiling of iterative stencil loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.6, p.975-1028, November 2004