Determining the idle time of a tiling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Determining the idle time of a tiling

Full text

Pdf (1.05 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Paris, France

Pages: 160 - 173

Year of Publication: 1997

ISBN:0-89791-853-3

Authors

Karin Högstedt	Department of Computer Science and Engineering, UCSD, 9500 Gilman Drive, La Jolla, CA
Larry Carter	Department of Computer Science and Engineering, UCSD, 9500 Gilman Drive, La Jolla, CA and San Diego Supercomputing Center
Jeanne Ferrante	Department of Computer Science and Engineering, UCSD, 9500 Gilman Drive, La Jolla, CA

Sponsors

L'Ecole des Mines de Paris : L'Ecole des Mines de Paris
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Ctr Natl de la Recherche Sci :
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	B92	Banerjee, U., "Unimodular Transformations of Double Loops", in Advances in Languages and Compilers for Parallel Processing, A. Nicolau and D. Padua, editors, MIT Press, 1992.
	CFH95a	Carter, L., J. Ferrante and S. Flynn Hummel, "Efficient Parallelism via Hierarchical Tiling," Proc. of SIAM Conference on Parallel Processing for Scientific Computing, (February, 1995).
	CFH95b	Larry Carter , Jeanne Ferrante , Susan Flynn Hummel, Hierarchical tiling for improved superscalar performance, Proceedings of the 9th International Symposium on Parallel Processing, p.239-245, April 25-28, 1995
	CFHAG96	Carter, L., J. Ferrante, S. Flynn Hummel, B. Alpern, K. S. Gatlin, "Hierarchical Tiling: A Methodology for High Performance," UCSD Computer Science and Engineering Technical Report, available at http://wwwcse. ucsd. edu/users/carter/ppbib, html.
	CK92	S. Carr , K. Kennedy, Compiler blockability of numerical algorithms, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.114-124, November 16-20, 1992, Minneapolis, Minnesota, United States
	GJG88	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]
	HCF96	Karin Hogstedt , Larry Carter , Jeanne Ferrante, Determining the idle time of a tiling, University of California at San Diego, La Jolla, CA, 1999
	HA90	S. G. Abraham , D. E. Hudak, Compile-Time Partitioning of Iterative Parallel Loops to Reduce Cache Coherency Traffic, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.318-328, July 1991 [doi>10.1109/71.86107]
	H93	Hummel, S. F., "Fractiling: A Method for Scheduling Parallel Loops on NUMA Machines", IBM RC 18958, June 1993.
	IT88	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]
	JM86	Jalby, W. and U. Meier, "Optimizing Matrix Operations on a Parallel Multiprocessor with a Hierarchical Memory System," Proc. International Conference on Parallel Processing, August 1986, pp. 429-432.
	KM92	Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
	KP93	Wayne Kelly , William Pugh, Determining schedules based on performance estimation, University of Maryland at College Park, College Park, MD, 1993
	LRW91	Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
	L90	Lee, F. F., "Partitioning of Regular Computation on Multiprocessor Systems," Journal of Parallel and Distributed Computing, Vol. 9, 1990, pp. 312-317.
	RS91	J. Ramanujam , P. Sadayappan, Tiling multidimensional iteration spaces for nonshared memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.111-120, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125893]
	RAP87	D. A. Reed , L. M. Adams , M. L. Partick, Stencils and problem partitionings: their influence on the performance of multiple processor systems, IEEE Transactions on Computers, v.36 n.7, p.845-858, July 1987 [doi>10.1109/TC.1987.1676980]
	VSM96	Rob F. Van der Wijngaart , Sekhar R. Sarukkai , Pankaj Mehra, The effect of interrupts on software pipeline execution on message-passing architectures, Proceedings of the 10th international conference on Supercomputing, p.189-196, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237603]
	WL91	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
	WL91b	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]
	W87	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
	W89	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]

CITED BY 12

	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
	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. 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
	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
	Fabrice Rastello , Yves Robert, Automatic Partitioning of Parallel Loops with Parallelepiped-Shaped Tiles, IEEE Transactions on Parallel and Distributed Systems, v.13 n.5, p.460-470, May 2002
	Jingling Xue , Wentong Cai, Time-minimal tiling when rise is larger than zero, Parallel Computing, v.28 n.6, p.915-939, June 2002
	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
	Maria Athanasaki , Aristidis Sotiropoulos , Georgios Tsoukalas , Nectarios Koziris , Panayiotis Tsanakas, Hyperplane Grouping and Pipelined Schedules: How to Execute Tiled Loops Fast on Clusters of SMPs, The Journal of Supercomputing, v.33 n.3, p.197-226, September 2005
	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
	Lakshminarayanan Renganarayanan , DaeGon Kim , Sanjay Rajopadhye , Michelle Mills Strout, Parameterized tiled loops for free, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Georgios Goumas , Nikolaos Drosinos , Maria Athanasaki , Nectarios Koziris, Message-passing code generation for non-rectangular tiling transformations, Parallel Computing, v.32 n.10, p.711-732, November, 2006
	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