Tiling multidimensional iteration spaces for nonshared memory machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Tiling multidimensional iteration spaces for nonshared memory machines

Full text

Pdf (980 KB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 1991 ACM/IEEE conference on Supercomputing table of contents

Albuquerque, New Mexico, United States

Pages: 111 - 120

Year of Publication: 1991

ISBN:0-89791-459-7

Authors

J. Ramanujam	Dept. of Electrical and Computer Engineering, Louisiana State University, Baton Rouge, LA
P. Sadayappan	Dept. of Computer and Information Science, The Ohio State University, Columbus, OH

Sponsors

IEEE : Institute of Electrical and Electronics Engineers
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 16, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/125826.125893 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	M. Abramowitz and I. Stetgun. Handbook of Mathematical Functions. Dover Publications, New York, 1984.
	2	John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
	3	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]
	4	A. Bachem. The Theorem of Minkowski for Polyhedral Monoids and Aggregated Linear Diophantine Systems. Optimization and Operations Research- Proc. os~ Workshop, University of Bonn, October 1977, Lecture Notes in Economics and Mathematical Systems, Vol. 157, pages 1-14, Springer Verlag.
	5	V. Balasundaram, G. Fox, K. Kennedy and U. Kremer. An interactive environment for data partitioning and distribution. Proc. 5th Distributed Memory Computing Conference (DMCC5), Charleston, S. Carolina, pages 1160-1170, April 1990.
	6	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	7	D. Callahan and K. Kennedy. Compiling Programs for Distributed-Memory Multiprocessors. The Journal of Supercomputing, Vol. 2, Oct. 1988, pp. 151-169.
	8	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
	9	M. Chen, Y. Choo and J. Li. Compiling Parallel Programs by Optimizing Performance. The Journal of Supercomputing, 2, 1988, pp. 171-207.
	10	M. Chen, Y. Choo and J. Li. Theory and pragmatics of compiling efficient parallel code. Technical Report YALEU/DCS/TR-760, Yale University, December 1989.
	11	K. Gallivan , W. Jalby , D. Gannon, On the problem of optimizing data transfers for complex memory systems, Proceedings of the 2nd international conference on Supercomputing, p.238-253, June 1988, St. Malo, France [doi>10.1145/55364.55388]
	12	Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
	13	S. Hiranandani, K. Kennedy, C. Koelbel, U. Kremer and G. Tseng. An Overview of the Fortran D Programming System. Tech. Report Rice COMP TR91- 154, Department of Computer Science, Rice University, March 1991.
	14	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]
	15	C. King and L. Ni. Grouping in Nested Loops for Parallel Execution on Multicomputers. Proc. International Conf. Parallel Processing, 1989, Vol. 2, pp. II-31 to II-38.
	16	C. T. King , W. H. Chou , L. M. Ni, Pipelined Data Parallel Algorithms-II: Design, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.486-499, October 1990 [doi>10.1109/71.80176]
	17	Charles Koelbel , Piyush Mehrotra , John van Rosendale, Semi-automatic process partitioning for parallel computation, International Journal of Parallel Programming, v.16 n.5, p.365-382, October 1987 [doi>10.1007/BF01407902]
	18	C. Koelbel , P. Mehrotra , J. Van Rosendale, Supporting shared data structures on distributed memory architectures, ACM SIGPLAN Notices, v.25 n.3, p.177-186, Mar. 1990
	19	Charles Howard Koelbel, Compiling programs for nonshared memory machines, Purdue University, West Lafayette, IN, 1991
	20	U. Kremer, H. Bast, H. Gerndt and H. Zima. Advanced Tools and Techniques for Automatic Parallehzation. Parallel Computing, Vol. 7, 1988, pp. 387- 393.
	21	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]
	22	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]
	23	Mary E. Mace, Memory storage patterns in parallel processing, Kluwer Academic Publishers, Norwell, MA, 1987
	24	Alexandru Nicolau, Loop quantization: a generalized loop unwinding technique, Journal of Parallel and Distributed Computing, v.5 n.5, p.568-586, October 1988 [doi>10.1016/0743-7315(88)90013-5]
	25	David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
	26	A. Rogers , K. Pingali, Process decomposition through locality of reference, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.69-80, June 19-23, 1989, Portland, Oregon, United States
	27	Anne Marie Rogers, Compiling for locality of reference, 1990
	28	J. Ramanujam and P. Sadayappan. Tiling of Iteration Spaces for Multicomputers. Proc. 1990 International Conference on Parallel Processing, Vol 2, pages 179- 186, August 1990.
	29	Jagannathan Ramanujam, Compile-time techniques for parallel execution of loops on distributed memory multiprocessors, Rutgers University, New Brunswick, NJ, 1991
	30	Vivek Sarkar , John Hennessy, Partitioning parallel programs for macro-dataflow, Proceedings of the 1986 ACM conference on LISP and functional programming, p.202-211, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319863]
	31	Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
	32	Jack Dongarra , Robert Schreiber, Automatic Blocking of Nested Loops, University of Tennessee, Knoxville, TN, 1990
	33	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	34	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
	35	Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
	36	Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
	37	Michael Wolfe , Utpal Banerjee, Data dependence and its application to parallel processing, International Journal of Parallel Programming, v.16 n.2, p.137-178, April 1987 [doi>10.1007/BF01379099]
	38	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
	39	M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]
	40	H. Zima, H. Bast and H. Gerndt. SUPERB: A Tool for Semi-automatic MIMD/SIMD Parallelization. Parallel Computing, Vol. 6, 1988, pp. 1-18.

