Optimization of array accesses by collective loop transformations

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.

Optimization of array accesses by collective loop transformations

Full text

Pdf (1.10 MB)

Source

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

Cologne, West Germany

Pages: 194 - 205

Year of Publication: 1991

ISBN:0-89791-434-1

Authors

Vivek Sarkar	IBM Palo Alto Scientific Center, 1530 Page Mill Road, Palo Alto, CA
Guang R. Gao	School of Computer Science, McGill University, Montreal, Canada H3A 2A7

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

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

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.109077 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.

	AD79	W. B. Acherman , J. B. Dennis , William B Ackerman, VAL- ORIENTED ALGORITHMIC LANGUAGE, PRELIMINARY REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
	AHU74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	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]
	All83	John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
	AN90	K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990 [doi>10.1109/12.48862]
	Ban90	U. Banerjee. Unimodular transformations of double loops. In Proceedings o/the Third Workshop on Programming Languages and Compilers for Parallel Computing, Irvine, CA, August 1990. To be published by Pitman in Monographs in Parallel and Distributed Computing.
	BCKT89	P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, ACM SIGPLAN Notices, v.24 n.7, p.275-284, July 1989
	CAC+81	G. J. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register allocation via coloring. Computer Languages 6, pages 47-57, January 1981.
	CCK90	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
	Deo74	Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
	Dij59	E.W. Dijkstra. A note on two problems in connection with graphs. Numer~she Mathematik, 1:269-271, 1959.
	Gao86	Guang R Gao, A maximally pipelined tridiagonal linear equation solver, Journal of Parallel and Distributed Computing, v.3 n.2, p.215-235, June 1986 [doi>10.1006/jpdc.1996.0015]
	Gao90	Guang R. Gao, A Code Mapping Scheme for Dataflow Software Pipelining, Kluwer Academic Publishers, Norwell, MA, 1990
	GYDM90	G. R. Gao, R. Yates, J. B. Dennis, and L. Mullin. An efficient monolithic array constructor. In Proceedings of the 3rd Workshop on Languages and Compilers for Parallel Computing, Irvine, CA, 1990. To be published by MIT Press.
	Hud89	Paul Hudak, Conception, evolution, and application of functional programming languages, ACM Computing Surveys (CSUR), v.21 n.3, p.359-411, Sep. 1989 [doi>10.1145/72551.72554]
	KLL86	S.Y. Kung, S. C. Lo, and P. S. Lewi:~. Timing analysis and optimization of VLSI ,data flow arrays. In Proceedings of the 1986 International Conference on Parallel Processing, 1986.
	KRP+81	D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
	Kuh80	Robert Henry Kuhn. Optimization and Interconnection Complexity for Parallel Processors, Single-Stage Networks, and Decision Trees. PhD thesis, University of Illinois at Urbana- Champaign, 1980. Report No. UIUCDCS-R-80- 1009.
	Lei83	Charles Eric Leiserson, Area-Efficient VLSI Computation, MIT Press, Cambridge, MA, 1997
	Mea85	J.R. McGraw and et al. SISAL: Streams and iteration in a single assignment languagew language reference manual version 1.2. Technical Report M-146, Lawrence Livermore National Laboratory, 1985.
	Sar89	V. Sarkar, Partitioning and scheduling parallel programs for execution on multiprocessors, Stanford University, Stanford, CA, 1987
	Sar90	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
	SC90	Vivek Sarkar , David Cann, POSC—a partitioning and optimizing SISAL compiler, Proceedings of the 4th international conference on Supercomputing, p.148-164, June 11-15, 1990, Amsterdam, The Netherlands
	WL90	Michael E. Wolf and Monica S. Lain. Maximizing parallelism via loop parallelism. Proceedings of the Third Workshop on Languages and Compilers for Parallel Computing, August 1990.
	Wol89	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
	X3J90	The FORTRAN Technical Committee of ANSI X3J3, June 1990. FORTRAN 90, Draft of the International Standard.
	ZSY90	Z. Shen , Z. Li , P. C. Yew, An Empirical Study of Fortran Programs for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.356-364, July 1990 [doi>10.1109/71.80162]

CITED BY 13

	Ken Kennedy, Fast greedy weighted fusion, Proceedings of the 14th international conference on Supercomputing, p.131-140, May 08-11, 2000, Santa Fe, New Mexico, United States
	Siddhartha Chatterjee, Compiling nested data-parallel programs for shared-memory multiprocessors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.3, p.400-462, July 1993
	Andrew S. Huang , John P. Shen, A limit study of local memory requirements using value reuse profiles, Proceedings of the 28th annual international symposium on Microarchitecture, p.71-81, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	E. Christopher Lewis , Calvin Lin , Lawrence Snyder, The implementation and evaluation of fusion and contraction in array languages, ACM SIGPLAN Notices, v.33 n.5, p.50-59, May 1998
	Yonghong Song , Rong Xu , Cheng Wang , Zhiyuan Li, Data locality enhancement by memory reduction, Proceedings of the 15th international conference on Supercomputing, p.50-64, June 2001, Sorrento, Italy
	Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, ACM SIGPLAN Notices, v.28 n.6, p.112-125, June 1993
	Alok Choudhary , Geoffrey Fox , Seema Hiranandani , Ken Kennedy , Charles Koelbel , Sanjay Ranka , Chau-Wen Tseng, Unified compilation of Fortran 77D and 90D, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.95-114, March–Dec. 1993
	Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, ACM SIGPLAN Notices, v.36 n.7, p.103-112, July 2001
	Neungsoo Park , Bo Hong , Viktor K. Prasanna, Tiling, Block Data Layout, and Memory Hierarchy Performance, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.640-654, July 2003
	Ken Kennedy, Fast Greedy Weighted Fusion, International Journal of Parallel Programming, v.29 n.5, p.463-491, October 2001
	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
	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
	Martin Palkovic , Francky Catthoor , Henk Corporaal, Trade-offs in loop transformations, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.2, p.1-30, March 2009