CITED BY 18

	J. Ramanujam, Non-unimodular transformations of nested loops, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.214-223, November 16-20, 1992, Minneapolis, Minnesota, United States
	Karin Högstedt , Larry Carter , Jeanne Ferrante, Selecting tile shape for minimal execution time, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.201-211, June 27-30, 1999, Saint Malo, France
	D. González , F. Almeida , L. Moreno , C. Rodríguez, Towards the automatic optimal mapping of pipeline algorithms, Parallel Computing, v.29 n.2, p.241-254, February 2003
	Francisco Almeida , Rumen Andonov , Daniel Gonzalez , Luz M. Moreno , Vincent Poirriez , Casiano Rodriguez, Optimal tiling for the RNA base pairing problem, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	R. Andonov , S. Balev , S. Rajopadhye , N. Yanev, Optimal semi-oblique tiling, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.153-162, July 2001, Crete Island, Greece
	Anant Agarwal , David A. Kranz , Venkat Natarajan, Automatic Partitioning of Parallel Loops and Data Arrays for Distributed Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.943-962, September 1995
	W. Zhang , M. Karakoy , M. Kandemir , G. Chen, A compiler approach for reducing data cache energy, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
	Karin Högstedt , Larry Carter , Jeanne Ferrante, Determining the idle time of a tiling, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.160-173, January 15-17, 1997, Paris, France
	Michelle Mills Strout , Larry Carter , Jeanne Ferrante , Beth Simon, Schedule-independent storage mapping for loops, ACM SIGPLAN Notices, v.33 n.11, p.24-33, Nov. 1998
	Wei Zhang , Mahmut Kandemir , Mustafa Karakoy , Guangyu Chen, Reducing data cache leakage energy using a compiler-based approach, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.3, p.652-678, August 2005
	Chunhui Zhang , Fadi Kurdahi, On combining iteration space tiling with data space tiling for scratch-pad memory systems, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Karin Högstedt , Larry Carter , Jeanne Ferrante, On the Parallel Execution Time of Tiled Loops, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.307-321, March 2003
	Sriram Krishnamoorthy , Muthu Baskaran , Uday Bondhugula , J. Ramanujam , Atanas Rountev , P Sadayappan, Effective automatic parallelization of stencil computations, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Guangming Tan , Shengzhong Feng , Ninghui Sun, Biology---Locality and parallelism optimization for dynamic programming algorithm in bioinformatics, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida
	Chunhui Zhang , Fadi Kurdahi, Reducing off-chip memory access via stream-conscious tiling on multimedia applications, International Journal of Parallel Programming, v.35 n.1, p.63-98, February 2007
	Guangming Tan , Ninghui Sun , Guang R. Gao, A parallel dynamic programming algorithm on a multi-core architecture, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Nicholas Mitchell , Karin Högstedt , Larry Carter , Jeanne Ferrante, Quantifying the Multi-Level Nature of Tiling Interactions, International Journal of Parallel Programming, v.26 n.6, p.641-670, December 1998
	Jia Guo , Ganesh Bikshandi , Basilio B. Fraguela , Maria J. Garzaran , David Padua, Programming with tiles, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA